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

2017-07-03 / [haskell] [sml] [standardml] [parsec] [compiler]

やろうとしていること

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

やっていること

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

  1. リテラル (special constants)
  2. 識別子 (identifier)
  3. 型注釈 !!イマココ!!
  4. パターンマッチ
  5. 宣言
  6. モジュール構文

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

苦戦しているところ

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

再帰問題だ。

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でも左再帰を解決しつつ解析できそうな気がするのだけれど。

追記

Adam Wespiser Parsing

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使っていたな。

Write You a Haskell ( Stephen Diehl )

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

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