Proglr: SML用のGLRパーサージェネレーター

ちまちま作っていたSML用のパーサージェネレーターが結構形になってきたので紹介します。

https://github.com/tkob/proglr

先日の記事ではML-BNFCという名前で、パーサーはLR(0)の状態だった。当初のもくろみとしては一度SLR(1)にした後でBermudez and Logothetisの方法なるものを使ってLALR(1)にするということを考えていたんだけど、面倒に思えてきたのと、そのわりに得られる結果がLALR(1)で独自性がない気がしたので結局GLRにした。 そうするとこのパーサージェネレーターの独自性はどちらかというとGLRになるのでML-BNFCという名前もやめてML-GLRという名前にした。[追記参照] いまでは文法定義ファイルからSMLソースを生成するようになっていて、文法定義ファイルの解析自体もML-GLR自身が生成したものになっている。

[追記]: ML-GLRっていう名前のパーサージェネレーターが既にあった！http://www.cis.uni-muenchen.de/~leiss/relationaleGrammatik-09-10/ml-glr.pdf

ということでさらに名称変更してProglrという名前にした。 [追記終わり]

ビルド

git clone --recursive https://github.com/tkob/proglr
cd proglr
make -f Makefile.mlton

パターンマッチに関する警告がたくさん出ますが無視してください。 proglrという実行ファイルができます。 なお、MLtonのほかに一応MLKitとPoly/MLでもビルドできるようになっています。[追記]SML#2.0.0でもコンパイルできるようになりました。

使用例

文法定義は次のように書く。BNFCにおおむね似ている。

token Add "+" ;
token Sub "-" ;
token Mul "*" ;
token Div "/" ;
token LParen "(" ;
token RParen ")" ;
token Integer of int;

EAdd. Exp ::= Exp "+" Exp1 ;
_.    Exp ::= Exp1 ;
ESub. Exp ::= Exp "-" Exp1 ;
EMul. Exp1 ::= Exp1 "*" Exp2 ;
EDiv. Exp1 ::= Exp1 "/" Exp2 ;
_.    Exp1 ::= Exp2 ;
EInt. Exp2 ::= Integer ;
_.    Exp2 ::= "(" Exp ")" ;

この文法定義からは次のようなAST型が生成される。

  structure Ast = struct
    datatype exp =
      EAdd of Lex.span * exp * exp
    | ESub of Lex.span * exp * exp
    | EMul of Lex.span * exp * exp
    | EDiv of Lex.span * exp * exp
    | EInt of Lex.span * int
  end

スキャナーの定義はml-ulexを使う。

%defs (
  open Token
  type lex_result = Token.token
  val eof = fn () => Token.EOF
);

%name Lexer;

%let digit = [0-9];
%let space = [ \t\r\n];

<INITIAL> "+" => (Add);
<INITIAL> "-" => (Sub);
<INITIAL> "*" => (Mul);
<INITIAL> "/" => (Div);
<INITIAL> "(" => (LParen);
<INITIAL> ")" => (RParen);
<INITIAL> {digit}+ => (Integer (Option.valOf (Int.fromString (yytext))));
<INITIAL> {space}+ => (continue ());

ドライバとなるプログラムは次のような感じで書く。

structure Parse = ParseFun(Lexer)

open Parse.Ast

fun calc (EAdd (_, e1, e2)) = (calc e1) + (calc e2)
  | calc (ESub (_, e1, e2)) = (calc e1) - (calc e2)
  | calc (EMul  (_, e1, e2)) = (calc e1) * (calc e2)
  | calc (EDiv  (_, e1, e2)) = Int.div (calc e1, calc e2)
  | calc (EInt (_, e)) = e

fun main () =
  let
    val strm = Lexer.streamifyInstream TextIO.stdIn
    val sourcemap = AntlrStreamPos.mkSourcemap ()
    val ast = Parse.parse sourcemap strm
    val result = calc (hd ast)
  in
    print (Int.toString result);
    print "\n"
  end

val _ = main ()

ビルドするときはランタイムとしてsmlnj-libとmllpt-libをリンクする。

(* calc.mlb *)
$(SML_LIB)/basis/basis.mlb
$(SML_LIB)/smlnj-lib/smlnj-lib.mlb
$(SML_LIB)/mllpt-lib/mllpt-lib.mlb

calc-parse.sml
scan.ulex.sml
calc.sml

スキャナーとパーサーを生成するためのMakefile

mlglr: calc-parse.sml scan.ulex.sml
        mlton -output calc calc.mlb

calc-parse.sml: calc.cf
        proglr < calc.cf > calc-parse.sml

scan.ulex.sml: scan.ulex
        ml-ulex scan.ulex

clean:
        rm -f calc calc-parse.sml scan.ulex.sml

実行例

$ ./calc
(1 - 2) + 3 * 4 + 5
16