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 に次のように書く：

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を使ってみた