ANTLR 4左侧递归规则

1 左侧递归规则

左侧递归规则（Left-recursive rules）是最自然和直接的语言结构，如C declarators和算术表达式。但是同时也是模糊的。

左侧递归表达如下：

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使用语义谓词（Sematic Predicates）改写为非左侧递归。

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

expr[pr]只匹配优先级不小于pr的子表达式。预测通过比较当前操作符和之前操作符的优先级解决模糊问题。

2 之前的规则

4.2版本简化了之前的左侧递归规则，详见ALL(*) tech report

双向表达式：前后都有递归的
后缀表达式：递归调用仅在后面
前缀表达式：递归调用仅在前面

右侧关联说明符以前是基于单个标记的，但无论如何都是在替代的基础上完成的，因此该选项现在位于单个替代项上。例如，

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

如果4.0或4.1语法使用了右关联三元运算符，则需要更新语法，包括<assoc=right>在替代运算符中。为了平滑过渡，<assoc=right>记号引用仍允许使用，但将其忽略。

1 左侧递归规则

2 之前的规则

参考资料