ocamllexのlexerとmenhirのparserの間に任意のOCamlコードによる変換を挿入する
OCamlでパーサを書く場合
- lexerをocamllexで書く
- そのlexerを受け取るparserをmenhirで書く
というのが最近の鉄板のようだ。
let lexbuf = Lexing.from_channel stdin in let exp = Parser.f Lexer.f lexbuf in print (eval exp)
というような流れ。
ocamllexもmenhirも構文が普通のOCamlではなく、いったん独自構文で書かれた.mll/.mlyファイルを両ツールでOCamlの.mlに変換してから普通のOCamlモジュールとして使う。
なので長らくぱっと見どうやってocamllex製のlexerが返すトークンに対して任意の変換を行ってからmenhir製のparserに渡せばいいのか、イメージが湧かなかった。
しかし実際にやってみたら拍子抜けするほど簡単。
パースしたい言語
たし算をネストしたインデントで表現するこんな言語を考えてみたい:
+ 1 2 + 3 4 5
これが(+ 1 2 (+ 3 4) 5)
のようにパースされてほしい。
インデントをパースするための方針としては
- lexerは改行後のスペースの数を数えて
SPACE n
というトークンを作成する - parserに渡す前にlexerのトークンを解析し、
SPACE n
をINDENT
、DEDENT
、BR
といった新しいトークンに変換する - 変換済みのトークンをparserに渡す。parserの規則には
SPACE
は出て来ず、INDENT
、DEDENT
、BR
でマッチする
lexer
ocamllexで定義するlexerはこんな感じ:
{ open Parser } let digit = ['0'-'9'] let num = (digit | ['1'-'9'] digit*) let indent = '\n' ' '* let whitespace = [' ' '\t'] rule f = parse | indent as s { SPACE (String.length s - 1) } | whitespace+ { f lexbuf } | num as n { INT (int_of_string n) } | "+" { ADD } | eof { EOF }
'\n' ' '*
という文字列がマッチされ、SPACE (String.length s - 1)
で(改行を除いた)空白の文字数を保持するSPACE
トークンが作成されている。
これをocamllexに通すとLexer
というモジュールが作成され、その中のf関数が目的のlexerである。
Lexer.f
の型は
val f : Lexing.lexbuf -> Parser.token
Lexing.lexbuf
というOCaml標準ライブラリ内のlexer用の文字列データ型を引数として、menhirに渡す予定のparser.mlyで定義されているtoken型を一つ返す。
ミュータブルなlexbufを受け取り、副作用的にlexbufから文字を必要なだけ「消費」して一つのtokenを返す、という仕様だ。
終端tokenが帰ってくるまで何回でも同じlexbufを引数にLexer.f
が呼ばれる想定となる。
parser
parser.mly
はこんな感じ:
%token <int> INT %token ADD %token EOF %token <int> SPACE %token INDENT %token DEDENT %token BR %start f <Exp.t> %% f : e = expr; EOF { e } expr : | n = INT; BR { Exp.Int n } | ADD; BR; INDENT; es = list(expr); DEDENT { Exp.Add es }
これもmenhirを通すとParser
というモジュールになり、その中のf関数がparserとなる。
型は:
val f : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> Exp.t
lexerとlexbufを受け取り、別モジュールで定義されているExp.t
型のASTを返す。
この関数の内部実装は確認していないが、前述の通りLexing.lexbuf -> token
型の第一引数を第二引数のlexbufに対して何回も(終端トークンがでてくるまで)適用しているようだ。
ならLexer.fをラップしたLexing.lexbuf -> token
型の関数を用意してやればいい。
indenter
それがIndenter.f
関数:
module P = Parser let convert_space_to_indent width f = let indent = ref 0 in let make_indent _ = [P.BR; P.INDENT] in let make_dedent _ = [P.BR; P.DEDENT] in let g h a b = List.init (a - b) h |> List.concat in fun lexbuf -> match f lexbuf with | P.SPACE n -> let m = n / width in let k = !indent in if m > k then (indent := m; g make_indent m k) else if m < k then (indent := m; g make_dedent k m) else [P.BR] | P.EOF -> let k = !indent in (indent := 0; g make_dedent k 0 @ [P.EOF]) | e -> [e] let flatten f = let xs = ref [] in fun lexbuf -> match !xs with | x::xs' -> xs := xs'; x | [] -> (match f lexbuf with | x::xs' -> xs := xs'; x | [] -> failwith "Lexer did not return EOF token") let f = Lexer.f |> convert_space_to_indent 2 |> flatten
convert_space_to_indent
関数はindent一つ分のスペース数の指定と、lexbuf -> token
な関数(この場合はLexer.fを想定している)を引数に取り、lexbuf -> token list
な関数を返す。
その返ってきた関数はlexbufを受け取り、Lexer.fに渡し、戻ってきたトークンが:
- SPACEなら現在のインデントレベル(クロージャにrefとして保持されている)と比較し、インデントレベルの変更があればクロージャを変更したのちINDENT, DEDENT, BRトークンを必要なだけ返す。インデントに変更がなければBRだけのリストを返す。
- EOFなら現在のインデントレベル分のDEDENTとEOFの入ったリストを返す
- SPACEかEOF以外ならそのトークンだけが入ったリストを返す
flatten
はlexbuf -> token list
な関数を引数に取り、lexbuf -> token
な関数を返す。
クロージャに保持しているlist refにいったんtoken listを格納して、そのlistが空じゃない場合はlexbufをまったく消費せずにそのlistからトークンを返す仕様になっている。
この二つをLexer.fと組み合わせてIndenter.f
を作っている。
ただ、見返してみると、この実装だとIndenterモジュールの中にmutable stateを持ち込んでいてあまりよろしくない。
let f n = Lexer.f |> convert_space_to_indent n |> flatten
として呼び出す側で(Indenter.f 2)
などと新しくクロージャを作成するようにしたほうがいい。
使い方
あとはまあ使うだけ:
let rec eval = function | Exp.Int n -> n | Exp.Add ns -> List.map eval ns |> List.fold_left (+) 0 let _ = Lexing.from_channel stdin |> Parser.f Indenter.f |> eval |> string_of_int |> print_endline
普通だったらParser.f Lexer.f
としてるところをParser.f Indenter.f
としている。
まとめ
基本的にmenhirで作ったパーサにはLexing.lexbuf -> token
型で呼び出すごとにtokenが返ってくるような関数を渡してやればいいだけなので、内部状態をクロージャとして持つ関数でocamllex製のlexerをラップしてしまえば任意のコードでトークンストリームを変換できることがわかった。
今回のgist: