一種XML解析器技術(shù)的研究與實(shí)現(xiàn)

摘 要： 介紹了XML解析的詳細(xì)過(guò)程，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)特定Schema的XML解析器的自動(dòng)生成工具。該生成工具以一個(gè)XML Schema文件作為輸入，輸出一個(gè)JavaCC詞法和語(yǔ)法規(guī)格說(shuō)明文件，然后在JavaCC工具的幫助下，生成一個(gè)基于特定XML Schema的XML解析器。實(shí)驗(yàn)證明，這個(gè)生成解析器能夠?qū)ML文檔進(jìn)行解析的同時(shí)，驗(yàn)證其有效性。
關(guān)鍵詞： XML解析器；基于特定模式；驗(yàn)證；解析器生成器；JavaCC

　XML[1](Extensible Markup Language)是一種可擴(kuò)展標(biāo)記語(yǔ)言，可以用來(lái)定義其他的標(biāo)記語(yǔ)言。自從XML成為W3C推薦標(biāo)準(zhǔn)以來(lái)，XML以其簡(jiǎn)單、可擴(kuò)展性、自描述性、平臺(tái)中立的特點(diǎn)，正迅速成為Web上信息表示與數(shù)據(jù)交換的標(biāo)準(zhǔn)[2]。目前眾多國(guó)際著名公司都宣稱(chēng)其產(chǎn)品中支持XML，促使XML成為下一代Web的發(fā)展方向。越來(lái)越多的網(wǎng)站和Web的應(yīng)用使用XML技術(shù)進(jìn)行信息發(fā)布和數(shù)據(jù)交換，XML已成為一種備受矚目的技術(shù)，甚至被譽(yù)為互聯(lián)網(wǎng)上的世界語(yǔ)。XML現(xiàn)已被廣泛應(yīng)用在各種領(lǐng)域，如電子商務(wù)、企業(yè)協(xié)作、Web服務(wù)等。XML解析器是XML應(yīng)用的基礎(chǔ)，XML本身只是以純文本對(duì)數(shù)據(jù)進(jìn)行編碼的一種格式，要想利用XML，或是利用XML文件中所編碼的數(shù)據(jù)，必須先將數(shù)據(jù)從純文本中解析出來(lái)。因此，要求必須有一個(gè)能夠識(shí)別XML文檔信息的文本文件閱讀器(即XML解析器)，用來(lái)解析XML文檔并提取其中的內(nèi)容。為了提高數(shù)據(jù)的正確性和提高系統(tǒng)的可靠性，XML解析器還要檢查XML實(shí)例文檔是否符合模式的定義和約束，這個(gè)過(guò)程稱(chēng)為XML文檔的有效性驗(yàn)證[3]。但帶有驗(yàn)證功能的解析器通常效率比較低[4]。近年來(lái)，有很多旨在提高XML的解析和基于Schema 驗(yàn)證性能的研究，本文在詳細(xì)分析了XML解析器的解析過(guò)程的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)特定Schema解析器的生成工具。生成器根據(jù)特定的Schema，自動(dòng)產(chǎn)生一個(gè)遞歸下降的XML解析器。這個(gè)生成解析器能夠?qū)ML文檔同時(shí)進(jìn)行解析和有效性驗(yàn)證。
1 XML與Schema簡(jiǎn)介
　可擴(kuò)展標(biāo)記語(yǔ)言XML是由World Wide Web Consortium(W3C)于1998年2月發(fā)布的一種基于文本的數(shù)據(jù)描述語(yǔ)言的通行標(biāo)準(zhǔn)，與HTML類(lèi)似，XML是一種標(biāo)記語(yǔ)言，兩者在語(yǔ)法上有密切的聯(lián)系。不同的是，HTML著重于如何顯示數(shù)據(jù)，而XML的設(shè)計(jì)宗旨是存儲(chǔ)和傳輸數(shù)據(jù)，著重于如何描述數(shù)據(jù)。XML來(lái)源于標(biāo)準(zhǔn)通用標(biāo)記語(yǔ)言SGML(Standard Generalized Markup Language)，是SGML的一個(gè)精簡(jiǎn)子集[5]。XML有如下的特點(diǎn)：
　(1)可擴(kuò)展性：XML是一種元標(biāo)記語(yǔ)言，即XML可用來(lái)設(shè)計(jì)和定義標(biāo)記語(yǔ)言，XML強(qiáng)大的功能體現(xiàn)在它可以用來(lái)制定自己的標(biāo)記語(yǔ)言。不同的具體應(yīng)用領(lǐng)域可以制定專(zhuān)用的標(biāo)記語(yǔ)言，作為該領(lǐng)域共享數(shù)據(jù)和交換信息的基礎(chǔ)。
　(2)內(nèi)容與表現(xiàn)分離：XML使得用戶(hù)界面和結(jié)構(gòu)數(shù)據(jù)之間保持獨(dú)立。XML描述數(shù)據(jù)的內(nèi)容(即數(shù)據(jù)是什么)，而數(shù)據(jù)呈現(xiàn)方式則通過(guò)樣式單來(lái)表示。內(nèi)容與表現(xiàn)分離，使相同的數(shù)據(jù)可以不同的格式在不同的媒體上表現(xiàn)。
　(3)結(jié)構(gòu)化：XML以結(jié)構(gòu)化的方式描述數(shù)據(jù)。這個(gè)特點(diǎn)使得XML能夠描述復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，同時(shí)也為關(guān)系數(shù)據(jù)和層次數(shù)據(jù)提供一種方便的描述方式。
　(4)可驗(yàn)證：XML文檔的結(jié)構(gòu)和內(nèi)容由XML模式語(yǔ)言(如DTD，XML Schema等)定義。利用XML文檔所對(duì)應(yīng)的DTD或Schema，可以對(duì)XML文檔有效性進(jìn)行驗(yàn)證，提高了數(shù)據(jù)的可靠性和可用性。
　XML模式(Schema)指的是一類(lèi)XML文檔的結(jié)構(gòu)或是模型，這個(gè)模型描述了一個(gè)有效XML文檔內(nèi)的元素層次結(jié)構(gòu)和允許的內(nèi)容。模式定義了一個(gè)XML詞匯表，包括元素名稱(chēng)、屬性名稱(chēng)等。模式規(guī)定了一個(gè)XML文檔允許出現(xiàn)的元素、相應(yīng)的元素允許出現(xiàn)的屬性以及這些元素的層次結(jié)構(gòu)關(guān)系。XML的模式語(yǔ)言有很多，其中包括文檔類(lèi)型定義DTD(Document Type Definition)、XML Schema、XML規(guī)則語(yǔ)言描述RELAX(REgular LAnguage description for XML)、XML樹(shù)形規(guī)則表示TREX(Tree Regular Expressions for XML)和下一代RELAX NG(RELAX Next Generation)[6]。
　XML Schema是一種使用XML語(yǔ)法的XML模式語(yǔ)言。DTD曾是描述、約束XML文檔最廣泛的方法，但在應(yīng)用的過(guò)程中，DTD體現(xiàn)出一些局限性。主要表現(xiàn)在語(yǔ)法與XML語(yǔ)法不一致，只支持有限的數(shù)據(jù)類(lèi)型而不支持命名空間等方面。作為DTD的后繼者，XML Schema克服了這些缺陷。XML Schema區(qū)別于DTD的主要特性表現(xiàn)在[7]：
　(1)XML Schema本身就是XML文檔，使得XML Schema的處理可以與XML一樣，一些用來(lái)處理XML的技術(shù)也可以用來(lái)處理XML Schema。
　(2)定義了豐富的數(shù)據(jù)類(lèi)型，如布爾型、整型、日期時(shí)
間、URI、十進(jìn)制數(shù)等簡(jiǎn)單數(shù)據(jù)類(lèi)型。
　(3)支持用戶(hù)自定義數(shù)據(jù)類(lèi)型。XML Schema支持從現(xiàn)有的數(shù)據(jù)類(lèi)型派生出新的數(shù)據(jù)類(lèi)型，類(lèi)似于面向?qū)ο笾械睦^承。
　(4)充分支持命名空間。
　因此，XML Schema成為W3C的正式推薦標(biāo)準(zhǔn)，并正逐步取代XML DTD。
2 Schema解析器生成工具的設(shè)計(jì)與實(shí)現(xiàn)
　基于特定Schema的XML解析器的基本思想是根據(jù)某一特定的Schema，構(gòu)造一個(gè)專(zhuān)用的解析器，這個(gè)解析器能夠?qū)斎氲腦ML文檔進(jìn)行良構(gòu)檢查，同時(shí)驗(yàn)證其有效性?；谔囟⊿chema解析器將XML的解析和驗(yàn)證結(jié)合在一起，在一定程度上提高了基于XML應(yīng)用的效率和性能。但這個(gè)解析器只適用于由這個(gè)Schema定義的XML實(shí)例文檔，對(duì)于由其他Schema定義的XML實(shí)例文檔則無(wú)能為力。當(dāng)Schema改變時(shí)或者需要另外一個(gè)Schema定義時(shí)，必須重新構(gòu)造一個(gè)解析器。而本文設(shè)計(jì)并實(shí)現(xiàn)了利用JavaCC工具自動(dòng)生成一個(gè)特定Schema解析器的方法。該方法以一個(gè)Schema文件為輸入，生成一個(gè)基于這個(gè)Schema的解析器。
自動(dòng)生成特定解析器的基本流程如圖1所示。由于Schema文檔本身也是一種XML文檔，所以完全可以使用通用的XML解析器對(duì)其解析，也可以構(gòu)造一個(gè)專(zhuān)用于解析Schema的解析器，但由于Schema的語(yǔ)法比較復(fù)雜，構(gòu)造起來(lái)比較困難。一種較容易實(shí)現(xiàn)的方法是先將Schema轉(zhuǎn)化為XML樹(shù)模型的表示，再轉(zhuǎn)換為Schema的抽象模型表示?；谔囟⊿chema的XML解析器生成工具的基本步驟如下：
　(1)首先利用JavaCC構(gòu)造一個(gè)通用的XML解析器(GeneralParser)。
　(2)通用XML解析器將Schema輸入文件解析成一個(gè)XML語(yǔ)法的元素節(jié)點(diǎn)樹(shù)。
　(3)遍歷這一XML語(yǔ)法的樹(shù)模型，將其轉(zhuǎn)換為Schema語(yǔ)法的抽象模型。
　(4)根據(jù)Schema抽象模型，生成特定解析器的詞法和語(yǔ)法規(guī)格說(shuō)明。
　(5)利用JavaCC，生成基于輸入Schema的專(zhuān)用XML解析器。
2.1 構(gòu)造XML解析器
　構(gòu)造XML解析器的目的在于解析Schema文檔，提取其描述和約束XML文檔結(jié)構(gòu)和內(nèi)容的信息。XML Schema遵循XML語(yǔ)法，因此可以使用任何通用的XML解析器對(duì)其解析。下面介紹一個(gè)用于解析XML Schema文檔的XML解析器的構(gòu)造。
　由于XML文檔是可以包含DTD聲明和DTD子集的，所以處理XML文檔時(shí)也應(yīng)該包含DTD的語(yǔ)法的處理。但是XML Schema也是一種XML文檔，一般不會(huì)包含DTD聲明和定義。另外，由XML Schema定義的XML實(shí)例文檔通常也不會(huì)再用DTD定義，所以也不會(huì)包含DTD的聲明或DTD子集。因此，在處理XML Schema文檔時(shí)不考慮DTD語(yǔ)法的處理；在生成這個(gè)Schema定義的XML實(shí)例文檔的解析器時(shí)，也不考慮DTD語(yǔ)法的處理。這樣有助于簡(jiǎn)化設(shè)計(jì)和實(shí)現(xiàn)。
2.1.1 構(gòu)造詞法分析器
　JavaCC能根據(jù)輸入的詞法規(guī)格說(shuō)明，產(chǎn)生一個(gè)基于DFA的詞法分析器。因此需要提供一個(gè)合適的詞法規(guī)格說(shuō)明。
　JavaCC的詞法規(guī)格說(shuō)明使用正則表達(dá)式定義詞法結(jié)構(gòu)，每一個(gè)詞法記號(hào)(Token)名稱(chēng)對(duì)應(yīng)著一個(gè)正則表達(dá)式，例如：<S：(""|"t"|"n"|"r")+>表示空白空間的詞法構(gòu)成，其中S是助記符，而(""|"t"|"n"|"r")+是相應(yīng)的正則表達(dá)式，表示由一個(gè)或多個(gè)分隔字符組成的字符串，分隔字符包括空格、制表符′t′、換行符′n′和′r′。
XML規(guī)范中表示詞法結(jié)構(gòu)的表達(dá)式，很多可以比較容易地轉(zhuǎn)換為JavaCC詞法規(guī)格說(shuō)明的正則表達(dá)式形式。但有一些需要特殊的處理才能轉(zhuǎn)換為JavaCC可以識(shí)別的表示形式。
　JavaCC的詞法規(guī)格說(shuō)明由一些詞法狀態(tài)和定義在各個(gè)詞法狀態(tài)內(nèi)的正則表達(dá)式組成。生成的詞法分析器在分析詞法的任何時(shí)候都只能處于一個(gè)詞法狀態(tài)中。這種機(jī)制能夠有效地解決多個(gè)正則表達(dá)式發(fā)生沖突的問(wèn)題。例如，識(shí)別標(biāo)記間的字符數(shù)據(jù)的正則表達(dá)式可以表示為：<CHAR_DATA：(~["<"，"&"，"]"]|"]"~["<"，"&"，"]"]|"]"("]")+~["<"，"&"，">"])+("]")*>，這與其他很多記號(hào)的正則表達(dá)式相沖突，包括標(biāo)記中的元素名 <IDENTIFIER：<NAME>>。這是因?yàn)閮蓚€(gè)正則表達(dá)式表示的語(yǔ)言有公共子集，當(dāng)出現(xiàn)公共子集中的一個(gè)串時(shí)，詞法分析器不知道應(yīng)該匹配哪一個(gè)正則表達(dá)式。實(shí)際上JavaCC只將其匹配為在詞法規(guī)格文件中較早出現(xiàn)的那個(gè)表達(dá)式。利用詞法狀態(tài)可以解決這類(lèi)問(wèn)題，使元素名只會(huì)出現(xiàn)在標(biāo)記中，而字符數(shù)據(jù)只出現(xiàn)在標(biāo)記外，因而可以定義兩種詞法狀態(tài)：在標(biāo)記中的狀態(tài)和標(biāo)記外狀態(tài)，使它們分別在這兩個(gè)詞法狀態(tài)中識(shí)別。詞法狀態(tài)之間的轉(zhuǎn)移可以通過(guò)在匹配一個(gè)記號(hào)后，指定要轉(zhuǎn)移的下一個(gè)詞法狀態(tài)來(lái)實(shí)現(xiàn)。另一種更靈活的方法是在執(zhí)行詞法動(dòng)作(定義在匹配表達(dá)式后執(zhí)行的Java代碼)時(shí)，調(diào)用詞法分析器的SwitchTo()方法，轉(zhuǎn)移到某一指定的狀態(tài)中。
2.1.2 構(gòu)造語(yǔ)法分析器
　JavaCC使用自頂向下遞歸下降的分析方法，并且在需要選擇候選式的地方默認(rèn)向前看一個(gè)符號(hào)進(jìn)行判斷，因此JavaCC使用的也是一種LL(1)的分析方法。XML標(biāo)準(zhǔn)中的EBNF不是LL(1)的文法，這樣會(huì)導(dǎo)致一些選擇的沖突，使得語(yǔ)法分析器不能正確地分析語(yǔ)法。雖然JavaCC也支持LL(k)(k>1)的分析方法，即在所有的選擇點(diǎn)向前看k個(gè)符號(hào)，但這樣會(huì)很大程度地降低解析的效率。解決的方法是對(duì)XML標(biāo)準(zhǔn)中的EBNF表示的文法進(jìn)行改寫(xiě)，使其成為L(zhǎng)L(1)文法。將非LL(1)文法改寫(xiě)為L(zhǎng)L(1)的過(guò)程包括消除左遞歸和提取左因子。XML標(biāo)準(zhǔn)中的文法幾乎不存在左遞歸，因此只需要提取左因子。
　XML標(biāo)準(zhǔn)中語(yǔ)法的產(chǎn)生式存在公共左因子的典型例子是元素的產(chǎn)生式。元素及其相關(guān)的EBNF表達(dá)式如表1所示。

