こんにちは､びしょ〜じょです｡これはWORD Advent Calendar 2017の記事です｡
12月3日といえば冴草きいちゃんの誕生日!!!! みんなで祝いましょう｡ と思ったら『NEW GAME!』の遠山りんさんの誕生日でもあるのか!! この日はめでたいなぁ､国民の祝日にしましょう｡
WORDとは何か
1. はじめに
みなさんOCamlは書いてますか｡今年はほとんどOCamlとLaTeXしか書いてません｡ OCamlといえばメタランゲージとのことですので､メタランゲージでランゲージを作りたくなります｡ syntax.mlみたいなファイルにデータタイプを定義して､そのあとどうしますか｡ 全部手打ちでしょうか､それとも…
2. パーザージェネレーター
人類は偉い! 人類は偉いのでパーザー自体を書かずともいい雰囲気のものを書くとパーザーを作ってくれるパーザージェネレーターというものがあります｡ (中略)
3. Menhir
OCamlといえばocamlyaccを先に思いつきがちですが､Menhir1という便利なLR(1)パーザージェネレーターがあります｡ ocamlyaccよりも高機能で､menhirコマンドにも多くの便利オプションがあります｡
3-1. セッション
まずMenhirをインストールしてください｡OPAMやOSのパッケージマネージャーを使ってください｡
$ opam install menhir
# とか
$ yaourt -S ocaml-menhir # Archには公式リポジトリーに入ってない! 残念
以下のようなuntyped lambda calculus + listを考える｡
こんな感じだろうか｡
1 2 3 4 5
type term =
| Var of string
| Lamb of string * term
| App of term * term
| List of term list
今回はシンタックスだけ考えればいいから､もうええわ｡
パーザーにレキサーあり､という格言の通り､対応するレキサーを書きます｡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
{
open Parser
open Lexing
exception Error of string
}
let space = [' ' '\t' '\n' '\r']
let digit = ['0'-'9']
let alpha = ['a'-'z' 'A'-'Z']
let alnum = digit | alpha
rule token = parse
| '\\' { BACKSLASH }
| '.' { DOT }
| ',' { COMMA }
| '[' { LBRAC }
| ']' { RBRAC }
| '(' { LPAREN }
| ')' { RPAREN }
| xlower alnum* { VAR (lexeme lexbuf) }
| space+ { token lexbuf }
| eof { EOF }
| _ { raise (Error (Printf.sprintf "At offset %d: unexpected character.\n" (Lexing.lexeme_start lexbuf)))
}
Menhirもocamllexを呼んでる(と思う)んでここは共通やね｡
3-2. review ocamlyacc
リメンバーocamlyacc､ということじゃ｡
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
%{
open Syntax
%}
%token LBRAC RBRAC LPAREN RPAREN BACKSLASH DOT COMMA
%token <string> VAR
%token EOF
%start parse
%type <term> parse
%%
parse: | term EOF { $1 }
term: | lamb { $1 }
| VAR { Var $1 }
| lst { $1 }
| app { $1 }
| LPAREN term RPAREN { $2 }
lamb: | BACKSLASH VAR DOT term { Lamb($2, $4) }
app: | term term { App($1, $2) }
lstcont:
| { [] }
| term { [$1] }
| term COMMA lstcont { $1 :: $3 }
lst: | LBRAC lstcont RBRAC { List $2 }
[1]によるとocamlyaccと90%の互換性があるということで､ocamlyaccが受理できるmlyファイルはmenhirも受理します｡
$ ls
lexer.mll parser.mly syntax.ml
$ ocamlyacc parser.mly
8 shift/reduce conflicts.
$ menhir parse.mly
Warning: 2 states have shift/reduce conflicts.
Warning: 8 shift/reduce conflicts were arbitrarily resolved.
ええですな｡
3-3. dive to deep
3-3-1. naming token
{}の中でトークンを参照するときに$1とかやるの面倒くさい!
複雑になってくると何番目のトークンかをいちいち数えるのは面倒ですね｡
ここでトークンに名前を付けられるという素晴らしいアレがあります｡
lambルールをやっていっましょう｡
lamb: | BACKSLASH x = VAR DOT t = term { Lamb(x, t) }
オオ! これはわかりやすい｡
3-3-2. parameterized rule
非常に便利な関数がいくつか用意されている｡
lstcont､lstルールをもっと賢くエイヤッとやってみましょう｡
lst: | LBRAC lst = separated_list(COMMA, term) RBRAC { List(lst) }
オオッ､なんかインテリジェンスが高まっているな｡
separated_list(SEP, RULE)で(RULE SEP)* RULEみたいなものを発射してくれます｡
偉い｡
他にも偉い関数の数々
-
option(X)ルール
XにマッチすればSome(Xが返す値)を返し､なければNoneを返す -
list(X)X*みたいなやつ -
nonempty_list(X)X+ -
nonempty_separated_list(SEP, X)はい
3-3-3. user defined parameterized rule
separated_listみたいなものをユーザーも定義できる｡最高｡
%public xlist(X):
| LBRAC lst = separated_list(COMMA, X) RBRAC { lst }
何かを詰め込んだリストがホラこんな簡単に! 作れるわけだ｡
3-3-4. 他
%startと%typeを一緒にかける
%start <term> parse
で､こんな感じに
src/menhir_example/parser2.mly
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
%{
open Syntax
%}
%token LBRAC RBRAC LPAREN RPAREN BACKSLASH DOT COMMA
%token <string> VAR
%token EOF
%start parse
%type <term> parse
%%
parse: | term EOF { $1 }
term: | lamb { $1 }
| VAR { Var $1 }
| lst { $1 }
| app { $1 }
| LPAREN t = term RPAREN { t }
lamb: | BACKSLASH x = VAR DOT t = term { Lamb(x, t) }
app: | term term { App($1, $2) }
lst: | LBRAC lst = separated_list(COMMA, term) RBRAC { List lst }
この言語ではあまり味が出ないですね…!!!
3-3-5. 便利なオプション達
menhirはパーザーをジェネレートするだけでなく､デバッグ機能などもいい感じです｡ 詳細はヘルプなどを見ていただくとして､数点ピッカップします｡
interactive mode
$ menhir --interpret --interpret-show-cst --interpret-error parser2.mly
Warning: 2 states have shift/reduce conflicts.
Warning: 8 shift/reduce conflicts were arbitrarily resolved.
LPAREN BACKSLASH VAR DOT LBRAC VAR COMMA VAR RBRAC RPAREN LPAREN BACKSLASH VAR DOT VAR RPAREN
ACCEPT
[parse:
[term:
[app:
[term:
LPAREN
[term:
[lamb:
BACKSLASH
VAR
DOT
[term:
[lst:
LBRAC
[loption(separated_nonempty_list(COMMA,term)):
[separated_nonempty_list(COMMA,term):
[term: VAR]
COMMA
[separated_nonempty_list(COMMA,term): [term: VAR]]
]
]
RBRAC
]
]
]
]
RPAREN
]
[term:
LPAREN
[term: [lamb: BACKSLASH VAR DOT [term: VAR]]]
RPAREN
]
]
]
EOF
]
VAR VAR
ACCEPT
[parse: [term: [app: [term: VAR] [term: VAR]]] EOF]
INVALIDTOKEN
File "(stdin)", line 3, characters 0-12:
Error: "INVALIDTOKEN" is not a known terminal symbol.
すげぇ! 対話的にトークン列を渡すと解析木を出してくれる､偉い｡
graph
$ menhir --graph parser2.mly
$ dot -Tpng parser2.dot > parser2.png
ウオ〜縦長だがどういう感じなのかわかりますね! これは偉大
他にもいろんなオプションがあります｡menhir --helpしろ｡
4. おわりに
もう12月4日になっちゃったッピ〜〜!!!! というわけで解散してください｡
-
http://gallium.inria.fr/~fpottier/menhir/ ↩