Left Recursionの悪夢再び

はじめに

Happyで生成したパーサのコンパイル遅すぎてもう限界だったのでparser combinatorに戻ってきた。

そしてまた現れたのだ、やつが。。。。

問題

やろうとしてることは以前と変わらない。

SML Definitionを読んで型の注釈を表す式 ty を解析しようとしているが、 左無限再帰が起きてしまって解析が終了しないというもの。

ty ::= tyvar (1) type variable such as 'a { tyrow i } (2) record type tyseq longtycon (3) type constructor with type arguments ty -\> ty (4) function type tyseq ::= ty (5) singleton (6) empty (ty1, ty2, ... tyn) (7) list of type

ここの (3) を解析する時にで遭遇するのがLeft Recursion(左再帰)問題。

ty という構文を解析する際に、(3)の type constructor のサブツリーを作ろうとする場合を考える。

この時、まずは tyseq を解析するステップに入る。tyseq のEBNFを見ると明らかなようにこれは問題がある。

• (5) の場合は更に ty に解析を開始するため左再帰が無限に下降する。
• (6) はmegaparsecの option を使えば表現できると思われる。
• (7) カンマ区切りの型のリストだが結局これも ty の解析に入るので無限再帰する。

となるため確実に無限再帰に陥る。

よくブログ記事見かけるアドバイス

Text.Megaparsec.Exprを使えと言われる。

このモジュールは二項演算子や単項演算子で左再帰が発生する場合でも上手く取り扱ってくれる。

これを活用できないかと考えた。

-- ↓引数となる式 tyseq longtycon-- ↑後置単項演算子

こんな感じで捉える。

と思ったがこれを率直に実装するのは難しいと解った。 なぜなら型が合わないから。

このtype constructorの構文をADTのコンストラクタで表現するならこうなる。

TTyCon [Ty] TyCon

TyCon が後置演算子そのものを格納し、[Ty] が先行する tyseq を格納する。

このコンストラクタの型は [Ty] -> TyCon -> Ty となる。

が前述のモジュールでは後置演算子になれるコンストラクタは Ty -> Ty である必要がある。

少なくとも手持ちのコンストラクタは [Ty] だがライブラリが期待するのは Ty なのでどうも合わない。

というところで今日は終了。

これから

いやー厳しい戦いだ。

あんまり基礎的なところが解っていないっぽいので異様に解決まで時間くうことが容易に想像できる。