一種XML解析器技術的研究與實現

曹風華

(內蒙古財經學院 計算機信息管理學院，內蒙古 呼和浩特 010070)

XML[1](Extensible Markup Language)是一種可擴展標記語言，可以用來定義其他的標記語言。自從XML成為W3C推薦標準以來，XML以其簡單、可擴展性、自描述性、平臺中立的特點，正迅速成為Web上信息表示與數據交換的標準[2]。目前眾多國際著名公司都宣稱其產品中支持XML，促使XML成為下一代Web的發展方向。越來越多的網站和Web的應用使用XML技術進行信息發布和數據交換，XML已成為一種備受矚目的技術，甚至被譽為互聯網上的世界語。XML現已被廣泛應用在各種領域，如電子商務、企業協作、Web服務等。XML解析器是XML應用的基礎，XML本身只是以純文本對數據進行編碼的一種格式，要想利用XML，或是利用XML文件中所編碼的數據，必須先將數據從純文本中解析出來。因此，要求必須有一個能夠識別XML文檔信息的文本文件閱讀器(即XML解析器)，用來解析XML文檔并提取其中的內容。為了提高數據的正確性和提高系統的可靠性，XML解析器還要檢查XML實例文檔是否符合模式的定義和約束，這個過程稱為XML文檔的有效性驗證[3]。但帶有驗證功能的解析器通常效率比較低[4]。近年來，有很多旨在提高XML的解析和基于Schema驗證性能的研究，本文在詳細分析了XML解析器的解析過程的基礎上，設計并實現了一個特定Schema解析器的生成工具。生成器根據特定的Schema，自動產生一個遞歸下降的XML解析器。這個生成解析器能夠對XML文檔同時進行解析和有效性驗證。

1 XML與Schema簡介

可擴展標記語言XML是由World Wide Web Consortium(W3C)于1998年2月發布的一種基于文本的數據描述語言的通行標準，與HTML類似，XML是一種標記語言，兩者在語法上有密切的聯系。不同的是，HTML著重于如何顯示數據，而XML的設計宗旨是存儲和傳輸數據，著重于如何描述數據。XML來源于標準通用標記語言SGML(Standard Generalized Markup Language)，是 SGML 的一個精簡子集[5]。XML有如下的特點：

(1)可擴展性：XML是一種元標記語言，即XML可用來設計和定義標記語言，XML強大的功能體現在它可以用來制定自己的標記語言。不同的具體應用領域可以制定專用的標記語言，作為該領域共享數據和交換信息的基礎。

(2)內容與表現分離：XML使得用戶界面和結構數據之間保持獨立。XML描述數據的內容 (即數據是什么)，而數據呈現方式則通過樣式單來表示。內容與表現分離，使相同的數據可以不同的格式在不同的媒體上表現。

(3)結構化：XML以結構化的方式描述數據。這個特點使得XML能夠描述復雜的數據結構，同時也為關系數據和層次數據提供一種方便的描述方式。

(4)可驗證：XML文檔的結構和內容由XML模式語言(如 DTD，XML Schema等)定義。利用 XML文檔所對應的DTD或Schema，可以對XML文檔有效性進行驗證，提高了數據的可靠性和可用性。

XML模式(Schema)指的是一類XML文檔的結構或是模型，這個模型描述了一個有效XML文檔內的元素層次結構和允許的內容。模式定義了一個XML詞匯表，包括元素名稱、屬性名稱等。模式規定了一個XML文檔允許出現的元素、相應的元素允許出現的屬性以及這些元素的層次結構關系。XML的模式語言有很多，其中包括文檔類型定義 DTD(Document Type Definition)、XML Schema、XML規則語言描述 RELAX(REgular LAnguage description forXML)、XML樹 形 規 則 表 示 TREX(Tree Regular Expressions for XML)和下一代RELAX NG(RELAX Next Generation)[6]。

