[HOP]パーサを作ろう その2
なんとかターゲット決めうちで、ここまでパース出来るようになった。
>>>
('expression',)
('(', 'expression', ')')
('(', 'INT', '*', 'expression', ')')
('(', 'INT', '*', '(', 'expression', ')', ')')
('(', 'INT', '*', '(', 'INT', '+', 'expression', ')', ')')
('(', 'INT', '*', '(', 'INT', '+', 'INT', ')', ')')
>>>
ソースはここ
深さ優先で検索する方法が分かった。よく考えると、このパーサーのアルゴリズムで答えが無かったら無限ループするのって、幅優先も深さ優先も同じじゃね？と思ったら、やっぱりそうらしい。ここまで自分の手で動かして、ようやく@alohakun発言の意味が分かる。俺、コンピュータサイエンス弱ぇー。
http://twitter.com/alohakun/statuses/431771522
バックの絵きんもー！
yaccとか、lexとか、bisonとかいうのも、Wizard形式のプログラミングと一緒で、もともとそういうのが無くても出来る人が楽するためにあるんだよな。一歩ずつ行こう。
そんなことを思っていたら、本にコーヒーをこぼしてしまった。もう、誰にも貸せない本になった・・・
8.2 Parsing in general終了。
ようやく、再帰下降のパーサーに入る。
The comments to this entry are closed.
Comments
いや、yaccはyaccでいろいろ苦労がありまする。
BNFとかの構文定義をyaccのソースに落とすのはそれなりに
経験とかテクがいりますし、C++みたいにyaccでやると逆に苦労するというものもあります
#g++では手書きのパーザに戻っているはず
手書きでパーザを(再帰下降で)書く場合でもノウハウがそれなりに蓄積されているので、
yaccが開発された当時に比べれば書きやすいのではないかと。
Posted by: きむら（K) | 2007.11.25 12:10 AM
きむら（K)さん、こんにちは
> いや、yaccはyaccでいろいろ苦労がありまする。
えぇ、そうなんですか。世の中のハッカーは、こういうツールですらすらと構文解析しているのかと思ってました。
C++のパースに関しては、D&Eでも難しかったと書かれていたのを覚えています。
> 手書きでパーザを(再帰下降で)書く場合でもノウハウがそれなりに蓄積されているので、
> yaccが開発された当時に比べれば書きやすいのではないかと。
なるほど。
手書きで書くにしても、Boost等に走るにしても、基本が分かっていないと何もできないので
もう少し勉強進めてみます。
Posted by: Natsutan | 2007.11.25 09:44 PM
いつもお世話になっています。私の場合で恐縮ですが、手書きのパーサは書いたことがありません。Verilog-2001までは、Biosn/Flex系で、大体BNFイメージそのままに書けます。ところが、VHDLやSVになるとShift-Reduce/Reduce-Reduceの嵐になり、そのままでは、うまく解析できません。ですので言語仕様によるかと思います。
Posted by: たっく | 2007.11.26 06:53 AM
たっくさん、こんにちは。
そうか、言語仕様によってそのまま行けるかどうかが決まるのですね。
iverilogは、普通にyaccで処理しているようで、.yファイルがありました。
SVとか、かなり新しい言語なのにParserの事は考えられていないのが不思議です。
決める人と、作る人が違うんでしょうね。
Posted by: Natsutan | 2007.11.26 05:34 PM
あー言葉足らずですみません。確かに言語仕様も影響しますね。
あとは、lexer と parser が密接に絡んでいる場合、たとえばPerlの
正規表現リテラルの解析とか、C++の型宣言やキャストの解析はyaccのような
ツールを使うとかえって書きづらくなる部類です。
Rubyでも、まつもとさんがyaccと格闘してますw
yaccだと構文解析が LALRで行われるので、左再帰の問題を気にしないでいい
ってのはyaccを使うと楽になる点の一つでしょうね。
でまあそれなりに存在価値はあるが万能ではないというところでしょう>yacc
LLだと手書き派とyacc派とどっちが多いだろう?
Posted by: きむら（K) | 2007.11.27 12:40 AM
きむら（K)さん、こんにちは。
Perlでいうところの、デミリタの変更とかその辺りですよね。
LALRがwikipedia読んでもよく分からないので、勉強して出直してきます。
PEGはストリームで見ましたが、とても面白かったですよ。
きむら（K)さんなら、私よりもずっと楽しめたと思います。
Posted by: なつたん | 2007.11.28 09:30 PM