LR解析器

LR解析是自底向上解析的一种类型。它用于解析大量的语法。

在LR解析中, “ L”代表输入的从左到右扫描。

“ R”代表反向构建最正确的推导。

“ K”是用于做出解析决定数量的前瞻输入符号的数量。

LR解析分为四个部分：LR（0）解析, SLR解析, CLR解析和LALR解析。

LR算法

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

图：LR解析器的框图

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

堆栈用于包含语法符号序列, 在堆栈底部带有$。

解析表是一个二维数组。它包含两个部分：“操作”部分和“转到”部分。

LR（1）解析

LR（1）解析涉及的各个步骤：

• 对于给定的输入字符串, 请编写上下文无关的语法。
• 检查语法的歧义性。
• 在给定的语法中添加增补产生。
• 创建LR（0）个项目的规范集合。
• 绘制数据流程图（DFA）。
• 构造一个LR（1）解析表。

增强语法

如果我们在给定的语法G中再增加一个产生式, 则会生成增强的语法G`。它有助于解析器确定何时停止解析并宣布接受输入。

例

给定语法

S → AA
A → aA | b

增强语法G`表示为

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