文法转换
# 文法转换
# 左递归文法
左递归文法的定义
- 含有
形式产生式的文法称为是直接左递归的(immediate left recursive) - 如果一个文法中有一个非终结符
使得对某个串 存在一个推导 , 那么这个文法就是左递归的 - 经过两步或两步以上推导产生的左递归称为是间接左递归的
左递归文法可能会使递归下降分析器陷入无限循环
# 消除直接左递归
消除直接左递归的方法
对应的正则表达式为 对应的正则表达式为 - 这种消除过程实质上是将左递归转换成了右递归
消除直接左递归的示例
- 转换时提取左递归公式中的
和 , 然后直接代入上述的公式进行转换
消除直接左递归的一般形式
消除左递归是要付出代价的
- 引进了一些非终结符和
产生式
# 消除间接左递归
将间接左递归化为直接左递归,然后再消除
消除间接左递归的实例
- 可将
代入 产生式,得: - 消除
产生式的直接左递归,得:
# 消除左递归的算法
输入&输出
- 输入: 不含循环推导(形如
的推导) 和 产生式的文法 - 输出: 等价的无左递归算法
算法描述
算法理解
- 按照起始条件,循环不变式,和终止条件来理解
- 第 1 次循环,会使得
产生式中的每一个形如 的产生式,有 ,这主要通过第 6 行实现 - 当
时, 第 3 ~ 5 行的内层循环,会使得 中, ,第 6 行保证 - 终止时
, 此时 中将不再有形如 的产生式(因为 ),从而确保消除了所有的直接左递归
- 第 1 次循环,会使得
- 算法也消除了间接左递归
- 间接左递归是指通过变量替换会产生直接左递归
- 经过上述算法的变换后,形如
的产生式中,- 因此,即使将产生式
右部中的 都替换掉,也不会在其产生式右部的串首引入 ,即消除了间接左递归
- 因此,即使将产生式
- 而
中不再含有形如 的产生式,也就不可能存在直接左递归
为文法字符串,参照符号约定
# 提取左公因子
#
- 同一非终结符的多个候选式存在共同前缀,将导致回溯现象
例
- 文法
- 输入: abc
- 提取左公因子通过改写产生式来推迟决定,等读入了足够多的输入,获得足够信息后再做出正确的选择
例
- 文法
# 提取左公因子的算法
输入&输出
- 输入: 文法
- 输出: 等价的提取了左公因子的文法
方法:
- 对于每个非终结符
,找出它的两个或多个选项之间的最长公共前缀 。如果 ,即存在一个非平凡的( nontrivial )公共前缀,那么将所有 产生式- 替换为
- 其中,
表示所有不以 开头的产生式体 是一个新的非终结符
- 其中,
- 不断应用这个转换,直到每个非终结符的任意两个产生式体都没有公共前缀为止
- 替换为
编辑 (opens new window)