LR 解析器

LR 解析是一种自底向上的解析方法。它用于解析一大类文法。LR 解析器是一种非递归文法。它使用大量的上下文无关文法，这使得它成为最有效的语法分析方法。

它也被称为 LR(K)，其中

• “L”代表从左到右扫描输入。
• “R”代表构造最右推导的逆过程。
• “K”是用于做出许多解析决策的超前输入符号的数量。

LR 解析分为四个部分

• LR (0) 解析：这种类型的解析器也称为 LR 解析器。其中 0 指定解析器根据当前位置和下一个输入符号做出决策。它不如其他类型的解析方法强大。
• SLR 解析：它代表简单 LR 解析器。它适用于最小的文法类。它包括几个步骤，因此表格很小。
• CLR 解析：它代表规范 LR 解析器。这种类型的解析器更强大，因为它使用 LR(1) 项来解决冲突并识别一大类文法。
• LALR (1) 解析：它代表超前 LR 解析器。它适用于中间大小的文法。它具有与 SLR(1) 相同数量的状态。

LR 算法

LR 算法需要堆栈、输入、输出和解析表。在所有类型的 LR 解析中，输入、输出和堆栈都是相同的，但解析表是不同的。

图：LR 解析器的框图

输入缓冲区用于指示输入结束，它包含要解析的字符串，后跟一个 $ 符号。

堆栈用于包含一系列文法符号，堆栈底部带有一个 $ 符号。

解析表是一个二维数组。它包含两部分

• 动作表
• 转到表

这两个表都由函数 (Sm, ai) 表示，其中 Sm 代表上面定义的四种情况，ai 代表当前输入字符。

让我们逐一详细解释

动作表定义了用于执行输入流的当前位置和最终位置的文法规则。动作表中使用了四个操作，例如

• 移位 - 此操作涉及将当前符号和位置从输入缓冲区移动到堆栈。因此，它成为新的当前位置。
• 规约 - 规则 m 左侧提到的符号 m 指示在转到表中出现了一个新位置，并作为新的当前位置被推入堆栈。
• 接受 - 如果堆栈包含输入字符串的起始字符，并且输入缓冲区为空，则认为输入字符串已被接受。
• 错误 - 如果解析器无法执行移位规约操作，则字符串也未被接受，则表示处于错误状态。

转到表指定了应继续解析的下一个位置。

以下是 LR 解析器的示例。

示例

让我们考虑以下文法

A → A + B

A → B

B → B x C

B → C

C → (A)

C → id

LR 解析表的 ACTION 和 GOTO 函数如下所示

使用 ACTION 和 GOTO 函数表，解析输入字符串 "id x id + id"。

解决方案

LR (1) 解析

LR (1) 解析中涉及的各种步骤

• 对于给定的输入字符串，编写一个上下文无关文法。
• 检查文法的二义性。
• 在给定的文法中添加扩充产生式。
• 创建 LR (0) 项的规范集合。
• 绘制一个数据流图 (DFA)。
• 构造一个 LR (1) 解析表。

扩充文法

如果我们向给定的文法 G 中添加一个产生式，则将生成扩充文法 G`。它有助于解析器识别何时停止解析并声明接受输入。

示例

给定文法

• S → AA
• A → aA | b

解决方案

添加扩充产生式，并在文法中每个产生式的第一位置插入符号。

扩充文法 G` 表示为

• S`→ S
• S → AA
• A → aA | b
•  

关于 LR 解析器的常见问题。

1. 列出各种类型的解析器？

• LR (0)
• SLR (1)
• CLR (1)
• LALR (1)

2. LR 解析器的结构由什么组成？

• 一个输入
• 一个输出
• 用于存储数据的堆栈
• 一个可运行的程序，即 LR 解析器
• 解析表由两部分组成：动作和转到