试消除下列文法中存在的左递归 G[A]: A → BC | CZ | W B → Ab | Bc C → Ax | By | Cp
时间: 2023-10-22 08:03:53 浏览: 52
消除左递归的步骤如下:
1. 提取公因子,将产生左递归的规则中的公共部分提取出来。对于该文法,可以先提取出 A → CZ 和 B → Aβ,其中 β 可以是 b 或 c。
G1[A]: A → CZ | WB
B → Aβ
C → Ax | By | Cp
W → ε
2. 将左递归的规则修改为右递归。对于该文法,需要将 A → WB 改为 A → WB | WB', 其中 B' → ε。
G2[A]: A → CZ | WB | WB'
B → Aβ | B'
B' → ε
C → Ax | By | Cp
W → ε
3. 最后,消除新产生的直接左递归。对于该文法,B 和 B' 之间存在间接左递归,需要进行消除。
G[A]: A → CZ | WB | WB'
B → Aβ | ε
C → Ax | By | Cp
W → ε
经过以上步骤,该文法已经消除了左递归。
相关问题
试消除下列文法中存在的左递归 G[A]: A → BC | CZ | W B → Ab | Bc C → Ax | By | Cp
消除左递归的步骤如下:
1. 提取左公因子
G[A]: A → CZ | W A'
A' → BC | ε
B → aB' | cB'
B' → ε | aB' | cB'
C → Ax | By | Cp
2. 消除间接左递归
G[A]: A → CZ | W A'
A' → BC | ε
B → aB' | cB'
B' → ε | aB' | cB'
C → Ax | WY | Cp
Y → xY | ε
最终的文法为:
G[A]: A → CZ | W A'
A' → BC | ε
B → aB' | cB'
B' → ε | aB' | cB'
C → Ax | WY | Cp
Y → xY | ε
消除下列文法中存在的左递归 G[A]: A → BC | CZ | W B → Ab | Bc C → Ax | By | Cp
首先,我们需要检测文法中是否存在左递归。如果一个非终结符可以推导出以它自身开头的产生式序列,那么就存在左递归。
对于文法 G[A]: A → BC | CZ | W B → Ab | Bc C → Ax | By | Cp,我们可以看到 B 和 C 都存在左递归。具体来说,B 可以推导出以 B 开头的产生式序列,C 可以推导出以 C 开头的产生式序列。下面分别进行消除。
1. 消除 B 的左递归
将 B → Ab | Bc 改写为 B → cB',B' → ε | Ab'。这样就将原来的左递归消除了。
2. 消除 C 的左递归
将 C → Ax | By | Cp 改写为 C → pC',C' → ε | Ax' | By'。这样也将原来的左递归消除了。
最终的文法如下:
G[A]: A → BC | CZ | W
B → cB' | ε
B' → Ab' | ε
C → pC'
C' → Ax' | By' | ε