面向Ｃ＋＋的ＸＭＬ解析器的實現(xiàn)與研究

摘要：討論了XML解析器的C++實現(xiàn)以及對應的DOM接口，其主要任務是為應用程序提供一個簡潔、高速、低內(nèi)存消耗的XML解析接口，并在保證性能的前提下提供盡可能多的DOM支持。討論了一個解析器的模型，以及如何用LEX和YACC來實現(xiàn)這個解析器及DOM Level 1Core的C++實現(xiàn)和與解析器的配合問題。

關(guān)鍵詞：解析器； C++； 可擴展標記語言； 文檔對象模型

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2007)12-0268-04

0引言

XML是在因特網(wǎng)上應用非常廣泛的一種數(shù)據(jù)交換語言，經(jīng)常被稱為“因特網(wǎng)上的世界語”，其應用之廣泛可見一斑。從W3C制定其標準的那天開始，人們研究并實現(xiàn)了多個XML解析器的版本，一般有DOM和SAX兩種。DOM^[1](document object model，文檔對象模型)用對象的概念來描述文檔中的各種元素。DOM是基于平臺、語言無關(guān)的官方W3C標準。基于樹的層次，其優(yōu)點是可以移植，編程容易，開發(fā)人員只需調(diào)用建樹的指令；其缺點是加載大文件不理想。SAX^[2]是基于事件模型的，它在解析 XML文檔時可以觸發(fā)一系列的事件。當發(fā)現(xiàn)給定的tag時，它可以激活一個回調(diào)方法，告訴該方法制定的標簽已經(jīng)找到，它類似于流媒體的解析方式，所以在加載大文件時效果不錯。

DOM完全在內(nèi)存中描述一個元素樹，所以DOM需要大量的內(nèi)存和較高的主頻，這使它很難與許多輕量級的Web應用一起工作。SAX沒有在內(nèi)存中建立一個元素樹，但是SAX也不支持修改XML文檔和隨機讀取。絕大部分涉及XML的應用程序，并不需要XML標準里面所規(guī)定的所有東西，它們只需要其中的一小部分，并且希望這部分實現(xiàn)起來最好是快速的、低內(nèi)存消耗的。本系統(tǒng)的設計與研究旨在為利用C++技術(shù)為應用程序提供一個簡潔、高速、低內(nèi)存消耗的XML解析器。為了達到這個目標，首先必須對XML標準進行裁減，在此基礎上提供一個便于使用的接口。

1面向C++的XML解析器的設計與實現(xiàn)

系統(tǒng)采用層的結(jié)構(gòu)作為開發(fā)模型。這些層自下而上分別是操作系統(tǒng)文件層、編碼層、詞法分析層、語法分析層、內(nèi)部數(shù)據(jù)層和DOM接口層，如圖1所示。各個層的作用如下：

a)操作系統(tǒng)文件層。它負責讀取應用程序所指定的文件，以二進制數(shù)據(jù)流的形式傳送到編碼層。將該層獨立出來，提高了程序的可移植性，并且可以單獨針對特定的操作系統(tǒng)作性能優(yōu)化。

b)編碼層。該層將判斷數(shù)據(jù)流的編碼格式，并且將所有的格式轉(zhuǎn)換為內(nèi)部使用的UTF－16格式，將轉(zhuǎn)換后的unicode字符流傳送到詞法分析層。

c)詞法分析層。分析字符流、識別語法成分，并以語法標記的形式傳送給語法分析層。該層用LEX（lexical analyzer）和YACC（yet another compiler compiler）來實現(xiàn)。其中：LEX是一種生成掃描器的工具；YACC是一種工具，將任何一種編程語言的所有語法翻譯成針對此種語言的YACC語法解析器^[3]。

d)語法分析層。分析語法標記，并驗證其組合次序是否符合XML語法的規(guī)定；最后將符合規(guī)定的XML語法成分以特定的數(shù)據(jù)格式（XML記錄）拼裝起來，送入內(nèi)部數(shù)據(jù)層中。

e)內(nèi)部數(shù)據(jù)層。該層接收XML記錄，將其放入內(nèi)部數(shù)據(jù)表，并負責維護該數(shù)據(jù)表，提供調(diào)用接口。該層以精簡的方式存放了所有的XML數(shù)據(jù)，并且支持以流的方式來讀取，可以與關(guān)系數(shù)據(jù)庫直接對應。

