ML-Lexを使ってみた

Standard MLで言語処理系でも作ってみよう、ということでまずは初歩の電卓からやってみる。この記事では字句解析の部分を作る。

# 資料

ML-Lex/ML-Yaccに関連する資料

ML-Lexのマニュアル（1994年）：[A lexical analyzer generator for Standard ML. Version 1.6.0, October 1994](https://www.smlnj.org/doc/ML-Lex/manual.html)
ML-Yaccのマニュアル（2000年）：[ML-Yacc User's Manual Version 2.4](http://www.smlnj.org/doc/ML-Yacc/)
東北大の資料(2006年、PDF)：[ML-Yaccの使いかた](http://www.pllab.riec.tohoku.ac.jp/education/lectures/compiler/code/mlyaccKaisetsu.pdf)
κeen氏のブログ記事（2014年）：[mllexを使ってみる。あるいはlexユーザーに対するmllexの解説 | κeenのHappy Hacκing Blog](http://keens.github.io/blog/2014/12/10/mllexwoshi-tutemiru/)

古い資料は古いので、そのままではコード例が動かなかったりする。

# ML-Lexで字句解析器

電卓を作りたいので、以下のトークンを生成したい：

* 数値リテラル：数字の列。整数のみ。
* 演算子：四則演算（+, -, *, /）
* 左右カッコ

`calclex.lex` に次のように書く：

```sml: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のコマンドが利用できたが、インストール方法によってはコマンド名は異なるかもしれない。

```shell-session
$ 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ファイルができている。中身は

```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"` を与えたい。そのためには

```sml
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`, ...という風に返ってくる。

まとめると、

```sml

$ 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を使ってみた](https://qiita.com/mod_poppo/items/3ba0c07d652c4c566f2c#_reference-8048b9f42b95a22b8e9d)