XML Schema是一種使用XML語法的XML模式語言。DTD曾是描述、約束XML文檔最廣泛的方法，但在應用的過程中，DTD體現出一些局限性。主要表現在語法與XML語法不一致，只支持有限的數據類型而不支持命名空間等方面。作為DTD的后繼者，XML Schema克服了這些缺陷。XML Schema區別于DTD的主要特性表現在[7]：

(1)XMLSchema本身就是XML文檔，使得XML Schema的處理可以與XML一樣，一些用來處理XML的技術也可以用來處理XML Schema。

(2)定義了豐富的數據類型，如布爾型、整型、日期時間、URI、十進制數等簡單數據類型。

(3)支持用戶自定義數據類型。XML Schema支持從現有的數據類型派生出新的數據類型，類似于面向對象中的繼承。

(4)充分支持命名空間。

因此，XML Schema成為W3C的正式推薦標準，并正逐步取代XML DTD。

2 Schema解析器生成工具的設計與實現

基于特定Schema的XML解析器的基本思想是根據某一特定的Schema，構造一個專用的解析器，這個解析器能夠對輸入的XML文檔進行良構檢查，同時驗證其有效性。基于特定Schema解析器將XML的解析和驗證結合在一起，在一定程度上提高了基于XML應用的效率和性能。但這個解析器只適用于由這個Schema定義的XML實例文檔，對于由其他Schema定義的XML實例文檔則無能為力。當Schema改變時或者需要另外一個Schema定義時，必須重新構造一個解析器。而本文設計并實現了利用JavaCC工具自動生成一個特定Schema解析器的方法。該方法以一個Schema文件為輸入，生成一個基于這個Schema的解析器。

自動生成特定解析器的基本流程如圖1所示。由于Schema文檔本身也是一種XML文檔，所以完全可以使用通用的XML解析器對其解析，也可以構造一個專用于解析Schema的解析器，但由于Schema的語法比較復雜，構造起來比較困難。一種較容易實現的方法是先將Schema轉化為XML樹模型的表示，再轉換為Schema的抽象模型表示。基于特定Schema的XML解析器生成工具的基本步驟如下：

(1)首先利用JavaCC構造一個通用的XML解析器(GeneralParser)。

(2)通用XML解析器將Schema輸入文件解析成一個XML語法的元素節點樹。

(3)遍歷這一XML語法的樹模型，將其轉換為Schema語法的抽象模型。

(4)根據Schema抽象模型，生成特定解析器的詞法和語法規格說明。

(5)利用 JavaCC，生成基于輸入 Schema的專用 XML解析器。

2.1 構造XML解析器

構造XML解析器的目的在于解析Schema文檔，提取其描述和約束XML文檔結構和內容的信息。XML Schema遵循XML語法，因此可以使用任何通用的XML解析器對其解析。下面介紹一個用于解析XML Schema文檔的XML解析器的構造。

由于XML文檔是可以包含DTD聲明和DTD子集的，所以處理XML文檔時也應該包含DTD的語法的處理。但是XML Schema也是一種XML文檔，一般不會包含DTD聲明和定義。另外，由XML Schema定義的XML實例文檔通常也不會再用DTD定義，所以也不會包含DTD的聲明或DTD子集。因此，在處理XML Schema文檔時不考慮DTD語法的處理；在生成這個Schema定義的XML實例文檔的解析器時，也不考慮DTD語法的處理。這樣有助于簡化設計和實現。

2.1.1構造詞法分析器

JavaCC能根據輸入的詞法規格說明，產生一個基于DFA的詞法分析器。因此需要提供一個合適的詞法規格說明。

JavaCC的詞法規格說明使用正則表達式定義詞法結構，每一個詞法記號(Token)名稱對應著一個正則表達式，例如：＜S：(""|" "|" "|" ")+＞表示空白空間的詞法構成，其中S是助記符，而(""|" "|" "|" ")+是相應的正則表達式，表示由一個或多個分隔字符組成的字符串 ， 分 隔 字 符 包 括 空 格 、 制 表 符 ′ ′、 換 行 符 ′ ′和 ′ ′。

XML規范中表示詞法結構的表達式，很多可以比較容易地轉換為JavaCC詞法規格說明的正則表達式形式。但有一些需要特殊的處理才能轉換為JavaCC可以識別的表示形式。

