caperが吐いたコードを読む
LALR(1)はどうやって動作しているのでしょうか？
理解を完全にするために、caperの吐いたコードを追いかけてみたいと思います。
caperは、jonigataさんの作られたパーサジェネレーターです。パーサジェネレータの中では群を抜いてきれいなコードを吐いてくれます。最近のバージョンアップでジェネレータが追加されていろんな言語を吐いてくれますので私みたいなC/C++は一応読むことはできても直感的な理解には言語障害があるやつにはもってこいです。感謝感謝。
とりあえずcaper付属のcalc0.cpgを相手にします。
%token Number<int> Add Sub Mul Div; %namespace calc; %dont_use_stl; Expr<int> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<int> : [Identity] Number(0) | [MakeMul] Term(0) Mul Number(1) | [MakeDiv] Term(0) Div Number(1) ;
トークンはNumber, Add, Sub, Mul, Divの5種類。値はint。[]の中はセマンティックアクションの関数名です。左再帰もありますので手頃でしょう。
まずはソース生成。
> caper -d calc0.cpg calc0.d
そうして生成したcalc0.dを上から。
module calc0;
モジュール宣言。.cpgファイル中の%namespaceだの%dont_use_stlだのは、C++以外では壮絶に無視されます。どうでもいい。
enum Token {
token_eof,
token_Add,
token_Div,
token_Mul,
token_Number,
token_Sub
}
トークン宣言。覚えのないeofが勝手に追加されています。たぶんこれを最後にpostしないといけないのでしょう。
class Stack(T, int stackSize) { ...中略... }
えらくややこしいStackクラステンプレート。gap_とか一見わけわかりませんが、要するにreset_tmpで最後にcommit_tmpしたところまで巻き戻したいだけのようです。それも、post時のエラーリカバリにしか使われていません。こんなの単方向リンクリストでいいじゃん。無意味に固定長にして制限かけなくてもGCあるんだからさあ。誰だよDジェネレータ書いたの。
class Parser(Value, SemanticAction, int stackSize = 1024) { alias Token TokenType; alias Value ValueType; this(SemanticAction sa){ sa_ = sa; reset(); }
ここから本番です。
コンストラクタはSemanticActionを受け取りますが、SemanticActionの型はParserクラステンプレートをインスタンス化する時点で明記してますので、2回書かせるのは不親切と思います。autoのあるD言語らしくない。
calc0.Parser!(int, SemanticAction) parser(new SemanticAction);
Parser側でmixin SemanticAction;しとけばこれで良かったのに。誰だよDジェネレータ書いたの。Dを使う時はDらしく！C++を真似る意味は無いんですよ！
calc0.Parser!(int, SemanticAction) parser;
コンストラクタから呼ばれているresetメソ……member functionです。
void reset() { error_ = false; accepted_ = false; stack_ = new typeof(stack_); clear_stack(); reset_tmp_stack(); ValueType defaultValue; if(push_stack(&state_0, &gotof_0, defaultValue)){ commit_tmp_stack(); }else{ sa_.stack_overflow(); error_ = true; } }
Stackクラステンプレートの仕様のせいで煩雑になってますが、要するに状態0をスタックに積んでいるだけです。
スタックはこんなです。
alias bool delegate(TokenType, ValueType) state_type; alias bool delegate(int, ValueType) gotof_type; struct stack_frame { state_type state; gotof_type gotof; ValueType value; static stack_frame opCall(state_type s, gotof_type g, ValueType v) { stack_frame result; result.state = s; result.gotof = g; result.value = v; return result; } } Stack!(stack_frame, stackSize) stack_;
ValueType value;の型は本来途中のノードが取りうる値、.cpgファイルで
stack_frameのstaticなopCallは、Dでaggregateっぽいことをやるときの常套手段ですね。C99なら要らないです。
なおこのすぐ上に、privateな上にどこからも使われていない次の宣言がありますが、どこからも使われていないので誰だよDジェネレータ書いたのと言いながら無視しましょう。
alias typeof(this) self_type;
postは、処理のメインですね。
bool post(TokenType token, ValueType value) { assert(!error_); reset_tmp_stack(); while((stack_top().state)(token, value)){ } if(!error_){ commit_tmp_stack(); } return accepted_; }
要するに次の1行だけです。
while((stack_top().state)(token, value)){ }
state_?関数がtrueを返しつづける限りループします。
逆にいえば、falseが返されると入力が消費されたと言えます。
acceptとerrorは処理の流れとしては脇役ですので飛ばします。それ以外のprivate宣言は単にスタック操作に別名付けてるだけですので飛ばします。
bool accept(out ValueType v) {
bool error(){ return error_; }
そうすると後はstate_?関数とgoto_?関数だけです。短いですね。liby.aやparsing.mlが必要な上にグローバルで状態を持つどっかのパーサジェネレータとは大違いです。
bool gotof_0(int nonterminal_index, ValueType v) { switch(nonterminal_index){ case 0: return push_stack(&state_1, &gotof_1, v); case 1: return push_stack(&state_2, &gotof_2, v); } } bool state_0(TokenType token, ValueType value) { switch(token) { case Token.token_Number: // shift push_stack(&state_7, &gotof_7, value); return false; default: sa_.syntax_error(); error_ = true; return false; } }
shiftの時はreturn false;と書かれています。先ほどの推測を確認してみましょう。……shift……入力を消費、と、accept……終わり、と、エラーの時は、return false;ですね。
ではreduce……ひとつのルールが最後まで一致した時は？
case Token.token_eof: // reduce { int arg0; sa_.downcast(arg0, *get_arg(1, 0)); int r = sa_.Identity(arg0); ValueType v; sa_.upcast(v, r); pop_stack(1); return (stack_top().gotof)(0, v); }
gotof_??を呼び出した結果を返しています。では、gotof_??関数は？
bool gotof_0(int nonterminal_index, ValueType v) { switch(nonterminal_index){ case 0: return push_stack(&state_1, &gotof_1, v); case 1: return push_stack(&state_2, &gotof_2, v); } }
push_stackはスタックオーバーフロー以外常にtrueですので、結局あのwhileループは、入力を消費する時と終わる必要があるときはfalseで終了、ひとつのルールが最後まで一致した時つまり入力そっちのけでセマンティックアクション呼ぶときつまり入力を消費していない時はtrueで入力を消費するまで繰り返し、と、こうしてプッシュ型パーサが実現されているようです。プッシュ型パーサ素敵だ。
そしてgotof_??関数は、どうやらひとつのルールが完了したあとどこに戻るかの表っぽいですね。2次元配列ではなく関数になっているのは、手書きと主張できるようにするためでしょう。たぶん。……配列にすると大部分使わない領域になってしまったりそんなでしょうか。いや、知りませんが。
知りませんがと言えば、状態0から状態7に行く時に状態1を間に挟むように積んでおけば、goto_f??要らないのではと素人考え……。いや、LR型パーサは元々積んだ内容に対してマッチをかけているのを、状態遷移を入れることで効率化しているだけなので、スタックには本来値だけが詰まれているのが正しいのではないかな……で、余計なものを間に挟むと値に隙間ができるから良くないのでは……。しかし状態を導入した結果スタックの内容についてはマッチなんかしてないわけで、やっぱできるのでは……うーん、もっと大きい文法で試してみないとわからないかな。
そもそも順番が違います。まだLALR(1)の動きがよくわかってないのです。
実際に追っていってみましょう。
"0"(eof)が入力されたと仮定します。
| 0 | - |
↓
| 0 | - |
| 7 | 0 |
↓
| 0 | - |
| 2 | 0 |
↓
| 0 | - |
| 1 | 0 |
終わり。
状態の意味はこんなかな……。
| 0 | 最初 |
| 1 | [Identity] Term(0) ★ [MakeAdd] Expr(0) ★ Add Term(1) [MakeSub] Expr(0) ★ Sub Term(1) |
| 2 | [Identity] Number(0) ★ [MakeMul] Term(0) ★ Mul Number(1) [MakeDiv] Term(0) ★ Div Number(1) |
| 7 | [Identity] Number(0) ★ |
センスオブ再帰下降で考えますと、行きは一瞬ですけど、帰りは一段ずつセマンティックアクションを実行しながら戻ってきてますね。
"1+1"(eof)が入力されたと仮定します。
| 0 | - |
↓
| 0 | - |
| 7 | 1 |
↓
| 0 | - |
| 2 | 1 |
↓
| 0 | - |
| 1 | 1 |
↓
| 0 | - |
| 1 | 1 |
| 3 | - |
↓
| 0 | - |
| 1 | 1 |
| 3 | - |
| 7 | 1 |
↓
| 0 | - |
| 1 | 1 |
| 3 | - |
| 4 | 1 |
↓
| 0 | - |
| 1 | 3 |
終わり。
だいぶつかめてきました。
| 0 | 最初 |
| 1 | [Identity] Term(0) ★ [MakeAdd] Expr(0) ★ Add Term(1) [MakeSub] Expr(0) ★ Sub Term(1) |
| 2 | [Identity] Number(0) ★ [MakeMul] Term(0) ★ Mul Number(1) [MakeDiv] Term(0) ★ Div Number(1) |
| 3 | [MakeAdd] Expr(0) Add ★ Term(1) |
| 4 | [MakeAdd] Expr(0) Add Term(1) ★ |
| 7 | [Identity] Number(0) ★ |
こんな風にソースコード追っていくと、こんな感じです。
| 0 | 最初 |
| 1 | [Identity] Term(0) ★ [MakeAdd] Expr(0) ★ Add Term(1) [MakeSub] Expr(0) ★ Sub Term(1) |
| 2 | [Identity] Number(0) ★ [MakeMul] Term(0) ★ Mul Number(1) [MakeDiv] Term(0) ★ Div Number(1) |
| 3 | [MakeAdd] Expr(0) Add ★ Term(1) |
| 4 | [MakeAdd] Expr(0) Add Term(1) ★ |
| 5 | [MakeSub] Expr(0) Sub ★ Term(1) |
| 6 | [MakeSub] Expr(0) Sub Term(1) ★ |
| 7 | [Identity] Number(0) ★ |
| 8 | [MakeMul] Term(0) Mul ★ Number(1) |
| 9 | [MakeMul] Term(0) Mul Number(1) ★ |
| 10 | [MakeDiv] Term(0) Div ★ Number(1) |
| 11 | [MakeDiv] Term(0) Div Number(1) ★ |
例えば、これにエラー処理を加えるとしたら、いきなり"+"が来た場合はこんな遷移を用意すればいいのでしょうか。
| 0 | - |
↓
| 0 | - |
| 1 | * |
| 3 | - |
あとはMakeAddの1項目のExprを補ったという情報をどこかに残しておいて、そこから「Exprが必要です」とかなんとか。
先の疑問の回答は、左再帰があると、後に続くトークンによって何段階reduceすることになるかが可変のため、"1"の段階でスタックに戻り先を用意しておくことができないから、でいいのでしょうか。左再帰を検出してその時はポップしない(再帰下降で左結合の演算子を処理する時は再帰ではなくwhileで書く)ようにすればOKなんでしょうけれども、例外作ることになりますし、連鎖的に落とし穴作ってしまいそうです。
……ここから先はcaper本体側ですね。
