fight against happy conflict

lexerはだいぶ整ってきたのでparserを書いている。

Haskellでのパーサジェネレータ周りのツールチェインだとほぼalex + happy一択っぽいし 知見が多そうなのでそれを使っている。 (GHCでも使われている道具なので使いっぷりで困ったことがあればGHCのソース見るという逃げ道もあってお得)

この記事では僕のように今までlex/yaccを使ったことがないにもかかわらず、Haskellのalex/happyを使い出してしまうような死に急いでいる人向けの参考になれば、と思うことを書く。

conflict万歳

構文を定義してパーサ作っていたら思ったように解析してくれなかったり、 解析そのものに失敗することが増えてきた。

なんだろうなと思って入力を変えてみて解ったのだけれど、 とっととreduceしてもらいたいところなのに次のトークンを待つ(shift待ち)パターンが選ばれて 期待した入力がこないためにfailしていた。

reduceしてほしいのにshiftが動く、みたいな問題をshift/reduce conflictと呼ぶらしい。

happyが出力する.info拡張子のレポートを見ていると、 スタックに積まれたトークン列に対して発行できるreduceがいくつもあり得るという、 いわゆるreduce/reduce conflictのパターンも検出されていた。

こういうconflictを放置するとあとで大きな構文木を作ろうとするときのデバッグで苦労しそうなので今のうちに倒しておこうと思う。

conflictのデバッグ

王道なし、ということらしい。 なので.infoファイル読みながら闘うことになる。

conflictを見つける

happyのユーザガイドに何も書いてなかったので手探りでやる。

こんな感じで出てくる。

----------------------------------------------------------------------------- Info file generated by Happy Version 1.19.5 from src/Ily/Parser.y ----------------------------------------------------------------------------- state 2 contains 2 shift/reduce conflicts. state 8 contains 1 shift/reduce conflicts. state 14 contains 1 shift/reduce conflicts. state 15 contains 7 shift/reduce conflicts and 6 reduce/reduce conflicts.

r/r conflictがstate 15に見つかったらしい。

state 15

State 15 dec -\> val . seq(tyvar) valbinds (rule 72) dec -\> val . valbinds (rule 73) int shift, and enter state 6 (reduce using rule 107) string shift, and enter state 22 (reduce using rule 107) char shift, and enter state 23 (reduce using rule 107) and reduce using rule 127 (reduce using rule 107) end reduce using rule 127 (reduce using rule 107) in reduce using rule 127 (reduce using rule 107) op shift, and enter state 26 (reduce using rule 107) '(' shift, and enter state 94 (reduce using rule 107) '{' shift, and enter state 44 (reduce using rule 107) '\_' shift, and enter state 45 (reduce using rule 107) id reduce using rule 107 (reduce using rule 19) longid reduce using rule 107 (reduce using rule 19) tyvarid shift, and enter state 38 %eof reduce using rule 127 (reduce using rule 107) scon goto state 39 tyvar goto state 87 ope goto state 40 atpat goto state 41 pat goto state 88 valbinds goto state 89 valbind goto state 90 sep(valbind,and)goto state 91 seq(tyvar) goto state 92 rev\_sep(valbind,and)goto state 93

見分け方

shiftが適用されているけどreduceの可能性も示唆されているもの。

shift/reduce conflict

 int shift, and enter state 6 (reduce using rule 107)

reduceが適用されているけど別のreduce ruleの可能性も示唆されているもの。

reduce/reduce conflict

 id reduce using rule 107 (reduce using rule 19)

意外と見つけやすかった。

Stateは構文規則の何と対応づいているのか

conflictが起きている事実を確認できた。 これを修正しようといったいどの規則を直せばいいのか調べる必要がある。

これがわからない。

そもそも何故これが起きるのかを知るためには、 もとの構文規則とこのinfoファイルの中で言われていることの対応が明確でないといけない。