解析：时间线(2014)

1960年：ALGOL 60规范问世。它第一次指定了块结构语言。ALGOL委员会很清楚，没有人知道如何解析这样的语言。但他们相信，如果他们指定一种块结构语言，就会发明一种解析器。尽管这种方法有风险，但它是值得的.。

1961年：奈德·艾伦斯出版了他的ALGOL解析器。事实上，Irons解析器是第一个用印刷体描述的任何类型的解析器。奈德的算法是左解析器--递归下降的一种形式。与现代递归下降不同，Irons算法是通用的和语法驱动的。"；General"；意味着它可以解析用BNF编写的任何内容。语法驱动(也称为声明性)意味着解析器实际上是从BNF创建的-解析器不需要手工编写。

1961年：几乎同时，出现了手工编码的左解析方法。我们现在会认为这是递归下降。在接下来的几年里，与语法驱动的算法相比，手工编码的方法将更受左翼解析器的欢迎。有三个因素在起作用：在20世纪60年代，内存和CPU都极其有限。手工编码是值得的，即使收益很小。纯左解析是一种非常弱的解析技术。手工编码通常是必要的，以克服其局限性。这在今天和1961年一样真实。左解析与手工编码结合使用效果很好--它们非常适合。

1965年：Don Knuth发明了LR解析。努斯主要对数学感兴趣。他描述了一种解析算法，但它被认为是不实用的。

1968年：杰伊·厄利发明了以他的名字命名的算法。和Irons算法一样，Earley的算法也是语法驱动的，并且完全通用。与Irons算法不同的是，它不会回溯。Earley的核心思想是在表格中跟踪有关解析的一切。厄利的算法很诱人，但它有三个主要问题：第一，零长度规则的处理存在缺陷。其次，对于右递归，它是二次型的。第三，按照1968年硬件的标准，建立表格所需的簿记是令人望而生畏的。

1969年：Frank DeRemer描述了Knuth的LR解析的一个新变体。DeRemer的LALR算法只需要一个堆栈和一个大小相当可管理的状态表。

1972年：Aho和Ullmann描述了对Earley原始算法中零长度规则缺陷的直接修复。不幸的是，这个修复涉及到给Earley增加更多的记账功能。1975：贝尔实验室将其C编译器从手写的递归下降转换为DeRemer的LALR算法。

1977年：第一本“龙”书问世。这本即将成为经典的教科书是以封面上的一幅画命名的，在这幅画中，一名骑士与龙展开了较量。骑士长矛上的徽章上印有字母#34；LALR&34；。从现在开始，轻描淡写地谈论LALR将会玷污解析理论的盾牌。

1987年：Larry Wall介绍了Perl1。Perl接受了前所未有的复杂性。Larry非常积极地使用LALR--据我所知，无论是以前还是之后，他都比任何人都更积极地使用LALR。

1991年：Joop Leo在Earley的算法中发现了一种加速右递归的方法。Leo'；的算法对于几乎所有实际感兴趣的无歧义语法，以及许多歧义语法都是线性的。在1991年，硬件比1968年的硬件快了6个数量级，所以记账费用的问题已经变得不那么重要了。这是一项重大发现。当谈到速度时，游戏已经改变，有利于厄利算法。但是厄利解析几乎被遗忘了。还需要20年的时间，才会有人写出利奥算法的实际实现。

1990年：厄利被遗忘了。所以LALR-LAND的每个人都很满意，对吗？不对。事实上，远非如此。LALR的用户正在做出令人不快的发现。虽然LALR自动生成它们的解析器，但调试它们是如此困难，以至于可以很容易地手工编写解析器。一旦经过调试，他们的LALR解析器就可以快速地进行正确的输入。但他们告诉用户的关于错误输入的几乎所有信息都是不正确的。用拉里的话说，LALR是快速但愚蠢的。

2000年：Larry Wall决定彻底重新实现Perl--Perl6。Larry甚至没有考虑再次使用LALR。

2002年：Aycock&；Horspool出版了他们对快速、实用的Earley解析器的尝试。乔普·利奥(Joop Leo)的进步却从中消失了--他们似乎并没有意识到这一点。他们自己的加速效果是有限的，而且它带来的复杂性在评估时可能会适得其反。但他们的论文中埋藏着一个解决零长度规则缺陷的方案。这一次，解决方案不需要额外的簿记。

2006年：GNU宣布GCC编译器的解析器已经被重写。三十年来，业界的旗舰C编译器一直使用LALR作为它们的解析器--这证明了LALR和认真解析是等价的。现在，GNU用它在25年前取代的技术取代了LALR：递归下降。

2000年到今天：随着LALR的撤退，解析理论的威望崩溃了。半个世纪之后，我们似乎又回到了起点。如果你采用Ned Iron 1961年最初的算法，更改名称和日期，并从汇编语言和ALGOL的混合代码翻译成Haskell，你很容易在今天重新发布它，并将其标榜为革命性和新颖性。

多年来，我一次又一次地回到厄利的算法上。大约在2010年左右，我意识到最初放弃已久的愿景--高效、实用、通用和语法驱动的解析器--现在实际上很有可能实现。必要的部分已经就位了。

Aycock&；Hospool已经解决了零长度规则缺陷。Joop Leo已经找到了右递归的加速比。而簿记管理费用的问题几乎已经自行烟消云散了。机器操作现在比1968年快了10亿倍，而且可能在任何情况下都不再相关--缓存未命中现在是瓶颈。

但是，当厄利最初的问题消失时，一个新的问题出现了。有了像Earley那样强大的解析算法支持，语法驱动的方法可以比使用左侧解析器做更多的事情。但是，随着集体意识中对LALR的体验，很少有现代程序员准备信任纯粹的声明式解析器。正如林肯所说，一旦一只猫被烧伤，他甚至不会坐在冰冷的炉子上。

要被接受，MARPA需要允许过程解析，而不仅仅是声明性解析。因此，MARPA允许用户指定声明性解析暂停的事件--符号和规则的出现。暂停时，应用程序可以逐个令牌调用过程逻辑和单步前进。过程逻辑可以在它喜欢的任何时候将控制权交还给语法驱动的解析。Earley表可以为过程逻辑提供到目前为止解析状态的全部知识：到目前为止在所有可能的解析中识别的所有规则，以及预期的所有符号。厄利的算法现在比递归下降更适合手写过程逻辑。

有关MARPA的更多信息，请访问由Ron Savage维护的官方网站。我还有一个MARPA网站。关于这篇文章的评论可以在MARPA的谷歌群中发表。