面向Java開發人員的Scala指南: 構建計算器，第 2 部分

　　摘要特定領域語言（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 機制
    ○  構建計算器第 部分（ 年 月）是本文的前半部分

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26082.html