为什么存在LR(0)分析器但不存在LL(0)分析器？

Question

我在维基百科上阅读了有关LL(0)和LR(0)解析器的内容，发现虽然存在LR(0)解析器，但并不存在LL(0)解析器。

根据我的理解，LL(k)/LR(k)中的k代表解析器可以查看当前正在处理的字符之后多少个字符。

那么我的问题是，为什么尽管存在LR(0)，却没有LL(0)解析器呢？

- Shmoopy

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)。

希望这可以帮助你！

- templatetypedef

---

你的解释听起来很有趣，但对我来说并不完全清晰。按照定义，LL(0)可以查看0个输入标记以决定选择哪个产生式。所以你的意思是它只能回顾性地看到输入（如编码在其状态中），因此只能“处理”生成单个终端符号的语法吗？ - Eli Bendersky

在LL(0)语法中，解析器根据句子形式中剩余的下一个符号来决定是执行预测步骤还是匹配步骤。如果它是终端，则执行匹配步骤。如果它是非终端，则基于该非终端执行预测步骤。在执行预测步骤时，解析器查看输入流的下一个0个标记以确定要使用哪个产生式。因此，解析器必须能够根据句子形式中的非终端唯一确定要使用哪个产生式，而不需要查看输入。这有意义吗？ - templatetypedef

LL(0)解析器不就像递归下降解析器吗？ - Michael Ho Chum

@MichaelHoChum 不是很准确。LL解析器在进行预测时总是会确定一个固定的产生式，因此LL(0)解析器必须完全猜测正确使用哪些产生式，而不能根据输入得到反馈。LL(1)更接近递归下降，但没有回溯。 - templatetypedef

@templatetypedef 假设文法为 S->aA | bB，A-> 某些内容，B-> 某些内容。假设解析器是LL(0)，输入为ab。在开始时，我们将S放入栈中。现在，LL(0)解析器不需要向前看符号来决定选择哪个产生式，因为它可以基于当前符号本身（即a）来进行决策。因此，它会选择产生式S->aA。所以我不明白为什么你说该语言只有一个字符串或者解析器会一直循环。 - Jamāl