为什么解析器生成器而不仅仅是可配置的解析器？

Question

标题总结了这一点。可以用源代码生成解析器生成器(实质上是将要解析的语法硬编码到程序中)所能做的任何事情，都可以用一个可配置的解析器来完成(它将把要解析的语法作为数据结构进行软编码)。

我认为硬编码的代码生成解析器将会有一个性能上的优势，减少一个间接级别，但是必须编译和运行它(或者在动态语言中exec()它)的混乱，以及代码生成的整体笨拙似乎是一个相当大的缺点。有没有其他我不知道的生成解析器的好处？

我看到的大多数代码生成的地方都是为了绕过语言元编程能力的限制(即web框架，AOP，与数据库的接口)，但是整个lex-parse的事情看起来非常简单和静态，不需要你从代码生成中获得的任何额外的元编程动态性。怎么回事？性能优势有那么大吗？

Answer 1

如果您想要的只是一个解析器，您可以通过向它传递语法规则来配置它，这是可以实现的。只要给定一组规则，Earley解析器就可以解析任何上下文无关的语言。代价是重要的执行时间: O(N^3)，其中N是输入的长度。如果N很大(对于许多可解析的实体来说也是如此)，您可能会以非常慢的解析结束。

这就是解析器生成器(PG)的原因。如果你解析了很多文档，那么解析速度慢是个坏消息。编译器是人们解析大量文档的程序，没有程序员(或他的经理)希望程序员等待编译器。还有很多其他东西需要解析: SQL查询、JSON文档……所有这些都有“没有人愿意等待”的属性。

PGs所做的是采取许多必须在运行时发生的决策(例如，对于Earley解析器)，并在解析器生成时预先计算这些结果。因此，LALR(1) PG (例如，Bison)将生成在O(N)时间内运行的解析器，这在实际环境中显然要快得多。(ANTLR为LL(k)解析器做了类似的事情)。如果您想要完整的上下文无关的解析，通常是线性的，您可以使用一种称为GLR parsing的LR解析变体；这为您带来了“可配置”(Earley)解析器的便利，具有更好的典型性能。

这种预先计算的想法通常被称为partial evaluation，即，给定一个函数F(x，y)，并且知道x总是某个常数x_0，计算一个新函数F'( y) =F(x0，y)，其中仅依赖于x的值来预先计算决策和计算。F‘通常比F快得多。在我们的例子中，F类似于一般解析(例如，厄利解析器)，x是语法参数，x0是特定语法，F’是由PG计算的一些解析器基础结构P和附加代码/表，使得F'=PG(x)+P。

在对你的问题的评论中，似乎有一些有趣的问题，为什么不在运行时直接运行解析器生成器。简单的答案是，它支付了你想要在运行时摆脱的开销的很大一部分。