Scala怎么结合解析器组合子和case类构建计算器

发布时间:2021-12-09 09:05:18 作者:iii
来源:亿速云 阅读:112

这篇文章主要讲解了“Scala怎么结合解析器组合子和case类构建计算器”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Scala怎么结合解析器组合子和case类构建计算器”吧!

说明一下,目前我们的 DSL 有点零乱。我们有一个抽象语法树(Abstract Syntax Tree ),它由大量 case 类组成……

清单 1. 后端(AST)

package com.tedneward.calcdsl  {    // ...     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   }

……对此我们可以提供类似解释器的行为,它能最大限度地简化数学表达式……

清单 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[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)        }      }            // ...    }  }

……但在进行解析时,由于解析器组合子当前被编写为返回 Parser[Any] 类型,所以会生成 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[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)        }      }      object AnyParser extends JavaTokenParsers      {        def expr: Parser[Any] = (term~"+"~term) | (term~"-"~term) | term        def term : Parser[Any] = (factor~"*"~factor) | (factor~"/"~factor) | factor        def factor : Parser[Any] = "(" ~> 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[Expr]。如果让它自行更改,编译将会失败;这三个组合子知道如何获取 String,但不知道如何根据解析的内容生成 Expr 对象。为此,我们使用了另一个组合子,即 ^^ 组合子,它以一个匿名函数为参数,将解析的结果作为一个参数传递给该匿名函数。

如果您和许多 Java 开发人员一样,那么就要花一点时间进行解析,让我们查看一下实际效果:

清单 6. 产品组合子

package com.tedneward.calcdsl  {    // ...     object Calc    {      object ExprParser extends JavaTokenParsers      {        def expr: Parser[Expr] =          (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |          (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |          term          def term: Parser[Expr] =          (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |          (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |          factor         def factor : Parser[Expr] =          "(" ~> 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[Expr] =          (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |          (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |          term          def term: Parser[Expr] =          (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] =          "(" ~> 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)    }  }

成功啦!

感谢各位的阅读,以上就是“Scala怎么结合解析器组合子和case类构建计算器”的内容了,经过本文的学习后,相信大家对Scala怎么结合解析器组合子和case类构建计算器这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

推荐阅读:
  1. IDEA中使用SBT构建SCALA项目
  2. 构建与环境、域用户和组

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

scala case

上一篇:Scala如何构建计算器

下一篇:Scala2.8命名参数有哪些

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》