abnf java实现_详细讲解如何利用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 語法識別的實驗，如下表所示：
總結
以上是生活随笔為你收集整理的abnf java实现_详细讲解如何利用Java实现组合式解析器？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 融资融券担保品折算率是什么
- 下一篇： GUI动画演示java_java –