参考になるMenhir製パーサ その１（チュートリアル・サンプル編）
最近またぼちぼちMenhirでパーサを書いている。
けっこう仕様が大きめの自作言語用で、とりあえず書いてみたら案の定というか、見事にメチャクチャになって討ち死にした。なので一旦そのパーサ制作から離れてMenhir（とLRパーサ全般）について勉強し直している。
まずはもちろん公式のリファレンスがいい：
ただ、この文書からは「ライブラリの機能」はわかっても「書き方の流儀」は伝わってこない。後者に関しては実際にMenhirで書かれたパーサのコードを漁っていくのが良さそう。
というわけで見つけた良さげなMenhir製パーサに関してメモっていく。
Real World OCaml
OCamlerだったら大抵は知っているだろう名著RWOの章のひとつがMenhirによるパーサ作成の解説。
字句解析と構文解析、そしてそのツールであるocamllexとmenhirの説明から入って、最終的にJSONパーサを作成する。
コードの書き方はこんな感じ：
value:
| LEFT_BRACE; obj = object_fields; RIGHT_BRACE
{ `Assoc obj }
| LEFT_BRACK; vl = array_values; RIGHT_BRACK
{ `List vl }
| s = STRING
{ `String s }
セミコロンで各部分を区切ったり、s = STRING { \String s }`と必ず変数を用意するというやり方で、自分のMenhirコードの書き方は完全にこのスタイルを踏襲していることに気づいた。悪くいえば少し冗長なスタイル。
Cambium公式ブログ
Menhirプロジェクトは（多くのOCaml関連プロジェクトと同じように）フランスのINRIAで開発されている。そのINRIA内でMenhir関連の開発が行われていたGallium、そしてその後継チームであるCambiumの公式ブログに、Menhirパーサ作成の紹介記事がある：
題材は非常に簡単な四則演算の計算機なのだが、トークンの位置情報を上手にASTに組み込むやり方やMenhir特有の機能であるParametrized DefinitionやPoint-free構文などを紹介していて面白い。
let multiplicative_expr :=
| atomic_expr
| located(
~ = multiplicative_expr; ~ = multiplicative_op; ~ = atomic_expr; <EBinOp>
)
下の方で~ = ...; ... <...>という形になっているのがpoint-free構文。
Inline化やParametrized DefinitionなどのMenhir小技についても解説付きで紹介されているのが嬉しい。ここら辺が使えるかどうかはかなり重要（例えばうまくInline化するとShift/Reduce Conflictを解決できたりする）。
Programming Languages Zoo
OCaml製のトイ言語を集めたProgramming Languages Zooというサイトがある：
トイ言語とはいっても関数型やOO、静的・動的型、型チェックや型推論、などさまざまな言語機能のミニマルな実装が集まっているのでパーサ関連以外でも勉強になる。
パーサは基本的にMenhirを使っているようだ：
MiniML> let fact = fun f (n : int) : int is if n = 0 then 1 else n * f (n-1) ;; fact : int -> int = <fun> MiniML> fact 10 ;; - : int = 3628800
こんな感じの言語のパーサが100行ちょっとで読めるので面白い。ただし言語機能が切り詰められている分、実際の自作言語のパーサを書くのに参考にする場合このサンプルだけでは物足りないところはあった。例えば関数が単一引数しか取らなかったり。
MinCaml
これまた日本のOCamlerの間では非常に有名な、OCamlの限定的な機能を持つ言語のコンパイラを作成する教材MinCaml：
こちらもパーサはMenhir製。言語機能はOCamlのサブセットとはいえ、PL Zooのトイ言語よりはかなり複雑になっているのでパーサも読み応えがある（が空行なども含めて200行以内）。
コンパイラの各ステップに関しての解説がしっかりとしているのと、コード自体にもコメントが入っているのもありがたい。
より本格的なパーサ
ここまでの例を追っていれば、「ある言語機能が気になるから実装してみよう」というような動機での自作言語の構文ならMenhirでパースできるように思う。ただ、どちらかというと素直な構文ばかりなので、「実在の言語の構文」だとか「少し捻った構文」などのパースをするにはまだ足りない印象。
次回は実用的な言語のMenhir製パーサについてついて見ていく。
