8.4 一个需要packrat分析器的DSL实例

上一节我们用分析器组合子开发了一个完整的DSL，期间全然没有提起过packrat分析器。Packrat分析器很特别，因为它可以做到普通的自顶向下递归下降分析器做不到的事情。我们将在这一节里开发一个需要依靠packrat分析器才能实现的新的DSL。如果说上一节的DSL让我们认识到分析器组合子函数式的威力，本节的DSL将更多地表现Scala的PackratParsers实现所独具的光彩。

8.4.1 待解决的领域问题

交易指令处理领域已经被我们摸索得差不多了，接下来我们打算围绕一个交易后的业务用例来建立新的DSL。

从事存管业务的金融机构可以代表客户保管证券。客户需要做的只是在金融机构那里开设一个账户，以后客户买入卖出的证券就交由该机构代为照管维护。证券及现金交易完成后，要按照一定的规则来确定保管的结算银行和账户，我们的新DSL就是给投资经理用来设定这些规则的。用这个领域的术语来说，我们DSL描述了存管机构怎样为其客户管理结算常设指示（settlement standing instruction，简称SSI）。本节随附的插入栏简要说明了这个待解决的领域问题。

8.4 一个需要packrat分析器的DSL实例 - 图1金融中介系统：结算常设指示

交易就意味着要在交易各方之间进行证券和货币的交换。这个交换过程发生在交易确立之后，称为交易结算。结算涉及交易各方账户之间进行资金和证券的转移。根据交易类型、证券种类、交易者的身份以及其他各种因素，结算可能涉及多个账户。

为了便于处理资产的转移，投资经理需要维护一个常设规则数据库，每次交易后从中查询如何进行交收的指示。这些规则就是所谓的SSI。SSI要经常性地公布给中介和存管人知晓。

交易结算通常由两部分组成：证券部分和现金部分。两部分的结算指示可以相同，也可以不同。如果希望证券部分和现金部分分别结算，那么相应的SSI需要明确说明这一点。

举个例子，投资银行可能会有这样的规则表述：在日本市场履行的股票交易应本行内部结算到账户A-123。这条规则将适用于在该投资银行存管的所有客户。规则可以有层级关系，查找的时候按照从具体到宽泛的顺序。假如有另一条规则表述：对Sony的股票交易应外部结算到BOTM账户BO-234。那么综合两条规则，在日本市场履行的所有股票交易中，Sony股票的交易将通过BOTM结算，除此之外的股票交易都在本投资银行内部结算。

现实中什么人会使用这种DSL？首先投资经理是潜在的用户，其次还有投资银行内所有从事证券结算的业务人员。交易系统采用SSI有很大的好处，因为它能够将领域问题准确而精炼地向领域用户表述出来。在我们着手实现DSL之前，先来看看SSI在交易和结算流程中所处的位置。

1.理解业务流程

为了透彻理解SSI在交易和结算流程中扮演的角色，请看图8-10和图8-11。图8-10表示交易各方之间的基本交易及结算流程。

enter image description here

图8-10　交易和结算流程。交易是在买卖双方之间达成交换证券和现金的承诺。结算是对交易承诺的落实，相关的证券和现金被实际转移到对方的账户上

图8-11说明了为什么没有SSI信息就无法完成交易和结算流程。

enter image description here

图8-11　完成结算过程需要SSI。中介及受托存管人需要掌握银行及账户信息，才知道该向何处交收证券和现金

我们对什么是SSI有了一点概念之后，可以先看几条有代表性的SSI规则样例，以对投资经理希望发布的规则有个直观的印象。

2.将要实现的SSI规则样例

为了叙述简便起见，这里只涉及一小部分简单的规则，现实中的规则其实复杂得多。

  • 客户chase在JPN市场履行的对ibm的交易内部结算到本行账户a-345。
  • 客户chase在JPN市场履行的交易内部结算到本行账户a-123。
  • 客户nri在US市场履行的交易外部结算到CITI账户a-345。
  • 客户chase对sony的交易内部结算到本行账户n-234。
  • 客户chase发生自账户ch-123的交易内部结算到本行账户n-675。
  • 中介icici在JPN市场履行的交易，证券内部存管到本行账户us-123，现金外部结算到BOJ账户b-954。（这条规则对现金和证券分别指定了不同的SSI）

