ANTLR(或替代方案):将解析与评估分离

Question

我有一个相对简单的DSL,我想比一堆手动编码的java.util.regex.Pattern语句+解析逻辑更强大地处理.

最引用的工具似乎是ANTLR.我不熟悉它,我愿意尝试一下.但是当我查看示例时(例如,ANTLR 表达式计算器示例,或Martin Fowler的HelloAntlr,或者stackoverflow上的其他Q),我有点怀疑.这样做的原因是语法文件看起来像是一个语法定义的大杂烩,其中散布着本质上必不可少的实现语言(例如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

杰森S写道:

有没有办法做到这一点？

是.

首先定义你的语法(我把你的表达式解析器的例子只与+和*与()运营商):

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. 通过使用重写规则 ;
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你可以用它来创建自己的步行者/访问者留下语法对象为是.

HTH