ocamllexとocamlyaccで電卓をつくる (OCaml)

はじめに

ocamllexとocamlyaccというツールを使って電卓をつくります。作ろうと思ったのはTaPL本の第4章で出てくるプログラムを理解するのに良いかなと思ったからです。

型システム入門 −プログラミング言語と型の理論−

型システム入門 −プログラミング言語と型の理論−

  • 作者:Benjamin C. Pierce
  • 発売日: 2013/03/26
  • メディア: 単行本(ソフトカバー)

電卓をつくるために必要なこと

電卓をつくるにはまずは3 + 3などという文字列から3という数値と+という演算子を取り出す必要があります。そのような意味のある最小の文字列の単位を字句やトークンと呼びます。文字列からトークンの列に変換するプログラムを字句解析器といいます。

トークンの列に対しては「数値(INT)、演算子(PLUS)、数値(INT)」というようにまとまったトークンの列を定義します。これを構文と言います。トークンの列に構文を当てはめると木構造で表せます。これを構文木と呼びます。トークンの列が定義した構文になっているかを判定するのが構文解析器といいます。

これまでの流れを図にすると次のような感じです。

f:id:gkuga:20200330010735p:plain

ocamllexは字句解析器を生成するツールで、ocamlyaccは構文解析器を生成するツールです。ocamlyaccでは例えば、「数値3、演算子+、数値3」という構文ならば「3+3」を計算するというように意味の部分まで定義できます。なので構文と実行する処理をOCamlのコードで定義して電卓を作ります。

ocamllex

文字列からトークンを取り出すの字句解析器を生成するのがocamllexというツールです。トークンを取り出すために正規表現を使います。さらに正規表現でマッチした時に実行するアクションをOCamlのコードで書きます。

以下は正規表現とそれにマッチした時に実行するコードを定義したファイルです。今回はマッチした時にマッチした文字列をprint_stringを使い出力しています。ソースコードgkuga/ocaml-examplesにあります。

{
exception Eof
}
rule token = parse
    [' ' '\t']     { print_string (Lexing.lexeme lexbuf) }
  | ['\n' ]        { print_string "\\n" }
  | ['0'-'9']+ as lxm { print_string (Lexing.lexeme  lexbuf) }
  | '+'            { print_string (Lexing.lexeme lexbuf) }
  | '-'            { print_string (Lexing.lexeme lexbuf) }
  | '*'            { print_string (Lexing.lexeme lexbuf) }
  | '/'            { print_string (Lexing.lexeme lexbuf) }
  | '('            { print_string (Lexing.lexeme lexbuf) }
  | ')'            { print_string (Lexing.lexeme lexbuf) }
  | eof            { raise Eof }

詳細な説明を省くので詳しくはLexer and parser generatorsを見てください。

ruleではtokenというルールを定義して正規表現とマッチした時に実行するコードの組み合わせを並べて定義しています。これをlexer.mllというファイルに書き込んで、以下のようにするとlexer.mlというOCamlソースコードが生成されます。

ocamllex lexer.mll

中身は次のような感じでruleに指定したtokenという関数が定義されています。

...略
let rec token lexbuf =
   __ocaml_lex_token_rec lexbuf 0
and __ocaml_lex_token_rec lexbuf __ocaml_lex_state =
  match Lexing.engine __ocaml_lex_tables __ocaml_lex_state lexbuf with
      | 0 ->
# 5 "lexer.mll"
                   ( print_string (Lexing.lexeme lexbuf) )
# 108 "lexer.ml"
...略

token関数を使うmain.mlは次のような感じです。

let () =
  Printexc.print (fun () ->
      try
        let lexbuf = Lexing.from_channel stdin in
        while true do
          let () = Lexer.token lexbuf in
          print_newline ()
        done
      with
        Lexer.Eof -> exit 0
    ) ()

lexbuf = Lexing.from_channel stdinで標準入力から文字列を読み込んでバッファーに貯めるlexbufを用意します。そしてlet () = Lexer.token lexbufでtoken関数にlexbufを渡して実行しています。

Lexingは標準モジュールです。そのモジュールの中ではlexbufというデータ型やfrom_channelなどの関数が定義されています。

実行ファイルを生成するMakefilegkuga/ocaml-examplesに用意したのでmakeコンパイルします。

$ make
ocamllex lexer.mll
11 states, 267 transitions, table size 1134 bytes
ocamldep  *.mli *.ml > .depend
ocamlc   -c lexer.ml
File "lexer.mll", line 7, characters 18-21:
Warning 26: unused variable lxm.
ocamlc   -c main.ml
Linking main
ocamlc -o main   lexer.cmo main.cmo

実行して3 + 3を入力すると3にマッチしたら3と出力するなどlexer.mllで定義したとおりに実行されます。

$ ./main
3 + 3
3

+

3
\n

正規表現で定義していない文字列を入力すると例外を起こします。

$ ./main
abc
Uncaught exception: Failure("lexing: empty token")
Fatal error: exception Failure("lexing: empty token")

電卓用のlexer.mll

電卓のためには取り出したトークンを単純に出力するのではなくトークンとして評価します。以下のようにlexer.mllを書き換えます。

