Bonky Zhu
If someone is able to show me that what I think or do is not right, I will happily change, for I seek the truth, by which no one was ever truly harmed. It is the person who continues in his self-deception and ignorance who is harmed.

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

递归的预测分析法

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

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

非递归的预测分析法

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

基本思路如下:

  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)
  • 如果不能匹配,一个简单的办法就是从栈中弹出此终结符。

下面是一个简单的例子:

屏幕快照 2019-11-24 下午4.52.33

Share

You may also like...

发表评论