消除左递归及提取左公因子

|
| 字数统计: 502

消除左递归及提取左公因子的方法。

消除左递归

什么是左递归？

如果一个文法中有一个非终结符号A使得对某个串α存在一个推导A=》Aα，那么这个文法就是左递归的。递归分为立即左递归和非立即左递归。立即左递归单步即可看出来，非立即左递归

举个例子：

1
2
3
4
5
6
7
8
立即左递归：
A ——> Aα | β

非立即左递归：
 1）A→aB
 2）A→Bb
 3）B→Ac
 4）B→d

消除立即左递归只需要遵循以下规律进行转换就ok。

立即左递归

1
2
3
4
将A ——> Aα | β 转换为

A ——> β A' 
A' ——> α A' |ε

非立即左递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
先将其变为立即左递归
 1）B→aBc
 2）B→Bbc 
 3）B→d
可化简为：B→aBc | Bbc | d

然后按照上面的规则进行转换即可
 1）B→aBcB' |dB'
 2）B'→bcB' |ε

最后进行整合
 1）A→aB
 2）A→Bb
 3）B→(aBc|d)B'
 4）B'→bcB'|ε

通用算法

1
2
3
4
5
6
7
8
9
以某种顺序排列非终结符A1，A2，……，An；

for(int i = n; i<=n; i++) {
	for(int j = n; j<=i-1; j++) {
		将每个形如 Ai → Ajγ 的产生式替换为产生式组 Ａi → ξ1γ｜ξ2γ｜……｜ξkγ ，
		其中，Aj→a1｜a2｜……｜ak是所有的当前Aj产生式
	}
	消除关于Ai产生式中的直接左递归性
}

提取左公因子

什么是左公因子？

和数学中的公因子含义相同，就是公共的因子，而左公因子就是最左边的公因子。

例如：

1
S → aB1|aB2|aB3|aB4|...|aBn|y

可以看出前n项拥有一个共同的左公因子：a，所以可以把他提取出来。

提取规则

1
2
S → aS'|y
S'→ B1|B2|B3|...|Bn

S → aB1|aB2|aB3|aB4|…|aBn|y
可以看出前n项拥有一个共同的左公因子：a，所以可以把他提取出来。

S → aS’|y
S’→ B1|B2|B3|…|Bn