f)DOM接口層。用DOM的接口來包裝內(nèi)部數(shù)據(jù)層所提供的數(shù)據(jù)和接口，方便理解和使用。

該設計利用模塊化的思想，將各個功能單獨地封裝在一個模塊中，有較好的擴展性和通用性。

1．1實現(xiàn)方案

系統(tǒng)涉及三種編程工具，即C++編譯系統(tǒng)、LEX和YACC。它們的關(guān)系如圖2所示。

按照XML標準編寫詞法規(guī)則和語法規(guī)則，由LEX和YACC兩個工具處理后，可以得到詞法分析層和語法分析層的C++源代碼。將這些源代碼與其他層的組合起來，通過C++編譯系統(tǒng)來生成最后的程序。

1．1．1XML標準的加工

本系統(tǒng)所參照的XML標準為W3C的extensible markup language(XML) 1．0: 2nd edition。該標準規(guī)定了XML文檔的結(jié)構(gòu)，以及文檔中各種元素之間的邏輯對應關(guān)系。

這些標準是用EBNF的方式來描述的，總共有84條規(guī)則（規(guī)則最大編號為89。其中33~38條規(guī)則已經(jīng)被刪除，編號28的規(guī)則還有一條子規(guī)則為28a）。規(guī)則之間存在一些額外的約束，如單一元素約束，即一個XML文檔只能包括一個根節(jié)點。該標準由以下部分組成：

document文檔規(guī)則1

character range字符范圍規(guī)則2

white space空白字符規(guī)則3

names and tokens名稱與標記規(guī)則4~8

literals值規(guī)則9~13

character data字符數(shù)據(jù)規(guī)則14

comments注釋規(guī)則15

processing instructions處理說明規(guī)則16~17

CDATA sectionsCDATA段規(guī)則18~21

prolog序言規(guī)則22~27

document type definition文檔類型定義規(guī)則28~29

external subset外部子集規(guī)則30~32

規(guī)則33~38已經(jīng)被刪除

element元素規(guī)則39

start－tag開始標記規(guī)則40~41

end－tag結(jié)束標記規(guī)則42

content of elements元素內(nèi)容規(guī)則43

tags for empty elements空元素標記規(guī)則44

element type declaration元素類型定義規(guī)則45~46

element－content models元素內(nèi)容模型規(guī)則47~50

mixed－content declaration混合內(nèi)容定義規(guī)則51

attribute－list declaration屬性列表定義規(guī)則52~53

attribute types屬性類型規(guī)則54~56

enumerated attribute types枚舉屬性類型規(guī)則57~59

attribute defaults屬性默認值規(guī)則60

conditional section條件段規(guī)則61~65

character reference字符引用規(guī)則66

entity reference實體引用規(guī)則67~69

entity declaration實體定義規(guī)則70~74

external entity declaration外部實體定義規(guī)則75~76

text declaration文本定義規(guī)則77

well－formed external parsed entity格式完整的外部解析實體規(guī)則78

encoding declaration編碼定義規(guī)則80~81

notation declarations符號定義規(guī)則82~83

characters字符規(guī)則84~89

1．1．2裁減方案

1)XML標準裁減XML文檔的有效性驗證是整個解析過程中最耗資源的部分，所以裁減工作將主要集中在這部分^[4]。另外，標準規(guī)定了文檔的編碼方式，枚舉了所有可能出現(xiàn)的unicode字符。這樣大大降低了LEX與YACC的處理速度，生成的C++文件居然有7 MB，實在不可取，所以還將對XML標準的編碼部分進行相應的裁減。需要注意的是，裁減會使標準不完整：將標準中的文檔有效性驗證的部分拿掉以后，用戶所編寫的DTD將被系統(tǒng)忽略，所以一個不符合指定DTD的XML文檔也將被系統(tǒng)正常解析；把編碼部分拿掉，則不符合編碼規(guī)則的XML文檔也將被解析，當遇到不合法字符時，系統(tǒng)的行為不可預料。單獨設計了一個編碼層來負責編碼的驗證工作，該層由手工編寫，效率高于LEX自動產(chǎn)生的分析程序。

綜上所述，將標準中關(guān)于DTD的規(guī)則28~32、45~78、82~83去掉。這樣，規(guī)則數(shù)量少了許多，系統(tǒng)變得非常簡潔。編碼部分的規(guī)則從84~89均被省去。經(jīng)過精簡，系統(tǒng)只剩下了最重要的幾條規(guī)則，系統(tǒng)的數(shù)據(jù)模型也變得清晰起來，在此列舉最重要的幾條產(chǎn)生式并加以解釋：