　元素產(chǎn)生式的右部是空元素標(biāo)記或開(kāi)始標(biāo)記后跟元素內(nèi)容和結(jié)束標(biāo)記。其中空元素標(biāo)記和開(kāi)始標(biāo)記有比較長(zhǎng)的公共左因子′<′Name(S Attribute)*S？，當(dāng)語(yǔ)法分析器當(dāng)前的輸入符號(hào)為′<′時(shí)，無(wú)法確定選擇EmptyElemTag還是STag content ETag進(jìn)行推導(dǎo)，這時(shí)解析器就會(huì)報(bào)錯(cuò)，因此首先要將左因子提取出來(lái)。改寫(xiě)元素的產(chǎn)生式為：
　element：：=′<′Name(S Attribute)*S？(′/>′|′>′content ETag) (1)
　這樣語(yǔ)法分析器遇到′<′時(shí)，就不存在選擇的問(wèn)題，當(dāng)遇到′/>′或′>′時(shí)也能確定唯一的子式。但產(chǎn)生式還不是LL(1)的。其原因在于子式(S Attribute)*S？也存在選擇的沖突。因?yàn)镕IRST((S Attribute)*)∩FOLLOW((S Attribute)*)={S}，當(dāng)語(yǔ)法分析器遇到S符號(hào)時(shí)，不知道應(yīng)將其匹配為(S Attribute)*中的S，還是匹配為后面的S？中的S。因此還需要對(duì)產(chǎn)生式進(jìn)行進(jìn)一步的改寫(xiě)。
　先將子式AttS：：=((S Attribute)*S？)改寫(xiě)為等價(jià)的上下文無(wú)關(guān)文法，然后如圖2所示提取左因子。