递归的预测分析法
递归的预测分析法是指:在递归下降分析中,根据预测分析表进行产生式的选择
基本方法就是每个非终结符对应一个函数,再递归进行判断
非递归的预测分析法
有非递归的预测分析法如下
基本思路如下:
- 开始,状态栈里面只有开始符,需要分析的串即为剩余输入
- 判断栈顶是否为空,如果为空的话,则结束,否则获得剩余输入的第一个非终结符为
a
- 状态栈的栈顶元素
E
出栈, 如果栈顶元素是终结符,则判断是否和a
相同如果相同的话则将a
出栈,返回第2步,否则就不满足语法. - 在预测分析表寻找非终结符为
E
,输入符号为a
的产生式,假设为E->AB
- 将
AB
入栈(注意是从后往前入栈,即 A 在栈顶,而 B 在他的下面) - 返回第3步
递归的预测分析法vs.非递归的预测分析法
- 构造文法
- 改造文法:消除二义性、消除左递归、消除回溯
- 求每个变量的FIRST集和FOLLOW集,从而求得每个候选式的SELECT集
- 检查是不是 LL(1) 文法。若是,构造预测分析表
- 对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法
语法错误的处理
对于编译器最常见的错误有以下两种:
- 终结符和当前输入符号不匹配
- 非终结符于当前符号在预测分析表对应的值为空。
对于程序中的错误,我们主要有以下两种处理方式:
- 普遍的想法是检测到错误就退出
- 高级的想法是从错误中恢复, 以检查后面更多的错误
所以,对于一个合格的语法分析器,我们应该做到:
- 报告出现的错误
- 尽快从错误中恢复, 检查后面的错误
- 尽可能少的减少检测正确程序的开销
为了能够从错误中恢复,我们可以使用 恐慌模式
- 忽略输入中的一些符号,直到输入中出现同步词法单元 (synchronizing token,是编译器设计者自己设计的) 中的某个词法单元。
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复,一般可以使用
FOLLOW(A)
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复,一般可以使用
- 如果不能匹配,一个简单的办法就是从栈中弹出此终结符。
下面是一个简单的例子: