ANTLR(4) - ASTの分析

ANTLR

ANTLR(3)で作ったASTを分析。

ANTLRが便利だということは分かったけど、(3)くらいから黒魔術気分。

下準備

  1. ExprAst.g をコンパイルして ExprAst.tokens を作る
  2. ExprAst.tokens をこれから作る .g ファイルと同じフォルダに

文法

tree grammar ExprTraverse;

options {
	tokenVocab = ExprAst;
	ASTLabelType = CommonTree;
}

@header {
package introduction;
}

expr returns [double result]
	: ^('+' left=expr right=expr) { $result = left + right; }
	| ^('-' left=expr right=expr) { $result = left - right; }
	| ^('*' left=expr right=expr) { $result = left * right; }
	| ^('/' left=expr right=expr) { $result = left / right; }
	| ^(NEGATE operand=expr) { $result = - operand; }
	| NUMBER { $result = Double.parseDouble($NUMBER.text); }
	;
  • 「grammar」ではなく「tree grammar」
  • options で tokenVocab = ExprAst; とすることで、ExprAst.tokens をインポートしてくれる
  • @lexer::headerは書けない。lexer使ってないしね。
  • ルールは { } の形式で書く
    • ^(...) でツリーとマッチングできるみたい。
    • 単項マイナスにNEGATEとつけたのがここで効いてきた。所詮LL(*)なので ^('-' expr) のままだと中置マイナスの ^('-' expr expr) と衝突する。

ともあれ、文法とツリーの処理を分離できる模様。これはいい。

確認コード

public class ExprTraverseTest {
  public static void main(String[] args)
      throws IOException, RecognitionException {
    ANTLRInputStream in =
        new ANTLRInputStream(System.in, "UTF-8");
    Lexer lexer = new ExprAstLexer(in);
    CommonTokenStream tokens =
        new CommonTokenStream(lexer);
    ExprAstParser parser = new ExprAstParser(tokens);
    CommonTree root = parser.start().tree;
    
    CommonTreeNodeStream ast =
        new CommonTreeNodeStream(root);
    ExprTraverse traverser = new ExprTraverse(ast);
    
    System.out.println("tree: " + root.toStringTree());
    System.out.println("eval: " + traverser.expr());
  }
}
  • CommonTreeを作った後にCommonTreeNodeStreamをかぶせる
  • tree grammarから生成されたプログラムをかぶせる
  • ルール名(#expr())で実行
    • returns [double ...]だったのでdouble型の値が返ってくる

実行結果

> echo 1 + 2 * 3;
| java -cp bin;lib\antlr-runtime-3.0.1.jar introduction.ExprTraverseTest
tree: (+ 1 (* 2 3))
eval: 7.0

> echo (1 + 2) * 3;
| java -cp bin;lib\antlr-runtime-3.0.1.jar introduction.ExprTraverseTest
tree: (* (+ 1 2) 3)
eval: 9.0