摘要特定领域语言（Domainspecific languagesDSL）已经成为一个热门话题很多函数性语言之所以受欢迎主要是因为它们可以用于构建 DSL有鑒于此在 面向 Java 开发人员的 Scala 指南 系列的最后一篇文章中Ted Neward 继续讨论一个简单的计算器 DSL以展示函数性语言在构建外部DSL 的强大功能并在此过程中解决将文本输入转换成用于解释的 AST 的问题为了解析文本输入并将它转换成上一篇文章中解释器使用的树结构Ted 引入了 解析器组合子（parser combinator）这是一个专门为这项任务设计的标准 Scala 库（在 上一篇文章 中我们构建了一个计算器解析器和 AST）
回忆一下我们的英雄所处的困境在试图创建一个 DSL（这里只不过是一种非常简单的计算器语言）时他创建了包含可用于该语言的各种选项的树结构
● 二进制加/减/乘/除运算符
● 一元反运算符
● 数值
它背后的执行引擎知道如何执行那些操作它甚至有一个显式的优化步骤以减少获得结果所需的计算
最后的 代码 是这样的
清单 计算器 DSLAST 和解释器
package comtednewardcalcdsl
{
private[calcdsl] abstract class Expr
private[calcdsl] case class Variable(name : String) extends Expr
private[calcdsl] case class Number(value : Double) extends Expr
private[calcdsl] case class UnaryOp(operator : String arg : Expr) extends Expr
private[calcdsl] case class BinaryOp(operator : String left : Expr right : Expr)
extends Expr
object Calc
{
/**
* Function to simplify (a la mathematic terms) expressions
*/
def simplify(e : Expr) : Expr =
{
e match {
// Double negation returns the original value
case UnaryOp( UnaryOp( x)) => simplify(x)
// Positive returns the original value
case UnaryOp(+ x) => simplify(x)
// Multiplying x by returns the original value
case BinaryOp(* x Number()) => simplify(x)
// Multiplying by x returns the original value
case BinaryOp(* Number() x) => simplify(x)
// Multiplying x by returns zero
case BinaryOp(* x Number()) => Number()
// Multiplying by x returns zero
case BinaryOp(* Number() x) => Number()
// Dividing x by returns the original value
case BinaryOp(/ x Number()) => simplify(x)
// Dividing x by x returns
case BinaryOp(/ x x) if x == x => Number()
// Adding x to returns the original value
case BinaryOp(+ x Number()) => simplify(x)
// Adding to x returns the original value
case BinaryOp(+ Number() x) => simplify(x)
// Anything else cannot (yet) be simplified
case _ => e
}
}
def evaluate(e : Expr) : Double =
{
simplify(e) match {
case Number(x) => x
case UnaryOp( x) => (evaluate(x))
case BinaryOp(+ x x) => (evaluate(x) + evaluate(x))
case BinaryOp( x x) => (evaluate(x) evaluate(x))
case BinaryOp(* x x) => (evaluate(x) * evaluate(x))
case BinaryOp(/ x x) => (evaluate(x) / evaluate(x))
}
}
}
}
前一篇文章的读者应该还记得我布置了一个挑战任务要求改进优化步骤进一步在树中进行简化处理而不是像清单 中的代码那样停留在最顶层Lex Spoon 发现了我认为是最简单的优化方法首先简化树的 边缘（每个表达式中的操作数如果有的话）然后利用简化的结果再进一步简化顶层的表达式如清单 所示
清单 简化再简化
/*
* Lexs version:
*/
def simplify(e: Expr): Expr = {
// first simplify the subexpressions
val simpSubs = e match {
// Ask each side to simplify
case BinaryOp(op left right) => BinaryOp(op simplify(left) simplify(right))
// Ask the operand to simplify
case UnaryOp(op operand) => UnaryOp(op simplify(operand))
// Anything else doesnt have complexity (no operands to simplify)
case _ => e
}
// now simplify at the top assuming the components are already simplified
def simplifyTop(x: Expr) = x match {
// Double negation returns the original value
case UnaryOp( UnaryOp( x)) => x
// Positive returns the original value
case UnaryOp(+ x) => x
// Multiplying x by returns the original value
case BinaryOp(* x Number()) => x
// Multiplying by x returns the original value
case BinaryOp(* Number() x) => x
// Multiplying x by returns zero
case BinaryOp(* x Number()) => Number()
// Multiplying by x returns zero
case BinaryOp(* Number() x) => Number()
// Dividing x by returns the original value
case BinaryOp(/ x Number()) => x
// Dividing x by x returns
case BinaryOp(/ x x) if x == x => Number()
// Adding x to returns the original value
case BinaryOp(+ x Number()) => x
// Adding to x returns the original value
case BinaryOp(+ Number() x) => x
// Anything else cannot (yet) be simplified
case e => e
}
simplifyTop(simpSubs)
}
在此对 Lex 表示感谢
解析
现在是构建 DSL 的另一半工作我们需要构建一段代码它可以接收某种文本输入并将其转换成一个 AST这个过程更正式的称呼是解析（parsing）（更准确地说是标记解释（tokenizing）词法解析（lexing） 和语法解析）
以往创建解析器有两种方法
● 手工构建一个解析器
● 通过工具生成解析器
我们可以试着手工构建这个解析器方法是手动地从输入流中取出一个字符检查该字符然后根据该字符以及在它之前的其他字符（有时还要根据在它之后的字符）采取某种行动对于较小型的语言手工构建解析器可能更快速更容易但是当语言变得更庞大时这就成了一个困难的问题
除了手工编写解析器外另一种方法是用工具生成解析器以前有 个工具可以实现这个目的它们被亲切地称作lex（因为它生成一个 词法解析器）和 yacc（Yet Another Compiler Compiler）对编写解析器感兴趣的程序员没有手工编写解析器而是编写一个不同的源文件以此作为 lex 的输入后者生成解析器的前端然后生成的代码会与一个 grammar 文件 —— 它定义语言的基本语法规则（哪些标记中是关键字哪里可以出现代码块等等）—— 组合在一起并且输入到 yacc 生成解析器代码
由于这是 Computer Science 教科书所以我不会详细讨论有限状态自动机（finite state automata）LALR 或 LR 解析器如果需要深入了解请查找与这个主题相关的书籍或文章
同时我们来探索 Scala 构建解析器的第 个选项解析器组合子（parser combinators）它完全是从 Scala 的函数性方面构建的解析器组合子使我们可以将语言的各种片段 组合 成部件这些部件可以提供不需要代码生成而且看上去像是一种语言规范的解决方案
解析器组合子
了解 BeckerNaur Form（BNF）有助于理解解析器组合子的要点BNF 是一种指定语言的外观的方法例如我们的计算器语言可以用清单 中的 BNF 语法进行描述
清单 对语言进行描述
input ::= ws expr ws eoi;
expr ::= ws powterm [{ws ^ ws powterm}];
powterm ::= ws factor [{ws (*|/) ws factor}];
factor ::= ws term [{ws (+|) ws term}];
term ::= ( ws expr ws ) | ws expr | number;
number ::= {dgt} [ {dgt}] [(e|E) [] {dgt}];
dgt ::= |||||||||;
ws ::= [{ |\t|\n|\r}];
语句左边的每个元素是可能的输入的集合的名称右边的元素也称为 term它们是一系列表达式或文字字符按照可选或必选的方式进行组合（同样BNF 语法在 Aho/Lam/Sethi/Ullman 等书籍中有更详细的描述请参阅 参考资料）
用 BNF 形式来表达语言的强大之处在于BNF 和 Scala 解析器组合子不相上下清单 显示使用 BNF 简化形式后的清单
清单 简化再简化
expr ::= term {+ term | term}
term ::= factor {* factor | / factor}
factor ::= floatingPointNumber | ( expr )
其中花括号（{}）表明内容可能重复（ 次或多次）竖线（|）表明也/或的关系因此在读清单 时一个 factor 可能是一个 floatingPointNumber（其定义在此没有给出）或者一个左括号加上一个 expr 再加上一个右括号
在这里将它转换成一个 Scala 解析器非常简单如清单 所示
清单 从 BNF 到 parsec
package comtednewardcalcdsl
{
object Calc
{
//
import scbinator_
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep(+~term | ~term)
def term : Parser[Any] = factor ~ rep(*~factor | /~factor)
def factor : Parser[Any] = floatingPointNumber | (~expr~)
def parse(text : String) =
{
parseAll(expr text)
}
}
def parse(text : String) =
{
val results = ArithParserparse(text)
Systemoutprintln(parsed + text + as + results + which is a type
+ resultsgetClass())
}
//
}
}
BNF 实际上被一些解析器组合子语法元素替换空格被替换为 ~ 方法（表明一个序列）重复被替换为 rep 方法而选择则仍然用 | 方法来表示文字字符串是标准的文字字符串
从两个方面可以看到这种方法的强大之处首先该解析器扩展 Scala 提供的 JavaTokenParsers 基类（后者本身又继承其他基类如果我们想要一种与 Java 语言的语法概念不那么严格对齐的语言的话）其次使用 floatingPointNumber 预设的组合子来处理解析一个浮点数的细节
这种特定的（一个中缀计算器的）语法很容易使用（这也是在那么多演示稿和文章中看到它的原因）为它手工构建一个解析器也不困难因为 BNF 语法与构建解析器的代码之间的紧密关系使我们可以更快更容易地构建解析器
解析器组合子概念入门
为了理解其中的原理我们必须简要了解解析器组合子的实现实际上每个 解析器 都是一个函数或一个 case 类它接收某种输入并产生一个 解析器例如在最底层解析器组合子位于一些简单的解析器之上这些解析器以某种输入读取元素（一个 Reader）作为输入并生成某种可以提供更高级的语义的东西（一个 Parser）
清单 一个基本的解析器
type Elem
type Input = Reader[Elem]
type Parser[T] = Input => ParseResult[T]
sealed abstract class ParseResult[+T]
case class Success[T](result: T in: Input) extends ParseResult[T]
case class Failure(msg: String in: Input) extends ParseResult[Nothing]
换句话说Elem 是一种抽象类型用于表示任何可被解析的东西最常见的是一个文本字符串或流然后Input 是围绕那种类型的一个 scalautilparsinginputReader（方括号表明 Reader 是一个泛型如果您喜欢 Java 或 C++ 风格的语法那么将它们看作尖括号）然后T 类型的 Parser 是这样的类型它接受一个 Input并生成一个 ParseResult后者（基本上）属于两种类型之一Success 或 Failure
显然关于解析器组合子库的知识远不止这些 — 即使 ~ 和 rep 函数也不是几个步骤就可以得到的 — 但是这让您对解析器组合子的工作原理有基本的了解组合 解析器可以提供解析概念的越来越高级的抽象（因此称为 解析器组合子组合在一起的元素提供解析行为）
我们还没有完成是吗？
我们仍然没有完成通过调用快速测试解析器可以发现解析器返回的内容并不是计算器系统需要的剩余部分
清单 第一次测试失败？
package comtednewardcalcdsltest
{
class CalcTest
{
import orgjunit_ Assert_
//
@Test def parseNumber =
{
assertEquals(Number() Calcparse())
assertEquals(Number() Calcparse())
}
}
}
这次测试会在运行时失败因为解析器的 parseAll 方法不会返回我们的 case 类 Number（这是有道理的因为我们没有在解析器中建立 case 类与解析器的产生规则之间的关系）它也没有返回一个文本标记或整数的集合
相反解析器返回一个 ParsersParseResult这是一个 ParsersSuccess 实例（其中有我们想要的结果）或者一个 ParsersNoSuccessParsersFailure 或 ParsersError（后三者的性质是一样的解析由于某种原因未能正常完成）
假设这是一次成功的解析要得到实际结果必须通过 ParseResult 上的 get 方法来提取结果这意味着必须稍微调整 Calcparse 方法以便通过测试如清单 所示
清单 从 BNF 到 parsec
package comtednewardcalcdsl
{
object Calc
{
//
import scbinator_
object ArithParser extends JavaTokenParsers
{
def expr: Parser[Any] = term ~ rep(+~term | ~term)
def term : Parser[Any] = factor ~ rep(*~factor | /~factor)
def factor : Parser[Any] = floatingPointNumber | (~expr~)
def parse(text : String) =
{
parseAll(expr text)
}
}
def parse(text : String) =
{
val results = ArithParserparse(text)
Systemoutprintln(parsed + text + as + results + which is a type
+ resultsgetClass())
resultsget
}
//
}
}
成功了！真的吗？
对不起还没有成功运行测试表明解析器的结果仍不是我前面创建的 AST 类型（expr 和它的亲属）而是由 List 和 String 等组成的一种形式虽然可以将这些结果解析成 expr 实例并对其进行解释但是肯定还有另外一种方法
确实有另外一种方法为了理解这种方法的工作原理您将需要研究一下解析器组合子是如何产生非 标准 的元素的（即不是 String 和 List）用适当的术语来说就是解析器如何才能产生一个定制的元素（在这里就是 AST 对象）这个主题下一次再讨论
在下一期中我将和您一起探讨解析器组合子实现的基础并展示如何将文本片段解析成一个 AST以便进行求值（然后进行编译）
结束语
显然我们还没有结束（解析工作还没有完成）但是现在有了基本的解析器语义接下来只需通过扩展解析器产生元素来生成 AST 元素
对于那些想领先一步的读者可以查看 ScalaDocs 中描述的 ^^ 方法或者阅读 Programming in Scala 中关于解析器组合子的小节但是在此提醒一下这门语言比这些参考资料中给出的例子要复杂一些
当然您可以只与 String 和 List 打交道而忽略 AST 部分拆开返回的 String 和 List并重新将它们解析成 AST 元素但是解析器组合子库已经包含很多这样的内容没有必要再重复一遍
参考资料
● 您可以参阅本文在 developerWorks 全球网站上的 英文原文
● 面向 Java 开发人员的 Scala 指南面向对象的函数编程（Ted NewarddeveloperWorks 年 月）本系列的第 篇文章概述了 Scala并解释了它的函数性方法等本系列中的其他文章
○ 类操作（ 年 月）详述了 Scala 的类语法和语义
○ Scala 控制结构内部揭密（ 年 月）深入讨论了 Scala 的控制结构
○ 关于特征和行为（ 年 月）利用 Scala 版本的 Java 接口
○ 实现继承（ 年 月）Scala 式的多态
○ 集合类型（ 年 月）包括所有 元组数组和列表
○ 包和访问修饰符（ 年 月）讨论了 Scala 的包和访问修饰符以及 apply 机制
○ 构建计算器第 部分（ 年 月）是本文的前半部分
