特定領域語言（Domain-specific languages，DSL）已經成為一個熱門話題；很多函數性語言之所以受歡迎，主要是因為它們可以用於構建 DSL。有鑒於此，在 面向 Java 開發人員的 Scala 指南 系列的最後一篇文章中，Ted Neward 繼續討論一個簡單的計算器 DSL，以展示函數性語言在構建“外部”DSL 的強大功能，並在此過程中解決將文本輸入轉換成用於解釋的 AST 的問題。為了解析文本輸入，並將它轉換成上一篇文章中解釋器使用的樹結構，Ted 引入了 解析器組合子（parser combinator），這是一個專門為這項任務設計的標准 Scala 庫。（在 上一篇文章 中，我們構建了一個計算器解析器和 AST）。
回憶一下我們的英雄所處的困境：在試圖創建一個 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))
}
}
}
}
前一篇文章的讀者應該還記得，我布置了一個挑戰任務，要求改進優化步驟，進一步在樹中進行簡化處理，而不是像清單 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 表示感謝。
解析
現在是構建 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 語法與構建解析器的代碼之間的緊密關系使我們可以更快、更容易地構建解析器。
解析器組合子概念入門
為了理解其中的原理，我們必須簡要了解解析器組合子的實現。實際上，每個 “解析器” 都是一個函數或一個 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 元素。但是，解析器組合子庫已經包含很多這樣的內容，沒有必要再重復一遍。
