试消除下列文法中存在的左递归 G[A]: A → BC | CZ | W B → Ab | Bc C → Ax | By | Cp
时间: 2024-01-05 07:58:16 浏览: 31
消除左递归的步骤如下:
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' | ε
消除文法G: S→a|b|(T) T→TcS|S 的左递归;
消除文法的左递归是为了让文法满足LL(1)文法的要求,方便语法分析器进行处理。对于文法G:S→a|b|(T) T→TcS|S,我们可以按照以下步骤进行左递归的消除:
1. 将所有的直接左递归都消除,即将T→TcS转化为T→SU,其中U→cSU|ε;
2. 对于每一个非终结符号A,找到其所有能够推导出ε的直接或间接子孙非终结符号B1,B2,...Bn,并将其从A的产生式中删除;
3. 将删除ε后的产生式中的右部替换为其所有可能的组合,例如T→SU可以替换为T→cST|S;
4. 将新产生的文法规则加入原有文法中。
经过消除左递归后,G的新文法为:
S → a | b | '(' T ')'
T → SU
U → cSU | ε
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)