控制参数吸收

Question

我正在尝试编写一个支持函数调用而不使用括号的语法：

f x, y

与 Haskell 一样，我希望函数调用能够最小化其参数。也就是说，我想要

g 5 + 3

意思是

(g 5) + 3

而不是

g (5 + 3)

不幸的是，我用这个语法进行了第二次解析：

grammar Parameters;

expr
  : '(' expr ')'
  | expr MULTIPLICATIVE_OPERATOR expr
  | expr ADDITIVE_OPERATOR expr
  | ID (expr (',' expr)*?)??
  | INT
  ;

MULTIPLICATIVE_OPERATOR: [*/%];
ADDITIVE_OPERATOR: '+';

ID: [a..z]+;
INT: '-'? [0-9]+;
WHITESPACE: [ \t\n\r]+ -> skip;

我得到的解析树是这样的：

我原以为首先列出的子规则将首先被尝试。在这种情况下，

expr ADDITIVE_OPERATOR expr

出现在

ID

子规则之前，那么为什么

ID

子规则具有更高的优先级？

Answer 1

在这种情况下，ANTLR 没有进行正确的规则转换（以消除左递归并处理优先级）：

expr
    : expr_1[0]
    ;

expr_1[int p]
    : ('(' expr_1[0] ')' | INT | ID (expr_1[0] (',' expr_1[0])*?)??)
      ( {4 >= $p}? MULTIPLICATIVE_OPERATOR expr_1[5]
      | {3 >= $p}? ADDITIVE_OPERATOR expr_1[4]
      )*
    ;

导致

(expr (expr_1 a (expr_1 5 + (expr_1 3))))

正确的是：

expr
    : expr_1[0]
    ;

expr_1[int p]
  : ('(' expr_1[0] ')' | INT | ID (expr_1[5] (',' expr_1[5])*?)??)
  ( {4 >= $p}? MULTIPLICATIVE_OPERATOR expr_1[5]
  | {3 >= $p}? ADDITIVE_OPERATOR expr_1[4]
  )*
  ;

导致

(expr (expr_1 a (expr_1 5) + (expr_1 3)))

我不确定这是 ANTLR4 中的错误还是变换算法的权衡。也许应该向 ANTLR4 jira 写一个问题。

要解决您的问题，您只需将正确转换的语法放入代码中即可，它应该可以工作。规则转换的解释可以在第 249ff 页的“The Definitive ANTLR4 Reference”中找到（也许在网络上的某个地方）。

Answer 2

看来，根据Antlr对左递归规则的改造方式，在第一个符号上递归的左递归规则总是比那些没有递归的左递归规则具有更低的优先级。 以你的例子和上面@coronA的答案，

expr
  : '(' expr ')'
  | expr MULTIPLICATIVE_OPERATOR expr
  | expr ADDITIVE_OPERATOR expr
  | ID (expr (',' expr)*?)??
  | INT
  ;

将转变为：

expr_1[int p]: 
(
'(' expr_1[0] ')'  // first symbol is '(', not expr,
| INT              // first symbol is INT, not expr,
| ID (expr_1[5] (',' expr_1[5])*?)??) // first symbol is ID, not expr
)
(
  {4 >= $p}? MULTIPLICATIVE_OPERATOR expr_1[5] // first symbol is expr.
| {3 >= $p}? ADDITIVE_OPERATOR expr_1[4]       // first symbol is expr.
)*

这样，在匹配时，对于

g 5 + 3

，它会首先尝试将

g

作为ID来匹配，然后调用expr()来匹配其余的，即“5+3”。如果成功，则返回它。

所以

the prioror the rule is, the higher precedence it is

并不总是正确的。对于那些在第一个符号上自递归的符号来说是这样，对于那些不是自递归的符号来说也是如此，但是后者比先验符号具有更高的“优先级”。