利用Java實現組合式解析器

簡介：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 語法識別的實驗，如下表所示：

輸入字符串 成功標志 識別結果 剩余字符串 "" false "" "" "_U" false "" "" "2U" false "" "" "U" true "U" "" "U {" true "U" "{" "U2 {" True "U2" "{" "U_{" true "U_" "{" "U123_{" True "U123_" "{" "USER001" True "USER001" "" "USER001{" True "USER001" "{" "a0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789" True "a0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123" "456789"