algorithm - 解析上下文无关文法

Question

我知道自下而上的解析器比自上而下的解析器更好，因为它可以接受左递归语法，我们更喜欢自下而上解析而不是自上而下解析的其他原因是什么？

Answer 1

从理论上讲，对于任何 k，LL(k) 文法始终是 LR(k) 文法的严格子集，因此确定性预测自下而上解析器可以接受比确定性预测自上而下解析器严格更大的文法集。这也意味着任何 LL(k) 文法也是 LR(k)。

此外，一个棘手的证明表明，任何确定性 CFL（确定性下推自动机接受的 CFL）都具有 LR(1) 语法，这意味着 LR 语法与那些具有有效的基于堆栈的解析算法的语言精确对应。

也就是说，如果您允许使用更通用的解析算法，如 Unger 算法、Earley 算法或 CYK 算法，则存在自上而下和自下而上的方法来解析任意 CFG。但是，这些算法可能比预测方法慢得多，因此它们通常不用于编程语言。

希望这可以帮助！

Answer 2

我们有像 byson 这样的自下而上的解析器生成器。使用它们比手动编写解析器要简单得多。
此外，递归下降解析器默认使所有操作右关联，这对于算术是不正确的。将它们转回左关联需要额外的解析步骤。