java - ANTLR:从 CommonTree 到有用的对象图

Question

我今天开始使用 ANTLR 并创建了一个基本的解析器。

解析后我得到了一棵树。对我来说，这似乎只是一堆 String 放在 Tree 节点的树结构中。这对我不是很有用。我想要一个对象图。

澄清一下(这是一个例子，而不是我的实际应用):对于 "5-1+6" 我似乎以:

new String("PLUS")
    new String("MINUS")
        new String("5")
        new String("1")
    new String("6")

我认为更有用的是:

new Plus(
    new Minus(
        new IntegerLiteral(5),
        new IntegerLiteral(1)),
    new IntegerLiteral(6))

从第一种表示到另一种表示最方便的方法是什么？在 this article作者做了类似的事情:

public Expression createExpr(CommonTree ast) {

    // ...

    switch (ast.getType()) {
    case SimpleExpressionParser.INT:
        return new IntegerLiteral(ast.getText())
    case SimpleExpressionParser.PLUS:
        return new Plus(createExpr((CommonTree)ast.getChild(0)),    // recurse
                        createExpr((CommonTree)ast.getChild(1)));   // recurse
    case SimpleExpressionParser.MINUS:
        return new Minus(createExpr((CommonTree)ast.getChild(0)),   // recurse
                         createExpr((CommonTree)ast.getChild(1)));  // recurse
    }

    // ...
}

这是首选方式吗？!我不能指示 ANTLR 以某种方式生成此样板代码(它会很大)吗？

---

可能相关的问题:

• Converting Antlr syntax tree into useful objects (但我看不出答案如何回答我的问题。)

Answer 1

这是一个可行的方法。简而言之，这些是您要执行的步骤:

1. 创建将生成词法分析器和解析器的组合语法；
2. 在 (1) 的语法中混合 AST 重写规则，将扁平的标记列表转换为合适的树；
3. 写一个树语法，可以从(2)中遍历树；
4. 在您的 tree walker 中混合自定义代码；
5. 测试它。

1

让我们创建一个支持+、-、*、/、( ...) 和数字，看起来像:

grammar Exp; // file: Exp.g

eval
  :  exp EOF
  ;

exp 
  :  addExp 
  ;

addExp
  :  mulExp ((Add | Sub) mulExp)*
  ;

mulExp
  :  unaryExp ((Mul | Div) unaryExp)*
  ;

unaryExp
  :  Sub atom
  |  atom
  ;

atom
  :  Number
  |  '(' exp ')'
  ;

Add    : '+';
Sub    : '-';
Mul    : '*';
Div    : '/';
Number : '0'..'9'+;
Space  : ' ' {skip();};

2

包括重写规则，它看起来像:

grammar Exp; // file: Exp.g

options {
  output=AST;
}

tokens {
  U_SUB;
}

eval 
  :  exp EOF -> exp
  ;

exp 
  :  addExp 
  ;

addExp
  :  mulExp ((Add | Sub)^ mulExp)*
  ;

mulExp
  :  unaryExp ((Mul | Div)^ unaryExp)*
  ;

unaryExp
  :  Sub atom -> ^(U_SUB atom)
  |  atom
  ;

atom
  :  Number
  |  '(' exp ')' -> exp
  ;

Add    : '+';
Sub    : '-';
Mul    : '*';
Div    : '/';
Number : '0'..'9'+;
Space  : ' ' {skip();};

现在像 10 - 2 * (3 + 8) 这样的表达式将被转换为:

3

要创建为 (2) 中生成的 AST 生成迭代器的树语法，您需要执行如下操作:

tree grammar ExpWalker; // file: ExpWalker.g

options {
  tokenVocab=Exp; // use the tokens from Exp.g
  ASTLabelType=CommonTree;
}

eval
  :  exp
  ;

exp
  :  ^(Add exp exp)
  |  ^(Sub exp exp)
  |  ^(Mul exp exp)
  |  ^(Div exp exp)
  |  ^(U_SUB exp)
  |  Number
  ;

4

要在这个树迭代器中混合您的自定义类，请执行如下操作:

tree grammar ExpWalker; // file: ExpWalker.g

options {
  tokenVocab=Exp; // use the tokens from Exp.g
  ASTLabelType=CommonTree;
}

eval returns [ExpNode e]
  :  exp {e = $exp.e;}
  ;

exp returns [ExpNode e]
  :  ^(Add a=exp b=exp) {e = new AddExp($a.e, $b.e);}
  |  ^(Sub a=exp b=exp) {e = new SubExp($a.e, $b.e);}
  |  ^(Mul a=exp b=exp) {e = new MulExp($a.e, $b.e);}
  |  ^(Div a=exp b=exp) {e = new DivExp($a.e, $b.e);}
  |  ^(U_SUB a=exp)     {e = new UnaryExp($a.e);}
  |  Number             {e = new NumberExp($Number.text);}
  ;

5

下面是一些测试所有类的代码(将它们全部放在一个文件中:Main.java):

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    String source = "10 - 2 * (3 + 8)";
    ExpLexer lexer = new ExpLexer(new ANTLRStringStream(source));
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    ExpParser parser = new ExpParser(tokens);
    ExpParser.eval_return returnValue = parser.eval();
    CommonTree tree = (CommonTree)returnValue.getTree();
    CommonTreeNodeStream nodes = new CommonTreeNodeStream(tree);
    ExpWalker walker = new ExpWalker(nodes);
    ExpNode root = walker.eval();
    System.out.println(source + " = " + root.evaluate());
  }
}

interface ExpNode {
  double evaluate();
}

class NumberExp implements ExpNode {

  final double num;

  NumberExp(String s) {
    num = Double.parseDouble(s);
  }

  @Override
  public double evaluate() {
    return num;
  }
}

class AddExp implements ExpNode {

  final ExpNode left, right;

  AddExp(ExpNode a, ExpNode b) {
    left = a;
    right = b;
  }

  @Override
  public double evaluate() {
    return left.evaluate() + right.evaluate();
  }
}

class SubExp implements ExpNode {

  final ExpNode left, right;

  SubExp(ExpNode a, ExpNode b) {
    left = a;
    right = b;
  }

  @Override
  public double evaluate() {
    return left.evaluate() - right.evaluate();
  }
}

class MulExp implements ExpNode {

  final ExpNode left, right;

  MulExp(ExpNode a, ExpNode b) {
    left = a;
    right = b;
  }

  @Override
  public double evaluate() {
    return left.evaluate() * right.evaluate();
  }
}

class DivExp implements ExpNode {

  final ExpNode left, right;

  DivExp(ExpNode a, ExpNode b) {
    left = a;
    right = b;
  }

  @Override
  public double evaluate() {
    return left.evaluate() / right.evaluate();
  }
}

class UnaryExp implements ExpNode {

  final ExpNode exp;

  UnaryExp(ExpNode e) {
    exp = e;
  }

  @Override
  public double evaluate() {
    return -exp.evaluate();
  }
}

然后做:

# generate a lexer & parserjava -cp antlr-3.2.jar org.antlr.Tool Exp.g# generate the tree walkerjava -cp antlr-3.2.jar org.antlr.Tool ExpWalker.g# compile everythingjavac -cp antlr-3.2.jar *.java# run the main classjava -cp .:antlr-3.2.jar Main         # *nix java -cp .;antlr-3.2.jar Main         # Windows

打印:

10 - 2 * (3 + 8) = -12.0

您可以跳过 tree-walker 并将所有代码和 returns [...] 混合在您的组合语法中，但是 IMO，树语法使事情更加有序，因为词法分析器规则，并且( 和 ) 等标记已从中删除。

HTH