4

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

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

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

语法：

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

桌子： LR表

评估： LR评估

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

  1. 我对“前瞻”定义的假设（前瞻 = 未使用输入令牌）是错误的。对于 LL 解析器或 LR 解析器，前瞻只是意味着两种不同的东西。如果是这样，那么如何定义“前瞻”呢？

  2. LR 解析器（从理论的角度来看，当您使用下推自动机时）具有额外的内部状态，它们通过将输入标记放在堆栈上来消耗输入标记，因此只需查看即可做出移位减少决策在堆栈上。

  3. 上面显示的评估是 LR(1)。如果为真，LR(0) 评估会是什么样子？

现在什么是正确的，1、2 或 3 还是完全不同的？

4

1 回答 1

7

准确很重要：

LR ( k ) 解析器使用当前解析器状态和k前瞻符号来决定是否减少，如果是，则由哪个产生式来决定。

它还使用移位转换表来决定在移位下一个输入标记后它应该移动到哪个解析状态。无论k的值如何，移位转换表都由当前状态和正在移位的（单个）令牌作为键。

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

如果在给定的解析器状态下，不可能进行归约并且下一个输入符号无法移动（即，该输入符号的该状态没有转换），则解析失败并且算法终止。

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

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

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

  • 如果栈顶是非终结符，则将栈顶替换为该非终结符的一个产生式，使用接下来的k个输入符号来决定哪一个（不移动输入光标），然后继续。

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

  • 如果堆栈为空，则解析成功并且算法完成。（我们假设输入末尾有一个唯一的 EOF 标记$ 。）

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

如果k为 0，则：

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

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

于 2015-03-14T18:52:11.417 回答