Left-recursion.md

Left-recursive rules（左递归规则）

一些通用语言构造的最自然的表达是左递归。 例如C声明符和算术表达式。 不幸的是，算术表达式的左递归规范通常是模棱两可的，但比典型的自上而下语法所需的多级更容易写出。 这里是一个带有左递归表达式规则的示例ANTLR 4语法:

stat: expr '=' expr ';' // e.g., x=y; or x=f(x);
    | expr ';'          // e.g., f(x); or f(g(x));
    ;
expr: expr '*' expr
    | expr '+' expr
    | expr '(' expr ')' // f(x)
    | id
    ;

在直接上下文无关语法中，这样的规则是不明确的，因为1+2*3`可以将任一运算符解释为优先， 但ANTLR使用语义谓词将其重写为非左递归和明确化：

expr[int pr] : id
               ( {4 >= $pr}? '*' expr[5]
               | {3 >= $pr}? '+' expr[4]
               | {2 >= $pr}? '(' expr[0] ')'
               )*
             ;

谓词通过将当前运算符的优先级与先前运算符的优先级进行比较来解决歧义。 expr[pr]的扩展只能匹配优先级满足或超过pr的子表达式。

Formal rules(正则规则)

正则4.0，4.1 ANTLR左递归消除规则被更改 (简化) 为4.2，并在 [所有 (*) 技术报告] 中列出 (http://www.antlr.org/papers/allstar-techreport.pdf):

• Binary表达式是包含规则递归调用的表达式，该规则是可选的第一个和最后一个元素。
• Suffix表达式包含将规则递归调用作为备选方案的第一个元素，但不包含作为最后一个元素。
• Prefix 表达式包含规则的递归调用，作为替代方案的最后一个元素，但不作为第一个元素。

没有“三元”表达式——它们只是伪装的二进制表达式。

right associativity specifiers（右关联）过去用在单个Token上；但是无论如何它是在alternative基础上进行的，所以现在可选择用在单个alternative上；例如，

e : e '*' e
  | e '+' e
  |<assoc=right> e '?' e ':' e
  |<assoc=right> e '=' e
  | INT
  ;

如果您的4.0或4.1语法使用右关联三元运算符，则需要更新语法以在alternative运算符上包含 <assoc=right>”。 为了平滑过渡，Token引用仍然允许使用<assoc=right>，但它只是被忽略。