编程语言解析器的历史主要是解析表达式的棘手挑战，特别是数学表达式，考虑到表达式中运算符的优先顺序。现代形式语言理论始于20世纪50年代诺姆·乔姆斯基(Noam Chomsky)的工作，乔姆斯基在其中为语言学建立了一个数学框架。在这个数学框架下，语言存在于根据语言的难解析性定义的语言世系中。但是计算机程序员需要实用、高效的算法来解析计算机程序，以便翻译成机器代码。20世纪50年代的解析器依赖于特定的逻辑，而不是系统的算法(这一特性一直存在到今天，尽管程度要小得多)。20世纪60年代是解析算法研究的黄金时期，我们今天使用的几乎所有概念和算法都被发现并进行了严格的研究。到20世纪70年代初，解析理论已经发展到这样的地步：Bell Labs/AT&；T的计算机科学家Stephen C.Johnson能够开始开发YACC(现在称为“Yacc”)，“又一个编译器编译器”。2YACC于1975年首次公开描述，随Unix Version 3发布，至今仍在使用。
1961年，荷兰计算机科学家Edsger W.Dijkstra描述的古老的分段码算法部分解决了解析表达式的棘手挑战，该算法可以高效地解析具有值堆栈和运算符堆栈的二进制中缀运算符表达式，从下到上创建节点。Vaughan R.Pratt将Dijkstra的Sunting-Yard算法推广到整个语言的解析，这一次使用单个堆栈，或者使用递归下降将调用堆栈作为隐式堆栈，自上而下创建节点。Pratt的解析算法克服了调车码算法的一些限制，并且更简单。
优先级攀登显然是由Martin Richards在1979年为他的BCPL编译器首次发明的。优先级攀升使用单个递归函数和单个表将令牌ID映射到它们的优先级，而不是Pratt的相互递归下降和多个表。事实上，优先级攀升可以被视为Pratt解析的特例，尽管在历史上它们被理解为相关的，但并不相同。5、6。
Vaughan Pratt在6年前的1973年在POPL的第一次会议上描述了他的算法，这是编程语言原理研讨会，至今仍是该领域最重要的会议之一。有趣的是，1973年的POPL学报上还发表了哪些其他论文。例如，在其他几位有影响力的名人的论文中，人们可以找到，例如，Aho，S.C.Johnson和J.D.Ullman的“歧义语法的确定性解析”7和小詹姆斯·H·莫里斯的“Types Are Not Set”8。Vaughan Pratt一直在为MACLISP开发另一种名为CGOL的表达式语法，9他需要对其进行解析。
网络上已经有很多文章描述了Pratt解析算法。(我推荐5个。)。如果您不熟悉算法，请在返回这里之前先阅读一下。
典型的面向对象设计是为每种AST节点都有一个节点类，每个类实现自己的“parselet”方法，传统上命名为led，以表示在Pratt的原始文章之后的“左捐赠”，该方法由驱动程序算法调用，负责通过在返回之前回调到驱动程序来解析节点实例的操作数(子节点)。每个类还跟踪其关联性和优先级。驱动程序算法使用一个令牌，在表中查找适当的类，创建一个实例并调用其parslet方法。
如果只有少数几个超类对应于每个必需的(词缀、结合性)组合，我们可以稍微提高效率。在典型的面向对象的普拉特解析器设计中，每个操作符都需要表单的子类。
类乘法：public Infix LeftAssoc{Multiply(解析器解析器，ASTNode Left，标记运算符)：优先级(40){SUPER(解析器，左，运算符)；}T MultiplyMethodA(U param1，V param2){...}W MultiplyMethodB(X param1，Y param2){...}//等}
该类将乘法运算符建立为中缀左结合运算符。我们还将运算符优先级初始化为40。同样，InfixLeftAssoc超类和其他祖先类根据优先级和关联性的值计算左和右绑定力(LBP和RBP)，并实现LED方法(“左捐赠”parselette方法)和任何实用方法和成员。此具体子类用于以下目的：
但是我们为什么要使用不同的类呢？此OOP设计有几个缺陷：
它违反了关注点分离的原则：为什么AST节点要做解析器的工作？
它违反了DRY原则：除非您自动生成代码，否则您需要为每个操作符编写一个类-即使您将parslet代码归入少数几个超类。
这种解析器设计充斥着静态数据：操作符、优先级常量、关联性、词缀和令牌ID，所有这些都是多余的，因为它无论如何都存在于驱动程序算法使用的表中。(具有讽刺意味的是，正是因为它的面向对象设计，所以它所操作的代码和数据是如此不同。这并不完全是OOP本身的错，而是对应该将哪些概念物化为对象的糟糕选择。)。
概括前面的一点：此设计在编译时修复了语言。如果要更改运算符的优先级，则需要重写、重新编译和重新部署解析器。
静态地编写操作符表是很麻烦的：除非代码是自动生成的，否则编写“parser.registerOperator(op，prec，assoc，随便什么)”，该行所依赖的代码，以及每个操作符的每个子类都很糟糕。即使您自动生成代码，也必须编写代码生成器。
❝编写代码生成器的诱惑通常是存在更灵活设计的标志，这种设计利用代码中存在的任何规律性，使以编程方式生成代码成为可能。❞
编写代码生成器的诱惑通常是存在更灵活设计的迹象，这种设计利用了代码中存在的任何规律性，这些规律性首先使以编程方式生成代码成为可能。原则上，如果代码可以自动生成，也可以自动编译和执行。因此，也许可以重构(假设的)生成-编译-运行流水线(通常称为JIT或抖动)，以消除编译步骤。在我们的例子中，与其编写一个定制的Pratt解析器，在其中操作符表格既在类层次结构中编码，又在运行时再次生成，为什么不编写一个在启动时读取操作符数据库的通用Pratt解析器呢？另外，修改语言不需要重新编译：如果愿意，您可以在运行时添加、删除或修改操作符，维护表达式语法就像编辑电子表格中的值一样简单。(事实上，可能真的是这样！)。
TokenID可能由词法分析器/扫描器提供(许多PRATT解析器是无扫描器的)，并将用作标识符。运算符和NameString仅用于打印输出。剩余的列需要计算每个运算符的左和右结合幂。在此示例语言中，每个运算符要么是终端(数字)，要么是二元中缀运算符。
假设我们有三进制、混合修复或匹配修复运算符。然后，我们需要修改运算符数据库，以反映运算符标记在表达式中的显示方式。我们的操作员表的一部分现在可能如下所示。
在此设计中，数据库包括运算符的哪些标记可以接受左操作数(LToken)、可以开始表达式(无左操作数NToken)或包含在某个其他位置(OToken)。
LToken、NToken、OToken、AFIX和ARY都可以从单个示例用法中推断出来，例如：op1？OP2：OP3这表明可能有一种方法只使用示例就可以为表达式语言生成解析器。的确，有！
为了重申这一点，此操作员表可能位于纯文本CSV文件中。在启动时(而不是在编译时)，Pratt解析器读取运算符表。AST节点通过其TokenID(实际上是操作员ID)或字符串表示来了解其身份，并通过动态分派执行特定于身份的操作。
最后那句话应该引起你的怀疑。我认为，这种设计的一个基本好处是，它使您不必为每个操作符编写样板。我们只是将样板从操作符AST子类转移到跳转表实现吗？
不是的。除非计算机能够读懂我们的思想，否则就没有办法编写特定于操作员的代码。但是我们避免编写周围的类定义和用于静态定义运算符表的任何代码。后者被一个简单而通用的函数所取代，该函数将表从磁盘读入内存。有几种替代方案可以取代前者。
我们需要的是一种机制，允许在运行时创建/加载新函数，并将其与操作员操作相关联。然后，程序将动态分派调用，在运行时为每个操作员选择适当的函数。因为要调用哪个函数的选择和可用函数选择集都是在运行时确定的，所以让我们调用这个双重动态分派。定期的动态调度既古老又常见：一个简单的跳台就可以了。动态编程语言的解释器通常实现某种双重动态分派，通常有两种不同的形式：例如，通过调用用解释语言动态创建的函数，以及通过调用用C编写的外部库函数。使用哪种技术将取决于操作员特定功能的性质。举两个例子：
如果特定于运算符的函数可以分解成简单的原语，比如AST转换，那么可以用组合器或简单状态机可以使用的编码来描述它们。这本质上是一种几乎不加掩饰的DSL，在哲学上与调用在解释语言中动态创建的函数相对应。
使用实现运算符操作的预定API动态加载预编译函数库，指向该API的指针可以存储在查找表中。这就是解释语言实现其FFI的方式。
这两种技术都不像看起来那么困难。别让他们吓倒你。
这个理论比我在这里所能表达的要丰富得多。它存在于语言学、数学和计算机科学的交汇处，非常令人着迷。计算机科学家杰弗里·凯格勒称乔姆斯基的书“句法结构”是“有史以来最重要的书之一”。乔姆斯基，诺姆。1957年。三种句法结构。Mouton&Amp；Co.，1957年。↩。
请看杰弗里·凯格勒迷人的“解析：时间线”一书，我的大部分历史信息都是从这本书中衍生出来的。--↩。
这个名字说明了当时编译器构建的最先进水平，因为贝尔实验室还在使用其他几个“编译器编译器”。斯蒂芬·C·约翰逊，1975。“Yacc：又一个编译器-编译器”。美国电话电报公司贝尔实验室技术报告。美国电话电报公司贝尔实验室，新泽西州默里希尔，07974(32)。检索于2018年12月22日。-↩。
题名/责任者：A.V.Aho，S.C.Johnson和J.D.Ullman。1973年。歧义语法的确定性分析。在第一届ACM SIGACT-SIGPLAN编程语言原理研讨会(POPL‘73)的论文集上。ACM，纽约，纽约州，美国，1-21。Doi=http://dx.doi.org/10.1145/512927.512928和↩
詹姆斯·H·莫里斯，Jr.。1973年。类型不是集合。在第一届ACM SIGACT-SIGPLAN编程语言原理研讨会(POPL‘73)的论文集上。ACM，纽约，纽约州，美国，邮编：120-124。Doi=http://dx.doi.org/10.1145/512927.512938和↩。
普雷特，沃恩，1976年出版。CGOL：LISP用户的替代外部表示。人工智能工作论文121，麻省理工学院人工智能实验室，剑桥，马萨诸塞州，1976年3月。在线：https://dspace.mit.edu/bitstream/handle/1721.1/41951/AI_WP_121.pdf?sequence=1.和↩