parsing - 为什么有 LR(0) 解析器而没有 LL(0) 解析器？

Question

我一直在 Wikipedia 中阅读这两个内容，并注意到尽管存在 LR(0) 解析器，但没有 LL(0) 解析器之类的东西。

从我读到的内容，我了解到 LL(k)/LR(k) 中的 k 表示解析器可以在当前正在处理的当前字符之外看到多少个字符。

所以我的问题是，为什么没有 LL(0) 解析器之类的东西，即使 LR(0) 存在？

Answer 1

差异与 LR(k) 与 LL(k) 中 k 的含义有关。

在 LL(k) 中，解析器维护有关自上而下、从左到右的解析的信息，该解析追踪最左边的推导。解析器通过反复查看当前的非终结符来工作，然后检查输入流的下 k 个标记以确定应该使用哪个产生式。因此，如果您有一个 LL(0) 解析器，则解析器必须完全根据当前的非终结符来预测要使用的产生式。这只有在每个非终结符只有一个与之关联的产生式时才有可能，这意味着语法要么只产生一个字符串，要么根本不产生字符串（通过进入循环）。因此，虽然它在数学上是明确定义的，但在实践中从未使用过 LL(0) 解析。

在 LR(k) 中，解析器自下而上工作。它维护一堆符号以及当前的“状态”，然后不断地决定是执行移位（将另一个符号推到堆栈顶部）还是减少（从堆栈中弹出一些符号并应用产生式）相反）。LL(k) 和 LR(k) 解析器之间的一个关键区别是 LR(k) 解析器如何决定执行哪个操作。在 LR(k) 解析器中，基于前瞻的下 k 个标记和解析器的当前状态来决定下一步做什么。因此，即使 LR(0) 解析器看不到任何前瞻标记，它仍然可以对要执行的操作做出一些明智的决定，因为解析器的当前状态可以编码大量关于在生产中何处执行的信息。解析器是以及它可以实际期望看到的下一个输入标记（即使解析器不能直接查看这些标记）。

简而言之，LL(0) 非常弱，因为解析器必须完全基于当前的非终结符来做出决定，这意味着它不能根据可能使用的产生式采取许多不同的动作之一。LR(0) 解析器非常强大，因为解析器的选择基于其内部状态，内部状态通常足够详细，可以让解析器就下一步做什么做出明智的决定。

LL(0) 弱而 LR(0) 相当强大还有另一个原因。在 LL(0) 解析器中，解析器必须立即决定应该执行哪些产生式，这意味着解析器必须完全盲目地猜测产生式。在 LR(0) 解析器中，解析器可以在决定减少时间之前移动多个符号。因此，解析器在没有任何前瞻的情况下，可以推迟决定使用哪种归约​​，直到它看到足够的输入标记以了解字符串的结构。这是任何 LL(k) 文法自动为 LR(k) 的更普遍事实的特例。

希望这可以帮助！