java - 用antlr解析树深度

Question

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

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

这会产生一个非常深的解析树。例如。如果你有

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

如果您有多个规则，例如旧语法 (C grammar)，您可以轻松做到这一点。

expr:   orExpr
    ;

orExpr: andExpr ('OR' andExpr)*
        ;

andExpr : primExpr ('AND' primExpr)*
        ;

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

WS : ' ' -> skip;

示例文本:

a AND b AND c AND d

结果: