« バイナリアンへの道は遠い | Main | $の話 »

2008.04.27

LALR

コンパイラの本充になったので、ようやくLRなパーサの勉強をする。ざっくり読んで、雰囲気は分かった。実際手を動かしてみると、予想以上の難易度で驚く。

ありがちな数式の定義(http://kaiunix.cs.shinshu-u.ac.jp/Lesson/ProgLangT/2008/SyntaxAndSemantics.htmlとか)を考えたとき、(1 + 2) * (3 + 4) なら簡単にできるんだけど、1 + 1 + 1 + 1 + 1 になると、難しかったりする。1 + 1 + ・・・の段階では、どの+も右側が確定しないから、何にもできない。一番最後の式の終わりで、初めてこれtermじゃんって事がわかって、右から順番に、俺もterm、実は俺もterm・・・という感じでパースが終わる。アルゴリズム分かったけど、どうプログラムに落とすのかが、想像もつかない。

もう一度本に戻ると、状態遷移の表を作るらしい。表を追って、ひとりでああなるほどと納得する。じゃあ、この表をどうやってつくるんだとう当たり前の疑問。ここで、yaccの出番か!

|

« バイナリアンへの道は遠い | Main | $の話 »

Comments

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/41009278

Listed below are links to weblogs that reference LALR:

« バイナリアンへの道は遠い | Main | $の話 »