解析上下文无关语法
我知道自下而上的解析器比自上而下的解析器更好，因为它可以接受左递归语法，我们更喜欢自下而上的解析而不是自上而下的解析还有什么其他原因呢？
I know that a bottom-up parser is better than a top-down parser because it can accept left-recursive grammar, what can be other reasons that we prefer bottom-up parsing over top-down parsing?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
从理论上讲，对于任何 k，LL(k) 语法始终是 LR(k) 语法的严格子集，因此确定性预测自下而上解析器可以接受比确定性预测自上而下解析器严格更大的语法集。这也意味着任何 LL(k) 文法也是 LR(k)。
此外，一个棘手的证明表明任何确定性 CFL（确定性下推自动机接受的 CFL）都具有 LR(1) 语法，这意味着 LR 语法精确对应于那些具有高效的基于堆栈的解析算法的语言。
也就是说，如果您允许使用更通用的解析算法，例如 Unger 算法、Earley 算法或 CYK 算法，则可以使用自上而下和自下而上的方法来解析任意 CFG。不过，这些算法可能比预测方法慢得多，因此它们通常不用于编程语言。
希望这有帮助！
Theoretically speaking, the LL(k) grammars are always strict subsets of the LR(k) grammars for any k, so deterministic predictive bottom-up parsers can accept a strictly greater set of grammars than than deterministic predictive top-down parsers. This also means that any LL(k) grammar is also LR(k).
Also, a tricky proof shows that any deterministic CFL (a CFL accepted by a deterministic push down automaton) has an LR(1) grammar, which means that LR grammars correspond precisely to those languages that have efficient stack-based parsing algorithms.
That said, if you allow for more general parsing algorithms like Unger's algorithm, Earley's algorithm, or the CYK algorithm, then top-down and bottom-up methods exist for parsing arbitrary CFGs. These algorithms can be much slower than the predictive methods, though, so they typically aren't used for programming languages.
Hope this helps!
我们有像 byson 这样的自下而上的解析器生成器。使用它们比手动编写解析器要简单得多。
此外，递归下降解析器默认使所有操作都是右关联的，这对于算术来说是不正确的。将它们恢复为左关联需要额外的解析步骤。
We have bottom-up parsers generators like byson. Using them is much simpler then writing parsers manually.
Also, recursive descent parsers make all operations right-associative by default, which is incorrect for arithmetics. Turning them back to left-associative requires additional steps in parsing.