SLR 分析表：逻辑表达式 G[S] 的识别过程

逻辑表达式 G[S] 定义如下：

0	S→ A
1	A→A∨B
2	A→ B
3	B→B∧C
4	B→ C
5	C→┐D 
6	C→ D
7	D→（A）
8	D→a

其 SLR 分析表如下：

| 状态 | 动作 | GOTO | |---|---|---| | | | ┐ | ∨ | ∧ | a | ( | ) | # | A | B | C | D | | 0 | s5 | | | s7 | s6 | | | 1 | 2 | 3 | 4 | | 1 | | s8 | | | | | | a0 | | | | | | 2 | | r2 | s9 | | | r2 | r2 | | | | | | 3 | | r4 | r4 | | | r4 | r4 | | | | | | 4 | | r6 | r6 | | | r6 | r6 | | | | | | 5 | | | | s7 | s6 | | | | | | 10 | | 6 | s5 | | | s7 | s6 | | | 11 | 2 | 3 | 4 | | 7 | | r8 | r8 | | | r8 | r8 | | | | | | 8 | s5 | | | s7 | s6 | | | | 12 | 3 | 4 | | 9 | s5 | | | s7 | s6 | | | | | 13 | 4 | | 10 | | r5 | r5 | | | r5 | r5 | | | | | | 11 | | s8 | | | | s14 | | | | | | | 12 | | r1 | s9 | | | r1 | r1 | | | | | | 13 | | r3 | r3 | | | r3 | r3 | | | | | | 14 | | r7 | r7 | | | r7 | r7 | | | | |

#(a∨┐a)∧a# 的识别过程

| 步骤 | 栈内容 | 输入串 | 操作 | 内容 | |---|---|---|---|---| | | 1 | 0 | #(a∨┐a)∧a# | 移进# | | | 2 | 0# | (a∨┐a)∧a# | 转移至状态 5 | | | 3 | 0#5 | ∨┐a)∧a# | 移进∨ | | | 4 | 0#5∨ | ┐a)∧a# | 转移至状态 7 | | | 5 | 0#5∧ | a)∧a# | 移进∧ | | | 6 | 0#5∧ | a# | 转移至状态 7 | | | 7 | 0#5∧3 | # | 移进# | | | 8 | 0#5∧3# | | r4 | | | 9 | 0#5∧B | # | 转移至状态 4 | | | 10 | 0#5A | # | 转移至状态 2 | | | 11 | 0#A | # | 移进# | | | 12 | 0#A( | a∨┐a)∧a# | 移进a | | | 13 | 0#AD | ∨┐a)∧a# | 转移至状态 9 | | | 14 | 0#A | ┐a)∧a# | 移进┐ | | | 15 | 0#AC | a)∧a# | 转移至状态 3 | | | 16 | 0#AB | )∧a# | 移进) | | | 17 | 0#AB) | ∧a# | 移进∧ | | | 18 | 0#AB)∧ | a# | 转移至状态 7 | | | 19 | 0#AB)∧3 | # | r4 | | | 20 | 0#AB)∧B | # | 转移至状态 4 | | | 21 | 0#ABD | # | 转移至状态 6 | | | 22 | 0#A | # | r2 | | | 23 | 0#A∨ | # | 移进# | | | 24 | 0#A∨( | a∨┐a)∧a# | 移进a | | | 25 | 0#AD | ∨┐a)∧a# | 转移至状态 9 | | | 26 | 0#A∨ | ┐a)∧a# | 移进┐ | | | 27 | 0#A∨C | a)∧a# | 转移至状态 3 | | | 28 | 0#A∨B | )∧a# | 移进) | | | 29 | 0#A∨B) | ∧a# | 移进∧ | | | 30 | 0#A∨B)∧ | a# | 转移至状态 7 | | | 31 | 0#A∨B)∧3 | # | r4 | | | 32 | 0#A∨B)∧B | # | 转移至状态 4 | | | 33 | 0#A∨B∧ | # | r6 | | | 34 | 0#A∨C | # | r2 | | | 35 | 0#A∨C∨ | # | 移进# | | | 36 | 0#A∨C∨( | a∨┐a)∧a# | 移进a | | | 37 | 0#A∨CD | ∨┐a)∧a# | 转移至状态 9 | | | 38 | 0#A∨C∨ | ┐a)∧a# | 移进┐ | | | 39 | 0#A∨C∨C | a)∧a# | 转移至状态 3 | | | 40 | 0#A∨C∨B | )∧a# | 移进) | | | 41 | 0#A∨C∨B) | ∧a# | 移进∧ | | | 42 | 0#A∨C∨B)∧ | a# | 转移至状态 7 | | | 43 | 0#A∨C∨B)∧3 | # | r4 | | | 44 | 0#A∨C∨B)∧B | # | 转移至状态 4 | | | 45 | 0#A∨C∨B∧ | # | r6 | | | 46 | 0#A∨C∧ | # | r1 | | | 47 | 0#A∨B | # | r2 | | | 48 | 0#A∧ | # | r5 | | | 49 | 0S | # | 接受 | |

说明

s5, s7, s6 等代表移进操作，其后的数字代表转移至的状态。
r1, r2, r3 等代表规约操作，其后的数字代表规约所使用的产生式序号。
a0 代表接受状态。
其他操作符代表其本身。

通过 SLR 分析表，我们可以识别逻辑表达式 G[S] 的语法结构，并确定其是否符合语法规则。

注：本文中的逻辑表达式采用的是前缀表示法。