So-net無料ブログ作成

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

ちまちま作っていた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

nice!(0)  コメント(0)  トラックバック(0) 

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。