java - ANTLR(或替代): decoupling parsing from evaluation

Question

我有一个相对简单的 DSL，我希望它比一堆手动编码的 java.util.regex.Pattern 语句 + 解析逻辑更可靠地处理。

引用最多的工具似乎是 ANTLR。我对它不熟悉，愿意尝试一下。但是，当我查看示例时(例如 ANTLR expression evaluator example 或 Martin Fowler 的 HelloAntlr 或 this other Q on stackoverflow )，我有点怀疑。这样做的原因是语法文件看起来像是语法定义的大杂烩，其中散布着本质上是命令式的实现语言(例如 Java)的片段。

我真正喜欢的是将解析器的命令式/求值部分分开。有没有一种方法可以使用 ANTLR(或其他工具)来定义语法并生成一组 Java 源文件，以便将其编译成类，我可以使用这些类将输入解析为不作用于该结构的结构？

例如，如果我只想对 + 和 * 以及 () 运算符使用表达式求值，并且我有输入

3 * (4 + 7 * 6) * (3 + 7 * (4 + 2))

然后我想做的是编写一个语法将其转换为层次结构，例如

Product
  Term(3)
  Sum
     Term(4)
     Product
        Term(7)
        Term(6)
  Sum
     Term(3)
     Product
        Term(7)
        Sum
            Term(4)
            Term(2)

我可以在哪里使用类

interface Expression<T> {
    public T evaluate();
}

class Term implements Expression<Double> {
    final private double value;
    @Override public Double evaluate() { return value; }
}

class Product implements Expression<Double> {
    final private List<Expression<Double>> terms;
    @Override public Double evaluate() {
        double result = 1;
        for (Expression<Double> ex : terms)
            result *= ex.evaluate();
        return result;
    }
}

class Sum implements Expression<Double> {
    final private List<Expression<Double>> terms;
    @Override public Double evaluate() {
        double result = 0;
        for (Expression<Double> ex : terms)
            result += ex.evaluate();
        return result;
    }
}

并使用ANTLR构建结构。有没有办法做到这一点？我真的更愿意采用这种方法，因为它允许我(和其他软件工程师)编辑和可视化完整的 Java 类，而不必将这些类分割成 ANTLR 语法文件中的奇怪片段。

有办法吗？

---

澄清:我想在两个方面花费尽可能多的精力:定义语法本身，以及在独立于 ANTLR 的 Java 中(例如我的 Product/Sum/Term 类)。我想尽量减少我必须花在学习 ANTLR 语法、怪癖和 API 上的时间/经验。我不知道如何从 ANTLR 语法创建和操作 AST。因为这只是大型 Java 项目的一小部分，所以不仅仅是我，我团队中的任何人都必须审查或维护我的代码。

(我并不是要显得无礼:我愿意投入时间和精力来使用工具，但前提是该工具成为有用的工具并且不会继续成为绊脚石。)

Answer 1

Jason S wrote:

Is there a way to do this?

是的。

首先定义你的语法(我以你的表达式解析器为例，只有 + 和 * 和 () 运算符):

grammar Exp;

// parser rules
parse
  :  additionExp
  ;

additionExp
  :  multiplyExp (Add multiplyExp)*
  ;

multiplyExp
  :  atomExp (Mult atomExp)* 
  ;

atomExp
  :  Number
  |  LParen additionExp RParen
  ;

// lexer rules
Add    : '+' ;
Mult   : '*' ;
LParen : '(' ;
RParen : ')' ;   
Number : ('0'..'9')+ ('.' ('0'..'9')+)? ;
Spaces : (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;} ;

如果你想让 ANTLR 从上面的语法中生成一个合适的 AST，你必须把下面的代码放在你的语法的顶部(在语法声明下面):

options { 
  output=AST; 
}

并且您必须指明每个解析规则的根应该是什么。这可以通过两种方式完成:

1. 通过使用 rewrite rules ;
2. 或者通过将“内联树运算符”之一 ^ 和 ! 放在标记之后:
   • ^ 表示:将此标记设为根；
   • ! 表示:从 AST 中排除此标记。

现在你的语法应该是这样的:

grammar Exp;

options { 
  output=AST; 
}

// parser rules
parse
  :  additionExp
  ;

additionExp
  :  multiplyExp (Add^ multiplyExp)*
  ;

multiplyExp
  :  atomExp (Mult^ atomExp)* 
  ;

atomExp
  :  Number
  |  LParen! additionExp RParen!
  ;

// lexer rules
Add    : '+' ;
Mult   : '*' ;
LParen : '(' ;
RParen : ')' ;   
Number : ('0'..'9')+ ('.' ('0'..'9')+)? ;
Spaces : (' ' | '\t' | '\r'| '\n') {$channel=HIDDEN;} ;

如您所见，我创建了 Add 和 Mult 根，并排除了括号。

现在从语法生成词法分析器和解析器:

java -cp antlr-3.2.jar org.antlr.Tool Exp.g 

创建一个小测试工具:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import java.util.*;

public class Main {

    private static void preOrder(CommonTree tree, int depth) {
        for(int i = 0; i < depth; i++) {
            System.out.print("- ");
        }
        System.out.println("> "+tree + " :: " + ExpParser.tokenNames[tree.getType()]);
        List children = tree.getChildren();
        if(children == null) return;
        for(Object o : children) {
            preOrder((CommonTree)o, depth+1);
        }
    }

    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("3 * (4 + 7 * 6) * (3 + 7 * (4 + 2))");
        ExpLexer lexer = new ExpLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        ExpParser parser = new ExpParser(tokens);
        CommonTree tree = (CommonTree)parser.parse().getTree();
        preOrder(tree, 0);
    }
}

编译一切:

javac -cp antlr-3.2.jar *.java

并运行 Main 类:

// *nix/Mac OS
java -cp .:antlr-3.2.jar Main

// Windows
java -cp .;antlr-3.2.jar Main

产生以下内容:

> * :: Mult
- > * :: Mult
- - > 3 :: Number
- - > + :: Add
- - - > 4 :: Number
- - - > * :: Mult
- - - - > 7 :: Number
- - - - > 6 :: Number
- > + :: Add
- - > 3 :: Number
- - > * :: Mult
- - - > 7 :: Number
- - - > + :: Add
- - - - > 4 :: Number
- - - - > 2 :: Number

如您所见，parse 规则(方法)返回 CommonTree您可以用来创建自己的 walker/visitor 的对象，按原样保留语法。

HTH