8.1 分析器组合子

在第7章的时候，我们把语法分析器定义成一个作用于输入流，并将词法单元集合的引擎。它能在符号流中识别分析器认可的有效语言成分，或者在遇到无效符号的时候立即中止当前输入。无论哪种情况，分析器都返回一个（或成功或失败的）结果，同时返回尚未处理的剩余输入流。

如果分析器返回成功的结果，我们可以将剩余输入流送入另一个分析器继续处理。如果返回失败结果，我们可以回退到输入流的开头位置，尝试用另一个分析器来处理它。鉴于分析器自身的工作模式，可以将多个分析器按不同方式串联起来，实现对输入流的完整分析。图8-2描绘了将多个分析器组合起来，共同处理输入流的情形。

enter image description here

图8-2　串联起来的分析器。分析器1处理一部分输入流，分析器2处理分析器1余下的部分。这两个分析器组合而成的分析器，其返回结果也是原来两个返回结果的组合。只有当分析器1和分析器2都成功匹配其输入时，组合后的分析器才返回成功结果

本节将建立一种分析器的使用思路，即分析器是对它所识别的语言的一种函数式抽象。由于分析器是其输入的函数，所以可以一个一个地组合成别的分析器，而且每次组合都是DSL语法的一次扩增。对于能完成这样的组合的高阶函数，我们赋予它一个正式的名称：分析器组合子。

8.1.1 什么是分析器组合子

我们以函数式的思路来考虑分析器的组合问题。在函数式编程中，分析器是一个接受输入并产生结果的函数。分析器组合子允许我们单纯以组合的方式，将高阶函数（又叫做组合子）搭建成各式文法结构，如顺序、重复、可选项、分支选择等。如果宿主语言支持中缀运算符写法，那么用分析器组合子写出来的文法规则，看起来就像EBNF产生式的样子。

用组合子来分析语法，最大的好处在于能够提高组合性；少数基本的分析器经过函数式的组合，即可构成更大更复杂的分析器（本书附录A阐述了组合性特质的优点）。组合子的编排就像搭积木，我们从小块的材料开始，逐渐搭出高阶的结构。图8-2就是一个顺序组合子在履行它的搭建工作。

把搭积木的思路推广到DSL设计上，我们先用分析器组合子组合出一些小的语言片段，作为对DSL语法局部的建模，再由这些片段拼出完整的DSL结构。图8-2的顺序组合子只是众多组合子中的一种，图上它正在将两个DSL语法分析器顺序地连接起来。任何组合子库都会包含各式各样的组合子，就像一套积木里有不同的形状。我们从几个常用的组合子说起，看它们怎样处理输入流和识别语言文法，详见表8-1。

表8-1　常用的分析器组合子

组合子 组合方式
顺序 用于构造顺序结构的分析器组合子。若分析器P和Q以顺序组合子相连接，则当出现以下情况时，认为分析是成功的 - P成功处理一部分输入流； - Q跟在P之后处理P未处理的剩余输入；
替代 用于构造替代结构的分析器组合子。若分析器P和Q以替代组合子相连接，则当P或Q其中之一在以下情况下成功时，认为分析是成功的 - P先处理输入流。若P成功，则分析是成功的； - 若P失败，则输入流回退到P开始处理之前的位置，换由Q来处理同一输入流； - 若Q成功，则分析是成功的；否则分析失败；
函数施用 这个组合子在分析器上应用一个函数，结果产生一个新的分析器
重复 当重复组合子作用于分析器P时，返回另一个分析器，其分析对象是P的分析对象的一次或多次重复。有时候，重复组合子还允许重复模式与分隔符交错的情况 例如，P可分析字符串abc，对P应用重复组合子后产生的分析器，将能够分析abc的重复"abcacabc"…，或者允许模式abc与空格交错出现，即abc abc abc…

仅仅知道这几个基本的组合子，还不够用于讨论DSL的具体实现。我们要先学习怎样用分析器组合子来设计外部DSL。

8.1.2 按照分析器组合子的方式设计DSL

第7章我们在设计外部DSL时，自行建立了一套语言处理设施。由于手工实现分析器工作量巨大又容易出错，代码还常常膨胀到失控的地步，所以我们决定借助ANTLR和Xtext等外部框架。在外部框架的参与下，会形成如图8-3所示的实现架构。

enter image description here

图8-3　使用ANTLR等外部分析器生成器来设计外部DSL的实现架构。生成器产生分析器，分析器分析DSL脚本并生成应用的语义模型

图上的架构并不是一个坏的架构，相反，它是当前使用最为普遍的外部DSL设计范式。自从LEX、YACC那一代语言处理工具走出AT&T实验室以来，开发者们一直在沿用相同的架构风格。

虽然这个架构久经考验，但并不意味着我们不能通过探索找到更新更好的DSL实现方式。图8-3的架构有一个明显的缺点，就是这样实现出来的DSL具有外部依赖。分析器生成器作为一个外部实体（如图中所见），我们需要用它不同于宿主语言的语法来定义DSL的EBNF规则（请回忆一下第7章的EBNF知识），这就使得学习曲线更为陡峭。生成器生成的分析器代码结构是静态的，完全依赖于生成器内部的实现，用户没有多少调整定制的余地。

用分析器组合子来设计DSL是一种完全不同的体验。我们可以沉浸在宿主语言的抽象氛围里定义文法规则，用高阶函数定义DSL的语法，用库里预备的组合子添加定制动作。具体的细节我们会在后续章节内详细解说。从图8-4可以窥见宿主语言内生的分析器组合子对简化实现架构的成效。

enter image description here

图8-4　使用分析器组合子来设计外部DSL的实现架构。定义文法规则和定制动作时，完全不需要越出宿主语言的设施范围之外

在新的架构下，DSL不存在对外部框架的依赖。仅有的先决条件，是宿主语言必须提供一套分析器组合子库。相对而言，分析器组合子是DSL实现领域的新成员。不少现代语言，如Haskell、Scala和 Newspeak都在其核心语言上，以库的形式提供分析器组合子功能。你将在本章的学习过程中发现，分析器组合子蕴含了对函数式编程思维精彩而新颖的运用。我们要揭开它是怎么做到设计DSL时简洁而不失表现力的。

定义　Newspeak是由 Gilad Bracha设计的一种沿袭Self和Smalltalk语言传统的编程语言。关于这种语言的详情请参阅http://newspeaklanguage.org

下一节，我们将认识Scala的分析器组合子库，这个库以纯函数式的方式提供强大的外部DSL设计能力。我们定义的每一个分析器都是对DSL语法的一个小成分的建模，组合子像胶水一样把所有的成分连接起来，赋予它们语义。