JavaCC的詞法規格說明由一些詞法狀態和定義在各個詞法狀態內的正則表達式組成。生成的詞法分析器在分析詞法的任何時候都只能處于一個詞法狀態中。這種機制能夠有效地解決多個正則表達式發生沖突的問題。例如，識別標記間的字符數據的正則表達式可以表示 為 ：＜CHAR_DATA：(～["＜"，"&"，"]"]|"]"～["＜ "，"&"，"]"]|"]"("]")+～["＜"，"&"，"＞"])+("]")*＞，這與其他很多記號的正則表達式相沖突，包括標記中的元素名＜IDENTIFIER：＜NAME＞＞。這是因為兩個正則表達式表示的語言有公共子集，當出現公共子集中的一個串時，詞法分析器不知道應該匹配哪一個正則表達式。實際上JavaCC只將其匹配為在詞法規格文件中較早出現的那個表達式。利用詞法狀態可以解決這類問題，使元素名只會出現在標記中，而字符數據只出現在標記外，因而可以定義兩種詞法狀態：在標記中的狀態和標記外狀態，使它們分別在這兩個詞法狀態中識別。詞法狀態之間的轉移可以通過在匹配一個記號后，指定要轉移的下一個詞法狀態來實現。另一種更靈活的方法是在執行詞法動作(定義在匹配表達式后執行的Java代碼)時，調用詞法分析器的SwitchTo()方法，轉移到某一指定的狀態中。

2.1.2構造語法分析器

JavaCC使用自頂向下遞歸下降的分析方法，并且在需要選擇候選式的地方默認向前看一個符號進行判斷，因此JavaCC使用的也是一種LL(1)的分析方法。XML標準中的EBNF不是LL(1)的文法，這樣會導致一些選擇的沖突，使得語法分析器不能正確地分析語法。雖然JavaCC也支持LL(k)(k＞1)的分析方法，即在所有的選擇點向前看k個符號，但這樣會很大程度地降低解析的效率。解決的方法是對XML標準中的EBNF表示的文法進行改寫，使其成為LL(1)文法。將非LL(1)文法改寫為LL(1)的過程包括消除左遞歸和提取左因子。XML標準中的文法幾乎不存在左遞歸，因此只需要提取左因子。

XML標準中語法的產生式存在公共左因子的典型例子是元素的產生式。元素及其相關的EBNF表達式如表1所示。

表1 元素及其相關的EBNF表達式

元素產生式的右部是空元素標記或開始標記后跟元素內容和結束標記。其中空元素標記和開始標記有比較長的公共左因子′＜′Name(S Attribute)*S？，當語法分析器當前的輸入符號為′＜′時，無法確定選擇EmptyElemTag還是STag content ETag進行推導，這時解析器就會報錯，因此首先要將左因子提取出來。改寫元素的產生式為：

element：：=′＜′Name(S Attribute)*S？ (′/＞′|′＞′content ETag)(1)

這樣語法分析器遇到′＜′時，就不存在選擇的問題，當遇到′/＞′或′＞′時也能確定唯一的子式。但產生式還不是LL(1)的。其原因在于子式(S Attribute)*S？也存在選擇的沖突。因為FIRST ((S Attribute)*)∩FOLLOW((S Attribute)*)={S}，當語法分析器遇到S符號時，不知道應將其匹配為(S Attribute)*中的S，還是匹配為后面的S？中的S。因此還需要對產生式進行進一步的改寫。

先將子式 AttS：：=((S Attribute)*S？)改寫為等價的上下文無關文法，然后如圖2所示提取左因子。

上下文無關文法用EBNF表示為：

element改寫為：

