ML-Yaccを使ってみた

この記事は「[ML-Lexを使ってみた](https://qiita.com/mod_poppo/items/aa3dedd334a9f3eb0764)」の続きである。

# 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氏のブログ記事（2015年）：[mlyaccを使ってみてハマったところ | κeenのHappy Hacκing Blog](http://keens.github.io/blog/2015/01/31/mlyaccwotsukattemitehamattatokoro/)

# ML-Yaccでパーサー

文法の定義（ML-Yaccへの入力）は `.grm` というファイルに書く。

```sml:calcgrm.grm
%%

%pos int

%term NUM of int | PLUS | MINUS | TIMES | DIV | LPAREN | RPAREN | EOF
%nonterm EXP of int | START of int

%left PLUS MINUS
%left TIMES DIV

%name Calc

%eop EOF
%noshift EOF
%nodefault
%start START

%verbose

%%

START : EXP (EXP)

EXP : NUM (NUM)
    | EXP PLUS EXP (EXP1 + EXP2)
    | EXP MINUS EXP (EXP1 - EXP2)
    | EXP TIMES EXP (EXP1 * EXP2)
    | EXP DIV EXP (EXP1 div EXP2)
    | LPAREN EXP RPAREN (EXP)
```

例によって `.grm` ファイルは `%%` によって3つの部分に区切られ、それぞれ

* ユーザーの書くSMLコード
* ML-Yaccの宣言
* 文法定義

を書く。

今回使ったML-Yaccの宣言は

* `%pos` では、ソース位置を表す型を指定する。
* `%term` は終端記号（トークン）、`%nonterm` は非終端記号の一覧である。
* `%left` は演算子の結合を指定している。下に書いた方が強い結合になる。`%left` の他に `%right` と `%nonassoc` がある。
* `%name` はパーサーの名前をして指定する。
* `%eop` は end-of-parse symbols の略である。`EOF` を指定しておけば良い。
* `%noshift` はよくわからないが `EOF` を指定しておけば良いらしい。
* `%nodefault` もよくわからない。
* `%start` は開始記号を指定する。省略しても良い（その場合は文法定義）。
* `%verbose` を書くと `.grm.desc` というファイルに文法についてのあれこれが書き出される。文法に関しての警告も吐き出されるので、慣れないうちは指定しておいた方が良いだろう。

である。

文法定義は雰囲気でわかると思うが、カッコ内に規則適用時のコード（セマンティックアクション）を書く。コード中では、終端記号や非終端記号の値を、 `<名前><番号>` の形で参照できる（例：`EXP1`）。同じ名前の記号が1回しか出現しない場合は `<番号>` は省略できる。

今回はASTを構築するのではなく、セマンティックアクションの中で直接値を計算している。

# コンパイル

書いた `.grm` ファイルをML-Yaccで処理させる（例によってコマンド名は異なるかもしれない）

```sh
$ ml-yacc calcgrm.grm
```

すると、 `.grm.sig`, `.grm.sml`, それから `%verbose` を指定した場合は `.grm.desc` という3つのファイルが生成される。

```sml:calcgrm.grm.sig
signature Calc_TOKENS =
sig
type ('a,'b) token
type svalue
val EOF:  'a * 'a -> (svalue,'a) token
val RPAREN:  'a * 'a -> (svalue,'a) token
val LPAREN:  'a * 'a -> (svalue,'a) token
val DIV:  'a * 'a -> (svalue,'a) token
val TIMES:  'a * 'a -> (svalue,'a) token
val MINUS:  'a * 'a -> (svalue,'a) token
val PLUS:  'a * 'a -> (svalue,'a) token
val NUM: (int) *  'a * 'a -> (svalue,'a) token
end
signature Calc_LRVALS=
sig
structure Tokens : Calc_TOKENS
structure ParserData:PARSER_DATA
sharing type ParserData.Token.token = Tokens.token
sharing type ParserData.svalue = Tokens.svalue
end
```

```sml:calcgrm.grm.sml
functor CalcLrValsFun(structure Token : TOKEN) :
  sig
    structure ParserData : PARSER_DATA
    structure Tokens : Calc_TOKENS
  end
  = struct
      ...
    end
```

# 字句解析器の変更

前回の記事で作った字句解析器は単体で使えるようになっていたが、パーサーと組み合わせるには手直しが必要になる。

字句解析器とパーサーでトークンの型を共有できるようにするために、字句解析器をstructureではなくfunctorとする（`%header` 文）。トークンの型は自前で定義するのではなく、functorの引数で取るようにする。

```sml
(* -*- mode: sml-lex -*- *)

type pos = int
type svalue = Tokens.svalue
type ('a,'b) token = ('a,'b) Tokens.token
type lexresult = (svalue,pos) Tokens.token

fun error x = print x
fun eof () = Tokens.EOF (0,0)

%%
%header (functor CalcLexFun(structure Tokens: Calc_TOKENS));

digit = [0-9];
ws = [\ \t\n];

%%

{ws}+ => (lex());
"+" => (Tokens.PLUS (0,0));
"-" => (Tokens.MINUS (0,0));
"*" => (Tokens.TIMES (0,0));
"/" => (Tokens.DIV (0,0));
"(" => (Tokens.LPAREN (0,0));
")" => (Tokens.RPAREN (0,0));
{digit}+ => (Tokens.NUM (foldl (fn (a,r) => ord a - ord #"0" + 10 * r) 0 (explode yytext),0,0));
. => (error ("calc: ignoring bad character " ^ yytext); lex());
```

`Tokens.token` 型は型パラメーター `('a,'b)` を取るので渡してやる。

トークンの構築子 (`Tokens.EOF`, `Tokens.PLUS`, `Tokens.MINUS`, ...) は現在位置等の情報を受け取るようになっている（ここでは仮に `0,0` を与えているが、真面目にやるなら位置情報を計算して渡すべきである）。

これの `.lex` ファイルをML-Lexに処理させると、次のような `.lex.sml` ファイルが出来上がる：

```sml
functor CalcLexFun(structure Tokens: Calc_TOKENS) = 
  struct
    ...
  end
```

# 字句解析器とパーサーの結合

ML-Lexで生成されたものもfunctor, ML-Yaccで生成されたものもfunctorである。structureを得るには何かを組み合わせなくてはならない。というわけで、 `calcmain.sml` に次のように書く：

```sml:calcmain.sml
(* CalcLrValsFun は .grm.sml で定義されている *)
structure CalcLrVals = CalcLrValsFun(structure Token = LrParser.Token)

(* CalcLexFun は .lex.sml で定義されている *)
structure CalcLex = CalcLexFun(structure Tokens = CalcLrVals.Tokens)

structure CalcParser = Join(structure Lex = CalcLex
                            structure ParserData = CalcLrVals.ParserData
                            structure LrParser = LrParser)
```

`LrParser` と `Join` は今回生成されたコードには含まれていない。これらは `ML-Yacc` が提供するライブラリーに含まれている。

```sml:ml-yacc-lib
structure LrParser = ...
functor Join(structure Lex
             structure ParserData
             structure LrParser) = ...
```

`LrParser` や `Join` の定義が気になる、という方はML-Yaccのコードを読むと良いだろう。Webで読みたかったら [MLton の GitHub](https://github.com/MLton/mlton/blob/master/lib/mlyacc-lib/join.sml) で読めば良い。後述する `CalcParser.makeLexer` や `CalcParser.parse` 等の関数は `Join` で定義されているものが使われる。

## コンパイル

前回はコマンドを叩いてコンパイルしたが、今回は[Compilation Manager](https://www.smlnj.org/doc/CM/)を使ってみよう。`sources.cm` に次のように記述する：

```:sources.cm
Group is

$/basis.cm
$/ml-yacc-lib.cm
calclex.lex
calcgrm.grm
calcmain.sml
```

SML/NJの対話環境を起動し、 `CM.make "sources.cm";` を打ち込む：

```sml
$ sml
Standard ML of New Jersey v110.83 [built: Tue Jun 26 04:17:01 2018]
- CM.make "sources.cm";
[autoloading]
[library $smlnj/cm/cm.cm is stable]
[library $smlnj/internal/cm-sig-lib.cm is stable]
[library $/pgraph.cm is stable]
[library $smlnj/internal/srcpath-lib.cm is stable]
[library $SMLNJ-BASIS/basis.cm is stable]
[library $SMLNJ-BASIS/(basis.cm):basis-common.cm is stable]
[autoloading done]
[scanning sources.cm]
[library $/ml-yacc-lib.cm is stable]
[attempting to load plugin $/lex-ext.cm]
[library $/lex-ext.cm is stable]
[library $smlnj/cm/tools.cm is stable]
[library $smlnj/internal/cm-lib.cm is stable]
[plugin $/lex-ext.cm loaded successfully]
[attempting to load plugin $/mllex-tool.cm]
[library $/mllex-tool.cm is stable]
[plugin $/mllex-tool.cm loaded successfully]
[parsing (sources.cm):calclex.lex.sml]
[attempting to load plugin $/grm-ext.cm]
[library $/grm-ext.cm is stable]
[plugin $/grm-ext.cm loaded successfully]
[attempting to load plugin $/mlyacc-tool.cm]
[library $/mlyacc-tool.cm is stable]
[plugin $/mlyacc-tool.cm loaded successfully]
[parsing (sources.cm):calcgrm.grm.sig]
[parsing (sources.cm):calcgrm.grm.sml]
[parsing (sources.cm):calcmain.sml]
[library $SMLNJ-ML-YACC-LIB/ml-yacc-lib.cm is stable]
[compiling (sources.cm):calcgrm.grm.sig]
[code: 60, env: 439 bytes]
[compiling (sources.cm):calcgrm.grm.sml]
[code: 11445, data: 1001, env: 1124 bytes]
[compiling (sources.cm):calclex.lex.sml]
[code: 9678, data: 982, env: 1237 bytes]
[compiling (sources.cm):calcmain.sml]
[code: 4180, env: 3560 bytes]
[New bindings added.]
val it = true : bool
- 
```

古い文献だと `CM.make ();` でCompilation Managerを起動しているが、SML/NJ v110.20以降に同梱される「新しい」Compilation Managerでは `CM.make` の型が変わったようである（以前の `CM.make'` に相当？）。

## 字句解析器のテスト

前回同様、字句解析器を単体でテストしてみよう。

```sml
- 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 = TOKEN (T 0,(NUM fn,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 1,(VOID,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 0,(NUM fn,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 3,(VOID,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 0,(NUM fn,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 7,(VOID,0,0)) : CalcLex.Internal.result
- lexer ();
val it = TOKEN (T 7,(VOID,0,0)) : CalcLex.Internal.result
```

トークンの型が変わった影響で、pretty printの結果も変わっているが、なんとか動いているようである。

## パーサーのテスト

エラー表示用の関数 `print_error` をでっち上げる：

```sml
- fun print_error (s,p1,p2) = print s;
val print_error = fn : string * 'a * 'b -> unit
```

パーサーに食わせるレキサーは、 `CalcLex.makeLexer` ではなく `CalcParser.makeLexer` を使って構築する：

```sml
- val lexer = let val i = ref 0 in CalcParser.makeLexer(fn _ => if !i = 0 then (i := 1; "1 + 3 * 42") else "") end;
val lexer = -
  : (CalcParser.svalue,CalcParser.pos) ?.LrParser.Token.token 
      ?.LrParser.stream
```

今回作ったパーサーは `CalcParser.parse` として実行できる：

```sml
- CalcParser.parse(0,lexer,print_error,());
val it = (127,-)
  : CalcParser.result * 
    (CalcParser.svalue,CalcParser.pos) ?.LrParser.Token.token 
      ?.LrParser.stream
```

無事、 `1 + 3 * 42` が `127` として計算されたことがわかる。