问题1
同一非终结符的多个候选式存在共同前缀，将导致回溯现象
文法G
S → aAd | aBe
A → c
B → b
输入
a b c
问题2
左递归文法会使递归下降分析器陷入无限循环
文法G
E → E + T | E – T | T
T → T * F | T / F | F
F → ( E ) | id
输入
id + id * id
含有A→Aα形式产生式的文法称为是直接左递归的 (immediate left recursive)
如果一个文法中有一个非终结符A使得对某个串α存在一个推导A=>+Aα ，那么这个文法就是左递归的。
经过两步或两步以上推导产生的左递归称为是间接左递归的。
消除直接左递归
消除直接左递归的一般形式
消除左递归是要付出代价的——引进了一些非终结符和ε_产生式
消除间接左递归
将S的定义代入A-产生式，得：
A → A c | A a d | b d | ε
消除A-产生式的直接左递归，得：
消除左递归算法
- 输入：不含循环推导（即形如A =>+ A的推导）和ε-产生式的文法G
- 输出：等价的无左递归文法
- 方法：
按照某个顺序将非终结符号排序为A1，A2，… ，An .
for ( 从1到n的每个i ) {
for ( 从1到i -1的每个i ) {
将每个形如Ai → Aj γ的产生式替换为产生式组 Ai → δ1 γ∣δ2 γ∣…∣δk γ ，
其中Aj → δ1∣δ2∣… ∣δk ，是所有的Aj 产生式
}
消除Ai 产生式之间的立即左递归
}提取左公因子(Left Factoring )
例
文法G
S → aAd | aBe
A → c
B → b
文法G '
S → a S'
S' → Ad | Be
A → c
B → b
通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择。
提取左公因子算法
-
输入：文法G
-
输出：等价的提取了左公因子的文法
-
方法：
对于每个非终结符A，找出它的两个或多个选项之间的最长公共前缀α。如果α ≠ ε， 即存在一个非平凡的( nontrivial )公共前缀，那么将所有A-产生式 A → α β1 | α β2 | … | α βn | γ1 | γ2 | … | γm 替换为 A → α A' | γ1 | γ2 | … | γm A' → β1 | β2 | … | βn 其中， γi 表示所有不以α开头的产生式体； A'是一个新的非终结符。不断应用这个 转换，直到每个非终结符的任意两个产生式体都没有公共前缀为止
留言