LoginSignup
7
5

More than 5 years have passed since last update.

@mod_poppo

ML-Yaccを使ってみた

Posted at

この記事は「ML-Lexを使ってみた」の続きである。

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氏のブログ記事（2015年）：mlyaccを使ってみてハマったところ | κeenのHappy Hacκing Blog

ML-Yaccでパーサー

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

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で処理させる（例によってコマンド名は異なるかもしれない）

$ ml-yacc calcgrm.grm

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

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
calcgrm.grm.sml
functor CalcLrValsFun(structure Token : TOKEN) :
  sig
    structure ParserData : PARSER_DATA
    structure Tokens : Calc_TOKENS
  end
  = struct
      ...
    end

字句解析器の変更

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

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

(* -*- 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 ファイルが出来上がる：

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

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

ML-Lexで生成されたものもfunctor, ML-Yaccで生成されたものもfunctorである。structureを得るには何かを組み合わせなくてはならない。というわけで、 calcmain.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 が提供するライブラリーに含まれている。

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

LrParser や Join の定義が気になる、という方はML-Yaccのコードを読むと良いだろう。Webで読みたかったら MLton の GitHub で読めば良い。後述する CalcParser.makeLexer や CalcParser.parse 等の関数は Join で定義されているものが使われる。

コンパイル

前回はコマンドを叩いてコンパイルしたが、今回はCompilation Managerを使ってみよう。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
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' に相当？）。

字句解析器のテスト

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

- 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 をでっち上げる：

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

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

- 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 として実行できる：

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

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

7
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
5