Shift-Reduce解析器
解析器的作用
编译器是一种将用编程语言编写的源代码翻译成机器语言语句流的程序。编译过程包括两个阶段：解析和代码生成。在解析阶段，编译器读取源文件并分析其结构。解析阶段的输出通常是反映源文件中代码结构的中间数据结构。然后，该数据结构在代码生成阶段充当算法的输入。
赢博体育现代编程语言都是由上下文无关语法描述的上下文无关语言。源代码文件可以被认为是上下文无关语言中的一个长字符串。正如我们已经看到的，如果一个字符串在语法中有一个派生，那么这个字符串就是上下文无关语言的成员。我们还看到，派生在本质上等同于解析树。因此，解析算法的目的是从输入字符串构造解析树。
Shift-Reduce解析器
在这几节课中，我们将学习一种特殊的解析器，称为移位-简化解析器。这种解析器由输入流、解析器堆栈和某种控制设备组成。解析器将符号从输入移到堆栈上。当堆栈顶部的符号看起来像是某个语法规则的右侧时，解析器会将组成右侧的符号从堆栈中弹出，并将左侧的变量推入其位置，从而将右侧减少到规则的左侧。
该控件的目的是跟踪堆栈上的内容，并决定何时将新符号移到堆栈中，何时减少。该控件本质上是一个经过修改的有限状态机，充当语法规则右侧的识别器。下面我将描述这个机器的状态和转换的构造。这种控制在一个重要方面与传统的有限状态机不同。当终端和变量被压入堆栈时，我们也将有关当前状态的信息一起压入堆栈。当控件进入一个表明应该进行缩减的状态时，我们从堆栈中弹出适当数量的元素，然后跳转到位于堆栈顶部的状态。从那个状态我们得到由那个状态和我们要化简的规则左边的变量所表示的过渡。
配置
控件执行的主要任务是识别语法规则的右侧。通过使用配置，控制的状态跟踪识别右手边的进度。一个配置看起来像一个语法规则，增加了一个额外的符号，用来跟踪我们在识别右侧的过程。例如，考虑一个语法规则
A→b→c
在识别过程的开始，在我们看到右边的任何符号之前，我们处于这样的配置：
A→•b
在我们看到变量B之后，我们处于位形中
A→b•c
当我们看到规则的整个右侧时，我们就在构型中了
A→b→c
配置与•在右手边信号减少结束。
准备语法
Shift-reduce语法适用于大多数合理的语法，尽管需要做一些准备工作。我们要做的第一件事是在语法的结束符号中添加一个额外的结束符号，称为结束标记。结束标记将是输入流中的最后一个符号。在下面的每个示例中，我们都将使用符号$作为结束标记。
我们还必须使用一个额外的语法规则来设置语法，该规则称为扩增生成。该规则引入了一个新的开始符号（通常是S），其右侧由旧的开始变量和结束标记组成。
S→e $
LR (0)
我们要学习的第一种也是最简单的移位-约简解析器是LR(0)解析器。LR(0)控制中的控制状态是通过对配置执行闭包操作来构造的。一组配置的闭包通过展开出现在•右边的变量来添加新的配置。
下面是计算一组配置的闭包的算法大纲：
Set CLOSURE(I) {J = I；重复做每一项一个 → α•Bβ（每个产品）B → γG)如果(B→•γ不是在J)添加B→•γJ;直到在一个回合中没有更多的物品添加到J；返回J;｝
例如，考虑语法G1：
S→e $
E→t | E + t
T→Id | (E)
形成包含配置的集合的闭包
S→•e $
我们首先添加配置
E→•t
E→•E + t
采用这些附加配置的闭包将引入另外两个配置。
T→•Id
•(e)
通过采用配置闭包形成的配置集确定了驱动LR(0)解析器的有限机器的状态。有限机的起始状态，状态0，是通过取构型的闭包形成的
S→•e $
因此，用于G1的机器启动状态的配置集为
如果一个配置集包含在某个语法符号的左边带有•的配置，我们将从该状态添加一个标记为该语法符号的转换。转换将我们带到一个新状态，其配置集是原始配置的闭包，其中•移动到该语法符号后面。例如，状态0包含一个配置
•(e)
这个配置允许我们添加一个标记为符号的转换，它将我们带到一个新的状态，其配置集是的闭包
T→（•e）
或
完全控制
运行解析器
解析器将控件与状态堆栈结合使用。下面是解析器用来处理输入的算法。
- 首先将启动状态放到状态堆栈中。
- 重复以下步骤，直到到达接受状态：
- 取输入上的下一个可用符号标记的过渡。将该符号从输入中移除，并将所处的状态推入堆栈。
- 如果你到达了一个允许你进行约简的状态，那么就从堆栈中弹出尽可能多的状态，因为该规则右侧有多少项，然后返回到现在位于堆栈顶部的状态，并进行由你在约简中使用的规则左侧的变量标记的转换。
构建解析树
作为运行shift-reduce解析器的副作用，构造解析树是一件相对容易的事情。需要做的第一件事是保存解析器运行时触发的缩减的记录。反转该约简列表提供了为输入字符串构建最右侧派生的方法。
例如，使用上面的语法和输入字符串Id + (Id)会触发一系列的约简：
T→Id
E→t
T→Id
E→t
T→(e)
E→E + t
S→e $
颠倒这个序列可以得到最右边的推导
年代⇒E⇒E + T⇒E +美元(E)⇒E + (T)美元⇒E +⇒美元(Id)
T + (Id) $⇒Id + (Id) $
然后可以使用通常的方法将此派生转换为解析树。
在实践中，每当发生缩减时，shift-reduce解析器都会触发解析器操作。解析器操作是一段很短的代码，在进行缩减时运行。通常，解析器操作构造解析树的片段，并将这些片段存储在称为值堆栈的并行堆栈中。在解析过程结束时，解析树出现在值堆栈的顶部。
减少冲突，减少冲突
为了使LR(0)控制有效，它必须始终提供明确的方向。不幸的是，在实践中经常出现两种不同的歧义。要了解这些歧义是如何产生的，请考虑一个稍微复杂一点的语法G2
S→e $
E→t | E + t
T→p | T * p
P→Id | (E)
此语法的LR(0)控件的状态0具有以下配置集
由T驱动的从状态0的转换把我们带到一个状态，它的构型是
这个状态是shift-reduce冲突状态的一个例子。配置E→T•想要触发一个减少，而配置T→T•* P更喜欢一个移位动作，将其右侧的其余部分推到堆栈上。
另一种可能发生的冲突是reduce-reduce冲突，在这种冲突中，单个状态包含两个或多个想要使用不同规则触发reduce的配置。
SLR (1)
尽管LR(0)解析器状态可能存在冲突，但在许多情况下，我们可以赢博体育一个简单的策略来解决冲突。简单的策略是，如果配置集包含像T→T•* P这样的配置，并且输入中的下一个符号是*，则首选移位。如果不可能进行这种转变，下一个优先事项就是裁减。在减少-减少冲突的情况下，我们试图确定哪些终端可以跟随我们试图减少到的非终端。如果这些终端中的一个作为输入中的下一个符号出现，就会触发还原。
为了实现这个算法，我们使用了两个额外的函数First和Follow：
Set FIRST(X) {if（X是终端）返回{X} I = {}；（每件产品）X → Y1Y2⋯Ykin G) I = I∈FIRST(Y1）; 如果(X → εI = I∈ε;返回我;} Set FOLLOW(X) {I = {}；（每件产品）一个 → Xαβin G) I = I∈(FIRST(β) - {ε});（每件产品）一个 → αXin G) I = I∈FOLLOW(一个）; 返回我;｝
使用这些函数，我们可以通过按此顺序尝试这些操作来解决shift-reduce和reduce-reduce冲突。
- 如果配置集包含配置a→α•β，并且下一个输入符号在FIRST（β）中，则移位该符号。
- 如果配置集包含配置a→α•，并且下一个输入符号在FOLLOW(a)中，则执行该约简。
将LR(0)算法与这些规则进行扩充以解决冲突，形成简单LR，即SLR(1)算法。
LR (1)
不幸的是，许多语法产生的配置集不能用这些附加规则完全消除歧义。在某些情况下，可以通过重写语法来消除shift-reduce或reduce-reduce冲突。在其他情况下，冲突形成了语法所描述的语言的固有特征，再多的重写也无法解决问题。在这些情况下，我们必须切换到更强大的解析算法。
上面描述的单反算法有限地使用了向前看的概念。使用前瞻的shift-reduce解析器根据当前状态和从输入流前端获取的一个或多个前瞻符号的组合来决定下一步要做什么。单反仅在冲突出现时使用向前看解决冲突。一种更强大的方法是在解析器的控制下，将前瞻性考虑到赢博体育配置集的构造中。充分利用forward的最简单的shift-reduce解析器是LR(1)解析器，它使用一个forward符号来帮助确定解析器的操作。
与LR(0)解析器一样，LR(1)解析器基于配置。LR(1)配置中的一个新特性是一个forward组件，它列出了配置在移动右侧的赢博体育元素后期望在输入流前面看到的符号。此外，我们必须修改闭包算法以包含查找。
LR(1)关闭
LR(1)解析器的状态0是通过采用配置的闭包形成的
S→•e $, {ε}
为了形成LR(1)配置的闭包，我们添加了一些规则的配置，这些规则扩展了集合中配置中•之后找到的任何变量。我们添加的任何新配置的forward组件都包含在变量展开之后可能出现的任何终端符号。
以下是LR(1)闭包算法的代码：
设置CLOSURE(I){对每个项目重复一个 → α•Bβ, {一个}在I中)用于（每个产品）B → γ(每个终端b在第一(β一))添加B→•γ, {b}到我；直到在一轮中没有更多的物品添加到I；返回我;｝
例如，下面是上面所示配置的闭包：
这里需要一些解释。从配置开始
S→•e $, {ε}
我们首先添加配置
这些配置具有{$}的前瞻性，因为我们通过扩展S→•E $， {ε}中的变量E来添加这些配置。在该配置中，终端符号$出现在E之后，因此它成为这两个新配置的前瞻。这两个新构型中的第一个引入了构型
这两种构型的前向也是{$}，因为在第一个构型中出现在T后面的东西是那个构型的前向，$。展开两个新配置中的第二个配置将导致配置
因为在第二种构型中，E后面出现的符号是+。只有前瞻性不同的配置被合并到单个配置中，因此最终的配置集将包含这些配置
转换的形成方式与以前相同。再一次，在进行转换之后，我们形成了参与转换的配置的闭包。例如，在T的驱动下，从上面的状态0过渡到一个状态
这种状态下潜在的shift-reduce冲突可以通过向前看来解决。如果前瞻性是$或+，我们解决冲突，支持减少。对于任何其他的forward，我们将尝试进行移位（只有当输入中的下一个符号是*时才会成功）。
LALR (1)
LR(1)足够强大，可以作为大多数实用语法的解析算法。不过，它有一个缺陷。增加的前瞻性信息会增加可能的配置集数量。因此，LR(1)语法往往有许多状态。对于大约有100个语法规则的语言，LR(1)控制机器可以有数千个状态。有限状态机的大多数软件实现都是由表驱动的。特别是，转换表是一个二维表，其中行数等于状态数，列数等于语法中的符号数。对于具有数千个状态和大约100个语法符号的控件，这可能产生一个占用近1兆字节空间的转换表。
解决LR(1)解析器臃肿的一个解决方案是合并配置集，这些配置集的不同之处在于它们的前瞻性。在许多实际语法中，这可以将状态的数量减少到可管理的数量。唯一的缺点是偶尔合并状态会重新引入shift-reduce或reduce-reduce冲突。在大多数情况下，可以通过稍微重写语法来解决问题。LALR(1)解析算法使用通过合并LR(1)状态形成的控制，将状态数量降低到更可行的数量。该算法的全部细节超出了本课程讲稿的范围：要了解更多细节，您应该参考下面的两个参考资料之一。
参考文献
这些讲义中的材料来自编译器设计的两个标准文本：
- 编译器：原理，技术和工具，第二版由Aho， Lam， Sethi和Ullman编写。
- 制作一个编译器由Fischer和LeBlanc。