C++ 自作物

言語処理系をつくろう(第3回):乗除算を実装する

自作の言語処理系開発日記の第3回です。前回は加減算を実装したので、今回は乗除算の実装にチャレンジしていきます。

実装してみる

今回の実装において、トークナイザ・コード生成器・実行系(仮想マシン)については加減算のときと変わりません。単純に各種定義を追加して、それを扱えるようにしてあげるだけです。

一方、構文解析器についてはちょっとややこしいので、そこだけ解説します。

構文解析器

加減算では演算の優先順位がなかったので、単純に左結合(=左から順に計算していく)で処理していけばOKでした。しかし、乗除算が入ると演算の優先順位が生まれるので、これを上手くさばくには工夫が必要です。

今回は優先度を考慮した生成規則を考えることで、これを解決していきます。前回までの生成規則は以下の通りです。

program = add
add = num ("+" num | "-" num)*

この定義に従って構文木を展開する順序と、実行時の処理順(評価順)を比較すると、以下のような感じになります。

  • 構文木の展開順:program → add → num
  • 実行時の処理順:num → add → program

このように、両者の順序は真逆になります。つまり、生成規則上で深くにあればあるほど、実行時には優先的に評価されます。この考え方を使えば、生成規則を以下のようにすることで、乗除算は実現可能です。

program = add
add = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*

新たにmulという乗除算の規則を追加し、add中のnummulに置き換えました。こうすることで、加減算よりも深くで乗除算が展開されるため、実行時の優先度は乗除算の方が高くなります。

コードはこれまで通り、ノード種別の追加と上記の生成規則に対応した処理を実装するだけなので割愛します。

これで、乗除算を含んだ式を扱えるようになりました。以前に言語処理系の自作にチャレンジしたときは、この優先度にとても悩まされたのですが、生成規則でそれを解決するという方法にちょっと感動してしまいました。当時はそんなことは知らなかったので思いつきもしませんでしたが、やっぱり勉強は大事ですね…。

今回の実装のコミットは以下です。コード全体はこちらをご覧くださいm(_ _)m

乗除算の実装(3862655)

ではでは

広告の表示がブロックされています。
広告の表示がブロックされています。

関連記事

C言語 自作物 Linux プログラミング

wordleもどきのCUIアプリをつくってみた

最近、wordleという英単語当てゲームで遊んでいます。シンプルなゲームながら、通勤時間の暇つぶしや友人とのスコア比べなど意外と中毒性があり面白いです。 普通に英単語の勉強にもなるので、もっとたくさん ...

RaspberryPi Linux

Raspberry Pi4+Ubuntu ServerでGitLabを動かしてみる

お仕事でGitLabに触れる機会があったので、学習用に自宅にもGitLabが欲しくなりました。 手元にあるRaspberry Pi4+Dockerならお手軽に立ち上げられるはずと着手したものの、意外と ...

Flutter プログラミング

【Flutter】アプリ内の設定値を実装する方法

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に ...

RaspberryPi Linux

YoctoでRaspberryPi4のイメージをビルドしてみた

昨今、様々なデバイスでLinuxが動くようになっている中、組み込みLinuxのデファクトスタンダードとなりつつあるのが「Yocto」と呼ばれるビルドシステムです。 組み込みの現場ではその名前を聞くこと ...

C++ 自作物

言語処理系をつくろう(第7回):比較演算子を実装する

自作の言語処理系開発日記の第7回です。前回までで変数の実装が終わったので、ここからはいよいよ制御構文を実装…と思ったのですが、制御のためには比較演算子を実装する必要がありました。 ということで、今回は ...

Ryo Yoneyama

とある会社でソフトウェアエンジニアをしています。技術的な備忘録を中心にまとめてます。ネタがあれば日記も書きます。

    -C++, 自作物