SLR语法

SLR语法是简单LR解析器所接受的形式化语法的类别。SLR语法是所有LR(0)语法的一个超集，也是所有LALR(1)和LR(1)语法的一个子集。当被SLR分析器处理时，SLR语法被转换成解析表，对于任何LR(0)分析器状态和预期的lookahead符号的组合都没有shift/reduce或reduce/reduce冲突。

如果语法不是SLR，解析表对于某些状态和某些lookahead符号会有shift/reduce冲突或reduce/reduce冲突，而产生的拒绝解析器不再是确定性的。解析器不能决定下一步是移位还是还原，或者不能在两个候选还原之间作出决定。

SLR解析器使用Follow(A)计算来挑选每一个完成的非终端所期望的lookahead符号。LALR分析器使用不同的计算方法，有时会对相同的分析器状态给出更小、更紧密的lookahead集合。

这些较小的集合可以消除与该状态的移位动作的重叠，以及与该相同状态下的其他减法的lookaheads的重叠。然后，SLR解析器报告的重叠冲突是虚假的，是使用Follow(A)近似计算的结果。

对于每一种LR分析方法，包括SLR，一个含糊不清的语法都会有不可避免的移位/还原冲突或减少/还原冲突。计算机语言语法的一个常见方式是，如果某个非终端既是左递归又是右递归，就会出现歧义。Expr→Expr*ValExpr→Val+ExprExpr→Val

在SLR(1)自动机的一个状态中，形式为B→y-的规则被称为不可简化或处于简化状态，因为它已经被完全展开，无法进行任何转换。在这个状态下的规则将有一个点（-，当前的前瞻位置）位于其RHS（右手边）的最右端。

对于SLR(1)自动机中的每一个状态s，当且仅当以下条件没有被违反时，我们称A语法是SLR(1)。对于状态s中的任何可还原规则A→a-Xb（其中X是某个终端），一定不存在某个不可还原的规则，B→a-在同一状态s中，使得B的跟随集包含终端X。对于s中的任何两个完整项A→a-和B→b-，Follow(A)和Follow(B)是不相交的（它们的交集是空集），违反这一规则就是一个Shift-Reduce冲突。违反这条规则就是Reduce-Reduce冲突。解析算法如果以下简单的LR解析器算法没有产生歧义，则称该语法为SLR(1)。

如果状态s包含任何形式的项目A→a-Xb，其中X是一个终端，X是输入字符串中的下一个标记，那么动作是将当前的输入标记移到栈上，要推到栈上的新状态是包含项目A→aX-b的状态。如果状态s包含完整的项目A→y-，并且输入字符串中的下一个标记在Follow(A)中，那么行动就是通过规则A→y来减少。

通过规则S'→S（其中S是起始状态）来减少相当于接受；这只有在下一个输入标记是$时才会发生。从解析堆栈中移除字符串y和它所有对应的状态。

相应地，在DFA中倒退到构建y的开始状态。根据构造，这个状态必须包含一个形式为B→a-Ab的项目。将A推到堆栈中，并将包含B→aA-b项的状态推到堆栈中。如果下一个输入标记是上述两种情况都不适用的，就会宣布错误。