参考になるMenhir製パーサ その３（500行以上編）
前々回、前回に続いて500行以上の本格的なMenhirパーサの例。
C11パーサ
A simple, possibly correct LR parser for C11という論文のもとになった、Menhirを使ってなるべく正確な（過去のC11基準コンパイラがパースに失敗するプログラムもパースできる）C11パーサ。
著者の一人であるFrançois PottierはMenhirの開発者。
気になるテクニックで言えば、この行のような：
(https://github.com/jhjourdan/C11parser/blob/master/parser.mly#L90)
%token ELLIPSIS "..."
とトークンの定義の後に文字列のaliasが入っている。
それをこの行)で：
parameter_type_list:
| parameter_list option("," "..." {}) ctx = save_context
{ ctx }
と使っていてparameter_list option(COMMA ELLIPSIS {}) ctx = save_contextのようにトークンの名前ではなく、あたかも字句解析される文字列そのものが構文定義に書き出せる、というのが便利ポイント。
実際にこれが便利なのかどうかはまだ個人的に納得がいっていない。"..."とかならいいのだけど"_Alignas"だったらALIGNASトークンを書き出した方が良さそうなので一長一短？
Sesterl
gfngfnさんのErlang VMにコンパイルされるML言語Sesterlのパーサ：
スタイルで面白いなと思ったのは、セマンティックアクションが構文と同じ行に収まる場合は基本的に左揃えになっていて、複数行にまたがる場合はC言語ライクなbraceによるブロックの表現になっていること（構文の行の終端が{になっていて即改行、セマンティックアクションの後も改行が入ってその後閉じるための}が入る、というスタイル）。
Hack言語の実験的パーサ
Facebook（今はMetaか）のPHPに静的型付けを追加したHack言語のレポジトリにあるパーサ。何らかのProof of Conceptなんだと思うのだが、なんのために存在しているのかはいまいちわからない。
このパーサの特徴としては「パースが成功するとユニット型が返ってくる」というもの。ASTを作成するのではなく、単にパースが成功するかどうか（＝入力された文字列がHackの構文に合致しているか）をチェックするだけ。
構文にだけフォーカスして読めるので、これはこれで勉強になる。
SATySFi
gfngfnさんのMLベースの組版処理システムSATySFiのパーサ：
同じ作者だけあってSesterlとスタイルが似ている。全部で1300行のパーサコードでセマンティックアクション用のヘルパ関数が400行ほどあるというのも実際に使われるコードらしくて勉強になる（リファレンスパーサなどだと細かいエラー処理などがおざなりになるのでセマンティックアクションが簡単で済む印象）。
F*
マイクロソフトの依存型のあるプログラミング言語F*のパーサ：
F*はその名前からもわかるとおりF#がベースになっていて、元々はパーサもF#で書いてあったようだ。何故OCaml&Menhirで書き直したのか、もっと調べてみたいところではある。
SATySFiと違ってmlyファイル内で定義されているヘルパ関数は控えめ、そのかわり怒涛のOpenがある。
パーサの部分が綺麗に分離されているのでわかりやすい。一例としてPatterns and bindersの部分などは自作言語のパターンマッチのパーサを作るのに参考になりそう。
あとMenhirの特徴である「パーサ構文のライブラリ作成」のコードもしっかり読んでおきたい。再利用しやすい技が色々ありそうである。
OCaml
言わずと知れた、OCaml言語本体のパーサ。Menhirベースのパーサが実際に使われ出したのはOCaml 4.08.0以降。
いろいろ勉強になる点は多いと思うが、特に気になったのはこのテクニック：
| mkstr(
item_extension post_item_attributes
{ let docs = symbol_docs $sloc in
Pstr_extension ($1, add_docs_attrs docs $2) }
| floating_attribute
{ Pstr_attribute $1 }
)
mkstr(...)の中の部分が... {...} | ... { ... }のようなdisjunctive patternで記述できるというのは知らなかった。
Reason ML
OCamlのよりJS的な構文であるReason MLのパーサ：
これもFacebook発のプロジェクトだ。MetaはMLのMetaなんじゃないか？確かReactも元々はReasonのためのライブラリだったのをのちにJS用に書き直したものだったはず。
Reasonの方がOCamlよりも行数も多く、「Menhirの機能を限界まで使い倒している」という話も聞いた。
正直mlyファイルだけ見ているとそこまで難しさは伝わってこないが、以下のポストを見るとReasonで使われている機能の話が出ている：
MenhirのインクリメンタルAPI（トークンを一つずつパーサに与えていって中間のパーサ状態を返すAPI)を使ってバックトラックを実装（LR以上の構文をパース）したり、パースが失敗するところにセミコロンを挿入して再度パースを試みる、などの機能を実現している。
セミコロン挿入のロジックはmlyファイルではなくreason_single_parser.mlというファイルの中で実装されている。
ちなみにReasonの後継プロジェクト（厳密には違うが一言で関係を言い表すのが難しい）なReScriptは手書きの再帰下降法パーサを使っている。
終わりに
MenhirはOCaml界隈ではかなりデファクトスタンダードになっていて（パーサコンビネータのAngstromとかも有名だが）、小さいサンプルから大きい言語のプロダクションパーサまで参考になる例が豊富。使える機能も多岐に渡っていて、頑張ればLR構文を超えてバックトラックなどもできる。「MenhirがあるからOCamlで言語実装する」くらいの技術選択もあり得るくらいの強力なライブラリだと思う。もっと使いこなせるようになっていきたい。
