6 构造SLR语法分析器
简单 LR 语法分析技术（SLR）
中心思想：根据文法构造出 LR(0) 自动机，这个自动机的状态是规范 LR(0) 项集族中的元素，转换函数由 GOTO 给出，开始状态是 CLOSURE(\{[S'→·S]\})，所有的状态都是接受状态。
LR(0) 自动机 用于帮助做出 S-R 决定，具体规则如下：
假设文法符号串 \gamma 已经使自动机从开始状态运行到某个状态 j
- 如果下一个输入符号是 a，且状态 j 支持 a 的转换，就移入 a
- 否则，选择规约，状态 j 的项告诉我们使用哪个产生式进行规约
LR 语法分析算法
栈中移入一个状态，这个状态是对其下所有状态信息的浓缩
ACTION 语法分析表
签名：ACTION(i,a)
参数：i 表示当前状态；a 表示终结符号（或者 $）
返回：四种可能的取值
- 移入状态 j，状态 j 就代表了 a
- 规约 A→\beta，把栈顶的句柄规约为产生式头 A
- 接受
- 报错
GOTO 语法分析表
原来的 GOTO 函数是定义在项集上的，现在在 LR 分析中，一个状态就代表了一个项集，所以 GOTO 的定义可以迁移到状态集上。
如果 A 是非终结符，i,j 是状态，则 $$ GOTO[I_i,A]=I_j\Leftrightarrow GOTO[i,A]=j $$
LR 语法分析器行为
设当前格局为 (...s_{m-1}s_m\quad a_i...a_n\$)，语法分析器要据此决定下一个动作，它首先阅读 a_i 和 s_m，然后查询 ACTION[s_m,a_i] 获得下一步应该做的操作，然后：
- 如果 ACTION[s_m,a_i]= 移入 s，则下一个格局变为 (...s_{m-1}s_ms\quad a_{i+1}...a_n\$)
- 如果 ACTION[s_m,a_i]= 规约 A→\beta，则下一个格局变为 (...s_{m-r}s\quad a_i...a_n\$)，其中 r 是 \beta 的长度，s=GOTO(s_{m-r},A)，注意此时输入符号指针不发生改变
- 如果 ACTION[s_m,a_i]= 接受/出错，则另行处理
不同的 LR 语法分析器只是 ACTION 和 GOTO 的信息不一样。
SLR 语法分析表构造算法
输入：一个增广文法 G'
输出：G' 的 SLR 语法分析表函数 ACTION 和 GOTO
方法：
（1）构造 G' 的规范 LR(0) 项目集族 C=\{I_0,...,I_n\}
（2）根据 I_i 构造状态 i，其 ACTION 表按如下规则决定：
- 如果 [A→\alpha·a\beta]\in I_i，并且 GOTO(I_i,a)=I_j，那么 ACTION[i,a]= 移入 j，这里 a\in V_T
- 如果 [A→\alpha·a]\in I_i，则对于 FOLLOW(A) 中的所有 a，令 ACTION[i,a]= 规约 A→\alpha，这里 A\neq S'
- 如果 [S'→S·]\in I_i，则 ACTION[i,a]= 接受
（3）状态 i 对各个非终结符的 GOTO 表按如下规则决定：
- 如果 GOTO(I_i,A)=I_j，那么 GOTO(i,A)=j
（4）规则（2，3）没有定义的所有条目都设置为报错，并且如果出现冲突，则说明这个文法不是 SLR(1) 的，退出
（5）语法分析器的初始状态就是根据 [S'→·S] 所在项集构造得到的状态
本文阅读量这个算法给出的是 G 的 SLR(1) 分析表，使用 G 的 SLR(1) 分析表的 LR 语法分析器称为 G 的 SLR(1) 语法分析器。常常省略这里的 (1)。