Zenn
🌟

nand2tetrisで演算子の優先順位をつける

2021/04/06に公開
Python
compiler
nand2tetris
tech

先日終わらせたnand2tetrisで仮想マシンのコンパイラを作成したらとても俺俺コンパイラを作ってみたくなった。そこで今MSX用の俺俺クロスコンパイラを作っている最中なのだが、演算子の優先順位がない状態だと非常に使いにくいので優先順位に従って式が評価されるようにしてみた。

環境

  • 言語：python 3.8
  • PC： iMac 2019
  • OS： macOS 10.15.7

難しいことはしていないのでpython 3なら問題なく動くはず。

サンプル

俺俺クロスコンパイラからパーサの該当箇所を抜粋してgithubにアップロードした。
https://github.com/paraches/prioritizedExpression
main.pyを起動すればreplになるので、適当に式（以下expression）を入れるとpushと演算子（以下operator）で実行コードが表示される。

例えば1+2*3;と入力すると下記のようになる。

exp > 1+2*3;
push ('constant', '1', 'int')
push ('constant', '2', 'int')
push ('constant', '3', 'int')
arithmetic ('call Math.multiply 2',)
arithmetic ('add',)

1をpushして、2をpushして、3をpushして、2と3を掛けて、1を加える。
掛け算はライブラリで処理しているのでcall Math.multiplyになっている。

足し算を先にするために括弧を付けてみると。

exp > (1+2)*3;
push ('constant', '1', 'int')
push ('constant', '2', 'int')
arithmetic ('add',)
push ('constant', '3', 'int')
arithmetic ('call Math.multiply 2',)

1をpushして、2をpushして、1と2を足して、3をpushして掛け算する。
ちゃんと括弧の中が先に評価されている。

もう少し複雑にしてみる。

exp > 1+(2+3)*4+-1;
push ('constant', '1', 'int')
push ('constant', '2', 'int')
push ('constant', '3', 'int')
arithmetic ('add',)
push ('constant', '4', 'int')
arithmetic ('call Math.multiply 2',)
arithmetic ('add',)
push ('constant', '1', 'int')
arithmetic ('neg',)
arithmetic ('add',)

2と3を先に足して4を掛けて1を加えて最後に-1を加える。
-1はunary_operatorで処理されて1のnegになっている。

コード

アップロードしてあるファイルは下記の通り。

  • main.py
  • Token.py
  • Tokenizer.py
  • Parser.py

Parser.py以外はパースには関係ないので今回説明はなし。

Parser.py

処理の流れとしては、まずトークンに分割された式がparser.parse(tokens)に渡される。そこで最初のトークンを引数にしてdo_expression(token, priority)が呼ばれる。このdo_expressionは再帰的に呼び出され最終的にはdo_term(token, priority)で値が評価される。

do_expression、do_term共にもう一つの引数priorityがoperatorの優先順位。
優先順位はToken.pyでそれぞれの演算子について設定してあり、値は以下のページのCの優先順位をそのまま使っている。
https://en.cppreference.com/w/c/language/operator_precedence

expressionの評価は主にdo_expressionで行われている。
以下、優先順位がない場合とある場合で簡単に説明する。

優先順位なしの場合

nand2tetrisの教科書とちょっと違ってexpressionの定義がexpression: term (op expression)*と再帰的になっている。

if not token.is_term():
    self.error_message('Expression', 'Term', token)
    return token

token = self.do_term(token, priority)

while token.is_operator():
	opcodes = token.operator_code()
	
	token = self.get_token()
	token = self.do_expression(token)
	
	for opcode in opcodes:
		self.code_write('arithmetic', (opcode, ))

まず最初にトークンがtermかどうかを確認してる。

トークンがtermであれば、self.do_term(token, priority)でそれを処理して次のトークンが返ってくる。

そして、ここでトークンが演算子であれば再帰的にまた式が続くことになる。
operatorにexpressionが続くパターンが繰り返される限りどんどん再起が深くなっていき、最終的に;を読み込むと元に戻りつつoperatorで評価がなされる。

このコードでは全てが右側から順番に計算されるようになってしまう。

優先順位ありの場合