我们的实现依旧从文法开始。有了第8.3节运用Scala分析器组合子设计DSL的经验，代码清单8-7的文法定义一点也难不倒我们。

8.4.2 定义文法

完整的文法定义会比较长，不过至少大部分是我们熟悉的写法。因此本小节不再从头到尾讲解，而是聚焦到其中几个特殊之处。代码清单8-7给出了完整的文法定义。

代码清单8-7　SSI_Dsl的文法规则

  1. package trading.dsl
  2. import scala.util.parsing.combinator._
  3. object SSI_Dsl extends JavaTokenParsers
  4.                with PackratParsers {   声明使用PackratParsers
  6.   lazy val standing_rules = (standing_rule +)
  8.   lazy val standing_rule =
  9.   "settle" ~> "trades" ~> trade_type_spec ~ settlement_spec
  11.   lazy val trade_type_spec =  ➊ 左递归和依序选择
  12.     trade_type_spec ~ ("in" ~> market <~ "market") |
  13.     trade_type_spec ~ ("of" ~> security) |
  14.     trade_type_spec ~ ("on" ~> "account" ~> account) |
  15.     "for" ~> counterparty_spec
  17.   lazy val counterparty_spec =
  18.     "customer" ~> customer | "broker" ~> broker
  20.   lazy val settlement_spec =
  21.     settle_all_spec | settle_cash_security_separate_spec
  23.   lazy val settle_all_spec = settle_mode_spec
  25.   lazy val settle_cash_security_separate_spec =
  26.     repN(2, settle_cash_security ~ settle_mode_spec)
  28.   lazy val settle_cash_security =
  29.     "safekeep" ~> "security" | "settle" ~> "cash"
  31.   lazy val settle_mode_spec =
  32.     settle_external_spec | settle_internal_spec
  34.   lazy val settle_external_spec =
  35.   "externally" ~> "at" ~> bank ~ account
  37.   lazy val settle_internal_spec =
  38.   "internally" ~> "with" ~> "us" ~> "at" ~> account
  40.   lazy val market = not(keyword) ~> stringLiteral
  41.   lazy val security = not(keyword) ~> stringLiteral
  42.   lazy val customer = not(keyword) ~> stringLiteral
  43.   lazy val broker = not(keyword) ~> stringLiteral
  44.   lazy val account = not(keyword) ~> stringLiteral
  45.   lazy val bank = not(keyword) ~> stringLiteral
  47.   lazy val keyword =   将关键字建模为分析器
  48.     "at" | "us" | "of" | "on" | "in" | "and" | "with" |
  49.     "internally" | "externally" | "safekeep" |
  50.     "security" | "settle" | "cash" | "trades" |
  51.     "account" | "customer" | "broker" | "market"
  52. }

从这段文法中，你能看出来为什么我们需要用到packrat分析器吗？请注意针对trade_type_spec的规则➊。没错，这个地方出现了左递归和依序选择，如我们所知，这恰好是packrat分析器擅长处理的情况。Packrat分析器因为特别采用了记忆技术（见第8.2.3小节），能将左递归文法的分析复杂度从指数时间降低为线性时间。

在Scala语言里实现一个packrat分析器，你需要做几件事情，请看表8-4。

表8-4　在Scala语言里把分析器变成packrat分析器的步骤