document : prolog element Misc*

該規(guī)則是XML文檔的最高層規(guī)則，包括序言、一個根元素和若干個雜項信息。

prolog : XMLDecl Misc*

序言部分包括XML定義和雜項信息。

XMLDecl出現(xiàn)在XML文檔的開始處，確定了文檔版本和編碼方式等信息。

Misc : Comment |PI| S

雜項可以是注釋、處理說明或者是空白。

element定義會比較復雜一些。

element : EmptyElemTag | STag content ETag

該規(guī)則表明XML元素可以兩種形式出現(xiàn)：a)不包含其他內(nèi)容的自我終結(jié)的空元素，如〈person/〉；b)由開始標記和結(jié)束標記來包含其他內(nèi)容的元素，如〈Name〉〈/Name〉。EmptyElemTag和STag的定義中還包括了對元素屬性的定義，這兩種標記均可以包含若干個屬性。

這個定義還是一個遞歸的定義，content中可以包括若干個element或文本、注釋、空白、CDATA段和處理說明等信息。有了這樣的定義，XML文檔就可以用來描述一棵單根的無限層級的樹。通過圖3可以更清晰地看到這一點。

2）從EBNF到BNF的轉(zhuǎn)換XML標準使用EBNF（exten－ded backus－naur form）來描述。而所選用的編譯器生成工具YACC只支持BNF，所以必須進行從EBNF到BNF的轉(zhuǎn)換。

EBNF就是擴展的BNF，用來描述一種語言的語法。更通俗的理解就是：EBNF=BNF+正則式，即EBNF就是增加了正則式功能的BNF^[5]。

EBNF與BNF之間是有對應關(guān)系的，它們之間的替換操作主要針對的是正則式語法的替換：

“括號”的替換規(guī)則：...( v1|v2 ) ... = ... v ...v=v1|v2

“*”號的替換規(guī)則：... v* ... = ... ( v+ )?...

“+”號的替換規(guī)則：... v+ ... = ... vs ...vs = v | v vs

“?”號的替換規(guī)則：a v? b = a b|a v b

替換“?”號相對復雜一些。如果句子中出現(xiàn)了n個問號，那么該句子就應該對應2的n次方個新句子。

舉例說明如何應用這些替換規(guī)則。

XML標準中的第一條：document:=prolog element Misc*

這里面存在Misc*，所以必須進行替換。

首先，將Misc*替換為( Misc+ )?

然后再引入新的非終結(jié)符號recur_Misc來替換Misc+

recur_Misc:=Misc | Misc recur_Misc

有了這兩個式子可以對原句進行替換：

document:=prolog element (Misc+)?

:=prolog element | prolog element Misc+

:=prolog element | prolog element recur_Misc

recur_Misc:=Misc | Misc recur_Misc

這樣就得到了該條規(guī)則的BNF格式。

可以來看一個復雜一些的轉(zhuǎn)換：

規(guī)則（22）prolog:=XMLDecl?Misc*(doctypedecl Misc*)?

它的替代方案如下：

prolog:=空

|XMLDecl

|XMLDecl recur_Misc

|XMLDecl prolog_doctypedecl

|recur_Misc

|recur_Misc prolog_doctypedecl

|prolog_doctypedecl

|XMLDecl recur_Misc prolog_doctypedecl

prolog_doctypedecl:=doctypedecl

|doctypedecl recur_Misc

recur_Misc:=Misc | Misc recur_Misc

雖然系統(tǒng)對XML標準進行了裁減，但是XML標準的ENBF－BNF轉(zhuǎn)換卻是完整的。

3）加工DOM標準系統(tǒng)是使用C++開發(fā)的，開發(fā)的目的也正是為C++程序員提供一個語言級別的XML解析器。所以，必須用C++來實現(xiàn)DOM。雖然C++是一種面向?qū)ο笳Z言，但是C++本身并不提供“屬性”“事件”之類的面向?qū)ο缶幊痰闹匾δ堋Ｋ裕仨殞で笠粋€折中的辦法，最大限度地利用C++語言所提供的功能來描述DOM接口。

