Antlr 文法

Antlr4の文法ファイルは拡張子g4。今回の例ではsrc/main/antlr/text/Calc.g4を作成する。

文法解析について

レクサーは入力シーケンスをトークンに分解する。電卓で言えば、1 + 2 * 3のような式を、"1"、"+"、"2"、"*"、"3"のように、数字や記号に分解すること。

パーサーは分解されたトークンを、構文規則に合わせて解析し、解析木(Concrete Syntax Tree)を作成する。先の例なら、

  +
 / \
1   *
   / \
  2   3

のような木としてあらわされる。パーサージェネレーターは構文規則の記述から、その規則に沿ったパーサーを作成するツール。レクサーにはlexやflex、パーサージェネレーターにはyaccやそのGNU実装のbisonが有名。 Antlrはレクサーとパーサー双方を生成できる。

参考
yaccとlexについてのサイトだが、とても詳しく説明されている。

G4ファイル

ソース全体はこちらから

grammar Calc;

文法の名前を定義する。今回はレクサー/パーサーを一つのファイルで記述してしまうが、parser grammar Hoge;のようにして個別に指定することも可能。

@header {
package test;
}

@headerの内部は、生成されるファイルの先頭にそのまま追加される。ここではJavaのパッケージを指定している。

@members {
{
    this.removeErrorListeners();
    this.addErrorListener(Slf4jErrorListener.getInstance());
}
}

@membersには生成されるクラスのメンバーを記述でき、パーサーの機能を拡張できる。

ここでは少しトリッキーなことを行っており、インスタンス初期化子を追加している。 Antlrのパーサー/レクサーはデフォルトでConsoleErrorListenerを使用しており、標準エラー出力にエラーの内容を出力してしまう。これは余りよろしくない動作なので、出力先を切り替えたい。そこでインスタンス作成時にデフォルトのリスナーを削除し、Slf4Jに出力するリスナーを追加する処理を加えたい。しかしAntlrにはコンストラクターを変更する機能を持っていない。そこで、インスタンス初期化子がコンストラクターの実行前に呼ばれることを利用し、この処理を実装している。

参考

WS
    : (' ' | '\t') -> skip
    ;

NUMBER
    : '-'? [0-9]+ ('.' [0-9])?
    ;

PLUS
    : '+'
    ;

// (...)

トークンを定義していく。

空白はAntlrの便利なskip機能で無視することが出来る。数字は正規表現で、演算子はそのまま+=*/を指定する。ここでは負の数字を、単項演算子を利用するのではなく、数字の一部として記述している。また、面倒くさいので整数と浮動小数を区別しない。

expression
    : '(' expression ')'
    | expression primaryOperator expression
    | expression operator expression
    | NUMBER
    ;

operator
    : PLUS
    | MINUS
    ;

続いて、文法ルールを記述していく。

これはトークンがどのような順番で現れるかを示している。 expression : (...);は、expressionという名前の要素が、どんなトークンから構成されるのかを定義する。例えば、1 + 2という式を考える。これをトークンに分解するとNUMBER PLUS NUMBERとなる。NUMBERはexpressionの要素、PLUSはoperatorなので、この式はexpression operator expressionにマッチする。従って、1 + 2はexpressionという文法の規則として正しいということになる。

この書き方は左再帰と呼ばれる形であり、あまり望ましい形ではない。しかしAntlrは善きに計らってくれるので気にしない。気になるなら<assoc=left> expression operator expressionという風に、明示的に結合方向を指定する。

参考

環境構築
 Javaでの実装

Idiotproof

Antlr 文法

文法解析について

G4ファイル