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

结果: