compiler-construction - LR自动机实际上是如何工作的？

Question

在这个 LR(0) 自动机中

非终端也有转换，我不明白。如果输入是aab. 那么你最终会处于刚刚的状态A->a·。如果您要可视化通过输入aab或任何其他输入达到的状态，在它们之间没有弧的状态之间不会有转换吗？

我不明白为什么这与 DFA 或 NFA 不同，在 DFA 或 NFA 中，您从起始状态开始，并且仅沿着自动机中的弧线过渡，直到您达到接受状态。

Answer 1

LR 解析使用下推的状态堆栈，它在任何时候都代表解析中尚未完全识别的产品集。当达到具有完整产生式的状态时（点在末尾，例如在 ' A -> a.' 中），这意味着堆栈在顶部具有该产生式右侧的符号。您将它们弹出以返回开始此特定转换序列的状态，现在为该产品左侧的非终端进行转换。

因此，如果您到达 ' A -> a.'，则必须备份一个转换（标记为 ' a' 的路径）并A取而代之的是 ' ' 转换。如果您到达 ' S -> AB.'，则必须备份两个转换并S改为使用 ' ' 转换。等等。

DFA 或 NFA 没有这样的回溯（或相应的维护堆栈的需要）。

Answer 2

标有非终结符的转换仅在执行归约步骤后才进行。当你做一个 reduce 时，你将从解析堆栈中删除一些符号，然后将一个非终结符压入堆栈。此时，您将遵循标有该特定非终结符的转换。

解析自动机与典型的 DFA 或 NFA 不同，它旨在控制堆栈。转换都对应于解析堆栈上的不同动作；每个终端对应一个班次，完成的项目对应减少，非终端告诉你在减少之后去哪里。从理论上讲，LR 自动机是确定性下推自动机的控制，如果有帮助的话。

Answer 3

LR 自动机是一个下推自动机，它使用一堆状态，而不是像 DFA 那样使用单个当前状态。动作（shift、reduce 和 goto）由当前位于堆栈顶部的状态控制，shift 和 goto 推送一个新状态，reduce 根据被归约的规则弹出固定数量的状态。在您的示例中，如果我们对列中的状态进行编号（因此 0 是左上角的初始状态，3 是中间列中的状态），我们可以展示它如何解析输入字符串“ab”：

Action              Stack
initial state       0
shift a             0 1
reduce A->a         0
goto A              0 3
shift b             0 3 4
reduce B->b         0 3
goto B              0 3 5
reduce S->AB        0
goto S              0 2
accept

由于这是一个 LR(0) 解析器，每个状态都有 shift/goto 动作或单个 reduce 动作，并且不需要前瞻来知道下一步该做什么（尽管消耗输入令牌的 shift 确实取决于令牌来确定要转移到哪个状态）。

对于输入“aab”，该过程仅稍长一点：

Action              Stack
initial state       0
shift a             0 1
reduce A->a         0
goto A              0 3
shift a             0 3 1
reduce A->a         0 3
goto A              0 3 3
shift b             0 3 3 4
reduce B->b         0 3 3
goto B              0 3 3 5
reduce S->AB        0 3
goto S              0 3 6
reduce B->S         0 3
goto B              0 3 5
reduce S->AB        0
goto S              0 2
accept

显示了右递归规则匹配输入中的多个 a (B -> S -> AB) 的效果，这导致所有 a 被移位（将状态推入堆栈），直到递归序列结束到达，然后是一系列 reduce/goto 操作以将它们弹出。使用左递归规则更好，并使用固定数量的堆栈空间，交替移位和减少。