第 10 期，构建计算器，第 3 部分：将 Scala 解析器组合子和 case 类结合起来
本帖最后由 旧收音机 于 2015-5-23 23:42 编辑问题导读
1、怎么去处理前后端代码？
2、怎么去清理语法？
3、怎么去扩展 DSL 语言？
static/image/hrline/4.gif
欢迎勇于探索的读者回到我们的系列文章中！本月继续探索 Scala 的语言和库支持，我们将改造一下计算器 DSL 并最终 “完成它”。DSL 本身有点简单 — 一个简单的计算器，目前为止只支持 4 个基本数学运算符。但要记住，我们的目标是创建一些可扩展的、灵活的对象，并且以后可以轻松增强它们以支持新的功能。继续上次的讨论……说明一下，目前我们的 DSL 有点零乱。我们有一个抽象语法树（Abstract Syntax Tree ），它由大量 case 类组成……清单 1. 后端（AST）
package com.tedneward.calcdsl
{
// ...
private abstract class Expr
privatecase class Variable(name : String) extends Expr
privatecase class Number(value : Double) extends Expr
privatecase class UnaryOp(operator : String, arg : Expr) extends Expr
privatecase class BinaryOp(operator : String, left : Expr, right : Expr)
extends Expr
}
……对此我们可以提供类似解释器的行为，它能最大限度地简化数学表达式……清单 2. 后端（解释器）
package com.tedneward.calcdsl
{
// ...
object Calc
{
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 doesn't 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 1 returns the original value
case BinaryOp("*", x, Number(1)) => x
// Multiplying 1 by x returns the original value
case BinaryOp("*", Number(1), x) => x
// Multiplying x by 0 returns zero
case BinaryOp("*", x, Number(0)) => Number(0)
// Multiplying 0 by x returns zero
case BinaryOp("*", Number(0), x) => Number(0)
// Dividing x by 1 returns the original value
case BinaryOp("/", x, Number(1)) => x
// Dividing x by x returns 1
case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)
// Adding x to 0 returns the original value
case BinaryOp("+", x, Number(0)) => x
// Adding 0 to x returns the original value
case BinaryOp("+", Number(0), x) => x
// Anything else cannot (yet) be simplified
case e => e
}
simplifyTop(simpSubs)
}
def evaluate(e : Expr) : Double =
{
simplify(e) match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}
}
}
……我们使用了一个由 Scala 解析器组合子构建的文本解析器，用于解析简单的数学表达式……清单 3. 前端
package com.tedneward.calcdsl
{
// ...
object Calc
{
object ArithParser extends JavaTokenParsers
{
def expr: Parser = term ~ rep("+"~term | "-"~term)
def term : Parser = factor ~ rep("*"~factor | "/"~factor)
def factor : Parser = floatingPointNumber | "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
// ...
}
}
……但在进行解析时，由于解析器组合子当前被编写为返回 Parser 类型，所以会生成 String 和 List 集合，实际上应该让解析器返回它需要的任意类型（我们可以看到，此时是一个 String 和 List 集合）。要让 DSL 成功，解析器需要返回 AST 中的对象，以便在解析完成时，执行引擎可以捕获该树并对它执行 evaluate()。对于该前端，我们需要更改解析器组合子实现，以便在解析期间生成不同的对象。清理语法对解析器做的第一个更改是修改其中一个语法。在原来的解析器中，可以接受像 “5 + 5 + 5” 这样的表达式，因为语法中为表达式（expr）和术语（term）定义了 rep() 组合子。但如果考虑扩展，这可能会引起一些关联性和操作符优先级问题。以后的运算可能会要求使用括号来显式给出优先级，以避免这类问题。因此第一个更改是将语法改为要求在所有表达式中加 “()”。回想一下，这应该是我一开始就需要做的事情；事实上，放宽限制通常比在以后添加限制容易（如果最后不需要这些限制），但是解决运算符优先级和关联性问题比这要困难得多。如果您不清楚运算符的优先级和关联性；那么让我大致概述一下我们所处的环境将有多复杂。考虑 Java 语言本身和它支持的各种运算符（如 Java 语言规范中所示）或一些关联性难题（来自 Bloch 和 Gafter 提供的 Java Puzzlers），您将发现情况不容乐观。因此，我们需要逐步解决问题。首先是再次测试语法：清单 4. 采用括号
package com.tedneward.calcdsl
{
// ...
object Calc
{
// ...
object OldAnyParser extends JavaTokenParsers
{
def expr: Parser = term ~ rep("+"~term | "-"~term)
def term : Parser = factor ~ rep("*"~factor | "/"~factor)
def factor : Parser = floatingPointNumber | "("~expr~")"
def parse(text : String) =
{
parseAll(expr, text)
}
}
object AnyParser extends JavaTokenParsers
{
def expr: Parser = (term~"+"~term) | (term~"-"~term) | term
def term : Parser = (factor~"*"~factor) | (factor~"/"~factor) | factor
def factor : Parser = "(" ~> expr <~ ")" | floatingPointNumber
def parse(text : String) =
{
parseAll(expr, text)
}
}
// ...
}
}
我已经将旧的解析器重命名为 OldAnyParser，添加左边的部分是为了便于比较；新的语法由 AnyParser 给出；注意它将 expr 定义为 term + term、term - term，或者一个独立的 term，等等。另一个大的变化是 factor 的定义，现在它使用另一种组合子 ~> 和 <~ 在遇到 ( 和 ) 字符时有效地抛出它们。因为这只是一个临时步骤，所以我不打算创建一系列单元测试来查看各种可能性。不过我仍然想确保该语法的解析结果符合预期，所以我在这里编写一个不是很正式的测试：清单 5. 测试解析器的非正式测试
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
// ...
_cnnew1@Test def parse =
{
import Calc._
val expressions = List(
"5",
"(5)",
"5 + 5",
"(5 + 5)",
"5 + 5 + 5",
"(5 + 5) + 5",
"(5 + 5) + (5 + 5)",
"(5 * 5) / (5 * 5)",
"5 - 5",
"5 - 5 - 5",
"(5 - 5) - 5",
"5 * 5 * 5",
"5 / 5 / 5",
"(5 / 5) / 5"
)
for (x <- expressions)
System.out.println(x + " = " + AnyParser.parse(x))
}
}
}
请记住，这纯粹是出于教学目的（也许有人会说我不想为产品代码编写测试，但我确实没有在编写产品代码，所以我不需要编写正式的测试。这只是为了方便教学）。但是，运行这个测试后，得到的许多结果与标准单元测试结果文件相符，表明没有括号的表达式（5 + 5 + 5）执行失败，而有括号的表达式则会执行成功。真是不可思议！不要忘了给解析测试加上注释。更好的方法是将该测试完全删除。这是一个临时编写的测试，而且我们都知道，真正的 Jedi 只在研究或防御时使用这些源代码，而不在这种情况中使用。清理语法现在我们需要再次更改各种组合子的定义。回顾一下上一篇文章，expr、term 和 factor 函数中的每一个实际上都是 BNF 语句，但注意每一个函数返回的都是一个解析器泛型，参数为 Any（Scala 类型系统中一个基本的超类型，从其名称就可以知道它的作用：指示可以包含任何对象的潜在类型或引用）；这表明组合子可以根据需要返回任意类型。我们已经看到，在默认情况下，解析器可以返回一个 String，也可以返回一个 List（如果您还不信的话，可以在运行的测试中加入临时测试。这也会看到同样的结果）。要将它更改为生成 case 类 AST 层次结构的实例（Expr 对象），组合子的返回类型必须更改为 Parser。如果让它自行更改，编译将会失败；这三个组合子知道如何获取 String，但不知道如何根据解析的内容生成 Expr 对象。为此，我们使用了另一个组合子，即 ^^ 组合子，它以一个匿名函数为参数，将解析的结果作为一个参数传递给该匿名函数。如果您和许多 Java 开发人员一样，那么就要花一点时间进行解析，让我们查看一下实际效果：清单 6. 产品组合子
package com.tedneward.calcdsl
{
// ...
object Calc
{
object ExprParser extends JavaTokenParsers
{
def expr: Parser =
(term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
(term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
term
def term: Parser =
(factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
(factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
factor
def factor : Parser =
"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toFloat) }
def parse(text : String) = parseAll(expr, text)
}
def parse(text : String) =
ExprParser.parse(text).get
// ...
}
// ...
}
^^ 组合子接收一个匿名函数，其解析结果（例如，假设输入的是 5 + 5，那么解析结果将是 ((5~+)~5)）将会被单独传递并得到一个对象 — 在本例中，是一个适当类型的 BinaryObject。请再次注意模式匹配的强大功能；我将表达式的左边部分与 lhs 实例绑定在一起，将 + 部分与（未使用的）plus 实例绑定在一起，该表达式的右边则与 rhs 绑定，然后我分别使用 lhs 和 rhs 填充 BinaryOp 构造函数的左边和右边。现在运行代码（记得注释掉临时测试），单元测试集会再次产生所有正确的结果：我们以前尝试的各种表达式不会再失败，因为现在解析器生成了派生 Expr 对象。前面已经说过，不进一步测试解析器是不负责任的，所以让我们添加更多的测试（包括我之前在解析器中使用的非正式测试）：清单 7. 测试解析器（这次是正式的）
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
// ...
@Test def parseAnExpr1 =
assertEquals(
Number(5),
Calc.parse("5")
)
@Test def parseAnExpr2 =
assertEquals(
Number(5),
Calc.parse("(5)")
)
@Test def parseAnExpr3 =
assertEquals(
BinaryOp("+", Number(5), Number(5)),
Calc.parse("5 + 5")
)
@Test def parseAnExpr4 =
assertEquals(
BinaryOp("+", Number(5), Number(5)),
Calc.parse("(5 + 5)")
)
@Test def parseAnExpr5 =
assertEquals(
BinaryOp("+", BinaryOp("+", Number(5), Number(5)), Number(5)),
Calc.parse("(5 + 5) + 5")
)
@Test def parseAnExpr6 =
assertEquals(
BinaryOp("+", BinaryOp("+", Number(5), Number(5)), BinaryOp("+", Number(5),
Number(5))),
Calc.parse("(5 + 5) + (5 + 5)")
)
// other tests elided for brevity
}
}
读者可以再增加一些测试，因为我可能漏掉一些不常见的情况（与 Internet 上的其他人结对编程是比较好的）。完成最后一步假设解析器正按照我们想要的方式在工作 — 即生成 AST — 那么现在只需要根据 AST 对象的计算结果来完善解析器。这很简单，只需向 Calc添加代码，如清单 8 所示……清单 8. 真的完成啦！
package com.tedneward.calcdsl
{
// ...
object Calc
{
// ...
def evaluate(text : String) : Double = evaluate(parse(text))
}
}
……同时添加一个简单的测试，确保 evaluate("1+1") 返回 2.0……清单 9. 最后，看一下 1 + 1 是否等于 2
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
// ...
@Test def add1 =
assertEquals(Calc.evaluae("1 + 1"), 2.0)
}
}
……然后运行它，一切正常！扩展 DSL 语言如果完全用 Java 代码编写同一个计算器 DSL，而没有碰到我遇到的问题（在不构建完整的 AST 的情况下递归式地计算每一个片段，等等），那么似乎它是另一种能够解决问题的语言或工具。但以这种方式构建语言的强大之处会在扩展性上得到体现。例如，我们向这种语言添加一个新的运算符，即 ^ 运算符，它将执行求幂运算；也就是说，2 ^ 2 等于 2 的平方 或 4。向 DSL 语言添加这个运算符需要一些简单步骤。首先，您必须考虑是否需要更改 AST。在本例中，求幂运算符是另一种形式的二进制运算符，所以使用现有 BinaryOp case 类就可以。无需对 AST 进行任何更改。其次，必须修改 evaluate 函数，以使用 BinaryOp("^", x, y) 执行正确的操作；这很简单，只需添加一个嵌套函数（因为不必在外部看到这个函数）来实际计算指数，然后向模式匹配添加必要的代码行，如下所示：清单 10. 稍等片刻
package com.tedneward.calcdsl
{
// ...
object Calc
{
// ...
def evaluate(e : Expr) : Double =
{
def exponentiate(base : Double, exponent : Double) : Double =
if (exponent == 0)
1.0
else
base * exponentiate(base, exponent - 1)
simplify(e) match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
case BinaryOp("^", x1, x2) => exponentiate(evaluate(x1), evaluate(x2))
}
}
}
}
注意，这里我们只使用 6 行代码就有效地向系统添加了求幂运算，同时没有对 Calc 类进行任何表面更改。这就是封装！（在我努力创建最简单求幂函数时，我故意创建了一个有严重 bug 的版本 —— 这是为了让我们关注语言，而不是实现。也就是说，看看哪位读者能够找到 bug。他可以编写发现 bug 的单元测试，然后提供一个无 bug 的版本）。但是在向解析器添加这个求幂函数之前，让我们先测试这段代码，以确保求幂部分能正常工作：清单 11. 求平方
package com.tedneward.calcdsl.test
{
class CalcTest
{
// ...
@Test def evaluateSimpleExp =
{
val expr =
BinaryOp("^", Number(4), Number(2))
val results = Calc.evaluate(expr)
// (4 ^ 2) => 16
assertEquals(16.0, results)
}
@Test def evaluateComplexExp =
{
val expr =
BinaryOp("^",
BinaryOp("*", Number(2), Number(2)),
BinaryOp("/", Number(4), Number(2)))
val results = Calc.evaluate(expr)
// ((2 * 2) ^ (4 / 2)) => (4 ^ 2) => 16
assertEquals(16.0, results)
}
}
}
运行这段代码确保可以求幂（忽略我之前提到的 bug），这样就完成了一半的工作。最后一个更改是修改语法，让它接受新的求幂运算符；因为求幂的优先级与乘法和除法的相同，所以最简单的做法是将它放在 term 组合子中：清单 12. 完成了，这次是真的！
package com.tedneward.calcdsl
{
// ...
object Calc
{
// ...
object ExprParser extends JavaTokenParsers
{
def expr: Parser =
(term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
(term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
term
def term: Parser =
(factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
(factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
(factor ~ "^" ~ factor) ^^ { case lhs~exp~rhs => BinaryOp("^", lhs, rhs) } |
factor
def factor : Parser =
"(" ~> expr <~ ")" |
floatingPointNumber ^^ {x => Number(x.toFloat) }
def parse(text : String) = parseAll(expr, text)
}
// ...
}
}
当然，我们需要对这个解析器进行一些测试……清单 13. 再求平方
package com.tedneward.calcdsl.test
{
class CalcTest
{
// ...
@Test def parseAnExpr17 =
assertEquals(
BinaryOp("^", Number(2), Number(2)),
Calc.parse("2 ^ 2")
)
@Test def parseAnExpr18 =
assertEquals(
BinaryOp("^", Number(2), Number(2)),
Calc.parse("(2 ^ 2)")
)
@Test def parseAnExpr19 =
assertEquals(
BinaryOp("^", Number(2),
BinaryOp("+", Number(1), Number(1))),
Calc.parse("2 ^ (1 + 1)")
)
@Test def parseAnExpr20 =
assertEquals(
BinaryOp("^", Number(2), Number(2)),
Calc.parse("2 ^ (2)")
)
}
}
……运行并通过后，还要进行最后一个测试，看一切是否能正常工作：清单 14. 从 String 到平方
package com.tedneward.calcdsl.test
{
class CalcTest
{
// ...
@Test def square1 =
assertEquals(Calc.evaluate("2 ^ 2"), 4.0)
}
}
成功啦！
结束语显然，还要做更多工作才能使这门简单的语言变得更好；不管您对该语言的各个部分测试（AST、解析器、简化引擎，等等）感觉如何，仅仅将该语言编写为基于解释器的对象都可以通过更少的代码来实现（也可能更快，这取决于您的熟练程度），甚至可以动态地计算表达式的值，而不是将它们转换为 AST 后再进行计算。向系统添加另一种运算符是非常简单的。该语言的设计也使它的扩展非常容易，扩展时不需要修改很多代码。事实上，我们可以通过许多增强来演示该方法的内在灵活性： 1、我们可以从使用 Doubles 转向使用 BigDecimals 或 BigIntegers，而不是用 java.math 包（以允许进行更大和/或更准确的计算）。 2、我们可以在语言中支持十进制数（当前解析器中不支持）。 3、我们可以使用单词（“sin”、“cos”、“tan” 等）而不是符号来添加运算符。 4、我们甚至可以添加变量符号（“x = y + 12”）并接受 Map 作为 evaluate() 函数的参数，该函数包含每个变量的初始值。更重要的是，DSL 完全隐藏在 Calc 类后面，这意味着从 Java 代码调用它与从 Scala 调用它一样简单。所以即使在没有完全采用 Scala 作为首选语言的项目中，也可以用 Scala 编写部分系统（那些最适合使用函数性/对象混合语言的部分），而且 Java 开发人员可以轻松地调用它们。本文到此结束。在下一篇文章中，我们将回顾 Scala 的更多语言功能（比如泛型，因为解析器组合子是由它们组成的）。Scala 还有许多东西需要学习，但希望您现在能够知道如何使用 Scala 解决那些用 Java 代码很难解决的问题。下次见！
相关导读：
第 1 期，面向对象的函数编程：了解 Scala 如何利用两个领域的优点
第 2 期，类操作：理解 Scala 的类语法和语义
第 3 期，Scala 控制结构内部揭密
第 4 期，关于特征和行为：使用 Scala 版本的 Java 接口
第 5 期，实现继承：当 Scala 继承中的对象遇到函数
第 6 期，集合类型：在 Scala 使用元组、数组和列表
第 7 期，包和访问修饰符：Scala 中的 public、private 以及其他成员
第 8 期，构建计算器，第 1 部分：Scala 的 case 类和模式匹配
第 9 期，构建计算器，第 2 部分：Scala 的解析器组合子
第 10 期，构建计算器，第 3 部分：将 Scala 解析器组合子和 case 类结合起来
第 11 期，Scala 和 servlet
第 12 期，深入了解 Scala 并发性：了解 Scala 如何简化并发编程并绕过陷阱
第 13 期，深入了解 Scala 并发性：了解 actor 如何提供新的应用程序代码建模方法
第 14 期，Scala + Twitter = Scitter
第 15 期，增强 Scitter 库
第 16 期，用 Scitter 更新 Twitter
页:
[1]