面向?qū)ο缶幊碳夹g(shù)應用得非常廣泛，是當前的主流技術(shù)，所以DOM這個專門為面向?qū)ο缶幊趟O計的標準也理所應當?shù)氐玫搅藦V泛應用。與此同時，DOM標準本身所規(guī)定的這些對象接口也具備良好的邏輯性和可用性。基于以上考慮，最終選用DOM來作為系統(tǒng)的頂層接口。

W3C定義了DOM Level 1 CORE來描述XML文檔^[6]，本文所采用的標準正是這個。該標準定義了19個類來描述XML文檔中的各種元素。其中：DOMString、DOMImplementation、DOMException、NamedNodeMap和NodeList為單獨定義，與其他對象無繼承關(guān)系。

系統(tǒng)有選擇地實現(xiàn)了XML標準，相應地也需要對DOM標準進行一些裁減，剔除不必要的對象，簡化實現(xiàn)過程。

在裁減XML標準時，被刪除的主要是與DTD相關(guān)的定義，所以，在裁減DOM標準時，把相應的Entity、EntityReference和Notation三個對象予以刪除^[7]。

1．1．3編碼層的實現(xiàn)

任何合法的ASCII編碼均會自動成為合法的UTF-8編碼，使得將現(xiàn)有的ASCII數(shù)據(jù)庫轉(zhuǎn)換為unicode數(shù)據(jù)庫效率較高，將數(shù)據(jù)流的格式轉(zhuǎn)換為內(nèi)部使用的unicode格式^[8]。本系統(tǒng)中將GB2312格式轉(zhuǎn)換成unicode格式：

void GB2312ToUTF_8(char**pOut，char *pText， int pLen)

