编译原理 – 语法分析之预测分析法

递归的预测分析法

递归的预测分析法是指：在递归下降分析中，根据预测分析表进行产生式的选择

基本方法就是每个非终结符对应一个函数，再递归进行判断

非递归的预测分析法

有非递归的预测分析法如下

基本思路如下：

1. 开始，状态栈里面只有开始符，需要分析的串即为剩余输入
2. 判断栈顶是否为空，如果为空的话，则结束，否则获得剩余输入的第一个非终结符为 a
3. 状态栈的栈顶元素 E 出栈, 如果栈顶元素是终结符，则判断是否和 a 相同如果相同的话则将 a 出栈，返回第2步，否则就不满足语法.
4. 在预测分析表寻找非终结符为 E ，输入符号为 a 的产生式，假设为 E->AB
5. 将 AB 入栈（注意是从后往前入栈，即 A 在栈顶，而 B 在他的下面）
6. 返回第3步

递归的预测分析法vs.非递归的预测分析法

1. 构造文法
2. 改造文法：消除二义性、消除左递归、消除回溯
3. 求每个变量的FIRST集和FOLLOW集，从而求得每个候选式的SELECT集
4. 检查是不是 LL(1) 文法。若是，构造预测分析表
5. 对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法
   

语法错误的处理

对于编译器最常见的错误有以下两种：

1. 终结符和当前输入符号不匹配
2. 非终结符于当前符号在预测分析表对应的值为空。

对于程序中的错误，我们主要有以下两种处理方式：

• 普遍的想法是检测到错误就退出
• 高级的想法是从错误中恢复, 以检查后面更多的错误

所以，对于一个合格的语法分析器，我们应该做到：

• 报告出现的错误
• 尽快从错误中恢复, 检查后面的错误
• 尽可能少的减少检测正确程序的开销

为了能够从错误中恢复，我们可以使用 恐慌模式

• 忽略输入中的一些符号，直到输入中出现同步词法单元 (synchronizing token，是编译器设计者自己设计的) 中的某个词法单元。
  • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复，一般可以使用 FOLLOW(A)
• 如果不能匹配，一个简单的办法就是从栈中弹出此终结符。

下面是一个简单的例子：