D->TL;T->i;T->f;T->L,x;L->x;如何消除左递归
时间: 2024-06-07 15:06:00 浏览: 16
为了消除左递归,我们需要将产生式改写为右递归形式。对于给定的文法:
D->TL;
T->i;
T->f;
T->L,x;
L->x;
我们可以将其改写为右递归形式如下:
D->TL';
L'->,TL';
L'->ε
T->i;
T->f;
T->L;
其中,L'是L的一个替代符号。这里我们添加了两个新的产生式,其中一个产生式生成逗号和一个新的非终结符L',它可以继续扩展为一个L和一个逗号,或者为空。这个新的产生式可以将原来的产生式D->TL,x转换为右递归形式D->TL',而不是左递归形式。同样地,我们可以使用L'来将T->L,x转换为右递归形式T->L,L'。最后,我们将L->x保持不变,因为它不涉及到左递归。这样,我们就成功地消除了左递归。
相关问题
D->TL,T->I, T->f,T->I,x,L->x如何消除左递归如何消除左递归
对于文法 D->TL,T->I, T->f,T->I,x,L->x,可以使用以下步骤消除左递归:
1. 找到所有左递归产生式。
文法中的左递归产生式为:D->TL 和 T->I,T->I,x。
2. 为每个左递归产生式添加一个新的非终结符,并重写产生式。
将 D->TL 改写为 D->TR 和 R->L,将 T->I,T->I,x 改写为 T->IY,Y->xI。
3. 消除间接左递归。
由于 R->L 仍然存在左递归,需要进一步消除。可以将 L->x 改写为 L->xR',R'->ε,然后将 R->L 改写为 R->xR'。
最终得到的文法如下:
D->TR
R->xR'
T->IY
Y->xI
L->xR'
R'->ε
对文法D->TL T->i T->f L->L,x L->x构造LR项目集族
首先,我们需要定义文法符号的编号,如下:
```
0: D'
1: D
2: T
3: L
4: i
5: f
6: ,
7: x
8: $
```
其中,`0` 表示起始符号,`8` 表示结束符号。
然后,我们可以按照以下步骤构造 LR 项目集族:
1. 初始化第 0 个项目集为 {`D' -> .D`}。
2. 对于每个项目集 `I` 和文法符号 `X`,进行如下操作:
a. 遍历 `I` 中的每个项目 `A -> α.Xβ`。
b. 对于 `X` 的每个产生式 `X -> γ`,构造新的项目 `X -> .γ` 并将其加入集合 `J` 中。
c. 对于 `J` 中的每个项目 `X -> .γ`,计算其闭包 `closure(X -> .γ)` 并将其加入集合 `I` 中。
d. 若集合 `I` 为新的项目集,则重复以上操作,直到不再出现新的项目集。
e. 记录 `I` 中 `X -> .γ` 对应的项目编号,并将其加入 LR 分析表的对应位置。
下面是构造过程的详细过程:
| I0: {D' -> .D} |
| --- |
1. 初始项目集为 `{D' -> .D}`。
| I0: {D' -> .D} |
| --- |
| D -> .TL |
2. 对于 `I0` 中的项目 `D -> .TL`,有两个产生式 `T -> i` 和 `T -> f`。因此,构造两个新的项目:
```
T -> .i
T -> .f
```
并将它们加入集合 `J0` 中:
```
J0: {T -> .i, T -> .f}
```
接下来,计算 `J0` 中每个项目的闭包:
```
closure(T -> .i): { T -> .i }
closure(T -> .f): { T -> .f }
```
并将它们加入项目集 `I0` 中:
```
I0: { D' -> .D, T -> .i, T -> .f }
```
最后,记录 `T -> .i` 和 `T -> .f` 对应的项目编号,并将其加入 LR 分析表的对应位置:
```
ACTION[0,i] = shift(1)
ACTION[0,f] = shift(2)
```
| I0: {D' -> .D, T -> .i, T -> .f} |
| --- |
| T -> .i |
| T -> .f |
3. 对于 `I0` 中的项目 `T -> .i`,没有新的产生式可以扩展,因此不需要进行操作。
4. 对于 `I0` 中的项目 `T -> .f`,有两个产生式 `L -> L,x` 和 `L -> x`。因此,构造两个新的项目:
```
L -> .L,x
L -> .x
```
并将它们加入集合 `J1` 中:
```
J1: {L -> .L,x, L -> .x}
```
接下来,计算 `J1` 中每个项目的闭包:
```
closure(L -> .L,x): { L -> .L,x, L -> .x }
closure(L -> .x): { L -> .x }
```
并将它们加入项目集 `I1` 中:
```
I1: { T -> .f, L -> .L,x, L -> .x }
```
最后,记录 `L -> .L,x` 和 `L -> .x` 对应的项目编号,并将其加入 LR 分析表的对应位置:
```
ACTION[1,x] = shift(3)
ACTION[1,$] = reduce(L -> x)
```
| I1: {T -> .f, L -> .L,x, L -> .x} |
| --- |
| L -> .L,x |
| L -> .x |
5. 对于 `I1` 中的项目 `L -> .L,x`,只有一个产生式 `L -> L,x` 可以扩展,因此构造新的项目:
```
L -> L.,x
```
并将其加入集合 `J2` 中:
```
J2: {L -> L.,x}
```
接下来,计算 `J2` 中的项目闭包:
```
closure(L -> L.,x): { L -> L.,x, L -> .L,x, L -> .x }
```
并将其加入项目集 `I2` 中:
```
I2: { L -> L.,x, L -> .L,x, L -> .x }
```
最后,记录 `L -> L.,x` 对应的项目编号,并将其加入 LR 分析表的对应位置:
```
ACTION[2,x] = shift(4)
```
| I2: {L -> L.,x, L -> .L,x, L -> .x} |
| --- |
| L -> L.,x |
| L -> .L,x |
| L -> .x |
6. 对于 `I2` 中的项目 `L -> .L,x`,只有一个产生式 `L -> L.,x` 可以扩展,因此构造新的项目:
```
L -> L.,x
```
并将其加入集合 `J3` 中:
```
J3: {L -> L.,x}
```
接下来,计算 `J3` 中的项目闭包:
```
closure(L -> L.,x): { L -> L.,x, L -> .L,x, L -> .x }
```
并将其加入项目集 `I3` 中:
```
I3: { L -> L.,x, L -> .L,x, L -> .x }
```
最后,记录 `L -> L.,x` 对应的项目编号,并将其加入 LR 分析表的对应位置:
```
ACTION[3,x] = reduce(L -> L)
ACTION[3,$] = reduce(T -> fTL)
```
最终得到的 LR 项目集族如下:
| I0: {D' -> .D, T -> .i, T -> .f} |
| --- |
| T -> .i |
| T -> .f |
| I1: {T -> .f, L -> .L,x, L -> .x} |
| --- |
| L -> .L,x |
| L -> .x |
| I2: {L -> L.,x, L -> .L,x, L -> .x} |
| --- |
| L -> L.,x |
| L -> .L,x |
| L -> .x |
| I3: {L -> L.,x, L -> .L,x, L -> .x} |
| --- |
| (reduce) L -> L |
| (reduce) T -> fTL |
LR 分析表如下:
| | i | f | , | x | $ |
| -- | -------- | -------- | -------- | -------- | -------- |
| 0 | shift(1) | shift(2) | | | |
| 1 | | | shift(3) | reduce | reduce |
| 2 | | | | shift(4) | reduce |
| 3 | | | | reduce | reduce |
| 4 | shift(1) | shift(2) | | | |
相关推荐
![C](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)