Javaでパーサジェネレータ

Javaで簡単な文法の独自言語を実装したかったので、構文解析器を生成してくれるパーサジェネレータ、つまりyaccのようなものがないか調べた記録。別に誰向けの記事ということはなく、単なるメモ。ぐぐってみたところ、

の３つが見つかった。最初、JavaCC を触ってみたのだが、どうも yacc っぽい定義方法ではなかったので辞めて、BYACC/J が YACC-compatible だと謳っていたのでそちらを使ってみることにした。コードが sourceforge においてあるので古いアプリケーションっぽくて不安があり後回しにしていたのだが、なんと驚くべきことに動くようです。

典型的な四則演算をするサンプルがホームページに書いてあって、以下のようなものだった

%{
import java.lang.Math;
import java.io.*;
import java.util.StringTokenizer;
%}

/* YACC Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG /* negation--unary minus */
%right '^' /* exponentiation */

/* Grammar follows */
%%
input: /* empty string */
 | input line
 ;

line: '\n'
 | exp '\n' { System.out.println(" " + $1.dval + " "); }
 ;

exp: NUM { $$ = $1; }
 | exp '+' exp { $$ = new ParserVal($1.dval + $3.dval); }
 | exp '-' exp { $$ = new ParserVal($1.dval - $3.dval); }
 | exp '*' exp { $$ = new ParserVal($1.dval * $3.dval); }
 | exp '/' exp { $$ = new ParserVal($1.dval / $3.dval); }
 | '-' exp %prec NEG { $$ = new ParserVal(-$2.dval); }
 | exp '^' exp { $$ = new ParserVal(Math.pow($1.dval, $3.dval)); }
 | '(' exp ')' { $$ = $2; }
 ;
%%

String ins;
StringTokenizer st;

void yyerror(String s)
{
    System.out.println("par:"+s);
}

boolean newline;
int yylex()
{
    String s;
    int tok;
    Double d;
    if (!st.hasMoreTokens()) {
        if (!newline) {
            newline=true;
            return '\n'; //So we look like classic YACC example
        } else {
            return 0;
        }
    }
    s = st.nextToken();
    System.out.println("tok:"+s);
    try {
        d = Double.valueOf(s);/*this may fail*/
        yylval = new ParserVal(d.doubleValue());
        tok = NUM;
    } catch (Exception e) {
        tok = s.charAt(0);/*if not float, return char*/
    }
    return tok;
}

void dotest()
{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    System.out.println("BYACC/J Calculator Demo");
    while (true) {
        System.out.print("expression:");
        try {
            ins = in.readLine();
        } catch (Exception e) {
        }
        st = new StringTokenizer(ins);
        newline=false;
        yyparse();
    }
}

public static void main(String args[])
{
    Parser par = new Parser(false);
    par.dotest();
}

使い方

このコードを

yacc -J calc.y

として喰わせると、Parser.java と ParserVal.javaが生成されるので、javac でコンパイルすれば良い。

javac Parser.java ParserVal.java

サンプルコードには main コードも書いてあって、java コマンドで実行すると標準入力を受け付けて、四則演算を確認できた。

java Parser ParserVal
> 33 + 5
tok:33
tok:+
tok:5
38.0
> 33+5
par:syntax error
par:stack underflow. aborting...

スペースがないとダメなのは、yylex メソッドで StringTokenizer を使って字句解析を行っているため。

.y の構成

YACCにおけるC宣言部に #include などを書く代わりに Java らしく import を記述する(以降、Java宣言部)
Yacc宣言部に yacc と同様にトークンや優先順位の記述を書く
文法規則部に yacc と同様に BNF で文法を記述する
YACCにおける追加Cプログラム部に、 Java コードを記述する (以降、追加Javaプログラム部)

たしかにほとんど yacc と同じで compatible 感あった。

Yacc宣言部

/* YACC Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG /* negation--unary minus */
%right '^' /* exponentiation */

NUMというトークンを定義して、これによって文法規則部および、追加Javaプログラム部で NUM 定数を利用できるようになる。 %left で優先順位を記述していて、- と + は同列だが、* と / がそれより優先され、さらに NEG が優先されるようになる。

文法規則部

exp: NUM { $$ = $1; }
 | exp '+' exp { $$ = new ParserVal($1.dval + $3.dval); }
 | exp '-' exp { $$ = new ParserVal($1.dval - $3.dval); }
 | exp '*' exp { $$ = new ParserVal($1.dval * $3.dval); }
 | exp '/' exp { $$ = new ParserVal($1.dval / $3.dval); }
 | '-' exp %prec NEG { $$ = new ParserVal(-$2.dval); }
 | exp '^' exp { $$ = new ParserVal(Math.pow($1.dval, $3.dval)); }
 | '(' exp ')' { $$ = $2; }
 ;

BNF で文法が定義されていて、{} に Java コードを記述して、どのように処理するのかを記述する。ParserVal はParserVal.java に出力されているクラスで、$1 なども ParserVal クラスのインスタンスになるようだ。dval メソッドを呼ぶと double な value が返ってくるように ParserVal クラスは実装されていた。

追加Javaプログラム部

自動生成される Parser クラスは int yylex() メソッドを読んで、次のトークンを取得して、分岐処理を行う。返り値は１つのトークンを返す必要があって、33 のような２文字の数字の場合は、返り値としてはYacc宣言部で定義した NUM トークンを返して(実体は整数で、Parser.java に埋め込まれる)、33 という値自体は ParserVal インスタンスに直して、yylval に保存するように実装する。 yylval に値を保存すると、文法規則部で $1 や $3 のように$記号でアクセスできるようになる。

ylval = new ParserVal(d.doubleValue());
return NUM;

+ や - の場合は、１文字なのでそれそのものをトークンとして扱うことができて、String#charAt でASCIIコードを返せば良い。

return s.charAt(0)

字句解析は自前で実装してあって、java の StringTokenizer を利用している。そのため、トークンの区切りにスペースがないとちゃんと動かない。33 + 5 は動くが、33+5 は動かない。

    if (!st.hasMoreTokens())
      return 0;
    s = st.nextToken();

おわりに

字句解析をより難しいルールで行いたい場合は、自分で頑張ってもよいし、lex などの字句解析器を使ってみても良い。java の場合は JFlex というものがあるようだ。ただ、今回は触っていない。

サンプルでは、字句解析のあと構文解析と同時に「実行」していたが、実世界では、構文解析の段階では AST (Abstract Syntax Tree)の構築だけをしておき、あとでASTを実行する方式を取ることが多い。そうすれば再実行の際は、構文解析をスキップして、ASTの再実行だけでよくなる。

字句解析 (lexer) - token -> 構文解析 (parser) - AST -> 実行

AST の構築、および実行にはいわゆる Interpreter パターンでコードを書けばよいだろう。まさしくそのためのデザインパターンだし。

後記: JFlex やってみた => Javaで構文解析器ジェネレータ

追記

JFlex とはてブコメントで教えてもらったが、ANTLR というものが人気らしい。たしかに、サイトをみるととても良くメンテナンスされているように見える。IntelliJ プラグインまである。ただし、実行時に runtime が必要になり、その runtime が遅いという欠点があるとのこと。

ためしてみると Lexer.java というファイルも生成されたので、JFlex の役割も同時に担うのかもしれない。あとは、やはり yacc / flex とは書き方が違うので、ちょっと学習コストがありそうといったところかな。=> と思ったが Java だけでなく C, C++, Python, Ruby などでも ANTLR 文法(?)のツールがあるようなので、学んでも損にはならないのかもしれない。

sonots:blog