预测分析法
# 预测分析法
- 由于一个产生式的右部可能具有多个文法符号,因此在自顶向下的预测分析进行匹配时,需要记忆其右部未匹配部分的文法符号
- 根据实现记忆的方法,分为递归和非递归的预测分析
- 递归的预测分析借助递归过程实现记忆功能
- 非递归的预测分析借助栈来实现记忆功能
- 根据实现记忆的方法,分为递归和非递归的预测分析
# 递归的预测分析法
定义
- 递归的预测分析法是指:
- 在递归下降分析中,根据预测分析表进行产生式的选择
- 根据每个非终结符的产生式和LL(1)文法的预测分析表,为每个非终结符编写对应的过程
- 预测分析表用于应对一个非结结符对应多个产生式的情况
算法实现
- 结合当前输入符号
根据 SELECT 表进行选取 的产生式 - 遍历选定的产生式(非 ε-产生式)时
- 非终结符调用对应的过程
- 终结符直接与输入符号对比,如果匹配,则继续读入下一个符号;如果不匹配,则报错
- 如果选定的是 ε-产生式,则可以直接返回 (图中未显示)
- 如果没有产生式可选,则报错 (图中未显示)
- 遍历选定的产生式(非 ε-产生式)时
示例
描述程序构造的简单文法
-
TYPE
表示类型STLIST
表示语句序列DECLIST
表示标志符的序列PROGRAM
表示程序
注意对于
-产生式,要针对其 SELECT
集进行判断,与 S_文法 中的示例类似
-
针对非终结符
PROGRAM
的程序针对非终结符
DECLIST
的程序针对非终结符
DECLISTN
的程序- 此处相当于根据
TOKEN
在 (3)(4) 产生式中进行选择,如果都不满足要求,则报错
- 此处相当于根据
针对非终结符
STLIST
的程序针对非终结符
STLISTN
的程序- 此处相当于根据
TOKEN
在 (6)(7) 产生式中进行选择,如果都不满足要求,则报错
- 此处相当于根据
针对非终结符
TYPE
的程序- 此处相当于根据
TOKEN
在 (8)(9) 产生式中进行选择,如果都不满足要求,则报错
- 此处相当于根据
# 非递归的预测分析法
基本原理
- 非递归的预测分析不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析
- 借助栈当做储存器,可以储存状态,实现记忆的功能,相当于是增加了栈的有穷自动机(下推自动机)
- 相当是用栈替代了递归的过程
- 如对于
,碰到 即将其压入栈中,碰到 后将栈中的 弹出一个。如果匹配到末尾,栈为空,则说明 的个数相同
示意图
- 借助栈当做储存器,可以储存状态,实现记忆的功能,相当于是增加了栈的有穷自动机(下推自动机)
表驱动的预测分析法的算法实现
- 初始时将
和文法开始符号压入栈中 相当于一个查表过程, 为 error
表明相应的语法分析条目为空- 如果压入的是 ε-产生式,则直接跳过压栈过程
实例
# 递归的预测分析法与非递归的预测分析法对比
递归的预测分析法 | 非递归的预测分析法 | |
---|---|---|
程序规模 | 程序规模较大, 不需载入分析表 | 主控程序规模较小, 需载入分析表(表较小)😄 |
直观性 | 较好 😄 | 较差 |
效率 | 较低 | 分析时间大约正比于待分析程序的长度 😄 |
自动生成 | 较难 | 较易 😄 |
提示
- 递归的预测分析需要高深度的递归调用,因此效率较低
- 不需要载入分析表,并不意味着不需分析表。程序的编写仍然需要依据分析表来选择对应的产生式
- 非递归的预测分析法采用的是类似于自动机的方式,容易自动生成程序
# 预测分析法的实现步骤⭐
实现步骤
# 预测分析中的错误处理
# 错误处理的目的 ➕
提示
- 如果编译器只处理正确的程序,则它的设计和实现会大大简化;但人们还期望编译器能够帮助程序员定位和跟踪错误
- 大部分的程序设计语言没有规定编译器应该如何处理错误
- 错误的处理方法由编译器的设计者决定
# 错误检测
针对非递归的预测分析, 两种情况下可以检测到错误
- 栈顶的终结符和当前输入符号不匹配
- 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空
# 错误恢复
提示
- 错误恢复最简单的方法是让语法分析器在检测到第一个错误时给出错误提示信息,然后退出
- 但如果语法分析器给将自己恢复到某个状态,且有理由预期从那里开始处理输入将提供有意义的诊断信息,通常会发现更多的错误
- 但如果错误太多,最好让编译器在超过某个数量上界之后停止分析
- 这样,比让编译器产生大量恼人的“可疑”错误信息更好
- 但如果错误太多,最好让编译器在超过某个数量上界之后停止分析
# 恐慌模式
实现方法
- 忽略输入中的一些符号,直到输入中出现由设计者选定的同步词法单元(synchronizing token)集合中的某个词法单元
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
- 例如可以把
中的所有终结符放入非终结符 的同步记号集合
- 例如可以把
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
- 如果终结符在栈顶而不能匹配,一个简单的办法就是弹出此终结符
示例: 含有同步词法单元的分析表
- 分析表的使用方法
- 如果
是空,表示检测到错误,根据恐慌模式,忽略输入符号 - 如果
是 ,表时检测到错误,此时弹出栈顶的非终结符 ,试图继续分析后面的语法成分
- 如果
- 如果栈顶的终结符和输入符号不匹配,则弹出栈顶的终结符
示例: 借助含有同步词法单元的分析表进行预测分析
-
- 输入字符串中的起始的字符如果不能匹配,可忽略
编辑 (opens new window)