自作の言語処理系開発日記の第3回です。前回は加減算を実装したので、今回は乗除算の実装にチャレンジしていきます。
実装してみる
今回の実装において、トークナイザ・コード生成器・実行系（仮想マシン）については加減算のときと変わりません。単純に各種定義を追加して、それを扱えるようにしてあげるだけです。
一方、構文解析器についてはちょっとややこしいので、そこだけ解説します。
構文解析器
加減算では演算の優先順位がなかったので、単純に左結合（＝左から順に計算していく）で処理していけばOKでした。しかし、乗除算が入ると演算の優先順位が生まれるので、これを上手くさばくには工夫が必要です。
今回は優先度を考慮した生成規則を考えることで、これを解決していきます。前回までの生成規則は以下の通りです。
add = num ("+" num | "-" num)*
この定義に従って構文木を展開する順序と、実行時の処理順（評価順）を比較すると、以下のような感じになります。
- 構文木の展開順：program → add → num
- 実行時の処理順：num → add → program
このように、両者の順序は真逆になります。つまり、生成規則上で深くにあればあるほど、実行時には優先的に評価されます。この考え方を使えば、生成規則を以下のようにすることで、乗除算は実現可能です。
add = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*
新たにmulという乗除算の規則を追加し、add中のnumをmulに置き換えました。こうすることで、加減算よりも深くで乗除算が展開されるため、実行時の優先度は乗除算の方が高くなります。
コードはこれまで通り、ノード種別の追加と上記の生成規則に対応した処理を実装するだけなので割愛します。
これで、乗除算を含んだ式を扱えるようになりました。以前に言語処理系の自作にチャレンジしたときは、この優先度にとても悩まされたのですが、生成規則でそれを解決するという方法にちょっと感動してしまいました。当時はそんなことは知らなかったので思いつきもしませんでしたが、やっぱり勉強は大事ですね…。
今回の実装のコミットは以下です。コード全体はこちらをご覧くださいm(_ _)m
ではでは
