Arantium Maestum

プログラミング、囲碁、読書の話題

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 nINDENTDEDENTBRといった新しいトークンに変換する
  • 変換済みのトークンをparserに渡す。parserの規則にはSPACEは出て来ず、INDENTDEDENTBRでマッチする

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以外ならそのトークンだけが入ったリストを返す

flattenlexbuf ->  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:

gist.github.com