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