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

Question

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

parsinglexical-analysis

14

标题已经概括了问题。假设使用源代码生成的解析器生成器（其将要解析的语法硬编码到程序中）所能实现的任何功能，都可以通过可配置解析器来实现（该解析器将要解析的语法以数据结构的形式保存）。

我想，硬编码的代码生成解析器将具有性能优势，因为少了一层间接引用，但是编译和运行它（或在动态语言中使用exec() ）及代码生成过程的混乱似乎是一个很大的缺点。除此之外，是否还有其他使用代码生成解析器的好处？

我看到大多数使用代码生成的地方都是为了解决语言元编程能力的限制（即Web框架、AOP、与数据库交互等），但整个词法分析过程似乎非常简单和静态，不需要从代码生成获得的额外元编程动态性。怎么回事？难道性能优势如此巨大吗？

- Li Haoyi

1

@BartKiers：虽然如此，由解析器生成器生成的解析器是否比生成器本身更复杂或通用呢？换句话说，如果解析器生成器可以生成足够复杂的代码来解析某些东西，为什么它不能只是生成代码，编译并在内存中执行代码以立即解析它呢？这不等同于直接解析它吗？（可能不是这样，因为解析器生成器确实存在，我只是不知道为什么） - Li Haoyi

1

通过一些努力，可以获得由lex和yacc（flex和bison）生成的表格，并在非标准框架中使用它们。最大的问题是连接用户提供的操作。 - wildplasser

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

如果你只需要一个可以通过提供语法规则进行配置的解析器，那是可以实现的。Earley解析器将解析任何上下文无关语言，只需一组规则即可。代价是显著的执行时间：O(N^3)，其中N是输入的长度。如果N很大（对于许多可解析实体来说是这样），你可能会得到非常慢的解析结果。

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

PG（Parser Generator）的作用是在解析器生成时预先计算许多需要在运行时进行决策的结果（例如，对于Earley解析器）。因此，LALR（1）PG（例如Bison）将生成在O（N）时间内运行的解析器，在实际情况下显然更快。（ANTLR为LL（k）解析器执行类似操作）。如果您想要完全的上下文无关分析，通常可以使用一种名为GLR parsing的LR分析器变体；这为您提供了“可配置”的（Earley）解析器的便利性，并具有更好的典型性能。

这种预先计算的想法通常被称为部分求值，即给定一个函数F（x，y），并且知道x始终是某个常数x0，计算一个新函数F'（y）= F（x0，y），其中仅依赖于x值的决策和计算已经预先计算。 F'通常比F运行得快。在我们的情况下，F类似于通用解析（例如Earley解析器），x是一个语法参数，x0是特定的语法，而F'是由PG计算的一些解析器基础设施P和附加代码/表格，使得F'=PG(x)+P。

在您的问题的评论中，似乎有人对为什么不只在运行时运行解析器生成器感兴趣。简单的答案是，在运行时执行它会支付你想要消除的开销的重要部分。