本文的第 1 部分簡要討論了語法、解析器和 BNF。然后它介紹了 JavaCC，一個流行的解析器生成器。第 2 部分演示了如何修改第 1 部分中的樣本代碼，這樣就可以使用附加工具 JJTree 來構(gòu)建相同解析的解析樹表示。您將探索這種方法的優(yōu)點，并研究如何編寫 Java 代碼在運行時遍歷該解析樹以便恢復(fù)其狀態(tài)信息，并對正在解析的表達式求值。本文結(jié)尾將演示如何開發(fā)通用例程，用于遍歷從一小部分 XQuery 語法生成的解析樹，并對其求值。
使用 JavaCC 解析器生成器有一個嚴(yán)重缺點：許多或大多數(shù)客戶機端 Java 代碼需要嵌入到 .jj 語法腳本中，該腳本編碼了您的 BNF（巴科斯-諾爾范式，Backus-Naur Form）。這意味著您失去了在開發(fā)周期中合適的 Java IDE 可以向您提供的許多優(yōu)點。
開始使用 JJTree 吧，它是 JavaCC 的伙伴工具。JJTree 被設(shè)置成提供一個解析器，該解析器在運行時的主要工作不是執(zhí)行嵌入的 Java 操作，而是構(gòu)建正在解析的表達式的獨立解析樹表示。這樣，您就可以獨立于生成該解析樹的解析代碼，捕捉在運行時易于遍歷和查詢的單個樹中的解析會話的狀態(tài)。使用解析樹表示還會使調(diào)試變得更容易，并縮短開發(fā)時間。JJTree 是作為 JavaCC 分發(fā)版（distribution）的一部分發(fā)布的（請參閱 參考資料）。
在我們繼續(xù)之前，我要特別提一下，術(shù)語 解析樹和 抽象語法樹（或 AST）描述了非常相似的語法結(jié)構(gòu)。嚴(yán)格地講，對于我在下面提到的解析樹，語言理論家更精確地把它稱作 AST。
要使用 JJTree，您需要能夠：
- 創(chuàng)建 JJTree 作為輸入獲取的 .jjt 腳本
- 編寫客戶機端代碼以遍歷在運行時生成的解析樹并對其求值
本文演示了如何執(zhí)行這兩種操作。它并沒有涵蓋所有內(nèi)容，但肯定能帶您入門。
JJTree 基礎(chǔ)知識
JJTree 是一個預(yù)處理器，為特定 BNF 生成解析器只需要簡單的兩步：
- 對所謂的 .jjt 文件運行 JJTree；它會產(chǎn)生一個中間的 .jj 文件
- 用 JavaCC 編譯該文件（ 第 1 部分中討論了這個過程）
幸運的是，.jjt 文件的結(jié)構(gòu)只是我在第 1 部分中向您顯示的 .jj 格式的較小擴展。主要區(qū)別是 JJTree 添加了一個新的語法 node-constructor構(gòu)造，該構(gòu)造可以讓您指定在解析期間在哪里以及在什么條件下生成解析樹節(jié)點。換句話說，該構(gòu)造管理由解析器構(gòu)造的解析樹的形狀和內(nèi)容。
清單 1 顯示了一個簡單的 JavaCC .jj 腳本，它類似于您在第 1 部分中看到的腳本。為簡便起見，我只顯示了結(jié)果。
清單 1. simpleLang 的 JavaCC 語法
void simpleLang() : {} { addExpr() <EOF> }
void addExpr() : {} { integerLiteral() ( "+" integerLiteral() )? }
void integerLiteral() : {} { <INT> }
SKIP : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }
|
該語法說明了該語言中的合法表達式包含：
- 單個整數(shù)文字，或
- 一個整數(shù)文字，后面跟一個加號，再跟另一個整數(shù)文字。
對應(yīng)的 JJTree .jjt 腳本（再次聲明，略有簡化）看上去可能如下：
清單 2. 等價于清單 1 中的 JavaCC 語法的 JJTree
SimpleNode simpleLang() : #Root {} { addExpr() <EOF> { return jjtThis; }}
void addExpr() : {} { integerLiteral()
( "+" integerLiteral() #Add(2) )? }
void integerLiteral() : #IntLiteral {} { <INT> }
SKIP : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }
|
該腳本對您已經(jīng)看到的腳本添加了一些新的語法特性。現(xiàn)在，我們只討論突出顯示的部分。以后，我會詳細(xì)說明。
逐句說明 JJTree 語法
首先請注意，最頂層的 simpleLang() 結(jié)果的 JavaCC 的過程性語法現(xiàn)在指定了一個返回類型： SimpleNode 。它與嵌入的 Java 操作 return jjtThis （有一點為 JJTree 虛張聲勢）一起指定了從應(yīng)用程序代碼調(diào)用解析器的 simpleLang() 方法將返回解析樹的根，然后這個根將用于樹遍歷。
在 JavaCC 中，解析器調(diào)用看上去如下：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
parser.simpleLang();
|
而現(xiàn)在看上去象下面這樣：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
SimpleNode rootNode = parser.simpleLang();
|
注：所抓取的根節(jié)點并不僅僅是 SimpleNode 類型。它其實是 Root 類型，正如 清單 2 中的 #Root 偽指令所指定的（雖然您不會在上述調(diào)用代碼中那樣使用）。 Root 是 SimpleNode 子代，就象 JJTree 生成的解析器構(gòu)造的每個節(jié)點一樣。我將在下面向您顯示 SimpleNode 的一些內(nèi)置方法。
addExpr()
結(jié)果中的 #Add(2) 構(gòu)造與上述的 #Root 偽指令不同，體現(xiàn)在以下幾方面；
- 它是參數(shù)化的。樹構(gòu)建器在構(gòu)造樹期間使用節(jié)點堆棧；沒有參數(shù)的節(jié)點構(gòu)建器的缺省行為是將自己放在正在構(gòu)造的解析樹的頂部，將所有節(jié)點彈出在同一個 節(jié)點作用域 中創(chuàng)建的節(jié)點堆棧，并把自己提升到那些節(jié)點父代的位置。參數(shù)
2 告訴新的父節(jié)點（在此示例中是一個 Add 節(jié)點）要恰好采用 兩個子節(jié)點，它們是 下一段文字 中描述的兩個 IntLiteral 子節(jié)點。JJTree 文檔更詳細(xì)地描述了這個過程。使用好的調(diào)試器在運行時遍歷解析樹是另一個寶貴的輔助方法，它有助于理解樹構(gòu)建在 JJTree 中是如何工作的。
-
將
#Root 偽指令放在其結(jié)果的主體之外表示 每次 遍歷該結(jié)果時都會生成一個 Root 節(jié)點（而在此特定示例中，只允許發(fā)生一次），這一點具有同等的重要性 。但是，將 #Add(2) 偽指令放在可選的“零或一”項中表示僅當(dāng)在解析期間遍歷包含它的選擇子句時 ― 換句話說，當(dāng)該結(jié)果表示一個真的加法操作時 ― 才 有條件地 生成一個 Add 節(jié)點。當(dāng)發(fā)生這種情況時，會遍歷 integerLiteral() 兩次，每次調(diào)用時都將一個 IntLiteral 節(jié)點添加到樹上。這兩個 IntLiteral 節(jié)點都成為調(diào)用它們的 Add 節(jié)點的子節(jié)點。但是，如果正在解析的表達式是單個整數(shù)，那么作為結(jié)果的 IntLiteral 節(jié)點將直接成為 Root 的一個子節(jié)點。
一圖勝千言（引用一句古老的諺語）。以下是由上述語法生成的兩種類型的解析樹的圖形表示：
圖 1：單個整數(shù)表達式的解析樹
圖 2：加法操作的解析樹
讓我們更詳細(xì)地研究 SimpleNode 的類層次結(jié)構(gòu)。
使用解析樹
在 .jjt 腳本中聲明的每個節(jié)點都指示解析器生成 JJTree SimpleNode 的一個子類。接下來， SimpleNode 又實現(xiàn)名為 Node 的 Java 接口。這兩個類的源文件都是由 JJTree 腳本和定制 .jj 文件一起自動生成的。 清單 1 顯示了定制 .jj 文件的當(dāng)前示例。在當(dāng)前示例中，JJTree 還提供了您自己的 Root 、 Add 和 IntLiteral 類以及沒有在這里看到的一些附加的助手類的源文件。
所有 SimpleNode 子類都繼承了有用的行為。 SimpleNode 方法 dump() 就是這樣一個例子。它還充當(dāng)了我以前的論點（使用解析樹使調(diào)試更容易，從而縮短開發(fā)時間）的示例。以下三行客戶機端代碼的代碼片段實例化了解析器、調(diào)用解析器、抓取所返回的解析樹，并且將一個簡單的解析樹的文本表示轉(zhuǎn)儲到控制臺：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
SimpleNode rootNode = parser.simpleLang();
rootNode.dump();
|
圖 2
中的樹的調(diào)試輸出是：
Root
Add
IntLiteral
IntLiteral
|
輔助導(dǎo)航
另一個有用的內(nèi)置 SimpleNode 方法是 jjtGetChild(int) 。當(dāng)您在客戶機端向下瀏覽解析樹，并且遇到 Add 節(jié)點時，您會要抓取它的 IntLiteral 子節(jié)點、抽取它們表示的整數(shù)值，并將這些數(shù)字加到一起 ― 畢竟，那是用來練習(xí)的。假設(shè)下一段代碼中顯示的 addNode 是表示我們感興趣的 Add 類型節(jié)點的變量，那我們就可以訪問 addNode 的兩個子節(jié)點。（ lhs 和 rhs 分別是 左邊（left-hand side）和 右邊（right-hand side）的常用縮寫。）
SimpleNode lhs = addNode.jjtGetChild( 0 );
SimpleNode rhs = addNode.jjtGetChild( 1 );
|
即使到目前為止您已經(jīng)執(zhí)行了所有操作，但您仍然沒有足夠的信息來計算該解析樹表示的算術(shù)運算的結(jié)果。您的當(dāng)前腳本已經(jīng)省略了一個重要的細(xì)節(jié)：樹中的兩個 IntLiteral 節(jié)點實際上不包含它們聲稱要表示的整數(shù)。那是因為當(dāng)記號賦予器（tokenizer）在輸入流中遇到它們時，您沒有將它們的值保存到樹中；您需要修改 integerLiteral() 結(jié)果來執(zhí)行該操作。您還需要將一些簡單的存取器方法添加到 SimpleNode 。
保存和恢復(fù)狀態(tài)
要將所掃描的記號的值存儲到適當(dāng)?shù)墓?jié)點中，將以下修改添加到 SimpleNode ：
public class SimpleNode extends Node
{
String m_text;
public void setText( String text ) { m_text = text; }
public String getText() { return m_text; }
...
}
|
將 JJTree 腳本中的以下結(jié)果：
void integerLiteral() : #IntLiteral {} <INT> }
|
更改成：
void integerLiteral() : #IntLiteral { Token t; }
{ t=<INT> { jjtThis.setText( t.image );} }
|
該結(jié)果抓取它剛在 t.image 中遇到的整數(shù)的原始文本值，并使用您的 setText() setter 方法將該字符串存儲到當(dāng)前節(jié)點中。 清單 5 中的客戶機端 eval() 代碼顯示了如何使用相應(yīng)的 getText() getter 方法。
可以很容易地修改 SimpleNode.dump() ，以提供任何節(jié)點的 m_text 值供其在解析期間存儲 ― 我把這作為一個眾所周知的練習(xí)留給您來完成。這將讓您更形象地理解在進行調(diào)試時解析樹看起來是什么樣子。例如，如果您解析了“42 + 1”，略經(jīng)修改的 dump() 例程可以生成以下有用的輸出：
Root
Add
IntLiteral[42]
IntLiteral[1]
|
組合：XQuery 的 BNF 代碼片段
讓我們通過研究實際語法的一個代碼片段來進行組合和總結(jié)。我將向您演示一段非常小的 XQuery 的 BNF 子集，這是 XML 的查詢語言的 W3C 規(guī)范（請參閱 參考資料）。我在這里所說的大多數(shù)內(nèi)容也適用于 XPath，因為這兩者共享了許多相同的語法。我還將簡要地研究運算符優(yōu)先級的問題，并將樹遍歷代碼推廣到成熟的遞歸例程中，該例程可以處理任意復(fù)雜的解析樹。
清單 3
顯示了您要使用的 XQuery 語法片段。這段 BNF 摘自 2002 年 11 月 15 日的工作草案：
清單 3：一部分 XQuery 語法
[21] Query ::= QueryProlog QueryBody
...
[23] QueryBody ::= ExprSequence?
[24] ExprSequence ::= Expr ( "," Expr )*
[25] Expr ::= OrExpr
...
[35] RangeExpr ::= AdditiveExpr ( "to" AdditiveExpr )*
[36] AdditiveExpr ::= MultiplicativeExpr (("+" | "-") MultiplicativeExpr )*
[37] MultiplicativeExpr ::= UnionExpr (("*" | "div" | "idiv" | "mod") UnaryExpr )*
...
|
您將要構(gòu)建一個剛好適合的 JJTree 語法腳本來處理結(jié)果 [36] 和 [37] 中的 + 、 - 、 * 和 div 運算符，而且簡單地假設(shè)該語法所知道的唯一數(shù)據(jù)類型是整數(shù)。該樣本語法 非常小，并不能妥善處理 XQuery 支持的豐富的表達式和數(shù)據(jù)類型。但是，如果您要為更大、更復(fù)雜的語法構(gòu)建解析器，它應(yīng)該能給您使用 JavaCC 和 JJTree 的入門知識。
清單 4
顯示了 .jjt 腳本。請注意該文件頂部的 options{} 塊。這些選項（還有許多其它可用選項開關(guān)）指定了其中樹構(gòu)建在本例中是以 多重 方式運行的，即節(jié)點構(gòu)造器用于顯式地命名所生成節(jié)點的類型。備用方法（不在這里研究）是結(jié)果只將 SimpleNode 節(jié)點提供給解析樹，而不是它的子類。如果您想要避免擴散節(jié)點類，那么該選項很有用。
還請注意原始的 XQuery BNF 經(jīng)常將多個運算符組合到同一個結(jié)果中。在 清單 4中，我已經(jīng)將這些運算符分離到 JJTree 腳本中的單獨結(jié)果中，因為這讓客戶機端的代碼更簡單。要進行組合，只需存儲已掃描的運算符的值，就象對整數(shù)所進行的操作一樣。
清單 4：清單 3 中的 XQuery 語法的 JJTree 腳本
options {
MULTI=true;
NODE_DEFAULT_VOID=true;
NODE_PREFIX="";
}
PARSER_BEGIN( XQueryParser )
package examples.example_2;
public class XQueryParser{}
PARSER_END( XQueryParser )
SimpleNode query() #Root : {} { additiveExpr() <EOF> { return jjtThis; }}
void additiveExpr() : {} { subtractiveExpr()
( "+" subtractiveExpr() #Add(2) )* }
void subtractiveExpr() : {} { multiplicativeExpr()
( "-" multiplicativeExpr() #Subtract(2) )* }
void multiplicativeExpr() : {} { divExpr() ( "*" divExpr() #Mult(2) )* }
void divExpr() : {} { integerLiteral()
( "div" integerLiteral() #Div(2) )* }
void integerLiteral() #IntLiteral : { Token t; }
{ t=<INT> { jjtThis.setText(t.image); }}
SKIP : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }
|
該 .jjt 文件引入了幾個新的特性。例如，該語法中的運算結(jié)果現(xiàn)在是 迭代的 ：通過使用 * （零次或多次）發(fā)生指示符來表示它們的可選的第二項，這與 清單 2 中的 ? （零次或一次）表示法相反。該腳本所提供的解析器可以解析任意長的表達式，如“1 + 2 * 3 div 4 + 5”。
實現(xiàn)優(yōu)先級
該語法還知道 運算符優(yōu)先級。例如，您期望乘法的優(yōu)先級比加法高。在實際例子中，這表示諸如“1 + 2 * 3”這樣的表達式將作為“1 + ( 2 * 3 )”進行求值，而不是“( 1 + 2 ) * 3”。
優(yōu)先級是通過使用級聯(lián)樣式實現(xiàn)的，其中每個結(jié)果會調(diào)用緊隨其后的較高優(yōu)先級的結(jié)果。級聯(lián)樣式和節(jié)點構(gòu)造的位置和格式保證了以正確的結(jié)構(gòu)生成解析樹，這樣樹遍歷可以正確執(zhí)行。用一些直觀圖形也許更易于理解這一點。
圖 3
顯示了由此語法生成的解析樹，它可以讓您正確地將“1 + 2 * 3”當(dāng)作“1 + ( 2 * 3 )”進行求值。請注意， Mult 運算符與它的項之間的聯(lián)系比 Plus 更緊密，而這正是您希望的：
圖 3. 結(jié)構(gòu)正確的樹
而 圖 4顯示的樹（該語法 不會生成這樣的樹）表示您（錯誤地）想要將該表達式當(dāng)作“(1 + 2) * 3”求值。
圖 4. 結(jié)構(gòu)不正確的樹
遍歷解析樹客戶機端
就象我曾答應(yīng)的，我將用客戶機端代碼的清單作為總結(jié)，該清單將調(diào)用該解析器并遍歷它生成的解析樹，它使用簡單而功能強大的遞歸 eval() 函數(shù)對樹遍歷時遇到的每個節(jié)點執(zhí)行正確操作。 清單 5中的注釋提供了關(guān)于內(nèi)部 JJTree 工作的附加詳細(xì)信息。
清單 5. 可容易泛化的 eval() 例程
// return the arithmetic result of evaluating 'query'
public int parse( String query )
//------------------------------
{
SimpleNode root = null;
// instantiate the parser
XQueryParser parser = new XQueryParser( new StringReader( query ));
try {
// invoke it via its topmost production
// and get a parse tree back
root = parser.query();
root.dump("");
}
catch( ParseException pe ) {
System.out.println( "parse(): an invalid expression!" );
}
catch( TokenMgrError e ) {
System.out.println( "a Token Manager error!" );
}
// the topmost root node is just a placeholder; ignore it.
return eval( (SimpleNode) root.jjtGetChild(0) );
}
int eval( SimpleNode node )
//-------------------------
{
// each node contains an id field identifying its type.
// we switch on these. we could use instanceof, but that's less efficient
// enum values such as JJTINTLITERAL come from the interface file
// SimpleParserTreeConstants, which SimpleParser implements.
// This interface file is one of several auxilliary Java sources
// generated by JJTree. JavaCC contributes several others.
int id = node.id;
// eventually the buck stops here and we unwind the stack
if ( node.id == JJTINTLITERAL )
return Integer.parseInt( node.getText() );
SimpleNode lhs = (SimpleNode) node.jjtGetChild(0);
SimpleNode rhs = (SimpleNode) node.jjtGetChild(1);
switch( id )
{
case JJTADD : return eval( lhs ) + eval( rhs );
case JJTSUBTRACT : return eval( lhs ) - eval( rhs );
case JJTMULT : return eval( lhs ) * eval( rhs );
case JJTDIV : return eval( lhs ) / eval( rhs );
default :
throw new java.lang.IllegalArgumentException(
"eval(): invalid operator!" );
}
}
|
|
結(jié)束語
如果您想要查看可以處理許多實際 XQuery 語法的功能更豐富的 eval() 函數(shù)版本，歡迎下載我的開放源碼 XQuery 實現(xiàn)（XQEngine）的副本（請參閱 參考資料 ）。它的 TreeWalker.eval() 例程 例舉了 30 多種 XQuery 節(jié)點類型。還提供了一個 .jjt 腳本。
參考資料
關(guān)于作者
|
|
|
Howard Katz 居住在加拿大溫哥華，他是 Fatdog Software 的唯一業(yè)主，該公司專門致力于開發(fā)搜索 XML 文檔的軟件。在過去的大約 35 年里，他一直是活躍的程序員（一直業(yè)績良好），并且長期為計算機貿(mào)易出版機構(gòu)撰寫技術(shù)文章。Howard 是 Vancouver XML Developer's Association 的共同主持人，還是 Addison Wesley 即將出版的書籍 The Experts on XQuery的編輯，該書由 W3C 的 Query 工作組成員合著，概述了有關(guān) XQuery 的技術(shù)前景。他和他的妻子夏天去劃船，冬天去邊遠地區(qū)滑雪。可以通過 howardk@fatdog.com與 Howard 聯(lián)系。
|