ML-Lexを使ってみた
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を使ってみた
Author And Source
この問題について(ML-Lexを使ってみた), 我々は、より多くの情報をここで見つけました https://qiita.com/mod_poppo/items/aa3dedd334a9f3eb0764著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .