左再帰を含む構文解析むずい

やろうとしていること

Haskellのparsecを使ってSMLの構文を解析し構文木を生成する。

SMLの構文解析はいろいろステップがある。

リテラルや識別子はなんとか倒して、いま型注釈の解析に取り組んでいるところ。

この型注釈の構文解析で例の問題に突き当たった。

左再帰問題だ。

SMLの型注釈の構文はこんな感じ。

ty ::= tyvar
       { <tyrow> }
       tyseq longtycon
       ty -> ty'
       ( ty )

tyrow ::= lab : ty <, tyrow>

上記の中でもいま苦戦しているのが、

tyseq longtycon

というところ。

tyseq

とは0回以上tyにマッチするtype constructorへの引数を表す。最後にtype constructorにマッチさせる。

0回以上tyにマッチするかどうか検査するためには、再帰的にtyを呼び出すが、これが無限再帰を起こす。つまり構文木の左側をぐんぐん掘り進めていってしまう。

これは素朴な数値演算式でも起きうる問題だ。

expr ::= expr + expr

などでも再帰的に解析が走るためparserが停止しないというよく知られた問題。

今回のケースではlongtyconがoperatorとなりtyseqがoperandとなるためポーランド記法のようなものと捉えることができる。

幸いにしてText.Parsec.Exprにはこのようにoperatorがpostfixとして出現するケースを式として解析する技がある。しかしこのlongtyconは解析の過程で動的に発見される。果たして素直に使うことができるのだろうか。。。

市井の例を見るとpredefinedな算術演算子のみを扱っているケースが多くてあまり参考にならない。

parsecでこのままくのか。

それとも、Alex + Happyでparser generateするのか。

このあたりがわからなくなってきている。

IdrisやElmはparser combinatorをある程度自前で実装して構文解析しているのを見ると、やはりparsecでも左再帰を解決しつつ解析できそうな気がするのだけれど。

If our language required a lot of left-recursive parsing, Alex & Happy would probably be a better choice.

こんな記述があった。この記事ではschemeは比較的構文がシンプルなのでparsecでいくよ、と言っていた。

はて、僕が解析しようとしているSMLはどうだろう。とても左再帰が多い構文だ。

diehlさんも最初にparsec使っておいて結局Alex + Happy使っていたな。

いまはparsingの技術を掘り下げるよりも前に進むことを考えよう！

ということで、再びAlexでの字句解析をインクリメンタルに進めよう。