Standard MLで言語処理系でも作ってみよう、ということでまずは初歩の電卓からやってみる。この記事では字句解析の部分を作る。
資料
ML-Lex/ML-Yaccに関連する資料
ML-Lexのマニュアル（1994年）：A lexical analyzer generator for Standard ML. Version 1.6.0, October 1994
ML-Yaccのマニュアル（2000年）：ML-Yacc User's Manual Version 2.4
東北大の資料(2006年、PDF)：ML-Yaccの使いかた
κeen氏のブログ記事（2014年）：mllexを使ってみる。あるいはlexユーザーに対するmllexの解説 | κeenのHappy Hacκing Blog
古い資料は古いので、そのままではコード例が動かなかったりする。
ML-Lexで字句解析器
電卓を作りたいので、以下のトークンを生成したい：
- 数値リテラル：数字の列。整数のみ。
- 演算子：四則演算（+, -, *, /）
- 左右カッコ
calclex.lex に次のように書く：
(* -*- mode: sml-lex -*- *)
datatype lexresult = NUM of int | PLUS | MINUS | TIMES | DIV | LPAREN | RPAREN | EOF
fun error x = print x
fun eof () = EOF
%%
%structure CalcLex
digit = [0-9];
ws = [\ \t\n];
%%
{ws}+ => (lex());
"+" => (PLUS);
"-" => (MINUS);
"*" => (TIMES);
"/" => (DIV);
"(" => (LPAREN);
")" => (RPAREN);
{digit}+ => (NUM (foldl (fn (a,r) => ord a - ord #"0" + 10 * r) 0 (explode yytext)));
. => (error ("calc: ignoring bad character " ^ yytext); lex());
.lex ファイルは %% によって以下の3つの部分に区切られる：
- ユーザーが書くSMLコード
- ML-Lexでの定義
- 字句解析の規則
SMLコードの部分では lexresult や eof という名前の型や関数を定義する必要がある。
規則の => の右辺では yytext という文字列型の変数が使える。空白やコメントを無視する場合は lex 関数を（再帰的に）呼び出す。
コンパイルと実行
筆者はMacPortsでSML/NJを入れたので ml-lex という名前でML-Lexのコマンドが利用できたが、インストール方法によってはコマンド名は異なるかもしれない。
$ ml-lex calclex.lex
Number of states = 14
Number of distinct rows = 4
Approx. memory size of trans. table = 516 bytes
ML-Lexを実行すると calclex.lex.sml というSMLファイルができている。中身は
structure CalcLex :
sig
structure UserDeclarations : <sig>
exception LexError
structure Internal : <sig>
val makeLexer : (int -> string) -> unit -> Internal.result
end
という感じである。CalcLex という名前は %structure コマンドで指定したものが使われている。
普通は字句解析器は構文解析器と組み合わせて使うが、今回は字句解析器を直接叩いてみよう。
CalcLex.makeLexer の仕様は、
- 第1引数
int -> stringに「呼び出しごとに入力文字列を一部返す関数（最後まで読み終わったら空文字列を返す）」を与えると、 - 「呼び出しごとにトークンを返す」
unit -> Internal.result型の関数が返ってくる-
Internal.result型は.lexで定義したlexresult型と同一である。 - 入力文字列の終端に達した場合は
eof関数が呼ばれる。
-
である。
普通は入力文字列をファイルから読み取るが、今回は文字列リテラル "1 + 3 * 42" を与えたい。そのためには
val lexer = let val i = ref 0 in
CalcLex.makeLexer(fn _ => if !i = 0 then (i := 1; "1 + 3 * 42") else "")
end;
とすれば良い。あとは lexer () を繰り返し実行することでトークンが NUM 1, PLUS, NUM 3, ...という風に返ってくる。
まとめると、
$ ml-lex calclex.lex
Number of states = 14
Number of distinct rows = 4
Approx. memory size of trans. table = 516 bytes
$ sml
Standard ML of New Jersey v110.83 [built: Tue Jun 26 04:17:01 2018]
- use "calclex.lex.sml";
[opening calclex.lex.sml]
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[library $SMLNJ-BASIS/(basis.cm):basis-common.cm is stable]
[autoloading done]
structure CalcLex :
sig
structure UserDeclarations : <sig>
exception LexError
structure Internal : <sig>
val makeLexer : (int -> string) -> unit -> Internal.result
end
val it = () : unit
- val lexer = let val i = ref 0 in CalcLex.makeLexer(fn _ => if !i = 0 then (i := 1; "1 + 3 * 42") else "") end;
val lexer = fn : unit -> CalcLex.Internal.result
- lexer ();
val it = NUM 1 : CalcLex.Internal.result
- lexer ();
val it = PLUS : CalcLex.Internal.result
- lexer ();
val it = NUM 3 : CalcLex.Internal.result
- lexer ();
val it = TIMES : CalcLex.Internal.result
- lexer ();
val it = NUM 42 : CalcLex.Internal.result
- lexer ();
val it = EOF : CalcLex.Internal.result
- lexer ();
val it = EOF : CalcLex.Internal.result
という風に字句解析器の動作を確認できる。
今回はML-Lexの出力はstructureだったが、ML-Yaccと組み合わせる場合にはfunctorを吐かせることになる。ML-Yaccと組み合わせる話は別の記事に書く。→書いた：ML-Yaccを使ってみた