pccts 入門
LL(k) parser generator の pccts について少しだけ。
私が教えてあげるわけじゃなくって、私が入門。 つうか教えてくれ。
http://www.okisoft.co.jp/esc/whitepaper.html こちらの「開発」はおもしろおかしくディープなこと書いていらっしゃるし、書籍なら、
Nutshell の Lex & Yacc
あたりを読めば、lexer と parser でどんなことができるのか、 ひととおりは分かるようになるんじゃないかなあ (ちなみに yacc は LALR parser generator)。 って、日本語訳版は絶版になってるのか。 知らなかった。
配布元: http://www.polhode.com/pccts.html
lexer に dlg、parser に antlr という構成になっている。 現在は antlr は antlr 2 になって、 開発ターゲットが C++ やら java やら python やらに変更。 OpenBSD の ports は pccts だけで、antlr 2 は絶賛放置中。 私は C くらいしか必要としないし、良しとしておく。
とりあえず、上の本の例題(Chapter 3-03)をマネしてみる。 お約束の電卓だ。
lex/yacc 版は例題のコードをオンラインで読めるので、 見比べてみてはどうだろう。
でコードはこんな感じ: ch3-03.g。
top-down parser なので右再帰で書いていく。 左再帰はダメ。ゼッタイ。理由。 左再帰で書くと、
fatal: attrib/AST stack overflow foo.c(lineno)!
みたいなエラーでパース時に停止する羽目になる。恐怖。
で、ここのところは結局のところ末尾再帰なので goto に置き換えができる。 だからスタックが溢れたりすることはないので、湯水のように再帰を使ってよろしい。
文法としては、空記号を含む再帰を省略できるワイルドカードがどことなく正規表現風味。 yacc でいうころの %left, %right, %prec, %nonassoc 等の 優先順位や結合を制御する手抜きのための構文は pccts にはない。 ここは全部書き下すしかない。ちょっと不便かも。
それと、コンパイルしたら分かるけど、 { "\+" "\-" }, { "\*" "\/" } の終了条件が曖昧になって警告が出る。 生成されたコードはちゃんと期待通りに動くところを見ると、 antlr がうまく解決してくれているようだ。
といっても、やはり文法自体を直したいなあ。
prim: ...
| Symbol {"="^ expr }
がまずいのは一目瞭然だけど、どう直したらいいんだろう。
それは置いておいて、 ビルドは付属の genmk を使えば Makefile を自動生成できる。
$ genmk -project ch3-03 ch3-03.g > Makefile
けど、Makefile を見る限り、自分で書く方がいいのかもしれない。
あ、そういえば emacs 標準の antlr-mode が壊れているので以下のように修正すべし。
(defface antlr-default '((t ())) "Face to prevent strings from language dependent highlighting. Do not change." :group 'antlr) ;; backward-compatibility alias (put 'antlr-font-lock-default-face 'face-alias 'antlr-default)
defface の第 2 引数はリストなのだ。
それにしても関連文書が少ない。 manual.txt と A PCCTS Tutorial と、comp.compilers.tools.pccts と、 あとは付属のサンプルを気合で読んでいくしかないのだろうなあ。
どこまで使えるか、ちょっとしたインタプリタでも組んでみよう。
追記
あー、なるほど。LL(1) だと、行頭のトークンが Symbol だった時は
Symbol "=" expr Symbol "\n"
のどちらを差しているのかどうか、判定できないのか。
結局、上の本と同じような文法にしたければ、LL(2) じゃないとダメなのだろうか。 その2 : ch3-03p1.g
antlr に食わせるときにオプションスイッチ -k 2 を入れてやる必要がある(LL(2) で開始)。 しかも、二回先読みで "\n" を読んでしまった後だから、二回改行しないと評価が終了しない。 これじゃあ repl できないよなあ。困った。 LL(1) にできないものか。
