4.3 语法分析——Adaptive LL(∗) 语法分析算法

Antlr 使用的算法是 LL：Adaptive LL(*)

（间接左递归：A→B，B→A，因此最终还是 A→A，不支持是因为工程上一般不会这么去写，且如果要改写，改写后的会非常复杂，因此干脆不支持了）

Antlr 4 处理直接左递归和优先级——优先级上升算法

如果想在当前层的下一层展开，那么优先级要上升/更高。

antlr4 LRExpr -Xlog 加上这个参数后，可以在 log 中看到 Antlr4 重写语法后的语法（Antlr4 会把上面这样左递归的文法(expr:expr)改写成非左递归的）

下面的转化成了上面的形式

上面左递归的 expr 和 expr : (INT|ID)(*expr | +expr )* 这样的非左递归的形式是等价的，也即上面改写后的形式。但是 Antlr4增加了：

• expr 中的 int _p 就是定义了这 expr 的优先级（Antlr4规定的是写在上面的优先级最高，因此 * 的优先级最高是 5），在展开 expr 的时候都要带上优先级，比如上面写的 expr[5]，

• {4 >= $p}? 就是 if 判断，如果传入的优先级比 4 小，那么就用当前的展开

• 

• 在 exp[4] 处发现不能展开，因此就回到上层，展开成下面的样子

• 

  优先级控制了是在这一层展开还是回到上一层去展开，比如这里的 4，就不能满足 + 的条件，因此不能在这一层展开，会回到上一层，也即 exp[4] 所在是层进行展开 2+3，这样就实现了加法的左结合。【()*就相当于 while 循环，当循环中的都不满足，那就结束本层的递归调用回到上一层】

  

• 因此关键就是展开后下一层递归传入的优先级是多少，在本层循环中的条件设置成多少

• 

• 

括号的优先级更高，为什么不放到 +* 的上面呢，因此它不是左递归的，因此和 INT、ID所在的位置一样，会被优先处理

下面同理

-expr 和 ID 是一组，因为不是左递归，剩下两个是一组，因此改写后是这样的形式：

处理右结合的：

对于 ^ 判断条件是 3，传入到下一层递归的参数也是 3，因此可以连续在下一层展开 ^，也即实现右结合，没有优先级上升

总结：

• 处理左结合运算符，采用优先级上升

• 处理右结合运算符，采用优先级不变

Antlr 4 处理错误报告与恢复

原则：报错、恢复、继续分析

在当前词法单元出错时：

• 单词法符号移除：

  

• 单词法符号补全

  

group:1 表示选择第一个备选分支进行展开

FOLLOWING 是在运行这个文法时动态的集合【相比于静态的 FOLLOW，动态可以有更多信息去利用，因此集合内的元素也更少更确定，比如已知是group:1，那么肯定不会期望 )】。因为我们选择了 group 的第一个备选分支，因此我们知道，如果能从 expr 中恢复过来，我们期望的是 ]，因此跟在 expr 后面的是 ]，同理从 atom 恢复过来是期望后面的是 ^

因此整个流程就是，先看到 [，选择第一个备选分支，然后看到 ]，当作 expr 来处理，然后当作 atom 来处理，结果发现 atom 中没有与之匹配的终结符，因此出错。现在要恢复过来：先计算 FOLLOWING(expr,atom)={^,]}，因此读取后面的输入发现了 ]，就假装 atom 成功找到了它的下一个字符，回到 expr，因为 atom 成功，所以 expr 要匹配 ^，但确实 ]，同理计算，然后假装成功并返回到 group，并与 group 想要的 ] 匹配成功。

Adaptive LL(∗) [不做考试要求]

P表示的语言用正则表达式表示就是 S→a*bc | a*bd

这个文法不是 LL(k)文法，因为不论 k 取多少，都不能唯一确定 S 要选取哪个备选分支，因为 A 可以产生任意多个 a、

在决策点，对于每个备选分支产生一个解析器，并行地看当前的输入是不是符合的，如果不是，那么这个解析器 die；如果有歧义【多个达到了一个相同的状态或者都到达了 EOF，即说明这几个解析器没有区分开，是歧义】，最后选择仍然存活的分支（如果有多个即存在歧义，那么选择其中的第一个）

三元组的含义分别是：（当前状态，当前分支，进入下一个非终结符后并完成后要返回的状态栈【即一个递归调用栈】）

注意：这里更准确的说法是，f₁ 里两个三元组的第二个分量都是 1，所以可以确定使用第 1 条产生式，与是否进入 P_s’ 没有直接关系。这里是巧合。

什么叫做通过move，通过闭包得到的状态