スクリプト言語の作り方
千葉 滋
２週間でできる！スクリプト言語の作り方
技術評論社、March 2012.
ISBN 978-4-7741-4974-5
ソースコード
Eclipse へのプロジェクトの読み込み
上記のソースコードをダウンロードして適当な場所に展開します。 次に以下のようにします。
-
Eclipse の File メニューの Import を実行します。
-
General の Existing Projects into Workspace を選択します。
-
Root directory として展開したソースファイルの stone-lang を選択し、読み込みを実行します。
正誤表
（現在は修正済）
（一部の指摘は筑波大学の前田敦司先生による）
- 4.1 章 p.42 の図4.4 の表題
13 + x * 2 の抽象構文木(抽象構文木は括弧を含まない)
は誤りで、
(13 + x) * 2 の抽象構文木(抽象構文木は括弧を含まない)
が正しい。
- 4.2 章 p.43 表 4.1
ASTLeaf child(int i) は正しくは ASTree child(int i)
- 4.3 章 p.52 上から3行目
expresion : term | expression ("+" | "-") term
の左端の expresion はスペルが間違っている。expression が正しい。
- 5.2 章 p.58 下から2行目
「パサー」は「パーサ」が正しい。
- 5.3 章 p.66 の図5.1
根のオブジェクトは ASTLeaf ではなく ASTList オブジェクト。
- 6.2 章 p.84 リスト 6.3
IfEx クラスの eval メソッドの 2 行目
if (c instanceof Integer && ((Integer)c).intValue() != FALSE)
は
if (!(c instanceof Integer && ((Integer)c).intValue() == FALSE))
が正しい。 後者であれば続く p.86 の囲みコラム下から 2 行目の記述「整数0なら偽、それ以外ならなんでも真」と一致する。
補遺
p.302 下部に次のような対話文があります。
-
C: 後で説明する先読みをたくさんやればLL構文解析もLR構文解析と遜色ないからLLを解説することにした。
-
F: LL の方が LR より弱いのは、先読みを最大１個に限定した LL(1) と LR(1) の比較のときですよね。
これについて東京工業大学の佐々政孝先生よりコメントをいただきました。
それによると、LL(k) と LR(1) の比較でも LL(k) の方が弱いそうです。しかし、この話はそれほど簡単ではありません。
厳密には、LL(k) で解析できる言語、つまり LL(k) 言語は、どんなものでも、文法をうまく書き換えると LR(1) で解析できる言語になります。 あるプログラミング言語があって、その文法が LL(k) で解析できるのなら、文法を少し修正することで LR(1) でも解析できる、ということです。 文法を修正するときは、もちろん、修正の前後でその文法が意味するところが変わらないように修正します。 修正前の文法の下で正しい（正しくない）プログラムは修正後の文法の下でも正しくなる（正しくない）ように修正します。
逆に LR(1) で解析できる言語の中には、どう書き換えても LL(k) で解析できる言語にならないものがあります。 LL(k) より LR(1) の方がより広い範囲の言語を解析できることになります。
ただしこの議論は、「文法を書き換えると」という点がくせものです。 LL(k) 文法を書き換えて LR(1) でも解析できるようにすると、その文法が非常に理解しづらくなることがあります。 文法の読みやすさ、という観点からは LL(k) を用いて解析した方がよいこともあるようです。
また文法の書き換えを許さないとすると、LL(k) では解析できるが、LR(1) では解析できない文法が存在します。 LR(1) より LL(k) を使った方がよい場合もあるということです。 なお LL(k) で解析できるのなら、必ず LR(k) でも解析できますが、LR(k) のアルゴリズムは手で書くにはあまりに複雑ですし、LR(k) による構文解析器を生成するツールも簡単に手に入るものはないように思えます。
この辺りの議論は奥が深いので、興味のある方は参考文献を参照ください。 なお「プログラミング言語処理系」（佐々政孝）の該当箇所は p.122 と p.211 です。
参考文献
佐々政孝、プログラミング言語処理系、岩波講座ソフトウェア科学、岩波書店
Aho, A. and Ullman, J. D.: The Theory of Parsing, Translation, and Compiling, Vol. 1: Parsing.