8.3 用分析器组合子设计DSL的步骤

分析器组合子结合了EBNF文法系统的简洁特性和纯函数的强大组合能力。我们已经讲解了很多分析器组合子的特性，现在可以从一个DSL设计者的角度，试着把它们融汇起来，实际制作一套完整交易指令处理领域专用语言。

我们用不同的宿主语言如Ruby、Groovy和Scala设计过内部DSL，也尝试了分析器生成器和DSL工作台方式下的各种外部DSL设计技法。下面即将要进行的是分析器组合子的实际演练，它会成为我们放在随身工具箱里的又一件得力工具。表8-3是几种不同实现技术的对比表格，在开始设计之前，让我们先看看内部DSL设计方式和两种外部DSL设计方式之间的区别。

表8-3　DSL实现技术的对比

特征 内部DSL 外部 DSL
分析器生成器 分析器组合子
完全在宿主语言内构建 是。可以完全内嵌于宿主语言（如Scala），也可以是生成式的（如Ruby和Lisp） 否。通常需要外部的分析器生成器设施（如LEX、YACC和ANTLR） 是。宿主语言必须支持高阶函数并提供分析器组合子库（如Scala和Haskell）
供最终用户使用的DSL是可直接运行的宿主语言代码 是。DSL产物是宿主语言的方法调用 否。分析设施对DSL作语法分析，然后执行每个符号所关联的函数 否。每个词法单元都被转换成一个Parser实例，然后通过组合子串联起来
最终用户需要掌握宿主语言 基本上是，异常和错误处理要借助宿主语言的设施。而且DSL本身就必须是宿主语言下的有效程序 否。DSL是通过分析器生成器产生的一种全新语言 否。DSL是借用宿主语言提供的语言处理设施建立的一种新语言

希望以上对比能帮助你理清概念。接下来我们就以代码清单8-2的文法设计为基础，按部就班地建立一个完整的语言模型。第一步，我们需要验证一下该文法是否真的能识别我们的语言并生成一棵分析树。

8.3.1 第一步：执行文法

观察代码清单8-2的设计，这段文法已经完整地定义了我们的交易指令处理DSL，能够完全胜任对清单后DSL脚本的分析工作。下面这段程序将依据前面的文法定义处理DSL脚本，并在分析成功时产生输出。

代码清单8-4　运行DSL处理程序

  1. val str = """(100 IBM shares to buy at max 45, 40 Sun shares
  2.   to sell at min 24, 25 CISCO shares to buy at max 56)
  3.   for account "A1234""""
  5. import OrderDsl._
  7. order(new lexical.Scanner(str)) match {  ➊ 调用order分析器
  8.   case Success(order, _) =>
  9.     println(order)  ➋ 分析成功
  10.   case Failure(msg, _) => println("Failure: " + msg)
  11.   case Error(msg, _) => println("Error: " + msg)
  12. }

在这段程序里，我们调用了DSL文法中级别最高的抽象order分析器➊（见代码清单8-2的文法定义）。如果我们输入的脚本分析成功了，那么就把输出打印出来➋；否则打印出分析器产生的错误消息。单纯打印出分析器的默认输出并无太大意义，对于语言的分析也没什么实际作用。在下一小节里，我们会在这个地方生成语义模型。不过现在，你能猜出打印语句➋会输出什么结果吗？

为了找到答案，我们要从分析过程产生的分析树着手。请看图8-8。

enter image description here

图8-8　根据代码清单8-2的文法定义产生的分析树。省略号的部分代表可以出现多个line_item成分。所有成分最终归约为树根处的order节点

这个分析过程与我们在第7章讲解用ANTLR开发外部DSL时介绍的分析过程相同。在分析过程的每一步，我们都把分析结果作为字符串输出。输出内容取决于我们搭建文法时使用的组合子。例如DSL脚本中“100 IBM shares”的部分，负责归约它的文法规则是lazy val security_spec = numericLit ~ (ident <~ "shares")。因为我们用了<~组合子，所以其中的“shares”部分被从输出中刈除。整个片段的分析结果由numericLit和ident的结果顺序组合而成，即输出为(100~IBM)。注意rep1sep组合子会生成一个由所有line_item抽象组成的List。可选项组合子（?）会生成一个Scala语言的Option[]结构。

对图8-5分析树上所有的节点都进行类似的处理之后，我们得到DSL脚本分析成功的最终输出：

  1. (List((((100~IBM)~buy)~(Some(max)~45)),
  2.   (((40~Sun)~sell)~(Some(min)~24)),
  3.   (((25~CISCO)~buy)~(Some(max)~56)))~A1234)

