LL和LR句法分析的差异

Question

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

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) parsers有一些在LR(1)解析器中没有显示的细微差别。通过专门阅读LL(1)解析、LR(0)解析和LR(1)解析，您可能会找到正在寻找的信息，并且可以将其用作启动点。