前回の投稿の解決編です。前回はコンフリクトの概要と思っていないコンフリクトが出て私の心が折れたところまで
でした。元の問題のサンプルコードなどはお手数ですが、前回のページをご覧ください。
コンフリクトを分析する
コンフリクトの警告が出た時、当てがついていればすぐ修正できますが、大抵は正しいと思って書いているので、なんで?と困惑することになります。また、警告メッセージも不親切で、コンフリクトの数しか表示されず、何行目等の情報はでません。かといって、あてずっぽうで修正するのも、時間がかかるし直ったとしても修正に自信がもてないと思います。少し面倒でも、ちゃんと原因まで特定して対処したほうがよいでしょう。
レポートの出力
実はbisonにはコンフリクトも含めた詳細なレポートを出力する機能があります。前回の最後に書いたように下記のレポート出力のオプションを付けてコマンドを実行しましょう。入門系のサイトを見ても簡単な計算機の例しか書いていないことがほとんどなので、知らない人も多いのではないかと思います。
$ bison conflict.yy -r all --report-file=conflict.log
すると、指定した場所(ここではconflict.log)にレポートが出力されます。テキストエディタで開いてみてください。
レポートの見方
コンフリクトがあれば最初に以下のような情報が出力されているはずです。
State 16 conflicts: 1 shift/reduce
State 28 conflicts: 1 reduce/reduce
State 38 conflicts: 1 shift/reduce
State 40 conflicts: 2 shift/reduce
State 41 conflicts: 2 shift/reduce
...
ソースの場所は書いてませんが、コンフリクトがでたStateとその番号が出てます。なにか手がかりになりそうです。試しに一番問題がありそうなreduce/reduce conflictの"State 28"を検索してみましょう。
...
State 28
7 return_value: type_def ID . [ID, ',']
21 declaration: type_def ID . [',', ';']
',' reduce using rule 7 (return_value)
',' [reduce using rule 21 (declaration)]
';' reduce using rule 21 (declaration)
$default reduce using rule 7 (return_value)
...
なんか、それっぽい情報が書かれてますので、これが分かれば原因が分かりそうですね。ただし最大の問題は、このレポートの読み方についての情報がどこにあるのか私が知らないので(え?)、ここからは私の勘による解説です。ドキュメントを知ってる方がいたら教えてください。とはいえ、手がかりはこれしかないので、しばらく眺めて下さい。何か見えて来るでしょう?
記述が上部と下部に分かれてますね。上が現在の読み込んだ状態(2つまで)と、次に来る字句(トークン)、下が対応するアクションみたいなもんでしょうか。つまりState 28は、type_defとIDを読み込んだ状態ときの定義です。日本語(?)にすると
- type_defとIDを読み込み済で、次にくるトークンが 「ID」または「,」だったら [type_def+ID]をreturn_valueにする(還元)。
- type_defとIDを読み込み済で、次にくるトークンが 「,」または「;」だったら [type_def+ID]をdeclarationにする(還元)。
と書かれているようです。。。あれれ。 「,」が来たらどちらになるんでしょうね。
下部には具体的な動きが記述されています。つまり
- 「,」が来たらルール7を使って return_value にする。
- (衝突したので「,」が来た場合、declarationにするのは無し)
- 「;」が来たらルール21を使って declarationにする。
- それ以外(IDが来たら) ルール7を使って return_value にする。
と書かれています。このままだと何が起こるかわかるでしょうか?
このままだと、「,」が来た場合には問答無用でreturn_value(関数の戻り値)と解釈されるので、恐らく複数のdeclartation(変数宣言) は文法エラーになってしまうと思われます。
コンフリクトの解決方法
ここまで原因が具体的にわかれば、いくつかの対策が打てるのではないでしょうか? 下記の対策があると思います。
- 構文の見直し - 構文を変えられるのでしたらこれが一番楽でしょう。
- 例えば、関数宣言の前にキーワード (funcなど)を付けて、状態を分ける。今回の場合だと、funcが来た後のtype_def+IDは必ずretun_value、なければdeclarationが確定。
- return_valueとdeclarationの構文を全く同じにする。今回の場合だと名前なしreturn_valueをなくして、タイプ名を同じものを使用するとできる。
- 字句解析器の方で先読みなどして、トークンを分ける。- 今回は有効ではないですが、結構実用性高いと思います。
- 例えばIDではなく、字句解析器で先読みして、後に「(」が出てくるようであれば、ID -> RET_IDとする。
- GLRパーサーにする。先読みすればあいまいさがないと自信がある場合の秘密兵器。(私は使ったことないですが。。)
%glr-parser
%expect-rr 1
上の記述があると、bisonはデフォルトのLALR(1)パーサーでなくて、GLRパーサーを生成します。簡単にいうと、あいまいさがないところまですべての分岐を覚えておいて、あいまいさが解決した時点でいらないものを破棄します。2つ先読みぐらいだったらほとんど遅くならないと思いますが、アルゴリズム的には100倍遅くなっても文句言えません。
shift/reduceの分析と解決は?
同じように、レポートを眺めてれば、見えてくるのでは、、、、ではダメでしょうか。
今回は力尽きたのでまた次回(需要がありそうなら..)。多分、解決のカギは % left。