サンプルでなんとなく理解するmllex - ::Eldesh a b = LEFT a

やむを得ず調べてしまったので動く状態のサンプルを書き留めておきます。(タイガー本で書いたヤツとか忘れたわー(ノ｀´)ノミ┻┻)

mllexとは

mllexはlexのSML版です。トークンに対応する正規表現を並べておくと、それをストリームから切り出すレキサ(字句解析器)を生成してくれます。

SML/NJに付属するものとしてmllexが作られ、それをMLtonがforkして取り込んだようです。いくつか機能が追加されてるみたいですね。
SML/NJにはml-ulexというレキサジェネレータも付いてきますが別物です。こちらの方が後発で高機能なようです(が私は使ったことありません)。
SML#ディストリビューションにもmllexからfork(?)したsmllex*1が含まれており、これで構文のレキサを作っています。READMEを見る感じではバグフィックスが1つ入っただけでmllexと同じもののようです。v1.2.0を自分でビルドしたなら(src/ml-lex/smllex)にあるはず。

サンプル

いきなりサンプルから。
以下の例はML-Yaccの使い方(東北大学の資料)に大体合わせたlambda.lexです。

(* lambda.lex *)
datatype lexresult (* 読み出すトークンの型 *)
	= VAR of string
	| NUM of IntInf.int
	| OPER of string
	| LPAREN | RPAREN
	| LBRACKET | RBRACKET
	| LAM | DOT
	| EOF

fun toString (VAR id)    = concat["VAR(", id, ")"]
  | toString (NUM num)   = concat["NUM(", IntInf.toString num, ")"]
  | toString (OPER oper) = concat["OPER(", oper, ")"]
  | toString LPAREN   = "LPAREN"
  | toString RPAREN   = "RPAREN"
  | toString LBRACKET = "LBRACKET"
  | toString RBRACKET = "RBRACKET"
  | toString LAM      = "LAM"
  | toString DOT      = "DOT"
  | toString EOF      = "<EOF>"

(* トークンを読み出した行番号 *)
val pos = ref 0
(* ストリーム終端で構成する値を指定。後処理もあれば書く。 *)
val eof = fn () => EOF

%%
%structure LambdaLex
alpha=[A-Za-z];
prime=['];
digit=[0-9];
operator=[-+/*];
ws=[\ \t];

%%
\n              => (pos := (!pos) + 1; lex());
{ws}+           => (lex());
"\\"            => (LAM);
"."             => (DOT);
-?{digit}+      => (NUM(valOf (LargeInt.fromString yytext)));
"("             => (LPAREN);
")"             => (RPAREN);
"["             => (LBRACKET);
"]"             => (RBRACKET);
{alpha}{prime}* => (VAR yytext);
{operator}      => (OPER yytext);

何となくわかりそうですか？これが読み出そうとしているのは、関数適用を[](ブラケット)で囲う必要のあるラムダ式を構成するトークンです。(字句解析では文法は気にしないのでデタラメ順序でも読み出せますけど)

1つ目の %% の前に必要な幾つかの値と型を定義します。重要なのは lexresult 型で、これは生成するレキサが読み出す値の型として使います(名前はなんでもいいです)。
二つ目の %% の後ろには

<正規表現> => <SMLコード>

という記法で、切り出したいトークンを構築するSMLコードを指定します。この式は lexreult型である必要があります。

真ん中のセクションで指定している %structure では生成するstructureの名前を決めることが出来ます(例ではLambdaLex)。指定しない場合はTokenという名前になります。
ここではどうでもいいんですが、yaccと連携するときには気にする必要が出てきます…。

使い方

smlsharpのreplで実行してみます。
上のファイル(lambda.lex)をsmllexに投げると lambda.lex.sml が生成されるので、それを使うだけです。

$ smllex lambda.lex (* lambda.lex.sml が作られる *)

$ smlsharp
$ use "lambda.lex.sml";
$ open LambdaLex;
# val lex = LambdaLex.makeLexer(fn _=>valOf(TextIO.inputLine TextIO.stdIn));
val lex = fn : unit -> LambdaLex.UserDeclarations.lexresult
(* 補助関数を定義 *)
# fun pp s=print(s^"\n");
# infixr 1 $ ; fun f $ a = f a;
# fun lexpp f = pp $ LambdaLex.UserDeclarations.toString $ f();
(* 使う *)
# lexpp lex;
(\x.y); (* <- 標準入力 *)
LPAREN
# lexpp lex;
LAM
# lexpp lex;
VAR(x)
# lexpp lex;
DOT
# lexpp lex;
VAR(y)      (* lexを()に適用するたびにトークンが出てくる *)
# lexpp lex;
RPAREN
# lexpp lex; (* 入力ストリームが終端に達すると例外を投げる *)
uncaught exception: LambdaLex.LexError
#

解説

ここで重要なのは makeLexer という関数だけです。

val LambdaLex.makeLexer
	: (int -> string) -> unit -> LambdaLex.UserDeclarations.lexresult

この関数には *与えられた文字数の文字列を読み出す* 関数を与えると、レキサが手に入ります。ただここで与えられる文字数はストリームへのヒントなだけで実際に何文字読んでもよさげです。
上の例では標準入力から一行読んでます。これね＞

# val lex = LambdaLex.makeLexer(fn _=>valOf(TextIO.inputLine TextIO.stdIn));

で、得られたレキサ(()->lexresult)を () に適用するとそのたびにトークンが読み出されます。終わり。

おまけ

smllexはsmiファイルを吐いてくれないので、自分で定義しないとlexで生成した結果を他からコンパイルして使えません。
以下にsmiファイルを挙げます。

(* lambda.lex.smi *)
_require "basis.smi"
_require "ml-yacc-lib.smi"

structure LambdaLex =
struct
  structure UserDeclarations =
  struct
    datatype lexresult = DOT
                       | EOF
                       | LAM
                       | LBRACKET
                       | LPAREN
                       | NUM of intInf
                       | OPER of string
                       | RBRACKET
                       | RPAREN
                       | VAR of string
    val toString : lexresult -> string
  end
  exception LexError
  val makeLexer : (int -> string) -> unit -> UserDeclarations.lexresult
end

(あぁ、なんて短いんだろう…)

*1:名前が紛らわしすぎる…