面向Ｃ＋＋的ＸＭＬ解析器的實現與研究

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

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

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

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

0引言

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

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

1面向C++的XML解析器的設計與實現

系統采用層的結構作為開發模型。這些層自下而上分別是操作系統文件層、編碼層、詞法分析層、語法分析層、內部數據層和DOM接口層，如圖1所示。各個層的作用如下：

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

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

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

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

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

f)DOM接口層。用DOM的接口來包裝內部數據層所提供的數據和接口，方便理解和使用。

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

1．1實現方案

系統涉及三種編程工具，即C++編譯系統、LEX和YACC。它們的關系如圖2所示。

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

1．1．1XML標準的加工

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

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

document文檔規則1

character range字符范圍規則2

white space空白字符規則3

names and tokens名稱與標記規則4~8

literals值規則9~13

character data字符數據規則14

comments注釋規則15

processing instructions處理說明規則16~17

CDATA sectionsCDATA段規則18~21

prolog序言規則22~27

document type definition文檔類型定義規則28~29

external subset外部子集規則30~32

規則33~38已經被刪除

element元素規則39

start－tag開始標記規則40~41

end－tag結束標記規則42

content of elements元素內容規則43

tags for empty elements空元素標記規則44

element type declaration元素類型定義規則45~46

element－content models元素內容模型規則47~50

mixed－content declaration混合內容定義規則51

attribute－list declaration屬性列表定義規則52~53

attribute types屬性類型規則54~56

enumerated attribute types枚舉屬性類型規則57~59

attribute defaults屬性默認值規則60

conditional section條件段規則61~65

character reference字符引用規則66

entity reference實體引用規則67~69

entity declaration實體定義規則70~74

external entity declaration外部實體定義規則75~76

text declaration文本定義規則77

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

encoding declaration編碼定義規則80~81

notation declarations符號定義規則82~83

characters字符規則84~89

1．1．2裁減方案

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

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

document : prolog element Misc*

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

prolog : XMLDecl Misc*

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

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

Misc : Comment |PI| S

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

element定義會比較復雜一些。

element : EmptyElemTag | STag content ETag

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

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

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

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

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

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

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

“+”號的替換規則：... v+ ... = ... vs ...vs = v | v vs

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

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

舉例說明如何應用這些替換規則。

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

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

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

然后再引入新的非終結符號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

這樣就得到了該條規則的BNF格式。

可以來看一個復雜一些的轉換：

規則（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

雖然系統對XML標準進行了裁減，但是XML標準的ENBF－BNF轉換卻是完整的。

3）加工DOM標準系統是使用C++開發的，開發的目的也正是為C++程序員提供一個語言級別的XML解析器。所以，必須用C++來實現DOM。雖然C++是一種面向對象語言，但是C++本身并不提供“屬性”“事件”之類的面向對象編程的重要功能。所以，必須尋求一個折中的辦法，最大限度地利用C++語言所提供的功能來描述DOM接口。

面向對象編程技術應用得非常廣泛，是當前的主流技術，所以DOM這個專門為面向對象編程所設計的標準也理所應當地得到了廣泛應用。與此同時，DOM標準本身所規定的這些對象接口也具備良好的邏輯性和可用性。基于以上考慮，最終選用DOM來作為系統的頂層接口。

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

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

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

1．1．3編碼層的實現

任何合法的ASCII編碼均會自動成為合法的UTF-8編碼，使得將現有的ASCII數據庫轉換為unicode數據庫效率較高，將數據流的格式轉換為內部使用的unicode格式^[8]。本系統中將GB2312格式轉換成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轉換至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操作系統文件層的實現

操作系統文件層讀取應用程序所指定的文件，以二進制數據流的形式傳送到編碼層。該程序的實現代碼如下：

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，FIFO_HEAD_LEN);

}

lseek(fd，0，2);

bw=write(fd， pbuf， size);

2關鍵技術

經過加工的XML和DOM標準已經符合實現的要求，然后應該使用LEX和YACC來生成XML的解析程序，使得系統的內部數據模型及其與DOM接口的有一一對應的邏輯關系。

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

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

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

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

該規則定義了XML中雜項信息，在YACC中實現如下：

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

%token S

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

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

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

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

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來進行以上的處理來識別輸入的字符流中的詞法成分和語法成分，并在匹配時調用事先指定的C++程序即可獲得規范的XML文檔。

3結論

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

表1兩種解析器比較

解析器名稱XML文件大小內存/Byte解析時間

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

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

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

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

4結束語

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

參考文獻：

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

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

[3]張堯學.計算機網絡與Internet教程[M].北京:清華大學出版社，1999.

[4]柴曉路，梁宇奇.Web services技術、架構和應用[M].北京:電子工業出版社，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查詢及其優化機制[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.

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