式(2)中，AttS是一個非終結符，語法分析的過程中對應于一個過程調用，并且AttS中存在著遞歸，頻繁的調用與返回會使系統的消耗較大。因此本文考慮了更好的處理方法：首先對式(2)進析分析，式(2)中存在選擇沖突的原因在于(S Attribute)*的后面存在著S？，S表示空白空間，而一般的程序語言的語法分析是不處理空白空間的，通常在詞法分析階段就把它忽略。是否可以簡單地采取忽略空白的做法呢？答案似乎是不可以。因為忽略空白會導致一些良構約束的檢查變得困難。例如屬性間必須有空白，而且有時XML文檔中的空白是有意義的，應用程序可能會用到這些空白。但是標記內部的空白是不會提交給應用程序的，為此可以采取靈活的處理方法： 由于 XML 的 EBNF 語法 中′＞′或′/＞′前面 都必有S？ ，因此可以把 S？ 與′＞′或′/＞′合并為一個單詞。在詞法描述中，定義記號＜SRANGLE：(＜S＞)？ "＞"＞和＜SCLOSEDTAG：(＜S＞)？ "/＞"＞分別代替＜RANGLE："＞"＞和＜CLOSEDTAG："/＞"＞，這樣就消除了式(1)中的 S？ ，而(SAttribute)*中的S可以保留下來，使得FIRST((S Attribute)*)∩FOLLOW((S Attribute)*)=φ，得到元素的產生式為式(4)。式(4)每識別一個屬性比式(2)少了一次過程調用，并且消除了遞歸。

把XML標準的EBNF文法改寫，使得JavaCC可以用LL(1)分析法對其處理。但這種改寫有時需要一些技巧，并且不能保證一定有效，改寫后的表達式通常比較復雜，也不夠直觀。一種折中的方法是在少數的一些選擇點向前看2個符號。

2.1.3 語義分析

XML中元素間是層次嵌套的關系，因而可以用樹來表示元素間的關系，如圖3所示。樹中的節點表示一個XML元素，根節點就是XML。

Schema文檔唯一的根元素(Schema)，各個節點的子節點對應于各個元素的子元素。元素的屬性作為節點的屬性。圖4是元素節點及其屬性的UML類圖。

XML解析器采用語法制導的翻譯方法進行語義分析，即語義分析在語法分析的過程中完成。在XML文法產生式的右部中，嵌入相應的語義動作，如創建節點、添加子節點和添加屬性等。在分析的過程中，執行所遇到的語義動作。當語法分析結束而沒有產生任何錯誤時，就可以得到一棵包含Schema文檔元素和屬性信息的樹。

2.2 模型轉換

用本文構造的XML解析器分析Schema文檔，得到一棵以元素為節點的樹。這棵樹隱含了所需要的描述約束信息，但它是基于XML語法的，無法被直接利用，因此必須將其轉換為Schema語法的對象模型。

2.2.1 XML Schema抽象模型

為了能夠生成一個基于特定Schema的解析器，需要一個合適的模型來描述Schema文檔的結構和各種成分。XML Schema標準中定義了一個抽象模型。

XML Schema抽象模型由13種模式成分構成，可分為3組：主模式成分、二級模式成分、助手模式成分。主模式成分包括簡單類型定義、復雜類型定義、屬性聲明、元素聲明；二級模式成分包括屬性組定義、本體約束定義、模型組定義、記號聲明；助手模式成分包括注解、模型組、粒子、通配符、屬性使用。

主模式成分構成模式抽象模型的大部分，其中的聲明主要描述了XML實例文檔的內容，而類型定義尤其是復雜類型定義則描述了XML實例文檔的結構信息。對XML實例文檔的驗證主要是對XML文檔的內容和結構兩方面的驗證。

復雜類型定義使用了其他的模式成分來定義一個元素的內容，這些模式成分包括屬性聲明、屬性組聲明、粒子、模型組等，使用屬性聲明和屬性組定義元素的屬性，是使用一個粒子類型來定義一個復雜的元素內容模型。復雜類型可以派生新的復雜類型，派生的方式有擴展與約束兩種。

粒子(particle)是描述元素內容的一個術語，一個粒子包含兩個出現次數約束和一個項。出現次數約束包括最大出現次數和最少出現次數約束。粒子的項可以是一個元素或一個模型組或一個通配符。

