コンパイラの例題を書きなおし中

構文解析はコンピュータ技術の中でも古いものだな。字句解析で単語を切り出して、構文解析で文法にそって構文木を作るわけですけどね。

構文定義はBNF(Bucus Naur Form)で書くわけですが、

expr : arithmetic
arithmetic : multiply
| arithmetic '+' multiply
| arithmetic '-' multiply ;
multiply : term
| multiply '*' term
| multiply '/' term ;
term : NUM
| WORD
| '(' expr ')' ;

みたいな感じ。この構文要素を作る関数を作って、それを純に呼び出せば良いわけですね。再帰下降法だな。他にもいろいろあるんだけど、

＊　再帰下降法が実用的なんだから、それだけで良いじゃん

という立場です。左再帰をループに直すとかはやらんとあかんが。

今まで使ってたのは大域変数使い放題だったので、それを修正してます。それ自体は簡単なんだけど、もう少し継続ベースに書きなおしたいところだ。

属性文法とか、PrologのDefinite Clause Grammersとか、Haskellのモナドを使ったもの、まぁ、いろいろあるんだよな〜 LL(1) とかは、もう良いと思うんだけど。

Erlang はPrologに似た構文を持っているんだけど、DCGの方に近いとも言えるね。

コード生成して実行するところまで書いたが「あれ? 最後が少し結果が違うな」というところで時間切れでした。

http://www.ie.u-ryukyu.ac.jp/hg/teacher/index.cgi/home/hg/teacher/kono/cc/