设有文法G[B]: B→B(B)| e 构造该拓广文法的LR(0)项目集规范族C;判断该文法是否为SLR(1)文法,说明理由。
时间: 2024-02-13 16:59:49 浏览: 68
根据题目所给出的文法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)文法。
阅读全文