为什么自下而上的解析比自上而下的解析更普遍? [英] Why is bottom-up parsing more common than top-down parsing?

问题描述

看来递归下降解析器不仅是最简单的解释，而且也是最简单的设计和维护.它们不仅限于LALR(1)语法，而且代码本身可以被凡人理解.相比之下，自底向上的解析器对它们能够识别的语法有限制，并且需要使用特殊工具生成(因为驱动它们的表几乎不可能用手生成).

It seems that recursive-descent parsers are not only the simplest to explain, but also the simplest to design and maintain. They aren't limited to LALR(1) grammars, and the code itself can be understood by mere mortals. In contrast, bottom up parsers have limits on the grammars they are able to recognize, and need to be generated by special tools (because the tables that drive them are next-to-impossible to generate by hand).

那么，为什么自下而上(即递减)解析比自上而下(即递归下降)解析更普遍?

Why then, is bottom-up (i.e. shift-reduce) parsing more common than top-down (i.e. recursive descent) parsing?

推荐答案

如果选择功能强大的解析器生成器，则可以对语法进行编码，而不必担心特殊的属性. (LA)LR意味着您不必担心左递归，也不必担心头痛. GLR意味着您不必担心本地的歧义或超前.

If you choose a powerful parser generator, you can code your grammar without worrying about peculiar properties. (LA)LR means you don't have to worry about left recursion, one less headache. GLR means you don't have to worry about local ambiguity or lookahead.

自下而上的解析器往往效率很高.因此，一旦您付出了一些复杂机器的代价，就可以更容易地编写语法，并且解析器的性能也很好.

And the bottom up parsers tend to be pretty efficient. So, once you've paid the price of a bit of complicated machinery, it is easier to write grammers and the parsers perform well.

您应该期望在通常存在某种编程构造的任何地方都能看到这种选择:如果更容易指定并且执行得很好，即使机器很复杂，复杂的机器也将赢得胜利.再举一个例子，尽管您可以自己手动建立索引文件，但数据库世界已经使用了关系工具.编写数据模式更容易，指定索引也更容易，并且背后有足够复杂的机制(您无需查看齿轮，只需使用齿轮即可)，它们几乎可以毫不费力地快速完成.相同的原因.

You should expect to see this kind of choice whereever there is some programming construct that commonly occurs: if it is easier to specify, and it performs pretty well, even if the machinery is complicated, complex machinery will win. As another example, the database world has gone to relational tools, in spite of the fact that you can hand-build an indexed file yourself. Its easier to write the data schemas, its easier to specify the indexes, and with complicated enough machinery behind (you don't have to look at the gears, you just use them), they can be pretty fast with almost no effort. Same reasons.

这篇关于为什么自下而上的解析比自上而下的解析更普遍?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！