Arantium Maestum

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

OCamlで言語処理系覚え書き ocamllex/menhirパーサをduneでビルドする

OCamlでocamllexとmenhirを使ったパーサを書き、duneでビルドする場合の構成を調べていて、ようやく少しわかってきたので備忘録的に書き留めておく。

例として整数のたし算をパースして評価する非常に簡単な計算プログラムを実装する。

ディレクトリ構成

.
├── dune-project
├── src
│   ├── ast.ml
│   ├── parser.mly
│   ├── lexer.mll
│   └── dune
└── bin
    ├── ex.ml
    └── dune

トップレベ

dune-projectが以下のように定義されている:

(lang dune 1.0)
(using menhir 1.0)

srcディレクトリ内

src/ast.mlでAST定義:

type expr =
  | Int of int
  | Plus of expr * expr

そのAST定義を使ってMenhir Parserをsrc/parser.mlyで定義:

%{
open Ast
%}

%token LPAREN
%token RPAREN
%token EOF
%token <int> INT
%token PLUS

%left PLUS

%start <Ast.expr> prog

%%

prog:
  | e = expr EOF { e }

expr:
  | LPAREN; e = expr; RPAREN { e }
  | i = INT { Int i }
  | e1 = expr; PLUS; e2 = expr { Plus (e1, e2) }

parserで定義されているtokenを出力するsrc/lexer.mll:

{
open Parser
}

let digit = ['0'-'9']
let number = '-'? digit digit*
let whitespace = ['\t' ' ' '\n']

rule tokenize = parse
  | whitespace+ { tokenize lexbuf }
  | "(" { LPAREN }
  | ")" { RPAREN }
  | "+" { PLUS }
  | number as n { INT (int_of_string n ) }
  | eof { EOF }

srcディレクトリにあるast.mlparser.mlylexer.mlladderというライブラリとしてビルドするためのsrc/duneファイル:

(menhir
  (modules parser))

(ocamllex lexer)

(library
  (name adder))

binディレクトリ内

adderライブラリを使うmain関数的なものが定義されているex.ml:

open Adder

let rec pprint = function
  | Ast.Int n -> string_of_int n
  | Ast.Plus (n, m) -> Printf.sprintf "(Plus %s %s)" (pprint n) (pprint m)

let rec eval = function
  | Ast.Int n -> n
  | Ast.Plus (n, m) -> eval n + eval m

let _ =
  let lexbuf = Lexing.from_channel stdin in
  let expr = Parser.prog Lexer.tokenize lexbuf in
  Printf.printf "%s = %d\n" (pprint expr) (eval expr)

bin/duneファイル:

(executable
  (name ex)
  (libraries adder))

実行

shellで:

> echo '1+2+(3+4)+5' | dune exec bin/ex.bc
(Add (Add (Add 1 2) (Add 3 4)) 5) = 15

参考資料

qiita.com

github.com