为什么在这个规则中会出现递归溢出？

Question

这是来自此问题的“后续”：How to parse a parenthesized hierarchy root?（请注意，root规则现在已更名为​​）。

在我ANTLR语法，我现在尝试了强制转换将支持：

cast : '(' type ')' atom -> ^(CAST type atom); 

现在，我需要它的价值树的一部分。由于投射本身是原子，可以是层次结构的基础，并且可以在任何二元运算（因子，总和，比较）中使用，我认为它必须在​​（以前的root）规则中进行。

cast : '(' type ')' atom -> ^(CAST type atom); 

atom : cast | IDENTIFIER | SELF | literal | constructor | call | indexer | '('! value ')'!; 

hierarchy : atom (SUB^ (IDENTIFIER | call | indexer))*; 

factor : hierarchy ((MULT^ | DIV^ | MODULO^) hierarchy)*; 

sum : factor ((PLUS^ | MINUS^) factor)*; 

comparison : sum (comparison_operator^ sum)*; 

value : comparison; 

幸运的是，这一次似乎一切都足够LL（*）。然而，我得到一个无限递归从type到type：

type : name=IDENTIFIER (LESSER (generics+=type (SEPARATOR generics+=type)*) GREATER)? -> ^(TYPE $name ^(GENERICS $generics*)); 

[规则原子]备选1 [铸造]：匹配输入诸如PAREN_OPEN IDENTIFIER LESSER IDENTIFIER LESSER IDENTIFIER LESSER IDENTIFIER LESSER IDENTIFIER后{LESSER，SEPARATOR}决定无法预测由于递归溢出而引起的下一步到类型从类型

此案例反映了诸如(x<x<x<x<x[</,]之类的内容。

ANTLR的错误非常难以理解。我重新阅读了解释这个确切错误的章节，但我仍然不明白。我也不明白的是，在独立的基础上，规则永远不会触发任何无限递归警告。

我该如何解决？请你理解ANTLR，你能解释为什么现在触发吗？

Answer 1

我不会去尽可能说，ANTLR的错误消息（全部）坚不可摧，但没错，这错误 ...是

在这种情况下，ANTLR具有使区分一个问题作为type的一部分的关系表达式IDENTIFIER < atom和IDENTIFIER < ...。这两种替代方案都可以作为​​规则的开始。

您可以通过验证这个不断变化的通用型开始，以便它不一样的关系LT-表达式：

type 
: IDENTIFIER ('@' (type (',' type)*) '>')? 
; 

或离开LT标志在通用型，但是从​​规则去除IDENTIFIER：

type 
: IDENTIFIER ('<' (type (',' type)*) '>')? 
; 

atom 
: cast 
//| IDENTIFIER 
| SELF 
| literal 
| constructor 
| call 
| indexer 
| '('! value ')'! 
; 

两个，当然，不是现实的选择，我知道。

为了使ANTLR高兴的语法，你可以只在cast替代的​​规则的前面加上一个语法谓词（并离开type规则，你现在拥有它）：

atom 
: (cast)=> cast 
| IDENTIFIER 
| SELF 
| literal 
| constructor 
| call 
| indexer 
| '('! value ')'! 
; 

这强制解析器首先向前看，并确保真的是是cast替代匹配，并且当不存在时，它落在​​规则的后面的替代方案中。

但这里的更好的选择是，你不要让你的语法来匹配像关系式：

a < b < c 

不使有很大的意义：关系式a < b通常计算结果为布尔，这不能与c相比，对吧？此外，您现在将所有逻辑关系和相等关系运算符组合在一个规则中，使它们的所有具有相同的优先级：而在大多数情况下，OR具有最低优先级，然后是AND，然后等于关系运营商。

因此，而不是：

value  : comparison; 
comparison : sum (comparison_operator^ sum)?; 
... 

comparison_operator : EQUAL | NOT_EQUAL | GREATER | LESSER 
        | GREATER_OR_EQUAL | LESSER_OR_EQUAL 
        | AND | OR 
        ; 

做：

value : or; 
or : and (OR^ and)*; 
and : eq (AND^ eq)*; 
eq : rel ((EQUAL | NOT_EQUAL)^ rel)?; // note the '?' and no '*' 
rel : sum ((GREATER | LESSER | GREATER_OR_EQUAL | LESSER_OR_EQUAL)^ sum)?; // note the '?' and no '*' 
sum : factor ((PLUS | MINUS)^ factor)*; 
... 

，然后你不需要的type前谓词在​​规则和你有经营者优先按正确的顺序。