compiler-construction - 如何理解非 LR(0) reduce state in A pratical method for Construction Effective LALR(k) Parsers with Automatic Error Recovery

Question

我不明白非 LR(0) 减少状态的来源。这是否意味着：

1. 移除 LR(0) reduce 状态和 get LR'(0) states
2. 使用 LR'(0) states 来生成一个 LR(K) states 。而非 LR(0) 归约状态来自 LR(K) 状态。

这是A patyical method for cnstructing Effective LALR(K) Parders with Authomatic Error Recovery的副本

请阅读第 4.2 章

Answer 1

归约状态是可以归约的状态。也就是说，如果状态的项集包含最终项，则该状态是归约状态。

如果 reduce 状态是 LR(0)——这意味着状态的动作可以在没有任何前瞻的情况下被识别——那么状态的项目集必须只有一个项目，它必须是最终的。（如果不是这种情况，则状态不可能是 LR(0)，因为将有不止一种可能的动作可用，只能通过前瞻来区分。）

正如他所指出的，LR(0) reduce 动作必须是正确的，因为在那个状态下不可能有其他动作。因此，即使前瞻令牌将生成需要错误恢复的错误，也不需要撤消减少。所以作者提出去掉LR(0) reduce states。

当然，并不是所有的状态都是 LR(0)。在大多数州，采取的行动将取决于前瞻。特别是，在非 LR(0) 归约状态下，归约将取决于前瞻令牌。并且，在移除 LR(0) 归约状态后，所有剩余归约状态都是非 LR(0)。

但是因为表压缩可能会用默认减少来代替错误操作（而且，我认为，因为 LALR 状态合并，尽管本章可能不是关于 LALR），所以很有可能为前瞻令牌指示的减少实际上会被证明是不正确的。在这种情况下，可能需要撤消减少以从错误中恢复。

作者的假设似乎是，一般来说，撤消归约是不可能的，因此解析器需要推迟归约操作（包括堆栈修改），直到知道归约确实有效，这将是解析器最终的时候执行换档。本章的其余部分涉及实现这一目标。