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