生成文法S→ABC A→FH B→a B→b C→GBED F→c F→d F→e H→f H→g H→h H→i G→j G→k E→l D→m的action-goto表
时间: 2023-06-16 07:08:12 浏览: 196
用C语言实现的顺序表
为了方便说明,我们给每个符号都赋一个编号:
S:0
A:1
B:2
C:3
F:4
H:5
G:6
E:7
D:8
a:9
b:10
c:11
d:12
e:13
f:14
g:15
h:16
i:17
j:18
k:19
l:20
m:21
首先,我们需要构建 LR(0) 自动机:
状态0:
S → .ABC
A → .FH
B → .a
B → .b
C → .GBED
F → .c
F → .d
F → .e
H → .f
H → .g
H → .h
H → .i
G → .j
G → .k
E → .l
D → .m
状态1:
S → A.BC
A → F.H
B → .a
B → .b
C → .GBED
F → .c
F → .d
F → .e
H → .f
H → .g
H → .h
H → .i
G → .j
G → .k
E → .l
D → .m
状态2:
B → a.
B → b.
状态3:
C → G.BED
G → .j
G → .k
E → .l
D → .m
状态4:
F → c.
F → d.
F → e.
状态5:
H → f.
H → g.
H → h.
H → i.
状态6:
C → GB.ED
G → .j
G → .k
E → .l
D → .m
状态7:
E → l.
状态8:
D → m.
状态9:
S → AB.C
A → FH.
F → c.
F → d.
F → e.
H → f.
H → g.
H → h.
H → i.
状态10:
A → F.H
H → .f
H → .g
H → .h
H → .i
状态11:
C → GBE.D
G → .j
G → .k
E → .l
D → .m
状态12:
B → a
B → .b
状态13:
B → b.
状态14:
C → GBED.
根据 LR(0) 自动机,可以得到 action-goto 表如下:
| 状态 | a | b | c | d | e | f | g | h | i | j | k | l | m | G | E | D | A | B | C | F | H | S |
| :----: | :---: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| 0 | S2 | S13 | S4 | S4 | S4 | S5 | S5 | S5 | S5 | S6 | S6 | S7 | S8 | G3 | E7 | D8 | 1 | S9 | S10 | S11 | S12 | S1 |
| 1 | R1 | R1 | S4 | S4 | S4 | S5 | S5 | S5 | S5 | S6 | S6 | S7 | S8 | G14 | E7 | D8 | - | S9 | S10 | S11 | S12 | - |
| 2 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 3 | - | - | - | - | - | - | - | - | - | S15 | S16 | S7 | S8 | - | - | - | - | - | S17 | - | - | - |
| 4 | R3 | R3 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 5 | R4 | R4 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 6 | - | - | - | - | - | - | - | - | - | S15 | S16 | S18 | S8 | - | - | - | - | - | S17 | - | - | - |
| 7 | R7 | R7 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 8 | R8 | R8 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 9 | - | S13 | - | - | - | - | - | - | - | - | - | - | - | G19 | - | - | - | - | S10 | S11 | S12 | - |
| 10 | R2 | R2 | - | - | - | S5 | S5 | S5 | S5 | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 11 | - | - | - | - | - | - | - | - | - | S15 | S16 | S7 | S8 | - | S21 | S22 | - | - | - | - | - | - |
| 12 | S2 | S13 | S4 | S4 | S4 | S5 | S5 | S5 | S5 | S6 | S6 | S7 | S8 | - | E23 | D8 | - | S9 | S10 | S11 | S12 | - |
| 13 | R5 | R5 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| 14 | R6 | R6 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
其中,S 表示移进,R 表示规约,- 表示错误。例如,S2 表示将下一个输入符号看作 a 并移进状态2。
注意,表中没有状态15、16、17、18、20,因为它们都是不可行的状态。状态19表示已经接受了整个输入串,因此在状态19下,应该进行接受动作。
阅读全文