构造以下文法S→aSSb|aSSS|c的LR(0)分析表,并说明其是否为LR(0)文法。
时间: 2024-05-30 20:11:52 浏览: 8
首先,我们需要构造这个文法的所有 LR(0) 项集。
LR(0) 项集的构造步骤:
1. 将 S → ·aSSb 加入到初始项集 I0 中。
2. 对于每个在 I0 中的项,找到它的后继符号,将后继符号相同的项合并到同一个项集中。例如,对于项 S → a·SSb,在后继符号为 S 的项 S → ·aSSb 和 S → ·aSSS 中,S 的后继符号相同,因此将这两个项合并到同一个项集 I1 中。
3. 重复步骤 2,直到不再有新的项可以加入到项集中。
根据上述步骤,可以得到以下三个 LR(0) 项集:
I0:
S → ·aSSb
S → ·aSSS
S → ·c
I1:
S → aS·Sb
S → aS·SSS
I2:
S → aSS·b
接下来,我们需要构造 LR(0) 分析表。表中的行表示当前状态,列表示输入符号。表中的每个格子中填写一个动作符号(移进或规约)和一个状态号(下一个状态)。
LR(0) 分析表的构造步骤:
1. 对于每个 LR(0) 项集 Ii 中的每个项 A → α·aβ,如果 a 是终结符号,则将 A → α·aβ 加入到 Action[i, a] 中,并令下一个状态为 j,其中 j 是从 Ii 中的项 A → αa·β 转移而来的项集的编号。
2. 对于每个 LR(0) 项集 Ii 中的每个项 A → α·,如果 A 不是起始符号,则将 A → α· 加入到 Action[i, b] 中,并令下一个状态为 j,其中 b 是 Follow(A) 中的每个终结符号,j 是接受状态。
3. 对于每个 LR(0) 项集 Ii 中的每个项 S' → S·,如果 S' 是起始符号,则将 S' → S· 加入到 Action[i, $] 中,并令下一个状态为 j,其中 j 是接受状态。
4. 对于每个 LR(0) 项集 Ii 中的每个项 A → α·Bβ,如果 B 是非终结符号,则将 A → α·Bβ 加入到 Goto[i, B] 中,并令下一个状态为 j,其中 j 是从 Ii 中的项 B → ·γ 转移而来的项集的编号。
根据上述步骤,可以得到以下 LR(0) 分析表:
| | a | b | c | $ |
|---|---|---|---|---|
| 0 | s1 | | s2 | |
| 1 | s1 | s3 | | |
| 2 | r3 | s4 | r3 | r3 |
| 3 | s1 | s3 | | |
| 4 | r1 | r1 | r1 | r1 |
其中,s 表示移进,r 表示规约,数字表示转移到的状态编号。
因此,这个文法是 LR(0) 文法。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)