LR(0) 解析器不也使用前瞻吗？

Question

LL(1)-解析器需要先行符号才能决定使用哪个产生式。这就是为什么我一直认为使用术语 "lookahead" 的原因，当解析器在没有 "consuming" 的情况下查看下一个输入标记时（即它仍然可以通过下一个操作从输入中读取）。然而，LR(0) 解析器让我怀疑这是正确的：

我见过的每个 LR(0)-解析器示例也使用下一个输入标记来决定是移动还是减少。在减少的情况下，输入令牌不会被消耗。

我使用免费软件工具 "ParsingEmu" 生成 LR-table 并在下面对单词 "aab" 执行 LR 评估。如您所见，列头包含标记。从评估中，您可以看到解析器正在通过查看下一个输入标记来决定使用哪个列。但是当解析器在步骤 4 - 6 中减少时，输入不会改变（尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”）。

语法：

S -> A
A -> aA
A -> b

Table:

评价：

由于我的困惑，现在我做了以下假设：

我对 "lookahead" 定义的假设（前瞻 = 输入令牌未被消耗）是错误的。 Lookahead 对 LL 解析器或 LR 解析器意味着两种不同的东西。如果是，那么"lookahead"怎么定义呢？
LR 解析器具有（从理论上的角度来看，当您使用下推自动机时）额外的内部状态，它们通过将输入令牌放入堆栈来消耗输入令牌，因此能够只需查看堆栈即可做出 shift-reduce 决策。
上面显示的评价是LR(1)。如果为真，LR(0) 评估会是什么样子？

现在哪个是正确的，1、2 或 3 还是完全不同的东西？

Answer 1

准确是很重要的：

LR(k) 解析器使用当前解析器状态和 k 前瞻符号决定是否减少，如果是，减少哪种产量。

它还使用移位转换 table 来决定在移位下一个输入标记后应该移动到哪个解析状态。移位转换 table 由当前状态和正在移位的（单个）令牌作为键控，而不管 k.

的值如何

如果在给定的解析器状态下，可能同时产生移位和归约操作，则解析器有 shift/reduce 冲突，并且无效。因此，上述两个确定在理论上可以非确定性地进行。

如果在给定的解析器状态下，无法减少并且无法移动下一个输入符号（即，对于具有该输入符号的状态没有转换），则解析失败并且算法终止.

另一方面，如果移位转换导致指定的接受状态，则解析成功并且算法终止。

这意味着前瞻用于预测应该应用哪个减少（如果有的话）。在 LR(0) 解析器中，必须在读取下一个输入标记之前做出转换（更准确地说，尝试转换）的决定，但是要转换到的状态的计算do 是在读取令牌后进行的，此时如果无法进行移位，它将发出错误信号。

LL(k) 解析器必须在看到非终结符后立即预测哪个产生式会替换非终结符。基本 LL 算法从包含 [S、$]（从上到下）的堆栈开始，并执行以下适用的操作直到完成：

如果栈顶是非终结符，使用下一个 k[= 将栈顶替换为该非终结符的产生式之一67=]输入符号决定哪一个（不移动输入光标），继续

如果栈顶是终端，读取下一个输入令牌。如果是同一个终端，弹出堆栈并继续。否则，解析失败，算法结束。

如果堆栈为空，则解析成功，算法结束。（我们假设在输入的末尾有一个独特的 EOF 标记 $。）

在这两种情况下，先行具有相同的含义：它包括在不移动输入光标的情况下查看输入标记。

如果k为0，则：

LR(k) 解析器必须决定是否在不检查输入的情况下减少，这意味着任何状态都不能有两个不同的 reduce 动作或一个 reduce 和一个 shift 动作。

LL(k) 解析器必须决定给定非终结符的哪个产生式是适用的而不检查输入。实际上，这意味着每个非终结符只能有一个产生式，这意味着语言必须是有限的。

LR(0) 解析器不也使用前瞻吗？

Isn't an LR(0) parser using lookaheads as well?

parsing

compiler-construction

ll

lr

shift-reduce