ANTLR AST 规则失败并出现 RewriteEmptyStreamException

Question

我有一个简单的语法：

grammar sample;
options { output = AST; }
assignment
    : IDENT ':=' expr ';'
    ;
expr    
    : factor ('*' factor)*
    ;
factor
    : primary ('+' primary)*
    ;
primary
    : NUM
    | '(' expr ')'
    ;
IDENT : ('a'..'z')+ ;
NUM   : ('0'..'9')+ ;
WS    : (' '|'\n'|'\t'|'\r')+ {$channel=HIDDEN;} ;

现在我想添加一些重写规则来生成 AST。根据我在网上和《语言模式》书中阅读的内容，我应该能够像这样修改语法：

assignment
    : IDENT ':=' expr ';'   -> ^(':=' IDENT expr)
    ;
expr    
    : factor ('*' factor)* -> ^('*' factor+)
    ;
factor  
    : primary ('+' primary)* -> ^('+' primary+)
    ;
primary
    : NUM
    | '(' expr ')' -> ^(expr)
    ;

但它不起作用。虽然它编译得很好，但当我运行解析器时，我收到 RewriteEmptyStreamException 错误。这就是事情变得奇怪的地方。

如果我定义伪标记 ADD 和 MULT 并使用它们而不是树节点文字，则它可以正常工作而不会出现错误。

tokens { ADD; MULT; }

expr    
    : factor ('*' factor)* -> ^(MULT factor+)
    ;
factor  
    : primary ('+' primary)* -> ^(ADD primary+)
    ;

或者，如果我使用节点后缀表示法，它似乎也可以正常工作：

expr    
    : factor ('*'^ factor)*
    ;
factor  
    : primary ('+'^ primary)*
    ;

这种行为差异是否是一个错误？

Answer 1

不，不是错误，据我所知。以您的 expr 规则为例：

expr    
    : factor ('*' factor)* -> ^('*' factor+)
    ;

由于 * 可能不存在，因此它也不应该出现在您的 AST 重写规则中。因此，上述内容是不正确的，而 ANTLR 的抱怨是正确的。

现在，如果您插入一个像 MULT 这样的虚构标记：

expr    
    : factor ('*' factor)* -> ^(MULT factor+)
    ;

一切都可以，因为您的规则将始终生成一个或多个因子。

您可能想做的是这样的：

expr    
    :  (factor -> factor) ('*' f=factor -> ^('*' $expr $f))*
    ;

另请参阅 权威的 ANTLR 参考。特别是子规则中的重写规则（第173页）和在重写规则中引用先前的规则AST（第174/175页）段落。

Answer 2

如果您想为 '*' 运算符生成一个 N 叉树，并且所有子节点都处于同一级别，您可以这样做：

expr
    : (s=factor -> factor) (('*' factor)+ -> ^('*' $s factor+))?
    ;

以下是返回结果的一些示例：

Tokens: AST
factor: factor
factor '*' factor: ^('*' factor factor)
factor '*' factor '*' factor: ^('*' factor factor factor)

Bart 上面的第三个示例将生成一个嵌套树，因为每次连续迭代的 $expr 的结果是一个具有两个子节点的节点，如下所示：

factor * factor * factor: ^('*' factor ^('*' factor factor))

您可能不需要它，因为乘法是可交换的。