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

Question

标题总结了它.据推测,任何可以通过源代码生成解析器生成器(基本上将要解析的语法硬编码到程序中)完成的任何事情都可以通过可配置的解析器来完成(这将保持语法准备) - 经过软编码作为数据结构).

我认为硬编码的代码生成解析器将具有一个较低级别的间接性能,但是必须编译和运行它(或者exec()在动态语言中)以及代码生成的总体笨拙的混乱似乎相当大的缺点.代码生成您的解析器还有其他任何我不知道的好处吗？

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

Answer 1

如果你想要的只是一个解析器,你可以通过交配语法规则来配置,这可以完成.一个厄雷解析器将解析仅给定一组规则的任何上下文无关语言.价格是重要的执行时间:O(N ^ 3),其中N是输入的长度.如果N很大(就像许多可解析的实体一样),你可以以非常慢的解析结束.

这就是解析器生成器(PG)的原因.如果解析大量文档,慢速解析就是坏消息.编译器是人们解析大量文档的程序,没有程序员(或他的经理)希望程序员等待编译器.还有很多其他要解析的东西:SQL查询,JSON文档......所有这些都有"没有人愿意等待"的财产.

PG做的是做出许多必须在运行时发生的决定(例如,对于Earley解析器),并在解析器生成时预先计算这些结果.因此,LALR(1)PG(例如,Bison)将生成在O(N)时间内运行的解析器,并且在实际情况下显然更快.(ANTLR对LL(k)解析器执行类似的操作).如果您想要通常是线性的完全上下文自由解析,您可以使用称为GLR解析的LR解析变体; 这为您带来了"可配置"(Earley)解析器的便利性,具有更好的典型性能.

这种预先预先计算的想法通常被称为部分评估,即给定函数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.

在你的问题的评论中,似乎有一些兴趣,为什么一个人不只是在运行时运行解析器生成器.简单的答案是,它支付了你想要在运行时摆脱的开销成本的很大一部分.