B→B(B)| e 构造该拓广文法的LR(0)项目集规范族C;判断该文法是否为SLR(1)文法,说明理由。
时间: 2023-06-18 08:03:40 浏览: 94
首先将该拓广文法表示为如下形式:
```
S' -> B
B -> B(B) | ε
```
对该文法构造LR(0)项目集规范族C:
```
I0:
S' -> .B
I1:
S' -> B.
B -> .B(B)
B -> .
I2:
B -> B(.B)
B -> .B(B)
B -> .
I3:
B -> B(B.)
```
接下来,我们需要判断该文法是否为SLR(1)文法。SLR(1)文法必须满足以下两个条件:
1. 对于每个文法符号,在任何一个项目集中,其follow集中的符号与该文法符号的lookahead集中的符号没有交集;
2. 对于任何一个规约项 A -> α,如果存在两个不同的终结符号 a 和 b,使得a ∈ follow(A) 且 b ∈ follow(A),则必须满足 FIRST(αa) ∩ FIRST(αb) = ∅。
对于条件1,我们观察上面的LR(0)项目集规范族C,发现对于B这个文法符号,它在I2的lookahead集合中有"(",而在I3的lookahead集合中有")",两个集合有交集,因此该文法不是SLR(1)文法。
因此,该文法不是SLR(1)文法。
相关问题
设有文法G[B]: B→B(B)| e 构造该拓广文法的LR(0)项目集规范族C;判断该文法是否为SLR(1)文法,说明理由。
根据题目所给出的文法G[B],可以构造出该文法的LR(0)项目集规范族C如下:
```
I0:
B' -> .B
B -> .B(B)
B -> .e
I1:
B' -> B.
I2:
B -> B.(B)
B -> .B(B)
B -> .e
I3:
B -> B(B).
I4:
B -> B(B).
其中,B'为拓广文法的起始符号,"."代表项目符号,I0为初始状态。
接下来,我们需要判断该文法是否为SLR(1)文法。SLR(1)文法需要满足两个条件:
1. 对于同一状态S和终结符a,不存在两个不同的项目A -> α.aβ和B -> γ.aδ,其中A和B可以通过某些产生式推导出来。
2. 对于同一状态S和非终结符A,不存在两个不同的项目A -> α.Bβ和A -> γ.Bδ,其中B可以通过某些产生式推导出来,且FOLLOW(A)中的终结符和FOLLOW(B)中的终结符完全一致。
对于该文法,我们可以求出它的FOLLOW集合如下:
```
FOLLOW(B') = $
FOLLOW(B) = {(,),$}
```
接下来,我们需要求出每个LR(0)项目的展望符集合,然后根据上述两个条件来判断该文法是否为SLR(1)文法。
I0:
B' -> .B {$}
I1:
B' -> B. {$}
I2:
B -> B.(B) {), $}
B -> .B(B) {(}
B -> .e {), $}
I3:
B -> B(B). {), $}
I4:
B -> B(B). {), $}
根据上述每个LR(0)项目的展望符集合,我们可以发现:
1. 对于状态I2,存在两个不同的项目B -> .B(B)和B -> .e,它们的展望符集合分别为{(}和{), $},其中存在交集{)},因此不满足SLR(1)文法的第一个条件。
2. 对于状态I3和I4,它们的产生式都只有一个,不存在不同的项目,因此满足SLR(1)文法的两个条件。
因此,该文法不是一个SLR(1)文法。
已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法
首先,我们需要构造该文法的 LR(0)自动机。
LR(0)自动机的状态集合如下:
| 状态 | 项目集 |
| :-----: | :----------------: |
| I0 | A→•fAa |
| | A→•fAg |
| | A→•b |
| I1 | A→f•Aa |
| | A→f•Ag |
| I2 | A→fA•a |
| I3 | A→fA•g |
| I4 | A→•fAa |
| | A→•fAg |
| | A→•b |
| | A→f•Aa |
| | A→f•Ag |
| I5 | A→fA•a |
| I6 | A→fA•g |
| I7 | A→fAa• |
| I8 | A→fAg• |
接下来,我们需要构造该文法的 SLR(1)分析表。
| 状态 | a | b | f | g | $ |
| :---------: | :-----: | :-----: | :----: | :----: | :----: |
| 0 | s2 | s3 | s4 | s5 | |
| 1 | | | r3 | r3 | r3 |
| 2 | | | r2 | r2 | r2 |
| 3 | | | r1 | r1 | r1 |
| 4 | s2 | s3 | s4 | s5 | |
| 5 | | | s6 | s7 | |
| 6 | | | r5 | r5 | r5 |
| 7 | | | r4 | r4 | r4 |
| 8 | | | r6 | r6 | r6 |
其中,s表示移入状态,r表示规约状态,数字表示将要转移到的状态。
可以发现,该文法存在移入-规约冲突和规约-规约冲突,因此该文法不是 SLR(1)文法。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.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)
![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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)