LL 和 LR 解析之间的区别

Question

目前正在研究上下文无关语法及其解析方法。根据我的理解，上下文无关文法可以通过 top down/LL 或 bottom up/LR 来解析。 是否正确理解，LL 解析器要求语法在解析之前具有严格明确的生产规则？另一方面，LR 解析器也要求语法是明确的，但不必重写任何有歧义的产生式规则，而是可以向产生式规则添加额外的优先级规则来解决它们的歧义？但是，展望未来如何适应这一切？

Answer 1

From my understanding, context free grammars can be parsed via top down/LL or bottom up/LR.

是的，LL 解析有效 top-down。 LR 解析通常被认为是一种 bottom-up 解析方法，尽管一些作者认为它是 top-down 和 bottom-up 的混合体，因为它使用关于什么可以出现在生成的解析树中的上下文。

Is it correct understood that, LL parsers require grammars to have strictly unambiguous production rules before it can be parsed?

LL 解析器只适用于明确的语法。最常见的 类 LL 解析器（LL(1)、LL(*)）并不适用于所有语法，并且需要一些额外的限制，但语法是明确的。例如，LL(1) 解析器无法处理左递归。

And that LR parsers, on the other hand, also require grammars to be unambiguous, but instead of having to rewrite any ambiguous productions rules, additional precedence rules can added to the production rules to solve their ambiguity?

是，也不是。诚然，像 LL 解析器一样，最常见类型的 LR 解析器（LR(0)、SLR(1)、LALR(1)、LR(1)、IELR(1)）要求语法是明确的。你是对的，许多歧义可以通过优先声明来解决，这些声明可以打破其他歧义语法，但这不能解决所有歧义。此外，还有一些明确的语法无法被任何 LR(k) 解析器解析。

But how does look ahead fit into all this?

向 LL 或 LR 解析器添加前瞻性为解析器提供了更多上下文来决定应用哪些生产规则（对于 LL 解析器）或是否移动或减少（LR 解析器）。直观地，能够进一步查看标记序列允许解析器排除一些无法工作的选项，因为它们无法匹配接下来的内容。这种先行如何工作的具体规则取决于解析算法；例如， 有一些 LR(1) 解析器中没有的细微差别。通过专门阅读 LL(1) 解析、LR(0) 解析和 LR(1) 解析，您可能会找到您正在寻找的信息，并且可以将其用作启动点。