在簡要討論了語法、解析器和 BNF 后，本文將介紹 JavaCC，這是一個流行的解析器生成器工具。您將開發使用 JavaCC 的樣本代碼來構建定制的解析器，先從語法的 BNF 描述開始。第 2 部分接著將演示如何使用輔助工具 ― JJTree 來構建同一解析的解析樹表示，以及如何在運行時遍歷該樹，以發現其狀態信息。文章將以開發構建和遍歷解析樹的樣本代碼作為結束，該解析樹是您為一小部分 XQuery 語法生成的。
要完成最簡單的日常解析任務，您不需要使用象自動化解析器生成器那樣復雜的任何東西。例如，同“梳理”CSV（逗號分割的值，Comma-Separated-Value）文件的各部分同樣簡單的編程練習需要了解文件的結構，可能還需要了解如何使用 Java StringTokenizer 。另外，CSV 練習還需要了解很少的解析理論知識或者將自動化工具應用于任務的需求。
但是，一旦正式描述它的某種語言和語法變得復雜，那么語言中的有效表達式數量將迅速增加。而能夠手工處理將任意表達式解析成其組成部分（這或多或少是解析更簡明的定義）所需的代碼將變得越來越困難。自動化解析器生成器減輕了這種困難。其他程序員或許也可以將您生成的解析器用于他們自己的用途。
從 BNF 開始
復雜語言的語法通常都是使用 BNF（巴科斯-諾爾范式，Backus-Naur Form）表示法或者其“近親”― EBNF（擴展的 BNF）描述的。自動化工具可以使用那些描述（我將使用通用的術語 BNF來指代這兩種變體）或與它們近似的描述來為您生成解析代碼。本文就描述了這樣的一種解析器-生成器工具，稱為 JavaCC。我將簡要地研究一下 JavaCC 的基本知識，并在結束的時候花些時間研究一下它的一個輔助工具 ― JJTree，但是在討論中不會介紹太多的理論知識，以免偏離主題。本文力圖闡明我的理念：您并不需要了解很多有關正規的解析理論就能進行解析！
為什么使用 JavaCC 呢？有幾個原因：我對 XQuery 有著強烈的興趣，而 W3C 的 XML Query 工作組恰好使用 JavaCC 來構建并測試 XQuery 語法的版本，并且構建和測試它與 XSL 組共享的 XPath 語法。我還使用 JavaCC 來提供 XQEngine 中的查詢-解析代碼，XQEngine 是我自己的開放源碼 XQuery 實現（請參閱 參考資料）。
最后一點（但不是最不重要的），價格是完全合適的：盡管 JavaCC 不是開放源碼，但它是完全免費的。（請參閱 參考資料以了解有關如何獲得 JavaCC 的信息）。
解析 101
在我開始介紹一些實際的 XQuery 語法之前，讓我們先從一個非常簡單的 BNF 開始，它描述了一種語言，該語言僅由兩個只對整數進行運算的算術運算符構成。我稱這種語言為 SimpleLang ：
simpleLang ::= integerLiteral ( ( "+" | "-" ) integerLiteral )?
integerLiteral ::= [ 0-9 ]+
|
該語法中的每個規則都是一個 結果（production） ，其中左邊的項（結果的名稱）是依據語法中的其它結果描述的。最上面的結果 simpleLang 表明，該語言中有效的（或合法的）表達式是這樣構成的，一個整數值，可以任意選擇其后跟一個加號（+）或減號（-）以及另一個整數值或不跟任何東西。按照這種語法，單個整數“42”是有效的，同樣，表達式“42 + 1”也是有效的。第二個結果以類 regex 的方式更特定地描述了一個整數值看上去象什么：一個或多個數字的連續序列。
該語法描述了兩個結果 simpleLang 和 integerLiteral 之間存在的抽象關系。它還詳細描述了三個 記號（加號、減號和整數）組合的具體項，解析器在掃描整個輸入流時希望遇到這些項。解析器中負責該任務的部件稱為 掃描器（scanner）或 記號賦予器（tokenizer） 一點也不稀奇。在該語言中， simpleLang 是 非終端（non-terminal） 符號的一個示例，它對其它結果進行引用；另一方面，規則 integerLiteral 描述了 終端（terminal）符號：這是一種不能進一步分解成其它結果的符號。
如果解析器在其掃描期間發現了除這三個記號外的任何 其它記號，則認為它正在掃描的表達式是無效的。解析器的主要工作之一就是確定您傳遞給它的任何表達式的有效性，并且讓您知道。一旦認為某個表達式是有效的，則它的第二項工作是將輸入流分解成其組件塊，并以某個有用的方式將它們提供給您。
從 BNF 到 JavaCC
讓我們看看如何使用 JavaCC 實現該語法。JavaCC 使用稱為 .jj 的文件。該文件中的語法描述是使用非常類似于 BNF 的表示法編寫的，這樣從一種形式轉換到另一種形式通常就相當容易。（該表示法有自己的語法，從而使其在 JavaCC 中是可表達的。）
JavaCC .jj 文件語法和標準的 BNF 之間的主要區別在于：利用 JavaCC 版本，您可以在語法中嵌入操作。一旦成功遍歷了語法中的那些部分，則執行這些操作。操作都是 Java 語句，它們是解析器 Java 源代碼的一部分，該部分作為解析器生成過程的一部分產生。
（注：除了一條 Java println() 語句外， 清單 1并不包含您需要用來對該語言中的表達式實際求值的嵌入式 Java 代碼。當您研究過 JJTree 及其解析樹表示后，我將對此做更詳細的研究。）
清單 1. 編碼 SimpleLang 語法的完整 .jj 腳本
PARSER_BEGIN( Parser_1 )
package examples.example_1;
public class Parser_1 {}
PARSER_END( Parser_1 )
void simpleLang() : {} { integerLiteral()
( ( "+" | "-" ) integerLiteral() )? <EOF> }
void integerLiteral() : {Token t;} { t=<INT>
{ System.out.println("integer = "+t.image); }}
SKIP : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }
|
請注意有關該文件的下述情形：
-
PARSER_BEGIN
和 PARSER_END 偽指令指定了要生成的 Java 解析器的名稱（Parser_1.java），并提供一個位置以便將 Java 語句插入該類。在這個案例中，您正將一個 Java package 語句放置在文件的頂部。該 package 語句也放置在 Java 助手類文件的頂部，該文件是作為生成過程一部分產生的（請參閱 JavaCC 編譯過程 ）。盡管我在本示例中沒有這樣做，但是這也是一個聲明實例變量的好場所，該實例變量將由您結果中的 Java 語句引用。如果您喜歡，甚至可以在這里插入 Java main() 過程，并且使用它來構建獨立的應用程序，以啟動和測試您正在生成的解析器。
- JavaCC 語法看上去象一個過程，而結果看上去非常象進行方法調用。這并非偶然。在 JavaCC 編譯這個腳本時產生的 Java 源代碼包含與這些結果具有相同名稱的方法；這些方法在運行時按照它們在 .jj 腳本中調用的順序執行。我將在 遍歷解析代碼中為您演示那是如何工作的。（這里的術語“編譯”也不是偶然的 ― 解析器生成器通常也稱為“編譯器的編譯器”。）
- 花括號（{ 和 }) 內描述了結果的主體，并且排除了任何您正在嵌入的 Java 操作。請注意
integerLiteral 規則中用花括號包括的 System.out.println() 語句。該操作作為方法 Parser_1.integerLiteral() 的一部分產生。每當解析器遇到整數時，都執行該操作。
- 文件結尾的
SKIP 語句表明，在記號之間可以出現空白（空格、跳格、回車和換行），空白將被忽略。
-
TOKEN
語句包含類似 regex 的表達式，該表達式描述了整數記號看起來象什么。在前面的結果中，對這些記號的引用是用尖括號括起來的。
- 第二個結果
integerLiteral() 聲明了類型 Token （JavaCC 的內置類）的局部變量 t 。當在輸入流中遇到整數時會 觸發 該規則，該整數（象文本一樣）的值被賦給實例變量 t.image 。另一個 Token 字段 t.kind 被賦值為一個枚舉（enum），表明這個特殊的記號是一個整數，而不是解析器所知的另一種類型的記號。最后，在解析器中生成的 Java System.out.println() 代碼可以在解析時在那個記號的內部使用 t.image 進行訪問并且打印其文本值。
|
遍歷解析器代碼
讓我們非常簡要地了解一下您生成的解析器的內部原理。出于下面兩個原因，稍微了解由特殊的 .jj 語法生成的方法以及其在運行時的執行順序是很有用的：
- 有時候（特別是當您第一次做的時候），解析器似乎返回了不同的結果，而您認為是 .jj 文件指示它這樣做的。您可以在運行時單步遍歷產生的解析器代碼，以便查看它到底在做什么，并相應地調整語法文件。我現在還經常這樣做。
- 如果您知道結果／方法的執行順序，那么您將對在腳本中的什么地方嵌入 Java 操作以獲得特定的結果有更好的理解。在第 2 部分談論有關 JJTree 工具和解析樹表示時，我將回過頭來更詳細地討論這一內容。
盡管深入研究已生成解析器的詳細信息超越了本文的范圍，但是 清單 2 還是顯示了為方法 Parser_1.integerLiteral() 生成的代碼。這可能會讓您對最終代碼看起來象什么有一些了解。特別需要注意方法中的最后一條語句： System.out.println( "integer = "+t.image) 。該語句作為嵌入 .jj 腳本的 Java 操作發揮作用。
清單 2. Parser_1 中生成的方法
static final public void integerLiteral() throws ParseException {
Token t;
t = jj_consume_token(INT);
System.out.println( "integer = "+t.image);
}
|
以下高級、詳盡的描述說明了這個解析器將做什么：
- 最上面的方法
simpleLang() 調用 integerLiteral() 。
-
integerLiteral()
希望在輸入流中立即遇到一個整數，否則該表達式將無效。為了驗證這一點，它調用記號賦予器（Tokenizer.java）以返回輸入流中的下一個記號。記號賦予器穿過輸入流，每次檢查一個字符，直到它遇到一個整數或者直至文件結束。如果是前者，則以 <INT> 記號將值“包”起來；如果是后者，則當作 <EOF> ；并將記號返回給 integerLiteral() 做進一步處理。如果記號賦予器未遇到這兩個記號，則返回詞法錯誤。
- 如果記號賦予器返回的記號不是整數記號或
<EOF> ，那么 integerLiteral() 拋出 ParseException ，同時解析完成。
- 如果它是整數記號，表達式仍然可能是有效的，
integerLiteral() 再次調用記號賦予器以返回下一個記號。如果返回 <EOF> ，則由單個整數構成的整個表達式都是有效的，解析器將控制返還給調用應用程序。
- 如果記號賦予器返回加號或減號記號，則表達式仍然是有效的，
integerLiteral() 將最后一次調用記號賦予器，以尋找另一個整數。如果遇到一個整數，則表達式是有效的，解析器將完成工作。如果下一個記號不是整數，則解析器拋出異常。
注：如果解析器失敗了，則拋出 ParseException 或 TokenMgrError 。任何一種異常都表明您的表達式是無效的。
這里的 要點 是，只有當解析器成功地遍歷了嵌入 Java 操作的那部分結果后，才能執行嵌入到這兩個結果中的任何 Java 操作。如果將表達式“42 + 1”傳遞給該解析器，則語句 integer = 42 將被打印到控制臺，后跟 integer = 1 。如果運行無效的表達式“42 + abc”，則產生消息 integer = 42 ，后跟 catch 塊消息 a Token Manager error! 。在后一種情形中，解析器只成功地遍歷了 simpleLang 結果中的第一個 integerLiteral() 項，而未成功遍歷第二項：
void simpleLang() : {} { integerLiteral() ( ("+" | "-") integerLiteral() )? <EOF> }
|
換而言之，第二個 integerLiteral() 方法未被執行，因為未遇到希望的整數標記。
JavaCC 編譯過程
當您對 .jj 文件運行 JavaCC 時，它會生成許多 Java 源文件。其中一個是主解析代碼 Parser_1.java，當您有一個要解析的表達式時，您將從您的應用程序調用該代碼。JavaCC 還創建了其它六個由解析器使用的輔助文件。JavaCC 總共生成了以下七個 Java 文件。前三個是特定于這個特殊語法的；后四個是通用的助手類 Java 文件，無論語法是怎么樣的，都會生成這幾個文件。
- Parser_1.java
- Parser_1Constants.java
- Parser_1TokenManager.java
- ParseException.java
- SimpleCharStream.java
- Token.java
- TokenMgrError.java
一旦 JavaCC 生成了這七個 Java 源文件，則可以編譯它們并將它們鏈接到您的 Java 應用程序中。然后可以從您的應用程序代碼調用新的解析器，從而將表達式傳遞給它進行求值。下面是一個樣本應用程序，它實例化您的解析器，并且為它提供了一個硬連接在應用程序頂部的表達式。
清單 3：調用第一個解析器
package examples.example_1;
import examples.example_1.Parser_1;
import examples.example_1.ParseException;
import java.io.StringReader;
public class Example_1
{
static String expression = "1 + 42";
public static void main( String[] args )
//--------------------------------------
{
new Example_1().parse( expression );
}
void parse( String expression )
//-----------------------------
{
Parser_1 parser = new Parser_1( new StringReader( expression ));
try
{
parser.simpleLang();
}
catch( ParseException pe ) {
System.out.println( "not a valid expression" );
}
catch( TokenMgrError e ) {
System.out.println( "a Token Manager error!" );
}
}
}
|
這里有什么是值得注意的呢？
- 要調用
Parser_1 中的解析代碼，需要調用該類中的方法 simpleLang() 。.jj 文件中的結果順序通常是無關的，而本案例除外，在本案例中，語法中最頂部的結果名稱用于調用解析器。
- 如果正在傳遞給解析器代碼的表達式不能根據語法合法地構造，則將拋出
ParseException 或 LexicalError 。
- 如果表達式是有效的，則執行嵌入語法各部分的任何 Java 操作，這些語法部分都被成功遍歷，就象 遍歷解析器代碼結尾描述的一樣。
結束語
這篇文章結束后還有第 2 部分。您將從類似的樣本代碼開始著手，學習如何使用 JavaCC 的“伙伴”工具 JJTree 來創建在運行時構建解析的解析樹表示的解析器，而不是執行嵌入 .jj 腳本的操作。正如您將看到的，這有很多優點。
參考資料
關于作者
|
|
|
Howard Katz 居住在加拿大溫哥華，他是 Fatdog Software 的唯一業主，該公司專門致力于開發搜索 XML 文檔的軟件。在過去的大約 35 年里，他一直是活躍的程序員（一直業績良好），并且長期為計算機貿易出版機構撰寫技術文章。Howard 是 Vancouver XML Developer's Association 的共同主持人，還是 Addison Wesley 即將出版的書籍 The Experts on XQuery的編輯，該書由 W3C 的 Query 工作組成員合著，概述了有關 XQuery 的技術前景。他和他的妻子夏天去劃船，冬天去邊遠地區滑雪。可以通過 howardk@fatdog.com與 Howard 聯系。
|