LL和LR解析之间的区别



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

根据我的理解,上下文无关语法可以通过自顶向下/LL或自下而上/LR进行解析。

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

LL解析器要求语法在解析之前具有严格明确的生成规则,这一理解正确吗?

LL解析器仅适用于无歧义语法。最常见的LL解析器类(LL(1(,LL(*((并不适用于所有语法,并且需要一些额外的限制,除此之外,语法是明确的。例如,LL(1(解析器不能处理左递归。

另一方面,LR解析器也要求语法是明确的,但不必重写任何不明确的生成规则,而是可以在生成规则中添加额外的优先级规则来解决它们的模糊性?

是和否。的确,与LL解析器一样,最常见类型的LR解析器(LR(0(、SLR(1(、LALR(1(,LR(1。您是正确的,许多歧义可以通过优先声明来解决,这些声明打破了歧义语法,但这并不能解决所有歧义。此外,还有一些明确的语法是任何LR(k(解析器都无法解析的。

但展望未来如何适应这一切?

向LL或LR解析器添加前瞻性为解析器提供了更多的上下文,用于决定应用哪些生成规则(对于LL解析器(或是移位还是减少(LR解析器(。直观地说,能够进一步查看令牌序列,解析器就可以排除一些无法工作的选项,因为它们与接下来的选项不匹配。这种前瞻性工作的具体规则取决于解析算法;例如,LR(2(解析器有一些在LR(1(解析器中没有显示的细微差别。您可能会通过专门阅读ll(1(解析、LR(0(解析和LR(1(分析来找到您想要的信息,并可以将其作为启动点。

最新更新