parsing - LL 和 LR 解析的区别

Question

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

标签： parsingcontext-free-grammarlllr

Answer 1

据我了解，上下文无关语法可以通过自顶向下/LL 或自底向上/LR 进行解析。

是的，LL 解析是自上而下的。LR 解析通常被认为是一种自下而上的解析方法，尽管一些作者认为它是自上而下和自下而上的混合体，因为它使用关于在生成的解析树中可能出现的内容的上下文。

是否正确理解，LL 解析器要求语法在解析之前具有严格明确的生产规则？

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

另一方面，LR 解析器也要求语法是明确的，但不必重写任何不明确的产生式规则，可以在产生式规则中添加额外的优先级规则来解决它们的歧义性？

是的，没有。确实，像 LL 解析器一样，最常见的 LR 解析器类型（LR(0)、SLR(1)、LALR(1)、LR(1)、IELR(1)）要求语法是明确的。你是正确的，许多歧义可以通过优先声明来解决，否则会导致歧义语法，但这不能解决所有歧义。此外，还有一些明确的语法不能被任何 LR(k) 解析器解析。

但是，展望未来如何适应这一切呢？

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