uDiary

◆ [Haskell][Hand] Parser.y デバッグ

昨日、Haskell 2010 report みながら、えいっと Parser.y を書いたんだけど、
ずいぶん conflict を出してしまった。

unused rules: 5
shift/reduce conflicts:  144
reduce/reduce conflicts: 212

ひとつひとつ、文法の曖昧なのをなくしていこう。
ひとつの問題で沢山の衝突が引き起される傾向があるようなので、この数ほど修正箇所はないだろう。

1. 空の規則じゃなくて error トークンをつかう

レイアウト規則では、そうしないと構文エラーになる箇所には仮想閉じブレースが補われることに
なっている。

そこで、仮想ブレースが閉じていないのを許容する文法にすればいいのかなと思ったんだけど、
こういうのはいかにも衝突の原因になる。

ccurly_opt: vccurly                            {}
  |          {- empty -}                        { {- pop ctx -} }

GHC のパーサーのソースをみると、error トークンが使われていて、Happy のマニュアルにも
そういう利用方法が書かれている。

close : '}'                  { () }
      | error        { () }

ついでに、非終端記号の名前も真似して close にしてみよう。

unused rules: 5
shift/reduce conflicts:  96
reduce/reduce conflicts: 176

shift/reduce が 48 個減、reduce/reduce が 36 個へった。

2. 単純間違い

lpat: gcon seq_apat

は

lpat: gcon seq1_apat

の間違いだった。このせいで apat: gcon と衝突。

unused rules: 5
shift/reduce conflicts:  128 (+32)
reduce/reduce conflicts: 127 (-49)

3. 空規則の除去

やっぱ空の規則をつくりすぎるのよくないもう一つの例。

topdecl: 'class' sctx_opt tycls tyvar 'where' cdecls

ctx_opt: context '=>'
  |      {- empty -}

こんななのだが、context の最初にも tycls と同じ文字列が来てもいいので曖昧。
GHC のソースをみると、A -> (context '=>' |) のような非終端記号をつくるので
はなく、

tycl_hdr -> context '=>' tycls | tycls

のようにしてあった。こうすることで、問題となる還元規則がなくなり、

パーサは tycls が context の一部なのかそうでないのか判明するまで複数のポインタを
持てるようになる。（「lex&yacc プログラミング」p.301)

ただ、このあたりは、上のように文法を書き直すだけじゃなくて、もうちょっと整理しないとだめっぽい。

qconid, qtycls などもいっぱい衝突している。(軒並 qconid に還元しようとしたり)

まいったな、まだまだだな。