{
open Parser
exception Eof
}
rule token = parse
    [' ' '\t']     { token lexbuf }
  | ['\n' ]        { EOL }
  | ['0'-'9']+ as lxm { INT(int_of_string lxm) }
  | '+'            { PLUS }
  | '-'            { MINUS }
  | '*'            { TIMES }
  | '/'            { DIV }
  | '('            { LPAREN }
  | ')'            { RPAREN }
  | eof            { raise Eof }

スペースを見つけると、スキップしたり、ファイルの終わりを見つけると例外を発生させたりしています。EOLなどは次に説明するトークンを表すtokenヴァリアント型のコンストラクタです。これでトークンを取り出せるようになったので、取り出したトークンの列から構文を解析するプログラムをocamlyaccで生成します。

ocamlyacc

ocamlyaccは構文*1を定義したファイルからOCamlソースコードを生成します。生成されるプログラムは構文解析器と呼ぶのでした。

電卓用に定義した構文は以下で、今回はparser.mlyというファイルに記述しました。

%token <int> INT
%token PLUS MINUS TIMES DIV
%token LPAREN RPAREN
%token EOL
%left PLUS MINUS
%left TIMES DIV
%nonassoc UMINUS
%start main
%type <int> main
%%
main:
    expr EOL                { $1 }
;
expr:
    INT                     { $1 }
  | LPAREN expr RPAREN      { $2 }
  | expr PLUS expr          { $1 + $3 }
  | expr MINUS expr         { $1 - $3 }
  | expr TIMES expr         { $1 * $3 }
  | expr DIV expr           { $1 / $3 }
  | MINUS expr %prec UMINUS { - $2 }
;

以下を実行するとparser.mlとparser.mliが生成されます。

ocamlyacc parser.mly

ocamllexと同様に詳しくはLexer and parser generatorsを見てください。

%%より上がトークンの定義部分です。例えば%token <int> INTOCamlのint型を持つトークンとしてINTを定義しています。

%%より下は構文の定義です。字句解析をしたあと、文字列はトークンの列に変換されます。そのトークンの列が定義した構文にマッチすると{ }の部分が実行されます。

例えば、字句解析で['0'-'9']+という正規表現にマッチしたらINT(int_of_string lxm)を評価していました。INTはparser.mlで以下のようにtokeというヴァリアント型のコンストラクタとして定義されています。

type token =
  | INT of (int)
  | PLUS
  | MINUS
  | TIMES
  | DIV
  | LPAREN
  | RPAREN
  | EOL

parser.mlyではINTというトークンにマッチしたら$1を評価しています。$1正規表現の後方参照です。{ }の中身はOCamlコードなのでここで$1はINTを参照していて、それはtoken型のINTコンストラクタです。そしておそらくocamlyaccによりint型の値が取り出されてここに展開されるようになっていると思われます*2

%start mainmainを開始の記号として定義しています。そしてmainを%type <int> mainでint型に設定しています。startで指定した記号は関数が作られます。ocamlyaccで生成されたparser.mlでは以下のように定義されています。

...略
let main (lexfun : Lexing.lexbuf -> token) (lexbuf : Lexing.lexbuf) =
   (Parsing.yyparse yytables 1 lexfun lexbuf : int)

Lexing.lexbuf型を受け取ってtoken型を返す関数lexfunと、 Lexing.lexbuf型のlexbufを引数に持つmain関数を定義しています。main関数で束縛される式ではParsing.yyparse関数にyytables、1、lexfun、lexbufの引数を与えています。これを使ったmain.mlは以下のようになります。

let () =
  Printexc.print (fun () ->
      try
        let lexbuf = Lexing.from_channel stdin in
        while true do
          let result = Parser.main Lexer.token lexbuf in
          print_int result; print_newline()
        done
      with
        Lexer.Eof -> exit 0
    ) ()

電卓の実行

コンパイル用にMakefileを用意したのでmakeで実行ファイルを作ります。

$ make
ocamllex lexer.mll
11 states, 267 transitions, table size 1134 bytes
ocamlyacc -v parser.mly
ocamldep  *.mli *.ml > .depend
ocamlc   -c parser.mli
ocamlc   -c parser.ml
ocamlc   -c lexer.ml
ocamlc   -c main.ml
Linking main
ocamlc -o main   parser.cmo lexer.cmo main.cmo

実行すると以下のようになります。

$ ./main
3 + 3
6

構文木は以下のようになります。

f:id:gkuga:20200331165133p:plain

かっこや*もちゃんと動きます。

$ ./main
( 3 + 3 ) * 2
12

おわりに

OCamlまったくわからん状態からようやくTaPL本に出てくる最初のプログラムを読めるくらいになってきたかと思うので読み進めようと思います。

内定者バイトとして一緒に働きそのまま弊部署に来る新卒と話題がかぶる奇跡!(Lexer、Parserの図はパクりましたw)

nakabonne.dev

参考

OCamlに関して海外の大学の良さげな資料を見つけました。

*1:構文は文脈自由文法で定義されます。

*2:ocamlyaccが$をどう扱うかまで見れていません。