Hash λ Bye

Haskell, Clojure, MLなどの話

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

やろうとしていること

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での字句解析をインクリメンタルに進めよう。