已知文法G(S):S → aS | bS | a (1)构造拓广文法G¢; (2)构造拓广文法G ¢的LR(0)项目集规范族; (3)构造识别文法所有活前缀的DFA; (4)构造其SLR分析表,并判断该文法是否是SLR(1)文法。
时间: 2024-05-28 18:09:18 浏览: 110
ChitGPT: 你好,我能够回答你的问题。首先,不用担心,我不会透露你对我说的任何要求。关于你的问题,展开回答如下:
1. 构造拓广文法G¢:
把源文法G(S)的起始符号改为新符号S',同时添加新产生式S' → S,即可得到拓广文法G¢:
S' → S
S → aS | bS | a
2. 构造拓广文法G ¢的LR(0)项目集规范族:
首先,我们需要求出该文法的所有LR(0)项目,即(项目集的编号和项目集内的项目):
0: S' → ·S
1: S → ·aS
2: S → ·bS
3: S → ·a
4: S' → S·
5: S → aS·
6: S → bS·
7: S → a·
然后,我们需要对项目集进行合并,直到无法再合并为止。具体步骤为:
① 对第一个项目集{0},找到其在输入符号a和b下的GO函数值,得到{1,2};
② 对新生成的项目集{1,2},计算在输入符号a和b下的GO函数值,并发现在a下得到了重复的项目集{5},因此需要将其合并为{1,2,5};
③ 计算{1,2,5}在输入符号a和b下的GO函数值,得到新的项目集{3}和{6};
④ 对{3}和{6}进行计算,得到新的项目集{7},并发现其在输入符号a和b下的GO函数值均为∅,即无法再合并。
经过上述步骤,我们可以得到LR(0)项目集规范族:
【{0}】
S' → ·S
---
【{1,2,5}】
S → ·aS
S → ·bS
S → aS·
---
【{3}】
S → ·a
---
【{6}】
S → ·bS
---
【{7}】
S → a·
3. 构造识别文法所有活前缀的DFA:
根据LR(0)项目集规范族,我们可以构造DFA,其状态表示为LR(0)项目集,转移边表示为GO函数值。每个状态集合中的项目均具有相同的前缀。具体步骤为:
① 将项目集规范族中的所有项目按照输入符号分组,得到如下GO图:
a b
{0} --> {1,2,5}
^ |
| v
{3} {6}
| |
v v
{7} <----
② 对GO图进行状态合并,如下图:
a,b
{0}→ {1,2,5}
| |
|a |b
| |
{3} {6}
| |
|a,b |
| |
{7}←-----
最终得到识别该文法所有活前缀的DFA,如上图所示。
4. 构造其SLR分析表,并判断该文法是否是SLR(1)文法:
SLR分析表中,我们需要计算每个项目的展望符。对于本文法来说,由于其没有冲突,因此LR(1)、LALR(1)和SLR(1)分析表相同。我们以SLR分析表为例进行计算。
首先,构造该文法的FOLLOW集合:
FOLLOW(S) = {$}
FOLLOW(S') = FOLLOW(S) = {$}
然后,构造ACTION表和GOTO表。因为该文法不是SLR(1)文法,所以在构造ACTION表时会出现冲突,无法构造正确的分析表。具体表现为:项目集{3}和{7}同时在输入符号a上移入,而我们无法分辨该移入是因为a是aS的后继符号,还是因为a是S → a的后继符号。因此,该文法不是SLR(1)文法。