こんにちは、びしょ〜じょです。これはWORD Advent Calendar 2017の記事です。

12月3日といえば冴草きいちゃんの誕生日!!!! みんなで祝いましょう。 と思ったら『NEW GAME!』の遠山りんさんの誕生日でもあるのか!! この日はめでたいなぁ、国民の祝日にしましょう。

WORDとは何か

!!!以下に詳細が!!!

https://www.word-ac.net/about/

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を考える。

$$ \begin{array}{rcl} S & \leftarrow & Term\\ Term & \leftarrow & Lamb\ /\ Var\ /\ List\ /\ App\\ Lamb & \leftarrow & “\backslash”\ Var\ “.”\ Term\\ Var & \leftarrow & \left[a\text{-}zA\text{-}Z\right]\left[a\text{-}zA\text{-}Z0\text{-}9\right]*\\ List & \leftarrow & “\left[” \left(\left(Term\ “,”\right)*\ Term\right)? “\right]”\\ App & \leftarrow & Term\ Term \end{array} $$

こんな感じだろうか。

src/menhir_example/syntax.ml

1
2
3
4
5
syntax.ml
type term =
  | Var of string
  | Lamb of string * term
  | App of term * term
  | List of term list

今回はシンタックスだけ考えればいいから、もうええわ。

パーザーにレキサーあり、という格言の通り、対応するレキサーを書きます。

src/menhir_example/lexer.mll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
lexer.mll
{
    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、ということじゃ。

src/menhir_example/parser.mly

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
parser1.mly
%{
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

非常に便利な関数がいくつか用意されている。 lstcontlstルールをもっと賢くエイヤッとやってみましょう。

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
parser2.mly
%{
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.png

ウオ〜縦長だがどういう感じなのかわかりますね! これは偉大


他にもいろんなオプションがあります。menhir --helpしろ。

4. おわりに

もう12月4日になっちゃったッピ〜〜!!!! というわけで解散してください。