使用antlr分析树深度

Question

我有一个处理AND和OR表达式的antlr规则。看起来是这样的：

expr : expr 'AND' expr 
     | expr 'OR' expr 
     | 'a' | 'b' | 'c' | 'd'; 

这将生成一个非常深的解析树。E、 g.如果你有

a AND b AND c AND d

结果是这样的树：

              expr
           /    |  \
        expr   AND  d
     /    |  \
   expr AND  c
 / | \
a AND b

这可能会变得非常深入和昂贵，所以我想添加一个优化。我想同时处理多个顺序AND表达式（类似于OR-s）。

所以我想这样做：

expr : expr ('AND' expr)+
     | expr ('OR' expr)+
     | 'a' | 'b' | 'c' | 'd'; 

我认为这将为序列中的所有And-s生成一个节点。

然而，当我这样做的时候，antlr仍然选择生成递归树。我想那是因为规则是模棱两可的。有什么想法可以让它更扁平吗？是规则排序还是类似的问题？我关心深度的原因是因为深度递归导致的性能影响。

Answer 1

递归是否会产生实际的、可测量的性能问题。如果是这样，您能否量化您正在处理的递归程度。Antlr通常非常擅长处理递归，因此如果您遇到真正的性能问题，可能是由于Antlr中更深层次的问题。Ter和Sam需要重现它才能处理它。

这就是说，规则rhs上expr的每个实例都将创建一个递归。分组和限制实例

expr : expr ('AND' | 'OR') expr 
     | 'a' | 'b' | 'c' | 'd'
     ; 

不会更改满足规则所需的递归次数——这取决于正在处理的数据。

如果您的性能问题实际上源于大量深层递归规则失败，那么更大的好处可能是重新构造语法，使规则尽早失败，或者限制可能适用于任何给定数据序列的规则（或子规则）的数量。

根据迄今为止提供的信息，很难说到底是怎么回事。

已更新

为了澄清，Antlr中的递归规则调用的实现与任何其他规则调用没有区别；它不是通过递归Java方法调用实现的。

Antlr的LL（*）算法隐式地是针对预计算的有效状态网络运行的顺序路径解算器。检查点信息保存在每个决策点，包括规则调用，用于回溯。捕获规则调用状态转换所需的检查点数据相对简单，对是否；目标节点表示是否基于语法的递归调用。性能在很大程度上与规则节点评估的数量相关，尤其是包括所有尝试但最终失败的规则子路径的评估。

这就是为什么将递归规则展开为多个规则不太可能提高性能的原因。如果它们共同实现相同的递归函数，那么对相同的输入执行最多需要相同数量的规则调用。最坏的情况是，规则的非最小表达式将需要更多的规则调用，并且很可能会产生更多的内部检查点（every*和insertional都是隐式保护的）。

假设您的语法被优化最小化，并且20个表达式规则的顺序在统计上针对您的源数据进行了优化，您可以通过仅遍历实际匹配下一个源数据序列的确切子树来进一步优化。

只需提前统计预测正确的子树规则即可。考虑到评估解析树的次数，您应该能够相当快速地将源数据序列的一些简单计算签名与最终匹配的子树关联起来。或者至少决定一个更合适的子树排序。

根据目前提供的信息，很难确定签名函数应该是什么，或者成本效益是否为正。真正取决于您的源数据的性质。

Answer 2

如果您有一些像旧语法（C语法）中的规则，那么您可以很容易地做到这一点。

expr:   orExpr
    ;

orExpr: andExpr ('OR' andExpr)*
        ;

andExpr : primExpr ('AND' primExpr)*
        ;

primExpr:'a' | 'b' | 'c' | 'd'; 

WS : ' ' -> skip;

示例文本：

a AND b AND c AND d

结果：