这样一个纯文本的输出，真的能在现实的应用程序里起作用吗？确实不能，将一段由多元组和列表汇聚起来的DSL脚本变成无结构的文本表示，这样的分析成果没有任何现实意义。因此，我们要建立起Order抽象的语义模型，然后在分析过程中利用另外一些组合子向该模型填入实际的内容。

8.3.2 第二步：建立DSL的语义模型

现在我们知道，前面默认的分析结果输出毫无用处，我们需要在应用的上下文里赋予其意义和功用。那么具体应该怎么做呢？答案很简单：我们需要用一个更合适的抽象来充当DSL的语义模型。

为Order抽象建立语义模型并不是难题，但构建好的模型，要怎样结合到分析过程中去呢？

Scala组合子库准备了一些函数施用组合子，可以用在对分析结果的变换操作上。这些组合子帮助我们把语义模型和文法规则集成在一起。我们分析DSL脚本，同时调动这些组合子，一块一块地垒起语义模型。各分析器不再（像代码清单8-2那样）输出默认的返回值，而是返回语义模型需要的属性。这样，当分析过程完成时，作为语义模型的AST也就完整地建立起来了。

下面，我们来详细了解一下这些函数施用组合子。

1.函数施用组合子

Scala有两个函数施用组合子：^^和^^^。跟别的组合子一样，^^和^^^都是Parsers trait里的方法。对于分析器p和函数f，表达式p ^^ f将产生一个识别p的结果的分析器。如果p分析成功，则组合子将对p的结果施用函数f。请思考下面的文法片段：

  1. lazy val order: Parser[Order] = items ~ account_spec ^^
  2.   { case i ~ a => Order(i, a) }

^^组合子对表达式items ~ account_spec的分析结果施用了一个匿名的模式匹配函数。因此order分析器输出的不是默认返回值，而是一个Parser[Order]。值得注意的是，匿名函数返回的本来是一个Order抽象，但由于Parsers trait内定义的隐式转换，被提升为相应的Parser类型。对于这个细节的详细说明可以参看图8-9及其后的解释。

^^^组合子类似于^^组合子，只不过^^是对分析器p的结果施用一个函数f，而^^^则是将分析器p的结果替换为一个指定的取值r。

2.偏函数施用组合子

Scala的偏函数施用组合子是^吗?对于分析器p和偏函数f，表达式p ^? (f, error)产生一个识别p的结果的分析器。如果p分析成功，且f在p的结果上有定义，则组合子对p的结果施用函数f。如果f不适用，出现error并给出相应的理由。

我们的最终目标是解析DSL脚本并建立一个供核心应用使用的领域模型。对于交易指令处理DSL来说，Order抽象即为其中一个核心的领域构造产物。那么下一节，就让我们运用代码清单8-2定义的文法和刚刚学会的几个组合子来建立这个重要的Order抽象。

8.3.3 第三步：设计Order抽象

我们打算自底向上地构建Order抽象，这样随着语法分析的步骤进展，组成抽象的那些构造单元就正好对应地成为一个个AST节点。很容易想到，为了达到这种设想中的效果，我们可以用Scala的case类来建模抽象的构造单元，然后通过函数施用组合子直接将其插入到文法规则之中。（对Scala语言case类的详细介绍参见附录D。）

首先请看下面的Order模型。它既是语义模型，也是分析器要生成的AST。

代码清单8-5　交易指令处理DSL的语义模型

  1. package trading.dsl
  3. object AST {
  4.   trait PriceType
  5.   case object MIN extends PriceType
  6.   case object MAX extends PriceType
  8.   case class PriceSpec(pt: Option[PriceType], price: Int)
  10.   case class SecuritySpec(qty: Int, security: String)
  12.   trait BuySell
  13.   case object BUY extends BuySell
  14.   case object SELL extends BuySell
  16.   case class LineItem(ss: SecuritySpec,
  17.     bs: BuySell, ps: PriceSpec)
  19.   case class Items(lis: Seq[LineItem])
  21.   case class AccountSpec(account: String)
  23.   case class Order(items: Items, as: AccountSpec)
  24. }

这是再普通不过的Scala代码，我们在第6章设计内部DSL的时候就写过很多类似的。清单里的这些类要被分派、插入到各自对应的文法规则里，然后在实际生成AST的时候再汇合起来，组成我们现在看到的样子。

8.3.4 第四步：通过函数施用组合子生成AST

有了语义模型后，我们就可以在分析过程的每一个步骤里添加构造AST所需的Scala组合子。不管通过什么技术手段来处理DSL，最终目标总是产生一个可供应用在别处使用的抽象。

下面的代码清单在代码清单8-2的文法基础上添加了函数施用组合子。

