本文的第 1 部分簡要討論了語法、解析器和 BNF。然后它介紹了 JavaCC，一個流行的解析器生成器。第 2 部分演示了如何修改第 1 部分中的樣本代碼，這樣就可以使用附加工具 JJTree 來構建相同解析的解析樹表示。您將探索這種方法的優點，并研究如何編寫 Java 代碼在運行時遍歷該解析樹以便恢復其狀態信息，并對正在解析的表達式求值。本文結尾將演示如何開發通用例程，用于遍歷從一小部分 XQuery 語法生成的解析樹，并對其求值。
使用 JavaCC 解析器生成器有一個嚴重缺點：許多或大多數客戶機端 Java 代碼需要嵌入到 .jj 語法腳本中，該腳本編碼了您的 BNF（巴科斯-諾爾范式，Backus-Naur Form）。這意味著您失去了在開發周期中合適的 Java IDE 可以向您提供的許多優點。
開始使用 JJTree 吧，它是 JavaCC 的伙伴工具。JJTree 被設置成提供一個解析器，該解析器在運行時的主要工作不是執行嵌入的 Java 操作，而是構建正在解析的表達式的獨立解析樹表示。這樣，您就可以獨立于生成該解析樹的解析代碼，捕捉在運行時易于遍歷和查詢的單個樹中的解析會話的狀態。使用解析樹表示還會使調試變得更容易，并縮短開發時間。JJTree 是作為 JavaCC 分發版（distribution）的一部分發布的（請參閱 參考資料）。
在我們繼續之前，我要特別提一下，術語 解析樹和 抽象語法樹（或 AST）描述了非常相似的語法結構。嚴格地講，對于我在下面提到的解析樹，語言理論家更精確地把它稱作 AST。
要使用 JJTree，您需要能夠：
- 創建 JJTree 作為輸入獲取的 .jjt 腳本
- 編寫客戶機端代碼以遍歷在運行時生成的解析樹并對其求值
本文演示了如何執行這兩種操作。它并沒有涵蓋所有內容，但肯定能帶您入門。
JJTree 基礎知識
JJTree 是一個預處理器，為特定 BNF 生成解析器只需要簡單的兩步：
- 對所謂的 .jjt 文件運行 JJTree；它會產生一個中間的 .jj 文件
- 用 JavaCC 編譯該文件（ 第 1 部分中討論了這個過程）
幸運的是，.jjt 文件的結構只是我在第 1 部分中向您顯示的 .jj 格式的較小擴展。主要區別是 JJTree 添加了一個新的語法 node-constructor構造，該構造可以讓您指定在解析期間在哪里以及在什么條件下生成解析樹節點。換句話說，該構造管理由解析器構造的解析樹的形狀和內容。
清單 1 顯示了一個簡單的 JavaCC .jj 腳本，它類似于您在第 1 部分中看到的腳本。為簡便起見，我只顯示了結果。
清單 1. simpleLang 的 JavaCC 語法
void simpleLang() : {} { addExpr() <EOF> }
void addExpr() : {} { integerLiteral() ( "+" integerLiteral() )? }
void integerLiteral() : {} { <INT> }
SKIP : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }
|
該語法說明了該語言中的合法表達式包含：
- 單個整數文字，或
- 一個整數文字，后面跟一個加號，再跟另一個整數文字。
對應的 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"] )+ > }
|
該腳本對您已經看到的腳本添加了一些新的語法特性。現在，我們只討論突出顯示的部分。以后，我會詳細說明。
逐句說明 JJTree 語法
首先請注意，最頂層的 simpleLang() 結果的 JavaCC 的過程性語法現在指定了一個返回類型： SimpleNode 。它與嵌入的 Java 操作 return jjtThis （有一點為 JJTree 虛張聲勢）一起指定了從應用程序代碼調用解析器的 simpleLang() 方法將返回解析樹的根，然后這個根將用于樹遍歷。
在 JavaCC 中，解析器調用看上去如下：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
parser.simpleLang();
|
而現在看上去象下面這樣：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
SimpleNode rootNode = parser.simpleLang();
|
注：所抓取的根節點并不僅僅是 SimpleNode 類型。它其實是 Root 類型，正如 清單 2 中的 #Root 偽指令所指定的（雖然您不會在上述調用代碼中那樣使用）。 Root 是 SimpleNode 子代，就象 JJTree 生成的解析器構造的每個節點一樣。我將在下面向您顯示 SimpleNode 的一些內置方法。
addExpr()
結果中的 #Add(2) 構造與上述的 #Root 偽指令不同，體現在以下幾方面；
- 它是參數化的。樹構建器在構造樹期間使用節點堆棧；沒有參數的節點構建器的缺省行為是將自己放在正在構造的解析樹的頂部，將所有節點彈出在同一個 節點作用域 中創建的節點堆棧，并把自己提升到那些節點父代的位置。參數
2 告訴新的父節點（在此示例中是一個 Add 節點）要恰好采用 兩個子節點，它們是 下一段文字 中描述的兩個 IntLiteral 子節點。JJTree 文檔更詳細地描述了這個過程。使用好的調試器在運行時遍歷解析樹是另一個寶貴的輔助方法，它有助于理解樹構建在 JJTree 中是如何工作的。
-
將
#Root 偽指令放在其結果的主體之外表示 每次 遍歷該結果時都會生成一個 Root 節點（而在此特定示例中，只允許發生一次），這一點具有同等的重要性 。但是，將 #Add(2) 偽指令放在可選的“零或一”項中表示僅當在解析期間遍歷包含它的選擇子句時 ― 換句話說，當該結果表示一個真的加法操作時 ― 才 有條件地 生成一個 Add 節點。當發生這種情況時，會遍歷 integerLiteral() 兩次，每次調用時都將一個 IntLiteral 節點添加到樹上。這兩個 IntLiteral 節點都成為調用它們的 Add 節點的子節點。但是，如果正在解析的表達式是單個整數，那么作為結果的 IntLiteral 節點將直接成為 Root 的一個子節點。
一圖勝千言（引用一句古老的諺語）。以下是由上述語法生成的兩種類型的解析樹的圖形表示：
圖 1：單個整數表達式的解析樹
圖 2：加法操作的解析樹
讓我們更詳細地研究 SimpleNode 的類層次結構。
使用解析樹
在 .jjt 腳本中聲明的每個節點都指示解析器生成 JJTree SimpleNode 的一個子類。接下來， SimpleNode 又實現名為 Node 的 Java 接口。這兩個類的源文件都是由 JJTree 腳本和定制 .jj 文件一起自動生成的。 清單 1 顯示了定制 .jj 文件的當前示例。在當前示例中，JJTree 還提供了您自己的 Root 、 Add 和 IntLiteral 類以及沒有在這里看到的一些附加的助手類的源文件。
所有 SimpleNode 子類都繼承了有用的行為。 SimpleNode 方法 dump() 就是這樣一個例子。它還充當了我以前的論點（使用解析樹使調試更容易，從而縮短開發時間）的示例。以下三行客戶機端代碼的代碼片段實例化了解析器、調用解析器、抓取所返回的解析樹，并且將一個簡單的解析樹的文本表示轉儲到控制臺：
SimpleParser parser = new SimpleParser(new StringReader( expression ));
SimpleNode rootNode = parser.simpleLang();
rootNode.dump();
|
圖 2
中的樹的調試輸出是：
Root
Add
IntLiteral
IntLiteral
|
輔助導航
另一個有用的內置 SimpleNode 方法是 jjtGetChild(int) 。當您在客戶機端向下瀏覽解析樹，并且遇到 Add 節點時，您會要抓取它的 IntLiteral 子節點、抽取它們表示的整數值，并將這些數字加到一起 ― 畢竟，那是用來練習的。假設下一段代碼中顯示的 addNode 是表示我們感興趣的 Add 類型節點的變量，那我們就可以訪問 addNode 的兩個子節點。（ lhs 和 rhs 分別是 左邊（left-hand side）和 右邊（right-hand side）的常用縮寫。）
SimpleNode lhs = addNode.jjtGetChild( 0 );
SimpleNode rhs = addNode.jjtGetChild( 1 );
|
即使到目前為止您已經執行了所有操作，但您仍然沒有足夠的信息來計算該解析樹表示的算術運算的結果。您的當前腳本已經省略了一個重要的細節：樹中的兩個 IntLiteral 節點實際上不包含它們聲稱要表示的整數。那是因為當記號賦予器（tokenizer）在輸入流中遇到它們時，您沒有將它們的值保存到樹中；您需要修改 integerLiteral() 結果來執行該操作。您還需要將一些簡單的存取器方法添加到 SimpleNode 。
保存和恢復狀態
要將所掃描的記號的值存儲到適當的節點中，將以下修改添加到 SimpleNode ：
public class SimpleNode extends Node
{
String m_text;
public void setText( String text ) { m_text = text; }
public String getText() { return m_text; }
...
}
|
將 JJTree 腳本中的以下結果：
void integerLiteral() : #IntLiteral {} <INT> }
|
更改成：
void integerLiteral() : #IntLiteral { Token t; }
{ t=<INT> { jjtThis.setText( t.image );} }
|
該結果抓取它剛在 t.image 中遇到的整數的原始文本值，并使用您的 setText() setter 方法將該字符串存儲到當前節點中。 清單 5 中的客戶機端 eval() 代碼顯示了如何使用相應的 getText() getter 方法。
可以很容易地修改 SimpleNode.dump() ，以提供任何節點的 m_text 值供其在解析期間存儲 ― 我把這作為一個眾所周知的練習留給您來完成。這將讓您更形象地理解在進行調試時解析樹看起來是什么樣子。例如，如果您解析了“42 + 1”，略經修改的 dump() 例程可以生成以下有用的輸出：
Root
Add
IntLiteral[42]
IntLiteral[1]
|
組合：XQuery 的 BNF 代碼片段
讓我們通過研究實際語法的一個代碼片段來進行組合和總結。我將向您演示一段非常小的 XQuery 的 BNF 子集，這是 XML 的查詢語言的 W3C 規范（請參閱 參考資料）。我在這里所說的大多數內容也適用于 XPath，因為這兩者共享了許多相同的語法。我還將簡要地研究運算符優先級的問題，并將樹遍歷代碼推廣到成熟的遞歸例程中，該例程可以處理任意復雜的解析樹。
清單 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 )*
...
|
您將要構建一個剛好適合的 JJTree 語法腳本來處理結果 [36] 和 [37] 中的 + 、 - 、 * 和 div 運算符，而且簡單地假設該語法所知道的唯一數據類型是整數。該樣本語法 非常小，并不能妥善處理 XQuery 支持的豐富的表達式和數據類型。但是，如果您要為更大、更復雜的語法構建解析器，它應該能給您使用 JavaCC 和 JJTree 的入門知識。
清單 4
顯示了 .jjt 腳本。請注意該文件頂部的 options{} 塊。這些選項（還有許多其它可用選項開關）指定了其中樹構建在本例中是以 多重 方式運行的，即節點構造器用于顯式地命名所生成節點的類型。備用方法（不在這里研究）是結果只將 SimpleNode 節點提供給解析樹，而不是它的子類。如果您想要避免擴散節點類，那么該選項很有用。
還請注意原始的 XQuery BNF 經常將多個運算符組合到同一個結果中。在 清單 4中，我已經將這些運算符分離到 JJTree 腳本中的單獨結果中，因為這讓客戶機端的代碼更簡單。要進行組合，只需存儲已掃描的運算符的值，就象對整數所進行的操作一樣。
清單 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 文件引入了幾個新的特性。例如，該語法中的運算結果現在是 迭代的 ：通過使用 * （零次或多次）發生指示符來表示它們的可選的第二項，這與 清單 2 中的 ? （零次或一次）表示法相反。該腳本所提供的解析器可以解析任意長的表達式，如“1 + 2 * 3 div 4 + 5”。
實現優先級
該語法還知道 運算符優先級。例如，您期望乘法的優先級比加法高。在實際例子中，這表示諸如“1 + 2 * 3”這樣的表達式將作為“1 + ( 2 * 3 )”進行求值，而不是“( 1 + 2 ) * 3”。
優先級是通過使用級聯樣式實現的，其中每個結果會調用緊隨其后的較高優先級的結果。級聯樣式和節點構造的位置和格式保證了以正確的結構生成解析樹，這樣樹遍歷可以正確執行。用一些直觀圖形也許更易于理解這一點。
圖 3
顯示了由此語法生成的解析樹，它可以讓您正確地將“1 + 2 * 3”當作“1 + ( 2 * 3 )”進行求值。請注意， Mult 運算符與它的項之間的聯系比 Plus 更緊密，而這正是您希望的：
圖 3. 結構正確的樹
而 圖 4顯示的樹（該語法 不會生成這樣的樹）表示您（錯誤地）想要將該表達式當作“(1 + 2) * 3”求值。
圖 4. 結構不正確的樹
遍歷解析樹客戶機端
就象我曾答應的，我將用客戶機端代碼的清單作為總結，該清單將調用該解析器并遍歷它生成的解析樹，它使用簡單而功能強大的遞歸 eval() 函數對樹遍歷時遇到的每個節點執行正確操作。 清單 5中的注釋提供了關于內部 JJTree 工作的附加詳細信息。
清單 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!" );
}
}
|
|
結束語
如果您想要查看可以處理許多實際 XQuery 語法的功能更豐富的 eval() 函數版本，歡迎下載我的開放源碼 XQuery 實現（XQEngine）的副本（請參閱 參考資料 ）。它的 TreeWalker.eval() 例程 例舉了 30 多種 XQuery 節點類型。還提供了一個 .jjt 腳本。
參考資料
關于作者
|
|
|
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 聯系。
|