コンパイラの構文解析（上向き）の習得

コンパイラの仕組みについて興味があり勉強しています。
構文解析について下向きの再帰降下法についてはコンパイラの入門書などにも説明があり、簡単なものであれば自分でコードを書けるレベルになりました。

次にyaccなどに使用されているという上向きの構文解析法（LR/SLR/LALR等）を学びたいと思いましたが、良い資料が見つかりません。
具体的には理論の説明（集合の式等が理解しにくいです）だけではなくて、簡単な式などを評価するソースコードや実際の動作が解説されているものがあれば嬉しいです。

ネット上あるいは市販の3000円台程度の書籍で良いものがありましたらご紹介いただけると嬉しいです。
よろしくお願いします。

No.4 ベストアンサー 回答者： rinkun 回答日時： 2011/11/08 13:54

LR構文解析についてまじめに勉強するなら

　プログラミング言語処理系 ( http://www.amazon.co.jp/dp/4000103458 )
とかには事例も含めて細かく書かれていたと思うけど、集合の式は出てくるしアルゴリズムは書いてあってもソースコードはないので難しいかな。価格も5千円ほどするし。

あとは
　コンパイラ ( http://www.amazon.co.jp/dp/4274130134 )
とかかな。こっちは3千円強で買える。
このくらいしか知らないや。

なお、先の回答に書いた解析表現文法(PEG)とPackrat parserについては日本語の書籍を知りません。ただパーサの実物は一杯あるようなので、ソースを読むのが早いでしょう。

この回答へのお礼

再度のご回答ありがとうございました。

> コンパイラ ( http://www.amazon.co.jp/dp/4274130134 )

中田先生の本は既に参考にさせて頂いておりますが、残念ながらLR構文解析についての記載は無いようです。

> プログラミング言語処理系 ( http://www.amazon.co.jp/dp/4000103458 )

こちらの本は知りませんでした。検索してみると評判は良さそうですね。
ドラゴンブックは高すぎて手が出せませんが、こちらは何とかなりそうかもしれません、検討してみます。

情報ありがとうございました。

お礼日時：2011/11/09 18:58

No.3 回答者： rinkun 回答日時： 2011/11/07 15:00

LR解析器の理論を分かりやすく記述している本は知りませんね。

集合の計算が分からないと理解は難しいのじゃないかな。

なお、コンパイラの仕組みに興味があるなら解析表現文法(PEG)とPackrat Parserを調べてみるとおもしろいと思います。プログラム的には再帰下降法の延長で書けるし、LRに負けない表現力があるし。
# http://ja.wikipedia.org/wiki/%E8%A7%A3%E6%9E%90% …

この回答へのお礼

ご回答ありがとうございました。

> LR解析器の理論を分かりやすく記述している本は知りませんね。

やはり初心者向けではないということで簡単な解説書をいうのはないのでしょうか。
それではコンパイラ・コンパイラを作成される方はどう様に勉強されたのかという疑問も沸きますが……情報系の大学でしか学べないのかな。

> 集合の計算が分からないと理解は難しいのじゃないかな。

資料を読んでいてもいきなり、集合に関する数式がでてくるのでお手上げ状態です。
よく例で出てくる、E/T/F/idだけの構文から為る数式から状態表を作成する手順の説明とソースコードでもあれば助かるのですが。
でも、趣味でやっていることですので、もう少し、わけの分からない数式とにらめっこしてみたいと思います。


> コンパイラの仕組みに興味があるなら解析表現文法(PEG)とPackrat Parserを調べてみるとおもしろいと思います。

情報ありがとうございます。これらは初めて知りました、構文解析の方法もいろいろあるのですね。
これらについても勉強してみようと思います。

お礼日時：2011/11/07 19:10

No.2 回答者： MillenniuM 回答日時： 2011/11/07 02:41

手元にありませんが、.outputファイルの読み方については

『Rubyを256倍使うための本 無道編』でも詳しく書かれてたと思います。
bisonのマニュアルにも詳しく書かれてます。
状態機械の動作についてはraccがわかりやすいと思います。.outputの
状態遷移について見て取れたら、.tab.rbの状態遷移表と
lib/racc/parser.rb か ext/racc/cparse.cを見比べることで動作を
追跡できます。先読みのポイントはread_nextというフラグをどういう時に
使っているかでわかると思います。
raccにはy2raccというyaccの文法ファイルをracc用に変換するスクリプトが
付属してるので、いろいろ試してみると良いのではないでしょうか。
参考URLはbisonのマニュアルです。

動作についてじゃなく表の構築について知りたいなら、やっぱりソースか
マニュアルにある論文を当たるしかないように思います。

参考URL：http://www.gnu.org/s/bison/manual/bison.html

この回答へのお礼

再度のご回答ありがとうございます。

> 動作についてじゃなく表の構築について知りたいなら、やっぱりソースか
> マニュアルにある論文を当たるしかないように思います。

仰るとおり、表の構築の理論が一番わからないところとなります。後出しで申し訳ありませんがyacc（というかbison）とraccは既に使用してみたことがある（JavaCCについては既出の本を読んだのみです）ので、既に完成された表に対してのshift/reduceの動作は何とか理解できています。

ネットで検索して、大学の講義の資料のようなものをいくつか見てみたのですが、理論側によりすぎていて専門の知識のない私が理解するにはかなりキツイと感じました。（集合に関する数式が理解できません（笑）


ですので、簡単な実装・ソース・動作についての資料が無いかと質問させて頂いた次第です。

お礼日時：2011/11/07 04:40

No.1 回答者： MillenniuM 回答日時： 2011/11/06 17:43

1. GNUによるyacc実装のbisonのドキュメントには

　　簡単な電卓や関数電卓の完全な例があります。
　　ソースコードはringサーバーやGNU本家から自由に入手できます。

2. あとは、青木峰郎さんの『Rubyソースコード完全解説』第2部が
　　Rubyの構文解析について扱っています。参考URLで公開されています。

3. 同じく、青木さんのRubyによるyacc実装のraccも参考になるかと。
　　古書で探せばraccの256倍本も手に入るかもしれません。
　　これはかなりカジュアルなyacc入門書です。

4. 青木さんの『ふつうのコンパイラをつくろう』はJavaで
　　Cのサブセットを実装しています。

5. 今のところ日本で出版されたHaskell関係の本では
　　全てで何らかの構文解析を扱っているように思います。

参考URL：http://www.loveruby.net/ja/rhg/

この回答へのお礼

ご回答ありがとうございます。

念のための確認なのですが私の質問の趣旨は、yacc(racc)の使用方法ではなくて、yacc等で採用されているらしい上向き構文解析（LR法など）の仕組みの理解です。
ご提示いただいた項目でその理解は可能でしょうか？

『raccの256本』や『ふつうのコンパイラをつくろう』では、コンパイラ・コンパイラの内部動作についての解説は無かった様に記憶しております。

たしかにyaccやbisonのソースを見て理解という方法もありますが、今の私には敷居が高いです。

お礼日時：2011/11/06 18:28