parsing - 为什么使用解析器生成器而不是可配置解析器？

Question

标题总结了它。据推测，任何可以使用源代码生成解析器生成器(本质上将要解析的语法硬编码到程序中)都可以使用可配置解析器(它将维护待解析的语法)来完成-解析软编码为数据结构)。

我想硬编码的代码生成解析器会在间接级别减少的情况下获得性能奖励，但是必须编译和运行它(或动态语言中的exec()它)的困惑和代码的整体笨拙一代似乎是一个很大的缺点。代码生成解析器还有其他我不知道的好处吗？

我看到代码生成使用的大多数地方都是为了解决语言元编程能力的限制(即 Web 框架、AOP、与数据库的接口(interface))，但整个 lex-parse 看起来非常简单和静态，不需要您从代码生成中获得的任何额外的元编程活力。是什么赋予了？性能优势有那么大吗？

Answer 1

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

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

PG 所做的是做出许多必须在运行时发生的决定(例如，对于 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 类似于通用解析器(例如，Earley 解析器)，x 是语法参数，x0 是特定语法，F' 是一些解析器基础结构 P 和附加由 PG 计算的代码/表，使得 F'=PG(x)+P。

在对您的问题的评论中，似乎有人对为什么不只是在运行时有效地运行解析器生成器感兴趣。简单的答案是，它支付了您希望在运行时摆脱的大部分间接费用。