给出文法s->AS|b,A->SA|a的abab串的LR(0)分析过程,列出状态栈和符号栈
时间: 2024-05-02 20:16:14 浏览: 155
首先,根据文法构造LR(0)自动机:
```
(0) S' -> .AS
(1) S -> .AS
(2) S -> .b
(3) A -> .SA
(4) A -> .a
(5) S -> AS.
(6) A -> SA.
```
状态0的状态集合中有唯一的LR(0)项目,即 $S' \to .AS$。根据该项目的后继符号 $A$,可以构造状态1:
```
(0) S' -> A.S
(1) S -> A.S
(2) S -> .b
(3) A -> .SA
(4) A -> .a
(5) S -> AS.
(6) A -> SA.
```
状态1的状态集合中包含两个项目,即 $S' \to A.S$ 和 $S \to A.S$。根据这两个项目的后继符号 $S$ 和 $b$,可以构造状态2和状态3:
```
(0) S' -> AS.
(1) S -> AS.
(2) S -> .b
(3) A -> .SA
(4) A -> .a
(5) S -> AS.
(6) A -> SA.
(2) S -> b.
```
状态2的状态集合中包含一个规约项目 $S \to b.$,表示在读入一个 $b$ 后可以对 $S \to b$ 进行规约。状态3的状态集合中包含两个项目,即 $A \to S.A$ 和 $A \to a.$。根据这两个项目的后继符号 $S$ 和 $a$,可以构造状态4和状态5:
```
(0) S' -> AS.
(1) S -> AS.
(2) S -> b.
(3) A -> S.A
(4) A -> a.
(5) S -> AS.
(6) A -> SA.
(3) A -> SA.
(4) A -> a.
(5) S -> AS..
```
状态4的状态集合中包含一个规约项目 $A \to a.$,表示在读入一个 $a$ 后可以对 $A \to a$ 进行规约。状态5的状态集合中包含一个规约项目 $S \to AS..$,表示在读入输入串末尾符号后可以对 $S \to AS$ 进行规约。
最终得到的LR(0)自动机如下:
```
+----+ A +----+
| |-------->| |
| 0 | S | 1 |
| |<--------| |
+----+ +----+----+
| b
| |
v |
+----+ |
| | |
| 2 | |
| | |
+----+ |
| |
| A
| |
v v
+----+----+
| | |
| 3 | 4 |
| | |
+----+----+
| a
| |
v |
+----+ |
| | |
| 5 | |
| | |
+----+ |
| |
| $
| |
v v
+---------+
| |
| accept |
| |
+---------+
```
根据该自动机,可以进行分析:
```
状态栈 符号栈 输入串 动作
---------------------------------------------------
0 $ abab$ 移进
0 1 $A bab$ 移进
0 1 3 $AS ab$ 移进
0 1 3 4 $ASa b$ 规约 A -> a
0 1 3 $AS b$ 转移
0 1 3 2 $ASb $ 规约 S -> AS
0 1 3 5 $AS $ 规约 S -> AS
0 $S' $ 接受
---------------------------------------------------
```
因此,该文法的 LR(0) 分析表如下:
```
+---+---+---+---+---+---+---+---+
| | a | b | S | A | $ | S'| |
+---+---+---+---+---+---+---+---+
| 0 | s5| | s1| | | s0| |
+---+---+---+---+---+---+---+---+
| 1 | | | | | | |acc|
+---+---+---+---+---+---+---+---+
| 2 | | | | | | |r2 |
+---+---+---+---+---+---+---+---+
| 3 | s5| | s1| s3| | | |
+---+---+---+---+---+---+---+---+
| 4 | r4| r4| | | r4| | |
+---+---+---+---+---+---+---+---+
| 5 | r3| r3| | | r3| | |
+---+---+---+---+---+---+---+---+
```
其中,$s$ 表示移进,$r$ 表示规约,$acc$ 表示接受。
阅读全文