從Java走進Scala:構建計算器 解析器組合子入門
回憶一下我們的英雄所處的困境：在試圖創建一個 DSL（這里只不過是一種非常簡單的計算器語言）時，他創建了包含可用于該語言的各種選項的樹結構：
◆二進制加/減/乘/除運算符
◆一元反運算符
◆數值
它背后的執行引擎知道如何執行那些操作，它甚至有一個顯式的優化步驟，以減少獲得結果所需的計算。
最后的 代碼 是這樣的：
清單 1. 計算器 DSL：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
- 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 1 returns the original value
- case BinaryOp("*", x, Number(1)) => simplify(x)
- // Multiplying 1 by x returns the original value
- case BinaryOp("*", Number(1), x) => simplify(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)) => simplify(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)) => simplify(x)
- // Adding 0 to x returns the original value
- case BinaryOp("+", Number(0), 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("+", 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))
- }
- }
- }
- }
#p#
前一篇文章的讀者應該還記得，我布置了一個挑戰任務，要求改進優化步驟，進一步在樹中進行簡化處理，而不是像清單 1 中的代碼那樣停留在最頂層。Lex Spoon 發現了我認為是最簡單的優化方法：首先簡化樹的 “邊緣”（每個表達式中的操作數，如果有的話），然后利用簡化的結果，再進一步簡化頂層的表達式，如清單 2 所示：
清單 2. 簡化、再簡化
- /*
- * Lex's 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 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)
- }
在此對 Lex 表示感謝。
#p#
解析
現在是構建 DSL 的另一半工作：我們需要構建一段代碼，它可以接收某種文本輸入并將其轉換成一個 AST。這個過程更正式的稱呼是解析（parsing）（更準確地說，是標記解釋（tokenizing）、詞法解析（lexing） 和語法解析）。
以往，創建解析器有兩種方法：
手工構建一個解析器。
通過工具生成解析器。
我們可以試著手工構建這個解析器，方法是手動地從輸入流中取出一個字符，檢查該字符，然后根據該字符以及在它之前的其他字符（有時還要根據在它之后的字符）采取某種行動。對于較小型的語言，手工構建解析器可能更快速、更容易，但是當語言變得更龐大時，這就成了一個困難的問題。
除了手工編寫解析器外，另一種方法是用工具生成解析器。以前有 2 個工具可以實現這個目的，它們被親切地稱作lex（因為它生成一個 “詞法解析器”）和 yacc（“Yet Another Compiler Compiler”）。對編寫解析器感興趣的程序員沒有手工編寫解析器，而是編寫一個不同的源文件，以此作為 “lex” 的輸入，后者生成解析器的前端。然后，生成的代碼會與一個 “grammar” 文件 —— 它定義語言的基本語法規則（哪些標記中是關鍵字，哪里可以出現代碼塊，等等）—— 組合在一起，并且輸入到 yacc 生成解析器代碼。
由于這是 Computer Science 101 教科書，所以我不會詳細討論有限狀態自動機（finite state automata）、LALR 或 LR 解析器，如果需要深入了解請查找與這個主題相關的書籍或文章。
同時，我們來探索 Scala 構建解析器的第 3 個選項：解析器組合子（parser combinators），它完全是從 Scala 的函數性方面構建的。解析器組合子使我們可以將語言的各種片段 “組合” 成部件，這些部件可以提供不需要代碼生成，而且看上去像是一種語言規范的解決方案。
解析器組合子
了解 Becker-Naur Form（BNF）有助于理解解析器組合子的要點。BNF 是一種指定語言的外觀的方法。例如，我們的計算器語言可以用清單 3 中的 BNF 語法進行描述：
清單 3. 對語言進行描述
- 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 ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';
- ws ::= [{' '|'\t'|'\n'|'\r'}];
語句左邊的每個元素是可能的輸入的集合的名稱。右邊的元素也稱為 term，它們是一系列表達式或文字字符，按照可選或必選的方式進行組合。（同樣，BNF 語法在 Aho/Lam/Sethi/Ullman 等書籍中有更詳細的描述，請參閱 參考資料）。
用 BNF 形式來表達語言的強大之處在于，BNF 和 Scala 解析器組合子不相上下；清單 4 顯示使用 BNF 簡化形式后的清單 3：
清單 4. 簡化、再簡化
- expr ::= term {'+' term | '-' term}
- term ::= factor {'*' factor | '/' factor}
- factor ::= floatingPointNumber | '(' expr ')'
其中花括號（{}）表明內容可能重復（0 次或多次），豎線（|）表明也/或的關系。因此，在讀清單 4 時，一個 factor 可能是一個 floatingPointNumber（其定義在此沒有給出），或者一個左括號加上一個 expr 再加上一個右括號。
在這里，將它轉換成一個 Scala 解析器非常簡單，如清單 5 所示：
清單 5. 從 BNF 到 parsec
- package com.tedneward.calcdsl
- {
- object Calc
- {
- // ...
- import scala.util.parsing.combinator._
- 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 = ArithParser.parse(text)
- System.out.println("parsed " + text + " as " + results + " which is a type "
- + results.getClass())
- }
- // ...
- }
- }
BNF 實際上被一些解析器組合子語法元素替換：空格被替換為 ~ 方法（表明一個序列），重復被替換為 rep 方法，而選擇則仍然用 | 方法來表示。文字字符串是標準的文字字符串。
從兩個方面可以看到這種方法的強大之處。首先，該解析器擴展 Scala 提供的 JavaTokenParsers 基類（后者本身又繼承其他基類，如果我們想要一種與 Java 語言的語法概念不那么嚴格對齊的語言的話），其次，使用 floatingPointNumber 預設的組合子來處理解析一個浮點數的細節。
這種特定的（一個中綴計算器的）語法很容易使用（這也是在那么多演示稿和文章中看到它的原因），為它手工構建一個解析器也不困難，因為 BNF 語法與構建解析器的代碼之間的緊密關系使我們可以更快、更容易地構建解析器。
#p#
解析器組合子概念入門
為了理解其中的原理，我們必須簡要了解解析器組合子的實現。實際上，每個 “解析器” 都是一個函數或一個 case 類，它接收某種輸入，并產生一個 “解析器”。例如，在最底層，解析器組合子位于一些簡單的解析器之上，這些解析器以某種輸入讀取元素（一個 Reader）作為輸入，并生成某種可以提供更高級的語義的東西（一個 Parser）：
清單 6. 一個基本的解析器
- 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 是圍繞那種類型的一個 scala.util.parsing.input.Reader（方括號表明 Reader 是一個泛型；如果您喜歡 Java 或 C++ 風格的語法，那么將它們看作尖括號）。然后，T 類型的 Parser 是這樣的類型：它接受一個 Input，并生成一個 ParseResult，后者（基本上）屬于兩種類型之一：Success 或 Failure。
顯然，關于解析器組合子庫的知識遠不止這些 — 即使 ~ 和 rep 函數也不是幾個步驟就可以得到的 — 但是，這讓您對解析器組合子的工作原理有基本的了解。“組合” 解析器可以提供解析概念的越來越高級的抽象（因此稱為 “解析器組合子”；組合在一起的元素提供解析行為）。
我們還沒有完成，是嗎？
我們仍然沒有完成。通過調用快速測試解析器可以發現，解析器返回的內容并不是計算器系統需要的剩余部分：
清單 7. 第一次測試失敗？
- package com.tedneward.calcdsl.test
- {
- class CalcTest
- {
- import org.junit._, Assert._
- // ...
- @Test def parseNumber =
- {
- assertEquals(Number(5), Calc.parse("5"))
- assertEquals(Number(5), Calc.parse("5.0"))
- }
- }
- }
這次測試會在運行時失敗，因為解析器的 parseAll 方法不會返回我們的 case 類 Number（這是有道理的，因為我們沒有在解析器中建立 case 類與解析器的產生規則之間的關系）；它也沒有返回一個文本標記或整數的集合。
相反，解析器返回一個 Parsers.ParseResult，這是一個 Parsers.Success 實例（其中有我們想要的結果）；或者一個 Parsers.NoSuccess、Parsers.Failure 或 Parsers.Error（后三者的性質是一樣的：解析由于某種原因未能正常完成）。
假設這是一次成功的解析，要得到實際結果，必須通過 ParseResult 上的 get 方法來提取結果。這意味著必須稍微調整 Calc.parse 方法，以便通過測試。如清單 8 所示：
清單 8. 從 BNF 到 parsec
- package com.tedneward.calcdsl
- {
- object Calc
- {
- // ...
- import scala.util.parsing.combinator._
- 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 = ArithParser.parse(text)
- System.out.println("parsed " + text + " as " + results + " which is a type "
- + results.getClass())
- results.get
- }
- // ...
- }
- }
成功了！真的嗎？
對不起，還沒有成功。運行測試表明，解析器的結果仍不是我前面創建的 AST 類型（expr 和它的親屬），而是由 List 和 String 等組成的一種形式。雖然可以將這些結果解析成 expr 實例并對其進行解釋，但是肯定還有另外一種方法。
確實有另外一種方法。為了理解這種方法的工作原理，您將需要研究一下解析器組合子是如何產生非 “標準” 的元素的（即不是 String 和 List）。用適當的術語來說就是解析器如何才能產生一個定制的元素（在這里，就是 AST 對象）。這個主題下一次再討論。
在下一期中，我將和您一起探討解析器組合子實現的基礎，并展示如何將文本片段解析成一個 AST，以便進行求值（然后進行編譯）。
結束語
顯然，我們還沒有結束（解析工作還沒有完成），但是現在有了基本的解析器語義，接下來只需通過擴展解析器產生元素來生成 AST 元素。
對于那些想領先一步的讀者，可以查看 ScalaDocs 中描述的 ^^ 方法，或者閱讀 Programming in Scala 中關于解析器組合子的小節；但是，在此提醒一下，這門語言比這些參考資料中給出的例子要復雜一些。
當然，您可以只與 String 和 List 打交道，而忽略 AST 部分，拆開返回的 String 和 List，并重新將它們解析成 AST 元素。但是，解析器組合子庫已經包含很多這樣的內容，沒有必要再重復一遍。
【相關閱讀】
