参考になるMenhir製パーサ その２（500行未満編）
前回に続いて、今回は少し大きめの「教材ではない」パーサの例を挙げる。
GraphQL
GraphQLのクエリをパースするコード。OCamlでGraphQLサーバを作るライブラリの一部。クエリ言語であって本格的なプログラミング言語ではないので、ある程度簡単（SLOCにして200行弱）に収まっている。
*や+でMenhirのstandard libraryのlistやnonempty_listを表現できるのはとても便利そう。
ウェブアセンブリ
Andreas RossbergによるWASMのリファレンス実装（既に古くなっているが・・・）。WASMはS式なので、パーサ自体は簡単で200行弱に収まる。
ヘルパ関数をいろいろ定義しているのが特徴だろうか。トークンの位置情報をうまく扱うのに便利。
Lucid
プリンストン大学の公式Github Orgに載っているLucid言語のパーサ。（VHDLのようなハードウェア記述言語のようだ）
パーサのコードは$nの記法と、{ ... }の部分のはじまる列を揃えたスタイルで読みやすい印象。（graphqlやwasmも同じく$n記法で通していた）
ただし
{ inty_sp (fst $3) (snd $3) (Some $5) true (Span.extend $1 $5.tspan) }
のように飛び飛びでいくつか$nが出てきて、さらにそれがfstやsndで分解されているとちょっとわかりにくい気もする。
あと{ ... }の部分のはじまる列がところどころでズレているのを見ると、これを手作業でやるのは非常にめんどくさそう。Menhirの.mlyファイルのオートフォーマッタがあると便利かもしれない・・・
1ML
WASMと同じAndreas Rossbergの1ML。こちらはSMLやOCamlの式とモジュールが（構文・値などの面で）言語レベルで分かれているのを、統一した言語として定義し直したRossbergの有名な論文のリファレンス実装。WASMと同じヘルパ関数が定義されている。Menhirコードにも癖が出るんだな・・・
個人的には自作言語はMLベースを考えているので、言語機能的にも非常に参考になる。
Morbig
POSIX shellの実験的パーサであるMorbig。こちらの論文にいろいろと詳細が載っている。
The POSIX shell language defies conventional wisdom of compiler construction on several levels ... Token recognition cannot be specified by regular expres- sions, lexical analysis depends on the parsing context and the evaluation context, and the shell grammar given in the specification is ambiguous. ... This makes the standard usage of Lex and Yacc as a pipeline inadequate for the implementation of a parser for POSIX shell.
... we have resolved these difficulties using advanced parsing techniques (namely speculative parsing, parser state introspection, context-dependent lexical analysis and longest-prefix parsing) while keeping the implementation at a sufficiently high level of abstraction so that experts can check that the POSIX standard is respected.
ということなので、Menhirパーサとしてはかなり複雑なテクニックを使っているようだ。作者の一人Yann Régis-GianasはMenhir Reference Manualの共著者。
このパーサはもっと時間をかけて読み込んでいきたい。
追記： 上記の論文に関しては、特にこの部分が面白かった：
Actually, a far simpler answer can be implemented most of the time: the lexer can simply perform some speculative parsing to observationally deduce information about the parsing state. In other words, to determine if a token is compatible with the current parsing state, the lexer just executes the parser with the considered token to check whether it produces a syntax error, or not. If a syntax error is raised, the lexer backtracks to the parsing state that was just before the speculative parsing execution.
If the parsing engine of Menhir were imperative, then the backtracking process required to implement speculative parsing would necessitate some machinery to undo parsing side-effects. Since the parsing engine of Menhir is purely functional we do not need such a machinery: the state of the parser is an explicit immutable value passed to the parsing engine which returns in exchange a fresh new parsing state without modifying the input state.
Incremental APIを使えば簡単にバックトラックが実装できる、という話。（ただしこのバックトラックは「トークンの種類の解釈を複数試す」という部分に関して。PEG構文のパーサのような任意のバックトラックを含む構文を定義するのに使えるかはまだわからず）
Haxe
Haxeという静的型付きオブジェクト指向言語のプロトタイプパーサ。ActionScriptからの派生言語とのことで、構文はJavaScriptっぽいが、パターンマッチや台数的データ型も備えているらしい、ということでかなり大きめな言語のパーサである。いろいろと勉強になりそうで、しかもギリギリ500行未満というのはありがたい。
書き方の特徴としては単一の項目しかないルールを多用して、まとめる箇所では個別のルールの名前だけというスタイル。なかなか読みやすいかもと思う反面、明示的に名前付けせずにコメントで各productionを説明してもいいのでは？とも思うので、このスタイルを模倣するかは保留・・・。
これらのパーサの参考になる点
まだまだちゃんとコード読んで考えたいが、「$1などで変数を使わないスタイルで書くと構文のところがかなりスッキリする」「冒頭%{ ... %}で括ってあるところに便利なヘルパ関数を定義しておく」などは流し読みでも勉強になる。
次回
次は500行以上のパーサを見ていく。（OCamlそのものやReason ML、SATySFiなどのものも含む）
