Scala怎么結合解析器組合子和case類構建計算器

這篇文章主要講解了“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類構建計算器這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！