代码清单8-6　交易指令处理DSL的AST

  1. import scala.util.parsing.combinator._
  2. import scala.util.parsing.combinator.syntactical._
  4. object OrderDsl extends StandardTokenParsers {
  5.   lexical.reserved +=
  6.     ("to", "buy", "sell", "min", "max", "for", "account", "shares", "at")
  7.   lexical.delimiters += ("(", ")", ",")
  9.   import AST._   让分析器能够访问语义模型
  11.   lazy val order: Parser[Order] =
  12.     items ~ account_spec ^^ { case i ~ a => Order(i, a) }   函数施用组合子 ^^
  14.   lazy val items: Parser[Items] =
  15.     "(" ~> rep1sep(line_item, ",") <~ ")" ^^ Items
  17.   lazy val line_item: Parser[LineItem] =
  18.     security_spec ~ buy_sell ~ price_spec ^^
  19.       { case s ~ b ~ p => LineItem(s, b, p) }
  21.   lazy val buy_sell: Parser[BuySell] =
  22.     "to" ~> "buy" ^^^ BUY |   函数施用组合子 ^^^
  23.     "to" ~> "sell" ^^^ SELL
  25.   lazy val security_spec: Parser[SecuritySpec] =
  26.     numericLit ~ (ident <~ "shares") ^^
  27.       { case n ~ s => SecuritySpec(n.toInt, s) }
  29.   lazy val price_spec: Parser[PriceSpec] =
  30.     "at" ~> (min_max?) ~ numericLit ^?  ➊ 偏函数施用组合子 ^?
  31.       ({ case m ~ p if p.toInt > 20 => PriceSpec(m, p.toInt) },
  32.         ( m => "price needs to be > 20" ))
  34.   lazy val min_max: Parser[PriceType] =
  35.     "min" ^^^ MIN | "max" ^^^ MAX
  37.   lazy val account_spec: Parser[AccountSpec] =
  38.     "for" ~> "account" ~> stringLit ^^ AccountSpec
  39. }

只要熟悉每个组合子的含义，这段代码基本上是不言自明的。在大多数规则里面，我们用^^组合子解构分析器返回的多元组，并将其嵌入到紧跟其后的匿名模式匹配函数。图8-9对一段文法规则样本的归约过程进行了剖析，从语义的角度解释了幕后发生的活动。

enter image description here

图8-9　一条规则样本从归约过程开始到最终返回Parser[Order]的详细步骤。items和account_spec都是上游的Parser，分别在➊和➋汇入此规则。顺序组合子执行Parser[Items]和Parser[AccountSpec]，并将两者的结果构造为一个~实例，传递给函数施用组合子➌。模式匹配完成后➍，一个Order实例即被构造出来➎。然后在隐式转换的作用下，Order实例被提升为Parser类型➏，并返回➐

图8-9有一条规则没有按照“^^组合子加模式匹配”的格式书写：

  1. lazy val items: Parser[Items] =
  2. "(" ~> rep1sep(line_item, ",") <~ ")" ^^ Items

在这条规则里，我们没有通过一个匿名的模式匹配函数，而是直接使用了Items构造器。因为^^组合子的前一个分析器返回的是Seq[LineItem]类型的单一值，正好可以直接作为Items构造器的参数，所以我们可以采用这样的写法。account_spec对应的规则也采用了相同的技巧。

代码清单8-6用到偏函数组合子^了吗?➊ 偏函数有可能在分析器的返回值上没有定义，针对这样的例外情况，我们预备了只在特殊上下文内生效的错误消息。请考虑这样的场景，假设脚本中设定的单价最高为10；这时分析是成功的。但是我们在偏函数的定义里，加入了验证输入的语义。比如例中的模式匹配语句内设置了验证条件，规定单价的最小值必须高于20。（附录D对Scala的模式匹配特性有进一步的介绍）那么此时在代码清单8-6的位置➊，虽然分析器报告分析成功了，但PartialFunction在分析器的返回值上是没有定义的。于是我们就通过这样的技巧实现了验证输入，并能针对特定情况报告错误的语义。

至此，我们的分析器已经具有完备的功能，它按照语义模型规定的结构返回的AST，同时也是一个可以直接在应用中使用的Order对象实例。

enter image description here你有没有想过，为什么每个方法都是以lazy val开头，而不用def呢？因为对lazy val方法的求值会被推迟到真正使用的时刻，而且规则的定义顺序是无关紧要的。

祝贺一下自己吧！我们用分析器组合子完整地实现了一种外部DSL。这是一个简洁明了的DSL实现，其语法定义的表达形式仿照了大家熟悉的EBNF风格。其语义模型不但仅仅是由普通的Scala抽象构成的，而且完全与语法定义解耦。作为设计者，我们还能要求更多吗？

能交出这样一份答卷，证明我们已经准备好尝试更高级的练习——一种需要用到packrat分析器的DSL实现。