最初のdo_expressionの呼び出しは優先順位が低い20で行われる。俺俺コンパイラで実装している最低の優先順位が10なので11でも良かったのだが、今後他の演算子も加わるかもしれないので20にしてある。

ここで優先順位がない場合との違いはwhileの条件で「トークンの優先順位が今の優先順位よりも高ければ（値が小さければ）」が加わる。要は今処理している式より優先順位の高いoperatorが来たら先にそのexpressionを再帰的に処理している。

while token.is_operator() and token.priority() < priority:
	opcodes = token.operator_code()
	new_priority = token.priority()
	
	token = self.get_token()
	token = self.do_expression(token, new_priority)
	
	for opcode in opcodes:
		self.code_write('arithmetic', (opcode, ))

例えば1+2*3を考えると、1+2までトークンを読み終わって*が次のトークンの場合、1+2までの優先順位4より*の3の方が高いので*の式を先に処理する。

下記の書き方だとスペースの左側が最初のdo_expression呼び出しで、右側が2段目のdo_expression呼び出しになる。

1+2   ;		1+2まで読み込んだ状態
1+ 2*3;		*を読み込むと1段深いdo_expressionで2*3が先に処理される

この結果、優先順位の高いexpressionが先に評価され、それが終わると帰って来て元の優先順位の低いexpressionが評価される。

whileで同じ優先順位のoperatorが来た場合は、そこまでのexpressionの評価は終了して1段浅いdo_expressionでの評価が始まる。これで同じ優先順位の場合は左から順番に評価される。

1+2+3の場合

1+2   ;		1+2まで読み込んだ状態
1+2 +3;		+を読み込むと1+2が終了し1段浅いdo_expressionに戻って+3が処理される

これを繰り返して優先順位を考慮したexpressionの評価ができる。

do_termの処理

今回のサンプルではdo_termで処理しているのは3種類、整数定数と括弧の式、そしてunary_perator。

整数定数

これ以上の処理は必要ないので、そのままその数をpushしている。

if token.kind == 'integerConstant':
    term_value = token.value
    self.code_write('push', ('constant', term_value, 'int'))
    token = self.get_token()

括弧の式

トークンとして左括弧が来たら、その後からはそれまでの優先順位とは関係なく最低の優先順位の状態で新しいexpressionが始まる。
これで括弧の中はそれまでの優先順位とは関係なく先に評価されるようになる。
expressionの処理が終わったら次のトークンが右括弧であることを確認して評価は終了。

elif token.is_left_par():
    token = self.get_token()
    token = self.do_expression(token, LOWEST_PRIORITY)
    if not token.is_right_par():
        self.error_message('term left_par', '(', token)
        return token
    token = self.get_token()

unary operator

nary operatorは教科書の定義ではunaryOp termとなっているので、これをそのままコードにしてある。
nary operatorの次にくるtermを評価して、それに対してnary operatorの処理をしている。

elif token.is_unary_op():
    op = token

    token = self.get_token()
    if not token.is_term():
        self.error_message('term unaryOp', 'term', token)
        return token
    token = self.do_term(token, priority)

    self.code_write('arithmetic', (op.unary_code(),))

    return token

右結合

今のところtermで処理しているunary operator以外には右結合のoperatorはサポートしていない。が、もしも右結合をサポートするのであれば、優先順位なしの場合のコードのように、どんどん再帰を深くしていけば右側から演算するようになる。この場合の再帰を深くする条件は「優先順位が同じかそれ以上」の場合になる。これで右結合のoperatorもサポートできる（んじゃないかな）。

最後に

やってみたら思いの外簡単なコードになった演算子の優先順位。
あまりに簡単なので本当にこのコードで正しいのか非常に不安。思い付く限りいろいろな式で動作確認はしているのだがどうだろう…。バグレポートお待ちしています！

というわけで、俺俺クロスコンパイラの作成は思いの外楽しく、コンパイルされたZ80のマシン語をmsxのエミュレータで動かして遊んでいる。が、すぐにあれもやりたいこれもやりたいと仕様変更をしたくなってしまいmsxで動かすアプリの作成はなかなか先に進まないのが問題…

Discussion