问题 ANTLR（或替代）：将解析与评估分离


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

最引用的工具似乎是ANTLR。我不熟悉它，我愿意尝试一下。但是当我看一些例子时（例如ANTLR，我有点怀疑） 表达式评估器示例，或马丁福勒的 HelloAntlr， 要么 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项目的一小部分，所以不仅仅是我，我团队中的任何人都必须审查或维护我的代码。

（我并不是说听起来不礼貌：我愿意投入时间和精力来使用工具，但前提是该工具成为一种有用的工具并且不会继续成为绊脚石。）


11360
2017-10-11 21:04


起源

答案:

杰森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 rule（方法）返回一个 CommonTree 您可以用来创建自己的步行者/访客离开语法的对象 原样。

HTH


11
2017-10-12 07:05


+1。感谢您发布一步一步的示例，这或多或少都是我需要的。我看过的所有其他示例都在.g文件中有必要的操作，我无法弄清楚ANTLR-ism与可以删除的Java片段的语法是什么。 - Jason S
附：你使用org.antlr.stringtemplate的哪些部分？他们推荐/必要吗？ - Jason S
嗯。每个树节点 版画 作为一个字符串...但节点是什么？我如何判断节点是multiplyExp还是additionExp或其他什么？当我有机会的时候，我会通过调试器给它一个旋转，但如果有一个简短的+明显的答案，我会非常感激。 - Jason S
@Jason，内容了 CommonTree 在其中使用 toString(): String 方法。你可以通过它获得类型 getType(): int 方法（我稍微改变了我的样本）。不，没有必要 StringTemplate导入：我发布的其他一些演示中偶然出现了（我也删除了导入）。 - Bart Kiers
@Jason，是的，这是正确的。要么用你想要的标记重建AST，要么创建一个扩展的类 CommonTree，说 ExpTree，在其中添加额外的功能（如（摘要） evaluate() 方法）并从中创建一些子类 ExpTree （喜欢 Term， Sum 和 Product）。关于后者的更多信息可以在这里找到： 使用自定义AST节点类型 - Bart Kiers

答案:

杰森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 rule（方法）返回一个 CommonTree 您可以用来创建自己的步行者/访客离开语法的对象 原样。

HTH


11
2017-10-12 07:05


+1。感谢您发布一步一步的示例，这或多或少都是我需要的。我看过的所有其他示例都在.g文件中有必要的操作，我无法弄清楚ANTLR-ism与可以删除的Java片段的语法是什么。 - Jason S
附：你使用org.antlr.stringtemplate的哪些部分？他们推荐/必要吗？ - Jason S
嗯。每个树节点 版画 作为一个字符串...但节点是什么？我如何判断节点是multiplyExp还是additionExp或其他什么？当我有机会的时候，我会通过调试器给它一个旋转，但如果有一个简短的+明显的答案，我会非常感激。 - Jason S
@Jason，内容了 CommonTree 在其中使用 toString(): String 方法。你可以通过它获得类型 getType(): int 方法（我稍微改变了我的样本）。不，没有必要 StringTemplate导入：我发布的其他一些演示中偶然出现了（我也删除了导入）。 - Bart Kiers
@Jason，是的，这是正确的。要么用你想要的标记重建AST，要么创建一个扩展的类 CommonTree，说 ExpTree，在其中添加额外的功能（如（摘要） evaluate() 方法）并从中创建一些子类 ExpTree （喜欢 Term， Sum 和 Product）。关于后者的更多信息可以在这里找到： 使用自定义AST节点类型 - Bart Kiers

如何使用ANTLR AST（抽象语法树）并通过访问每个树节点为您的类构建镜像树。

@Giuseppe Cardone添加了一些很棒的链接，我在这里发布：

http://www.antlr.org/article/1100569809276/use.tree.grammars.tml

http://www.antlr.org/article/1170602723163/treewalkers.html

可以在以下位置找到一个示例：

http://sagarsunkle.spaces.live.com/blog/cns!E07F3B561597E4EE!664.entry?sa=97619042


3
2017-10-11 21:35


嗯。我是ANTLR的新手，所以我不熟悉如何做你的建议，或者它可能有什么优点/缺点。 - Jason S
我想进一步阐述这个问题，但基本上我同意@smink：建立一个AST（也许使用 output=AST ANTLR选项）然后使用树步行器检查/评估/编译它是将语法与代码分离的最简单方法。 - Giuseppe Cardone
+1 @Giuseppe Cardone获取链接。我在之前的项目中使用了这种技术，它工作正常。 - Jorge Ferreira
感谢您的精心制作。我并不是指以非建设性方式批评，但我不认为“use.tree.grammars.tml”或“treewalkers.html”链接是有用的。他们似乎是关于ANTLR是否采取正确方法的争论性争论：第一个说“访客不是一个好的解决方案”和“我喜欢ANTLR的语法+行动策略”（这正是我遇到的问题） ;第二个似乎是一个反驳，并建议应该有一个替代ANTLR做事的方式，但不建议一个。 - Jason S
示例链接（在sagarsunkle.spaces.live.com上）很有用......我有点得到它......但我却没有。 ：/ - Jason S

您提到的示例为了简洁起见，在语法内部嵌入了解析器操作。这适用于小型项目。对于较大的那些，你更喜欢先制作一个AST然后随意做任何事情。你可以通过嵌入创建树的动作来做到这一点，但是antlr提供了一种更好的声明方式：

http://www.antlr.org/wiki/display/ANTLR3/Tree+construction

然后，您可以使用Tree Grammar生成代码，例如使用StringTemplate。 我已经将这个工具链用于我的论文，它就像一个魅力。但我敢打赌，如果没有Anlr3参考书，我会遭受很多苦难（ http://pragprog.com/titles/tpantlr/the-definitive-antlr-reference ）

我还发现在antlr页面上链接的讲义非常有用： http://www.antlr.org/wiki/display/CS652/CS652+Home

另外，利用AntlrWorks来测试你的语法。还有一个语法单元测试套件。此外，antlr邮件列表非常活跃，Terence Parr积极响应大多数帖子。此外，它很有趣。


2
2017-10-11 23:26



热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来