parsing - 关于 LR 解析器的问题

Question

1. 与其说“最右推导”，不如说“最左归约”？他们的意思是一样的吗？我读起来非常困惑。

2. 什么是闭包集，它在解析过程中如何发挥作用？我在互联网上找到的每套讲义都假设我已经知道它是什么以及它做了什么。

Answer 1

为了回答第二个问题，“闭包集”是解析器构造过程的一部分，用于识别解析器存在的“状态”。一旦确定了状态并构造了解析器，闭包集就不再发挥作用了——也就是说，它们在实际的解析过程中没有任何作用。

“闭包集”是一组部分解析项，由一个或多个初始部分解析项的闭包构成。每个唯一的闭包集都映射到一个状态。闭集构造的规则是：如果集合包含形式为“X→α_Aβ”的项并且文法包含形式为“A→δ”的规则，则将项“A→_δ”添加到项集。对于任何给定的项集，您需要通过重复添加项来计算闭包，直到无法添加更多项为止。这也忽略了前瞻（与 LR(k) 构造相关，但与 LALR(1) 或 SLR(1) 构造无关）。

一旦确定了语法可访问的所有不同的闭包集，就为每个集分配一个唯一的“状态”符号（通常只是一个整数），这是在运行时解析时将在解析器堆栈上操作的标记一个输入。闭包集信息根本不用于解析，尽管知道为错误指定的语法调试行为不端的解析器可能很有用。