3、对于文法 G[S] S→A A→AB |ε B→aB | b (1) 请给出LR(1)项目的DFA,并构造LR(1)分析表; (15分) (2) 给出用LR(1)分析表对输入符号串abab$的分析过程。(5分)
时间: 2023-12-13 12:06:13 浏览: 101
(1) LR(1) 项目集规范族和 DFA 的构造过程如下:
LR(1) 项目集规范族:
$I_0=\{[S'→·S,\$]\}$
$I_1=\{[S'→S·,\$]\}$
$I_2=\{[S→·A,\$],[A→·AB,a/b],[B→·aB,a/b],[B→·b,a/b]\}$
$I_3=\{[A→A·B,a/b]\}$
$I_4=\{[B→a·B,a/b],[B→·a,a/b]\}$
$I_5=\{[B→b·,a/b]\}$
$I_6=\{[A→AB·,a/b]\}$
$I_7=\{[A→A·B,a/b],[B→·a,a/b],[B→·b,a/b]\}$
$I_8=\{[B→a·B,b],[B→·a,b]\}$
$I_9=\{[B→b·,b]\}$
$I_{10}=\{[A→AB·,b]\}$
$I_{11}=\{[A→A·B,b],[B→·a,b],[B→·b,b]\}$
DFA:
![](https://cdn.luogu.com.cn/upload/image_hosting/jymfz9n4.png)
LR(1) 分析表:
| 状态 | a | b | $ | A | B |
| :------: | :------: | :------: | :------: | :------: | :------: |
| 0 | s2 | s4 | | g3 | g5 |
| 1 | | | | | |
| 2 | s2 | s4 | acc | | |
| 3 | | | acc | | |
| 4 | r2 | r2 | r2 | | |
| 5 | r3 | r3 | r3 | | |
| 6 | s7 | s9 | | g8 | g5 |
| 7 | s7 | s9 | | g6 | g10 |
| 8 | | s11 | | | |
| 9 | r1 | r1 | r1 | | |
| 10 | | s12 | | | |
| 11 | | | | | |
| 12 | r3 | r3 | r3 | | |
(2) 对输入符号串 abab\$ 进行 LR(1) 分析的过程如下:
| 栈 | 符号 | 动作 |
| :------: | :------: | :------: |
| 0 | $ | - |
| 0 | S | Shift 2 |
| 02 | a | Shift 4 |
| 024 | b | Shift 9 |
| 0249 | a | Reduce 3 |
| 024A | a | Shift 4 |
| 0244A | b | Shift 9 |
| 02449A | b | Reduce 3 |
| 0244A | $ | Reduce 2 |
| 3 | $ | acc |