{

char buf[4];

char* rst=new char[pLen+(pLen>>2)+2];

memset(buf，0，4);

memset(rst，0，pLen+(pLen>>2)+2);

int i=0;

int j=0;

while(i

{

if( *(pText+i)>=0)

{ rst[j++]=pText[i++];}

else

{

WCHAR pbuffer;

Gb2312ToUnicode(pbuffer，pText+i);

UnicodeToUTF_8(buf，pbuffer);

unsigned short int tmp=0;

tmp=rst[j]=buf[0];

tmp=rst[j+1]=buf[1];

tmp=rst[j+2]=buf[2];

j+=3;

i+=2;

}}

rst[j]=\"\\0\";

pOut=rst;

delete []rst;

return;

}

再利用UTF-8轉(zhuǎn)換至unicode格式。

void UTF_8ToUnicode(char* pOut，char *pText)

{

char* uchar = (char *)pOut;

uchar[1] = ((pText[0] 0x0F) << 4) + ((pText[1] >> 2) 0x0F);

uchar[0] = ((pText[1] 0x03) << 6) + (pText[2] 0x3F);

return;

}

1．1．4操作系統(tǒng)文件層的實現(xiàn)

操作系統(tǒng)文件層讀取應用程序所指定的文件，以二進制數(shù)據(jù)流的形式傳送到編碼層。該程序的實現(xiàn)代碼如下：

fd=open(file_name， O_RDWR|O_CREAT， S_IRUSR|S_IWUSR|S_IROTH|S_IRGRP);

if (fd<0)

{

fprintf(stderr， \"filewrite(): failed open [%s]\\"， file_name);

return ERR_OPEN;

}

if (flock(fd， LOCK_EX)==-1)

{

fprintf(stderr，\"filewrite():failed lock [%s]\\"，file_name);

close(fd);

return ERR_LOCK;

}

lseek(fd， 0， 0);

if (read(fd， head_buf， FIFO_HEAD_LEN)

{

write(fd，head_buf，F(xiàn)IFO_HEAD_LEN);

}

lseek(fd，0，2);

bw=write(fd， pbuf， size);

2關(guān)鍵技術(shù)

經(jīng)過加工的XML和DOM標準已經(jīng)符合實現(xiàn)的要求，然后應該使用LEX和YACC來生成XML的解析程序，使得系統(tǒng)的內(nèi)部數(shù)據(jù)模型及其與DOM接口的有一一對應的邏輯關(guān)系。

LEX使用正則式來識別輸入串中符合模式的字符，并返回與正則式對應的指定標記。其中實現(xiàn)XML標準中的S規(guī)則為S:=(#x20|#x9|#xD|#xA)+

該式與以下正則式是等價的：S:=[\\\\f]+

在LEX的規(guī)則段：[\\\\f]+{return S；}

這段LEX程序描述如果遇到符合[\\\\f]+的字符串，就向LEX的調(diào)用者返回一個S標記，表明LEX尋找到了S。這樣調(diào)用LEX的程序就可以進行相應的操作了。LEX的作用就是把輸入流轉(zhuǎn)換為標記流（token stream），供上層程序使用。YACC根據(jù)給定的BNF格式的規(guī)則（即“產(chǎn)生式”），以及與這些規(guī)則相對應的處理程序來生成語法分析程序。其語法分析規(guī)則為Misc := Comment | PI | S。

該規(guī)則定義了XML中雜項信息，在YACC中實現(xiàn)如下：

首先，應該在YACC定義段中定義一個標記（token）S：

%token S

這個定義表明該YACC程序需要通過LEX來識別S這個標記。一旦LEX找到，則交由YACC處理。其次，在YACC的規(guī)則段中增加如下定義：

Misc : Comment | PI |S {printf(\"non-terminal Matched: Misc\")}；

如果有符合這個規(guī)則的輸入串，則執(zhí)行{}中的對應操作（當前看到的操作是輸出一段提示信息，告訴用戶這個產(chǎn)生式被匹配了）。需要注意的是Comment和PI是另外兩個非終結(jié)符，分別對應兩條不同的規(guī)則（產(chǎn)生式）^[9]。

對于具體的XML標簽數(shù)據(jù)，則可以作如下處理，對某個人的姓名數(shù)據(jù)進行處理，并說明該設計方法。

Name.y-語法文件

%

typedef char* string;

#define YYSTYPE string

%}

%token NAME EQ AGE

%%

file : record file

|record;

record: NAME EQ AGE {

printf(\"%s is %s years old!!!\\"， S1， S3); };

%%

Name.lex - Lex的解析器文件

char [A－Za－z]

num [0-9]

eq [=]

name {char}+

age {num}+

%%

{name} {yylval=strdup(yytext);

return NAME;}

{eq} {return EQ;}

{age} {yylval=strdup(yytext);

return AGE;}

%%

int yywrap()

{

return 1;

}

通過LEX和YACC來進行以上的處理來識別輸入的字符流中的詞法成分和語法成分，并在匹配時調(diào)用事先指定的C++程序即可獲得規(guī)范的XML文檔。

3結(jié)論

系統(tǒng)在VC++ CONSOLE、Windows 2000下實現(xiàn)，選取了SAX和DOM兩種解析器進行比較，如表1所示。

表1兩種解析器比較

解析器名稱XML文件大小內(nèi)存/Byte解析時間

面向C++的解析器2k1MB50.3MB1932k3965k56302k1s左右

SAX2k1MB50.3MB1823k4789k85004k1s左右

DOM2k1MB50.3MB1235k6521k98253k1s左右

由上可知，經(jīng)過裁減和優(yōu)化后的XML文檔通過面向C++的解析器的解析效率優(yōu)于其他兩個解析器。

4結(jié)束語

XML解析器是XML技術(shù)應用的基石，所以它的解析速度也是制約其廣泛應用的瓶頸之一。各大主流廠商正在不斷地更新和完善XML規(guī)范。本文對提高解析速度進行了的研究，并提出解析模型，對于XML的廣泛利用提供了有力的支持。

參考文獻：

[1]胡海靜.XML技術(shù)精粹[M].北京:機械工業(yè)出版社，2002.

[2]YOUNG M J. XML學習指南[M].北京:機械工業(yè)出版社，2004.

[3]張堯?qū)W.計算機網(wǎng)絡與Internet教程[M].北京:清華大學出版社，1999.

[4]柴曉路，梁宇奇.Web services技術(shù)、架構(gòu)和應用[M].北京:電子工業(yè)出版社，2003.

[5]LEVINE. LEX and YACC O’reilly[M].2nd ed. USA: Pearson， 2002.

[6]HOWARD K， CHAMBERLIN D， DRAPER D， et al. XQuery from the experts: a guide to the W3C XML query language[M]. USA: Pearson， 2002.

[7]KIFER M， LAUSEN G， WU J. Logic foundations of object－oriented and frame－based language[J]. Journal of the ACM， 1995，42(4):841-843.

[8]黃遠林，黃屹.基于本體的XML查詢及其優(yōu)化機制[J].計算機應用研究，2006，23(11):146－148.

[9]CHEN H， GU J， LI X， et al. An XML query mechanism with ontology integration[C]//Proc of ISPA’05 Workshops.Nanjing:Springer－Verlag， 2005:569-578.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”