Ward Cunningham 曾經說過，干淨的代碼清晰地表達了代碼編寫者所想要表達的東西，而優美的代碼則更進一步，優美的代碼看起來就像是專門為了要解決的問題而存在的。在本文中，我們將展示一個組合式解析器的設計、實現過程，最終的代碼是優美的，極具擴展性，就像是為了解析特定的語法而存在的。我們還會選取 H.248 協議中的一個例子，用上述的組合式解析器實現其語法解析器。讀者在這個過程中不僅能體會到代碼的美感，還可以學習到函數式編程以及構建 DSL 的一些知識。
DSL 設計基礎
我們在用編程語言(比如：Java 語言)實現某項功能時，其實就是在指揮計算機去完成這項功能。但是，語言能夠帶給我們的並不僅僅局限於此。更重要的是，語言提供了一種用於組織我們的思維，表達計算過程的框架。這個框架的核心就在於，如何能夠把簡單的概念組合成更為復雜的概念，同時又保持其對於組合方法的封閉，也就是說，組合起來的復雜概念對於組合手段來說和簡單的概念別無二致。引用“Structure and Interpretation of Computer Programs”一書中的話來講，任何一個強大的語言都是通過如下三種機制來達成這個目標的：
原子：語言中最簡單、最基本的實體;
組合手段：把原子組合起來構成更復雜實體的方法;
抽象手段：命名復雜實體的方法，命名後的復雜實體可以和原子一樣通過組合手段組合成為更復雜的實體。
像 Java 這種通用的編程語言，由於其所關注的是解決問題的一般方法。因此，其所提供的這三種機制也都是通用層面的。在解決特定問題時，這種通用的手段和特定問題領域中的概念、規則之間是存在著語義鴻溝的，所以某些問題領域中非常清晰、明確的概念和規則，在實現時就可能會變得不那麼清晰。作為程序員來說，用干淨的代碼實現出功能僅僅是初級的要求，更重要的是要提升通用語言的層次，構建出針對特定問題領域的語言(DSL)，這個過程中很關鍵的一點就是尋找並定義出面向問題領域的 原子概念、組合的方法以及抽象的手段。這個 DSL 不一定非得像通用語言那樣是完備的，其目標在於清晰、直觀地表達出問題領域中的概念和規則，其結果就是把通用的編程語言變成解決特定問題的專用語言。
我們曾經在“基於 Java 的界面布局 DSL 的設計與實現”一文中，構建了一種用於界面布局的 DSL，其中呈現了上述思想。在本文中，我們將以解析器的構造為例，來講述如何構建一種用於字符串解析的 DSL，這種 DSL 具有強大的擴展能力，讀者可以根據自己的需要定義出自己的組合手段。此外，從本文中讀者還可以領略到 函數編程的優雅之處。
解析器原子
什麼是解析器?最簡單的解析器是什麼?大家通常都會認為解析器就是判斷輸入的字符串是否滿足給定的語法規則，在需要時還可以提取出相應的語法單位實例。從概念上來講，這種理解沒什麼問題。不過要想定義出用於解析的 DSL，那麼就需要更為精確的定義，也就是說我們要定義出解析器這個概念的確切類型。在 Java 中，我們用 interface 來定義解析器類型，如下：
interface Parser
{
public Result parse(String target);
}
其中，target 為要解析的字符串，Result 是解析的結果，只要滿足這個接口語義的對象，我們就稱其為一個解析器實例。Result 的定義如下：
class Result
{
private String recognized;
private String remaining;
private boolean succeeded;
private Result(String recognized， String remaining，
boolean succeeded) {
this.recognized = recognized;
this.remaining = remaining;
this.succeeded = succeeded;
}
public boolean is_succeeded() {
return succeeded;
}
public String get_recognized() {
return recognized;
}
public String get_remaining() {
return remaining;
}
public static Result succeed(String recognized，
String remaining) {
return new Result(recognized， remaining， true);
}
public static Result fail() {
return new Result(“”， “”， false);
} }
其中，recognized 字段表示這個解析器所認識的部分，remaining 表示經過這個解析器解析後所剩余的部分，succeeded 表示解析是否成功，Result 是一個值對象。有了解析器的精確定義，接下來我們就可以定義出最簡單的解析器。顯然，最簡單的解析器就是什麼也不解析的解析器，把目標字符串原樣返回，我們稱其為 Zero，定義如下：
class Zero implements Parser
{
public Result parse(String target) {
return Result.succeed(“”， target);
}
}
Zero 解析器一定會解析成功，不做任何語法單位識別並直接返回目標字符串。下面我們來定義另外一個很簡單的解析器 Item，只要目標字符串不為空，Item 就會把目標字符串的第一個字符作為其識別結果，並返回成功，如果目標字符串為空，就返回失敗，Item 的定義如下：
class Item implements Parser
{
public Result parse(String target) {
if(target.length() 》 0) {
return Result.succeed(target.substring(0，1)，
target.substring(1));
}
return Result.fail();
}
}
Zero 和 Item 是我們解析器 DSL 中僅有的兩個原子，在下一小節中，我們來定義解析器的組合方法。
解析器組合子
我們在上一小節中定義了 Item 解析器，它無條件的解析出目標字符串中的第一個字符，如果我們希望能夠變成有條件的解析，就可以定義出一個 SAT 組合子，其接收一個條件謂詞(predicate)和一個解析器，並生成一個復合解析器，該復合解析器能否解析成功取決於原始解析器的解析結果是否滿足給定的條件謂詞，條件謂詞和 SAT 的定義如下：
interface Predicate
{
public boolean satisfy(String value);
}
class SAT implements Parser
{
private Predicate pre;
private Parser parser;
public SAT(Predicate predicate， Parser parser) {
this.pre = predicate;
this.parser = parser;
}
public Result parse(String target) {
Result r = parser.parse(target);
if(r.is_succeeded() && pre.satisfy(r.get_recognized())) {
return r;
}
return Result.fail();
}
}
如果，我們想定義一個解析單個數字的解析器，那麼就可以定義一個 IsDigit 條件謂詞，並通過 SAT 把該 IsDigit 和 Item 組合起來，代碼如下：
class IsDigit implements Predicate
{
public boolean satisfy(String value) {
char c = value.charAt(0);
return c》=‘0’ && c《=‘9’;
}
}
解析單位數字的解析器 digit 定義如下：
Parser digit = new SAT(new IsDigit()， new Item());
我們可以采用同樣的方法組合出單個字母、單個大寫字母、單個小寫字母等解析器來。
接下來，我們定義一個 OR 組合子，其接收兩個解析器，並分別用這兩個解析器去解析一個目標串，只要有一個解析成功，就認為解析成功，如果兩個都失敗，則認為失敗，代碼定義如下：
class OR implements Parser
{
private Parser p1;
private Parser p2;
public OR(Parser p1， Parser p2) {
this.p1 = p1;
this.p2 = p2;
}
public Result parse(String target) {
Result r = p1.parse(target);
return r.is_succeeded() ? r ： p2.parse(target);
}
}
我們可以定義出一個新的解析器 digit_or_alpha，如果目標字符是數字或者字母那麼該解析器就解析成功，否則就失敗。代碼如下：
判斷是否是字母的條件謂詞：
class IsAlpha implements Predicate
{
public boolean satisfy(String value) {
char c = value.charAt(0);
return (c》=‘a’ && c《=‘z’) || (c》=‘A’ && c《=‘Z’);
}
}
用於解析單個字母的解析器：
Parser alpha = new SAT(new IsAlpha()， new Item());
digit_or_alpha 解析器定義：
Parser digit_or_alpha = new OR(digit， alpha);
下面我們來定義一個 順序組合子 SEQ，該組合子接收兩個解析器，先把第一個解析器應用到目標字符串，如果成功，就把第二個解析器應用到第一個解析器識別後剩余的字符串上，如果這兩個解析器都解析成功，那麼由 SEQ 組合起來的這個復合解析器就解析成功，只要有一個失敗，復合解析器就解析失敗。當解析成功時，其識別結果由這兩個解析器的識別結果連接而成。
為了能夠連接兩個 Result 中已經識別出來的解析結果，我們在 Result 類中新增一個靜態方法：concat，其定義如下：
public static Result concat(Result r1， Result r2) {
return new Result(
r1.get_recognized().concat(r2.get_recognized())，
r2.get_remaining()， true);
}
順序組合子 SEQ 的定義如下：
class SEQ implements Parser
{
private Parser p1;
private Parser p2;
public SEQ(Parser p1， Parser p2) {
this.p1 = p1;
this.p2 = p2;
}
public Result parse(String target) {
Result r1 = p1.parse(target);
if(r1.is_succeeded()) {
Result r2 = p2.parse(r1.get_remaining());
if(r2.is_succeeded()) {
return Result.concat(r1，r2);
}
}
return Result.fail();
}
}
現在，如果我們想定義一個解析器用以識別第一個是字母，接下來是一個數字的情況，就可以這樣定義：
Parser alpha_before_digit = new SEQ(alpha， digit);
接下來我們定義本文中的最後一個組合子：OneOrMany。該組合子接收一個解析器和一個正整數值，其生成的復合解析器會用原始解析器連續地對目標串進行解析，每一次解析時的輸入為上一次解析後剩余的字符串，解析的最大次數由輸入的正整數值決定。如果第一次解析就失敗，那麼該復合解析器就解析失敗，否則的話，會一直解析到最大次數或者遇到解析失敗為止，並把所有成功的解析的識別結果連接起來作為復合解析器的識別結果，OneOrMany 組合子的定義如下：
class OneOrMany implements Parser
{
private int max;
private Parser parser;
public OneOrMany(int max， Parser parser) {
this.max = max;
this.parser = parser;
}
public Result parse(String target) {
Result r = parser.parse(target);
return r.is_succeeded() ? parse2(r，1) ： Result.fail();
}
private Result parse2(Result pre， int count) {
if(count 》= max) return pre;
Result r = parser.parse(pre.get_remaining());
return r.is_succeeded() ?
parse2(Result.concat(pre，r)，count+1) ： pre;
}
}
使用該組合子，我們可以容易地定義出用於識別由最少一個，最多 10 個字母組成的串的解析器，如下：
Parser one_to_ten_alpha = new OneOrMany(10，alpha);
本文的組合子就定義到此，不過讀者可以根據自己的需要，用同樣的方法容易地定義出符合自己要求其他組合子來。
抽象的手段
如果在 DSL 的構造中，僅僅提供了一些原子和組合手段，並且組合的結果無法再次參與組合，那麼這個 DSL 的擴展能力和適用性就會大大折扣。相反，如果我們還能提供出抽象的手段對組合結果進行命名，命名後的復合實體可以像原子一樣參與組合，那麼 DSL 的擴展能力就會非常的強大，適用性也會大大增加。因此，抽象的手段在 DSL 的構造過程中是至關重要的。
敏銳的讀者可能已經發現，對於我們的解析 DSL 來說，其實在前面的小節中已經使用了抽象的手段。比如，我們在 alpha，digit，digit_or_alpha 以及 alpha_before_digit 等復合解析器的定義中已經使用了抽象的手段來對其進行命名，然後可以直接使用這個抽象的名字再次參與組合。由於我們的解析器是基於 Java 語言中的 interface 機制定義的，因此，Java 語言中已有的針對 interface 的抽象支持機制完全適用於我們的解析 DSL。因此，我們就無需定義自己的特定抽象手段，直接使用 Java 語言中的即可。
相信讀者已經從上一小節中的例子中看到組合、抽象手段的強大威力。在下一小節中，我們將給出一個更為具體的例子：H.248 協議中 NAME 語法解析器的構造。
一個 H.248 實例
在本小節中，我們將基於前面定義的解析器原子和組合子，實現用於識別 H.248 協議中 NAME 語法的解析器的構造。
H.248 是一個通信協議，媒體網關控制器使用該協議來對媒體網關進行控制。H.248 協議是一個基於 ABNF(擴展 BNF)文法描述的基於文本的協議，協議中定義了 H.248 消息的組成部分和具體內容。我們僅僅關注其中的 NAME 語法定義，如下：
NAME = ALPHA *63(ALPHA / DIGIT / “_” )
ALPHA = %x41-5A / %x61-7A ; A-Z， a-z
DIGIT = %x30-39 ; digits 0 through 9
我們首先來解釋一下其中的一些規則，*63 其實是 n*m 修飾規則的一個實例，表示最少 n 個最多 m 個，當 n 等於 0 時，可以簡略寫成 *m。因此，*63 表示最少 0 個，最多 63 個。/ 表示或規則，表示兩邊的實體可選。()表示其中的實體必須得有一個。- 表示范圍。因此，DIGIT 表示單個數字，ALPHA 表示單個字母(大寫或者小寫)，(ALPHA/ DIGIT/ “_” )表示要麼是個字母，要麼是個數字，要麼是個下劃線。*63(ALPHA/ DIGIT/ “_” )表示，最少 0 個，最多 63 個字母或者數字或者下劃線。兩個實體順序寫在一起，表示一種順序關系，ALPHA *63(ALPHA/ DIGIT/ “_” ) 表示，以字母開始，後面最少 0 個，最多 63 個 字母或者數字或者下劃線。
根據前面的內容可以很容易地直接表達出用於解析這個語法規則的解析器來。如下：
class H248Parsec
{
public static Parser alpha() {
return new SAT(new IsAlpha()， new Item());
}
public static Parser digit() {
return new SAT(new IsDigit()， new Item());
}
public static Parser underline() {
return new SAT(new IsUnderline()， new Item());
}
public static Parser digit_or_alpha_or_underline() {
return new OR(alpha()， new OR(digit()， underline()));
}
public static Parser zero_or_many(int max， Parser parser){
return new OR(new OneOrMany(max，parser)， new Zero());
}
public static Parser name() {
return new SEQ(alpha()，
zero_or_many(64，
digit_or_alpha_or_underline()));
}
}
可以看出，我們的代碼和協議中的語法描述基本上完全一樣，我們通過定義自己的面向解析的 DSL，把 Java 這種通用語言變成了用於 ABNF 語法解析的專門語言，符合 Ward Cunningham 關於美的代碼的定義。最後，我們用該解析器來做一些關於 NAME 語法識別的實驗。