一個模型組包含了一組粒子，這些粒子的組合關系是以下三種之一：順序關系 (sequence)、選擇關系(choice)、全體關系(all)。順序關系的粒子必須以順序的次序出現；選擇關系則只出現一個粒子；全體關系的粒子可以任意的次序出現，每一個粒子最多只能出現一次，而且其粒子的項只能是元素。模型組與模型組定義緊密聯系而又有所區別，模型組定義是具有名字模式成分，相應的 XML元素是＜group＞，而模型組相應的 XML元素是＜all＞、＜choice＞和＜sequence＞。

XMLSchema只定義了概念上的抽象模型，具體的實現還需要自己來完成。本文提供了Schema抽象模型的一個簡化實現。這個簡化的實現暫時忽略了記號聲明、本體約束定義、注解和通配符。其他各模式成分也作了相應的簡化。簡化后實現包含以下各類：

SchemaModel Schema模型類：包含各種模式成分，如元素聲明、屬性聲明、類型定義、模型組定義等。

XSComponent抽象的模式成分類：所有模式成分類的父類，實現轉換文法接口。

XSElement元素聲明類：表示元素聲明模式成分。

XSAttribute屬性聲明類：表示屬性聲明和屬性使用模式成分。

XSAttGroup屬性組類：表示屬性組定義的模式成分，以及復雜類型定義中所有屬性聲明的集合。

XSType抽象類型類：作為簡單類型和復雜類型父類。

XSComplexType復雜類型定義類：表示復雜類型定義模式成分。

XSSimpleType簡單類型定義類：表示簡單類型定義模式成分。

XSModelGroup模型組類：表示模型組及模型組定義模式成分。

XSParticle粒子類：表示粒子模式成分。

2.2.2遍歷轉換

XML語法的模型轉換為Schema抽象模型通過遍歷元素節點樹來完成，遍歷使用遞歸的方式進行。對于元素節點樹中的每一個非葉子節點，遍歷其子節點，得到相應的子模式成分，然后返回本節點表示的模式成分。

對XML的元素節點樹的遍歷過程實際上也是對Schema文檔有效性驗證的過程。

本文介紹了XML解析的詳細過程，設計并實現了一個特定Schema的XML解析器的自動生成工具。這個生成工具以一個XML Schema文件作為輸入，輸出一個JavaCC詞法和語法規格說明文件，然后在JavaCC工具的幫助下，生成一個基于特定XML Schema的XML解析器。這個解析器能夠對XML文檔進行解釋的同時，驗證其有效性。

[1]劉芳，肖鐵軍.XML應用的基石：XML解析技術[J].計算機工程與設計，26(19)：2823-2839.2005.

[2]CHIU K，LU W.A Compiler-based approach to schemaspecific XML parsing [C].In： The FirstInternational Workshop on High PerformanceXML Processing， New York， USA， May， 2004：17-22.

[3]MATSA M， PERKINS E， HEIFETS A， et al.A highperformance interpretive approach to schema-directed parsing[C].In： WWW ‘07： Proceedings of the 16th international conference on World Wide Web， New York，NY， USA， ACM.2007：1093-1102.

[4]ZHANG W， ENGELEN R V.TDX：a high-performance table-driven XML parser[C].In： ACM-SE 44： Proceedings of the44th annual Southeast regional conference，New York， NY， USA， ACM.2006：726-731.

[5]ZHANG W，ENGELEN R V.A table-driven streaming XML parsing methodology for high-performance Web services[C].In： ICWS ‘06： Proceedings of the IEEE International Conference on Web Services(ICWS’06)，Washington， DC， USA， IEEE Computer Society.2006：197-204.

[6]KOSTOULAS M G，MATSA M，MENDELSOHN N，et al.Xml screamer：an integrated approach to high performance xml parsing， validation and deserialization[C].In： WWW‘06： Proceedings of the 15th international conference on World Wide Web， New York， NY， USA， ACM.2006：93-102.

[7]左偉明.即用即查XML數據標記語言參考手冊 [M].北京：人民郵電出版社，2007.