SLR、CLR、LALR Parser在编译器设计上有什么区别？

Z时代
2024-01-10
分类：综合

单反解析器

SLR代表“Simple LR Parser”。执行起来非常容易且具有成本效益。SLR 解析动作和 goto 函数来自识别可行前缀的确定性有限自动机。它不会为所有语法制作专门定义的解析动作表，但确实在几种编程语言的语法上取得了成功。给定一个文法 G。它扩充 G 以生成 G'，并且从 G' 可以构造 C，即 G' 的一组项目的规范集合。它可以使用以下简单的 LR 解析表构造技术从 C 构建解析动作函数 ACTION 和 goto 函数。它需要我们理解语法的每个非终结符 A 的 FOLLOW (A)。

CLR解析器

CLR 是指规范前瞻。CLR 解析使用 LR (1) 项的规范集合来构造 CLR (1) 解析表。与 SLR (1) 解析相比，CLR (1) 解析表产生更多的状态。在CLR(1)中，它只能在先行符号中定位reduce节点。

LALR 解析器

LALR Parser 是 Look Ahead LR Parser。它的功能介于 SLR 和 CLR 解析器之间。它是 CLR Parser 的压缩，因此在此获得的表将小于 CLR Parsing Table。

为了构建 LALR (1) 解析表，使用了 LR (1) 项的规范集合。在 LALR (1) 解析中，具有相同产生式但具有多个前瞻的LR (1)项被分组以形成单独的项集。除了解析表的一个区别外，它通常与CLR (1)解析相似。

所有这些 LR Parsers 的整体结构是相同的。有一些共同的因素，例如大小、它们支持的上下文无关语法的类别，以及它们在时间和空间方面不同的成本。

让我们看看 SLR、CLR 和 LALR Parser 之间的比较。

单反解析器	LALR 解析器	CLR解析器
It is very easy and cheap to implement.	它也易于实施且成本低廉。	It is expensive and difficult to implement.
SLR Parser 是最小的。	LALR 和 SLR 大小相同。因为他们的州数量较少。	CLR Parser is the largest. As the number of states is very large.
SLR 中的错误检测不是即时的。	LALR 中的错误检测不是立即进行的。	Error detection can be done immediately in CLR Parser.
SLR 无法为某类语法生成解析表。	它的功率介于 SLR 和 CLR 之间，即 SLR ≤ LALR ≤ CLR。	It is very powerful and works on a large class of grammar.
它需要更少的时间和空间复杂性。	它需要更多的时间和空间复杂性。	它还需要更多的时间和空间复杂性。