步骤 说明
1.混入PackratParsers 代码清单8-7的SSI分析器执行以下操作： object SSI_Dsl extends JavaTokenParsers with PackratParsers {
2.给出Reader[Elem]的具体类型，作为对分析器处理的输入类型Input的定义 Scala的packrat分析器实现依赖于一个特化的Reader实现，即PackratReader。其定义为： class PackratReader+T extends Reader[T] { PackratReader对内部的Reader进行包装，在其上实现记忆特性。由于我们继承了JavaTokenParsers，Reader所读入的元素类型已被定义为Char
3.显式指定返回类型为PackratParser[…] 不必把所有的分析器都变成packrat分析器。对于那些需要记忆特性来帮助处理回溯和左递归的分析器，显式声明其返回类型为PackratParser。我们将在实现语义模型时见到这样的例子

除了上面提到的地方，SSI_DSL的文法定义大体类似于我们曾经实现过的交易指令处理DSL。实现好的分析器还要有驱动程序才能真正运转起来，作为一个简单而实用的练习，读者可以尝试编写一个驱动程序来调用分析器并运行本节出现的一些DSL脚本。

接下来，我们讨论如何为SSI的领域抽象建立语义模型。

8.4.3 设计语义模型

我们设计的领域抽象要像第8.3.4小节的例子，能够直接通过函数施用组合子插入到文法规则之中。代表整个问题域的抽象被命名为SSI_AST，因为我们希望分析DSL脚本的时候就能够按照这个样子生成AST。完整的语义模型请看代码清单8-8。

代码清单8-8　SSI DSL的语义模型（即AST）

  1.     package trading.dsl
  2.     object SSI_AST {
  3.   type Market = String
  4.   type Security = String
  5.   type CustomerCode = String
  6.   type BrokerCode = String
  7.   type AccountNo = String
  8.   type Bank = String
  10.   trait SettlementModeRule
  11.   case class SettleInternal(accountNo: AccountNo)
  12.     extends SettlementModeRule
  13.   case class SettleExternal(bank: Bank, accountNo: AccountNo)
  14.     extends SettlementModeRule
  16.   trait SettleCashSecurityRule
  17.   case object SettleCash extends SettleCashSecurityRule
  18.   case object SettleSecurity extends SettleCashSecurityRule
  20.   trait SettlementRule
  21.   case class SettleCashSecuritySeparate(
  22.     set: List[(SettleCashSecurityRule, SettlementModeRule)])
  23.       extends SettlementRule
  24.   case class SettleAll(sm: SettlementModeRule) extends SettlementRule
  26.   trait CounterpartyRule
  27.   case class Customer(code: CustomerCode) extends CounterpartyRule
  28.   case class Broker(code: BrokerCode) extends CounterpartyRule
  30.   case class TradeTypeRule(cpt: CounterpartyRule,
  31.     mkt: Option[Market], sec: Option[Security],
  32.     tradingAccount: Option[AccountNo])
  34.   case class StandingRule(ttr: TradeTypeRule,
  35.     str: SettlementRule)
  37.   case class StandingRules(rules: List[StandingRule])
  38. }

这段Scala代码简单易懂，并不需要额外的解释。只是下一段代码通过函数施用组合子来处理分析结果时，要用到这些类，因此把它们列在这里便于参照。

在完整的文法定义里穿插处理AST的组合子，就得到代码清单8-9。这段代码最后生成的数据结构StandingRules就是我们的语义模型。

代码清单8-9　能生成语义模型的完整DSL实现

  1. object SSI_Dsl extends JavaTokenParsers
  2.                with PackratParsers {
  3.   import SSI_AST._   导入AST
  5.   lazy val standing_rules: Parser[StandingRules] =
  6.     (standing_rule +) ^^ StandingRules
  8.   lazy val standing_rule: Parser[StandingRule] =
  9.     "settle" ~> "trades" ~> trade_type_spec ~ settlement_spec
  10.       ^^ { case (t ~ s) => StandingRule(t, s) }
  12.   lazy val trade_type_spec: PackratParser[TradeTypeRule] =  ➊ 返回类型为PackratParser
  13.     trade_type_spec ~ ("in" ~> market <~ "market")
  14.       ^^ { case (t ~ m) => t.copy(mkt = Some(m)) } |
  15.     trade_type_spec ~ ("of" ~> security)
  16.       ^^ { case (t ~ s) => t.copy(sec = Some(s)) } |
  17.     trade_type_spec ~ ("on" ~> "account" ~> account)
  18.       ^^ { case (t ~ a) => t.copy(tradingAccount = Some(a)) } |
  19.     "for" ~> counterparty_spec
  20.       ^^ { case c => TradeTypeRule(c, None, None, None) }
  22.   lazy val counterparty_spec: Parser[CounterpartyRule] =
  23.     "customer" ~> customer ^^ Customer |
  24.     "broker" ~> broker ^^ Broker
  26.   lazy val settlement_spec =
  27.     settle_all_spec |
  28.     settle_cash_security_separate_spec
  30.   lazy val settle_all_spec: Parser[SettlementRule] =
  31.     settle_mode_spec ^^ SettleAll
  33.   lazy val settle_cash_security_separate_spec: Parser[SettlementRule] =
  34.     repN(2, settle_cash_security ~ settle_mode_spec) ^^ { case l: Seq[_] =>
  35.       SettleCashSecuritySeparate(l map (e => (e._1, e._2))) }
  37.    lazy val settle_cash_security: Parser[SettleCashSecurityRule] =
  38.     "safekeep" ~> "security" ^^^ SettleSecurity |
  39.     "settle" ~> "cash" ^^^ SettleCash
  41.   lazy val settle_mode_spec: Parser[SettlementModeRule] =
  42.     settle_external_spec |
  43.     settle_internal_spec
  45.   lazy val settle_external_spec: Parser[SettlementModeRule] =
  46.     "externally" ~> "at" ~> bank ~ account
  47.     ^^ { case b ~ a => SettleExternal(b, a) }
  49.   lazy val settle_internal_spec: Parser[SettlementModeRule] =
  50.     "internally" ~> "with" ~> "us" ~> "at" ~> account ^^ SettleInternal
  52.   //..   余下部分与代码清单8-6相同
  53. }

对于出现左递归文法的trade_type_spec规则➊，我们设置其返回类型为PackratParser[TradeTypeRule]。这样它对备选项作回溯分析的时候将会用上记忆技术，左递归的问题也会按照第8.2.3小节的优化方式得到解决。

很有成就感吧？一个完整的DSL连同它的领域模型一起漂亮地呈现在我们面前了。文法看上去生动到位，StandingRules抽象也准确地表达了领域实体的模样。所有的分析器经过函数施用组合子的沟通串联，按照各自的层级、先后，协力建立起领域模型。

我们知道，分析器组合子的关键是函数式编程，而组合子范式的扩展性也同样源自函数之间的组合。下一小节我们将看到Scala分析器对扩展DSL的贡献。

8.4.4 通过分析器的组合来扩展DSL语义

我们在第8.2节讲解过，分析器可以定义成接受输入并产出分析结果的纯函数。在Scala库里，我们把这样的定义表达为(Input => ParseResult[T])。而组合子是以顺序、替代、重复等方式对分析器进行组合的高阶函数。那么，分析器和分析结果之间是怎样组合的呢？

1.以Monad方式实现定制扩展

如果我们翻看Scala分析器组合子库的源代码，就会发现ParseResult[T]和Parser[+T]都是Monad化的结构。换言之，它们都实现了标准的map、flatMap和append方法，而这几个方法对于实现单个的组合子有很大的帮助，可以免去组合分析器时显式串接输入的麻烦。我们在对代码清单8-3的顺序组合子实现进行改造时已经体会过它们的作用，Monad化的Parser和ParseResult配合for-comprehension产生了非常精炼的顺序组合子实现。

如果能在分析器的基本抽象上附加一层组合语义，那么规则的编排将具有很强的灵活性。我们可以串联组合子，可以自定义任意的变换函数去变换分析结果，还可以在已有的分析器上添加额外的语义。举个例子，我们可能希望在交易指令处理DSL的某个分析器里记录下分析的过程。那么利用针对Parser抽象定义的log组合子，我们很容易就能做到：

  1. lazy val line_item: Parser[LineItem] =
  2.   log(security_spec ~ buy_sell ~ price_spec ^^ { case s ~ b ~ p =>
  3.     LineItem(s, b, p) })("line_item")

log来自Parsers 特性，它被实现为针对一个现有分析器的装饰器，可以在分析器执行前后记录信息。更详细的情况请参看Scala源代码。

2.把分析器设计成装饰器

我们在代码清单8-6里，利用偏函数施用组合子，在分析器里添加了仅在特定上下文内生效的验证功能。但如果想在分析过程中加入更丰富的语义，我们可以把分析器设计成装饰另一个分析器的形式。请看代码清单8-10。

代码清单8-10　一个带验证功能的分析器，在分析器上加入了领域语义

  1. trait ValidatingParser extends Parsers {
  2.   def validate[T](p: => Parser[T])(
  3.     validation: (T, Input) => ParseResult[T]): Parser[T] = Parser (
  4.       in => p(in) match {
  5.         case Success(x, in) => validation(x, in)
  6.         case fail => fail
  7.       }
  8.     )
  9. }

ValidatingParser对一个已有的分析器进行了包装，可在其上添加任意的领域语义。validate方法的参数validation是一个闭包，如果我们的DSL需要增加某些专门的领域语义的话，可以放在闭包里。稍后我们会在SSI_Dsl分析器（见代码清单8-7）上演示这种手法。

不知道你还是否记得，本章前面的插入栏里提到过，一条SSI可以分别对现金和证券的结算作出不同的指示。我们在代码清单8-9中将这种情况建模为下面的分析器：

  1. lazy val settle_cash_security_separate_spec: Parser[SettlementRule] =
  2.   repN(2, settle_cash_security ~ settle_mode_spec) ^^ { case l: Seq[_] =>
  3.     SettleCashSecuritySeparate(l map (e => (e._1, e._2))) }

分析器执行后得到一个SettlementRule抽象，该case类在我们的语义模型里是这样定义的：

  1. case class SettleCashSecuritySeparate(
  2.    set: List[(SettleCashSecurityRule, SettlementModeRule)])
  3.    extends SettlementRule

这条规则的分析器需要验证脚本中确实含有两段指示，这一点通过repN(2, ..)实现了。但仅仅这样还不能证明规则有效，我们还必须确定，其中一段是对证券结算的指示，另一段是对现金结算的指示。那么，应该怎么做呢？

3.接入装饰器

其中一种办法是接入刚才实现的ValidatingParser，通过它来执行检验SSI规则有效性的领域验证逻辑。下面的代码清单对相关文法规则实施了改造。

代码清单8-11　以装饰器形式实现的ValidatingParser

  1. lazy val settle_cash_security_separate_spec: Parser[SettlementRule] =
  2.     validate(
  3.       repN(2, settle_cash_security ~ settle_mode_spec)
  4.            ^^ { case l: Seq[_] =>
  5.            SettleCashSecuritySeparate(l map (e => (e._1, e._2))) }
  6.      ) { case (s, in) => {
  7.            if ((s hasSettleSecurity) && (s hasSettleCash))
  8.              Success(s, in)  ➊  验证通过
  9.            else Failure( ➋  验证失败
  10.              "should contain 1 entry for cash and
  11.    security side of settlement", in)
  12.          }
  13. }

如果验证前的分析结果为Success，且得到的List内含有一个SettleSecurity和一个SettleCash对象，那么我们返回Success作为验证后的最终结果➊；否则因为没能通过领域验证而将原来的成功结果改为Failure➋。当然，为了让ValidatingParser对我们的文法规则起作用，还要将它混入到原先的SSI_Dsl分析器中：

  1. object SSI_Dsl extends JavaTokenParsers
  2.                with PackratParsers
  3.                with ValidatingParser {
  4.   //..

这种将多个分析器组合的手法是Decorator设计模式的一种应用。这样的设计可以保持基本抽象（也就是例子里的核心分析器）不受侵染，同时又能随时根据需要插入额外的领域逻辑。