为什么自下而上的解析比自上而下的解析更常见？

Question

为什么自下而上的解析比自上而下的解析更常见？

Bil*_*eal 25 parsing context-free-grammar

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

那么为什么自下而上(即shift-reduce)解析比自上而下(即递归下降)解析更常见？

Answer 1

Ira*_*ter 17

如果您选择一个功能强大的解析器生成器,您可以编写语法代码而无需担心特殊属性.(洛杉矶)LR意味着你不必担心左递归,更少担心头痛.GLR意味着您不必担心本地模糊或前瞻.

而自下而上的解析器往往非常有效.因此,一旦你付出了一些复杂机器的代价,就可以更容易地编写语法并且解析器表现良好.

你应该期望看到这种选择,只要有一些常见的编程结构:如果它更容易指定,并且表现相当好,即使机器很复杂,复杂的机器也会获胜.另一个例子是,数据库世界已经转向关系工具,尽管您可以自己手工构建索引文件.它更容易编写数据模式,更容易指定索引,并且后面有足够复杂的机器(你不必看齿轮,只需使用它们),它们可以非常快速地完成任务.原因相同.

如果列表非常长,它们只会炸掉堆栈,这在实践中非常罕见.递归下降解析器与非常长的递归构造具有完全相同的问题.有些人会说这不是解析器的缺陷,而是使用固定大小的执行堆栈的缺陷,正如Windows或Linux平台上的大多数编程语言所提供的那样.(我们中的一些人使用具有堆分配的激活记录的语言;只有当你的虚拟内存不足时才能"吹掉堆栈"). (4认同)
至少在lex/yacc或flex/bison land中,右递归规则会在shift-reduce解析中使用堆栈.当然,它仍然可以识别语法,但它会表现糟糕.(至少根据[this](http://www.gnu.org/software/bison/manual/html_node/Recursion.html)).也许其他解析器生成器可以更好地处理这个,但我没有使用任何其他类似的工具. (3认同)
抱歉，我错误地使用了“吹出堆栈”——我的意思基本上是消耗大量堆栈空间。我相信 Yacc 和 Bison 都使用堆分配的堆栈来进行移位减少解析（尽管我可能是错的）。 (2认同)

Answer 2

Joh*_*oty 7

它源于几个不同的东西.

BNF(以及语法等理论)来自计算语言学:人们研究自然语言解析.BNF是一种非常有吸引力的描述语法的方式,因此想要使用这些符号来生成解析器是很自然的.

不幸的是,自上而下的解析技术在应用于这样的符号时往往会失败,因为它们无法处理许多常见情况(例如,左递归).这使你得到LR系列,它表现良好并且可以处理语法,并且因为它们是由机器生成的,谁关心代码是什么样的？

不过你是对的:自上而下的解析器更"直观"工作,因此它们更容易调试和维护,一旦你进行了一些练习,它们就像工具生成的那样容易编写.(特别是当你进入转移/减少冲突地狱时.)许多答案谈论解析性能,但实际上,自上而下的解析器通常可以优化为与机器生成的解析器一样快.

这就是为什么许多生产编译器使用手写的词法分析器和解析器.

实际上，对于任何 k，该文法不在 LR(k) 或 LL(k) 中。问题是你不知道在任何时候是执行左边还是右边，因为你不知道是否已经到达字符串的中间。（尝试在一些测试输入上实际运行您的算法，以了解问题：“xxxxx”应该解析，而“xxxxxx”不应该。）当然，当您想说“没有人会写这样的语法”之类的事情时“那么你是对的；实际上，大多数编程语言都非常适合 LR(k)，这就是为什么自下而上的解析如此流行，正如您所问的。 (3认同)
它没有出现在编程语言中,但像"P =('x'P'x')|'x'"这样的产品对于除了最强大的CFG机器之外的所有机器都是有问题的,尽管它完全是明确的. (2认同)
我不明白怎么办。使用递归下降可以毫无问题地解析它。即： P : if (下一项 == 'x') { if (P()) then { 执行第一个分支} else {执行第二个分支} return true;} else { return false; } 如果允许有更多的前瞻标记，那就更简单了。（公平地说，我认为大多数 LALR(1) 解析器生成器也需要很长时间才能完成这样的生成）。但最重要的是，当他们可以写 P: x+ 时，没有人会写这样的语法。 (2认同)

Answer 3

bco*_*sca 6

递归下降解析器试图假设输入字符串的一般结构,这意味着在字符串结束之前会发生大量的反复试验.这使得它们比自下而上的解析器效率低,后者不需要这样的推理引擎.

随着语法复杂性的增加,性能差异变得更大.

归档时间：	15 年，1 月前
查看次数：	10889 次
最近记录：	7 年，9 月前