Antlr左递归

Question

我试图将EBNF格式的scala中的后缀，中缀和前缀规则转换为ANTLR，但是我看到与infixExpression规则上的左递归有关的错误。

有问题的规则是：

public symbolOrID 
: ID 
| Symbol 
; 

public postfixExpression 
: infixExpression symbolOrID? -> ^(R__PostfixExpression infixExpression symbolOrID?) 
; 

public infixExpression 
: prefixExpression 
| infixExpression (symbolOrID infixExpression)? -> ^(R__InfixExpression infixExpression symbolOrID? infixExpression?) 
; 

public prefixExpression 
: prefixCharacter? simpleExpression -> ^(R__PrefixExpression prefixCharacter? simpleExpression) 
; 

public prefixCharacter 
: '-' | '+' | '~' | '!' | '#' 
; 

public simpleExpression 
: constant 
; 

如果我改变infixExpression规则：

public infixExpression 
: prefixExpression (symbolOrID infixExpression)? -> ^(R__InfixExpression prefixExpression symbolOrID? infixExpression?) 
; 

然后它，而不是抱怨：

warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} String" using multiple alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Number" using multiple alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Boolean" using multiple alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Regex" using multiple alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Null" using multiple alternatives: 1, 2 
As a result, alternative(s) 2 were disabled for that input 

最后，有什么办法在AST中有条件地创建节点，这样如果只有规则的左边部分为真，那么它不会添加该节点级别在？例如：

conditional_or_expression: 
    conditional_and_expression ('||' conditional_or_expression)? 
; 

如，可以说我创造出如下就像一个层次的语法：

conditional_and_expression 
    conditional_or_expression 
    null_coalescing_expression 

如果被解析的expresion为a || b，目前创建的AST是这个表达式将

conditional_and_expression 
    conditional_or_expression 

我怎么能得到它，所以它只是得到了部分conditional_or_expression？

在JavaCC中，你可以只设置节点元数，例如：#ConditionalOrExpression(>1)

编辑：这是一个有点晚了，昨晚，现在缀表达式属性格式修改！

最后编辑：我得到它的工作进行到底的方式有以下几条规则：

public symbolOrID 
: ID 
| Symbol 
; 

public postfixExpression 
: infixExpression (symbolOrID^)? 
; 

public infixExpression 
: (prefixExpression symbolOrID)=> prefixExpression symbolOrID^ infixExpression 
| prefixExpression 
; 

public prefixExpression 
: prefixCharacter^ simpleExpression 
| simpleExpression 
; 

public prefixCharacter 
: '-' | '+' | '~' | '!' | '#' 
; 

public simpleExpression 
: constant 
; 

Answer 1

Darkzaelus写道：

我试图转换从EBNF格式的scala到ANTLR的后缀，中缀和前缀规则，但是看到与左递归有关的错误

正如我在我的评论中所说：在您发布的规则中没有左递归。

Darkzaelus写道：

我怎么能得到它，所以它只是得到了部分conditional_or_expression？

我假设你正在使用ANTLRWorks'的解释或调试器，在这种情况下树：

conditional_and_expression 
      \ 
    conditional_or_expression 

仅显示这样的（分析树显示，而不是AST） 。如果你正确地改变你的orExpression成一个AST，表达a || b将变为：

|| 
/\ 
a b 

（即||为根，和a和b作为子节点）

例如，采取以下语法：

grammar T; 

options { 
    output=AST; 
} 

parse 
    : expr EOF -> expr 
    ; 

expr 
    : or_expr 
    ; 

or_expr 
    : and_expr ('||'^ and_expr)* 
    ; 

and_expr 
    : add_expr ('&&'^ add_expr)* 
    ; 

add_expr 
    : atom (('+' | '-')^ atom)* 
    ; 

atom 
    : NUMBER 
    | '(' expr ')' -> expr 
    ; 

NUMBER : '0'..'9'+; 

如果你现在从上面的语法，ANTLRWork产生解析器解析12+34 S（或Eclipse IDE ANTLR）将呈现以下分析树：

但这不解析器创建AST。 AST的其实是这样的：

（即or_expr，and_expr “层” 是在那里没有）

Darkzaelus写道：

不幸的是，这是相当危险的这个语言是早期阶段，所以我不得不保留语法秘密的全部细节。

没问题，但是你必须认识到，如果你隐瞒关键信息，人们不能正确回答你的问题。你不需要发布整个语法，但是如果你需要左递归帮助，你必须发布一个（部分）语法，它实际上会导致你提到的错误。如果我不能复制它，它就不存在！ :)

Answer 2

该生产：

infixExpr ::= PrefixExpr 
      | InfixExpr id [nl] InfixExpr 

可以重写

infixExpr ::= PrefixExpr 
      | PrefixExpr id [nl] InfixExpr 

事实上，我敢打赌，这仅仅是在语法错误。我们来看一个例子，它没问题。我们先用第一个语法减少（部分）一些东西，然后再尝试第二个语法。

InfixExpr id [nl] InfixExpr      
// Apply the second reduction to the first InfixExpr 
InfixExpr id [nl] InfixExpr id [nl] InfixExpr 
// Apply the first reduction to the (new) first InfixExpr 
PrefixExpr id [nl] InfixExpr id [nl] InfixExpr 
// Apply the first reduction to the new first InfixExpr 
PrefixExpr id [nl] PrefixExpr id [nl] InfixExpr 
// Apply the first reduction to the new first InfixExpr 
PrefixExpr id [nl] PrefixExpr id [nl] PrefixExpr 

让我们减少它与第二语法：

PrefixExpr id [nl] InfixExpr      
// Apply the second reduction to the first InfixExpr 
PrefixExpr id [nl] PrefixExpr id [nl] InfixExpr 
// Apply the first reduction to the new first InfixExpr 
PrefixExpr id [nl] PrefixExpr id [nl] PrefixExpr 

正如你看到的，你在这两种情况下相当于AST的结束。