某语言的拓广文法G′为: S′→S ;S → Db|B; D → d|ε ;B → Ba|ε (1)为这个文法构造LR(0)项目的DFA (2)证明该文法不是LR(0)文法而是SLR(1)文法。 (3)构造该文法的SLR(1)分析表
时间: 2023-06-23 22:10:29 浏览: 228
1. 构造LR(0)项目的DFA如下:
| I | 项目集 | ACTION | GOTO |
|:---:|:----------:|:--------------:|:-----------:|
| 0 | S' -> .S | | 1 |
| 1 | S' -> S. | acc | |
| 2 | S -> .Db | | 3 |
| 3 | S -> .B | | 4 / 5 |
| 4 | B -> .Ba | | 6 |
| 5 | B -> . | r2 / r1 | |
| 6 | B -> Ba. | r2 / r1 | |
| 7 | D -> .d | r4 / r3 | |
| 8 | D -> . | r4 / r3 | |
2. 首先,考虑该文法为LR(0)文法的证明。对于任何一个LR(0)文法,在其DFA中,如果存在一条形如X -> α.Bβ的项目(其中B为非终结符),那么必须满足:对于B的任何一个后继符号b,都有一个项目X -> αB.β,即B的“归约-移进”冲突必须被解决。然而,在上述DFA中,状态5和状态6都存在这样的冲突,因为在这两个状态下,后继符号集合中都包含了{a, $},而无法确定应该进行移进还是归约。因此,该文法不是LR(0)文法。
但是,我们可以使用SLR(1)分析表来分析该文法。由于该文法的所有冲突都发生在状态5和状态6中,因此我们只需要解决这两个状态的冲突即可。具体来说,我们需要对状态5和状态6分别构造出其SLR(1)的向前看符号集合:
- 对于状态5,后继符号集合为{a, $},因此我们需要考虑B -> ε和B -> Ba两个产生式。对于B -> ε,其Follow集合为{a, $},因此我们将{a, $}作为向前看符号;对于B -> Ba,其Follow集合为{a, $},而B -> Ba并不能被规约到状态5,因此我们不需要考虑该产生式。因此,状态5的向前看符号集合为{a, $}。
- 对于状态6,后继符号集合仍然为{a, $},因此我们需要考虑B -> ε和B -> Ba两个产生式。对于B -> ε,其Follow集合为{a, $},因此我们将{a, $}作为向前看符号;对于B -> Ba,我们将{a}作为向前看符号,因为状态6只有在遇到a时才能进行移进操作。因此,状态6的向前看符号集合为{a}。
最终,该文法的SLR(1)分析表如下:
| 状态 | ACTION(d) | ACTION(a) | ACTION($) | GOTO(B) | GOTO(D) | GOTO(S) |
|:------:|:-----------:|:----------:|:----------:|:--------:|:--------:|:--------:|
| 0 | | s1 | | 2 | | |
| 1 | | | | | | |
| 2 | s7 | | r3 | | 8 | 3 |
| 3 | r2 | | r2 | | | |
| 4 | | | acc | | | |
| 5 | r1 | s6 | r1 | | | |
| 6 | | | r2 | | | |
| 7 | r4 | | r4 | | | |
| 8 | | | r3 | | | |
其中,s表示移进操作,r表示归约操作,acc表示接受。