[發明專利]基于回溯自動機語法分析的JSAX解析器和解析方法

有效

• 申請號: 201210118808.0
• 申請日: 2012-04-20
• 公開（公告）號: CN102708155A
• 公開（公告）日: 2012-10-03
• 發明（設計）人: 段振華;張柯柯;王小兵;田聰
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 程曉霞;王品華

1.一種基于回溯自動機語法分析的JSAX解析器，在Eclipse環境下對XML文檔解析，包括詞法分析器，語法分析器和事件處理器，詞法分析器負責讀取XML文檔的內容，將讀取的記號輸出給語法分析器，語法分析器根據XML規范要求識別輸入記號流中的語言結構，將相應的事件信息傳遞給事件處理器，事件處理器接受解析器傳遞的所有事件信息并處理，從中發現所需數據，實現對XML文檔的解析，并給出解析結果，其中語法分析器是基于自動機構造的，自動機中回溯自動機的結構為五元組，結構為M＝(S，∑，δ，q₀，F)，還包含有一個狀態棧用來保存運行的部分歷史，其特征在于：所述語法分析器是基于回溯自動機來實現的，所述回溯自動機是改進回溯自動機，具體是對回溯自動機的動作轉移規則δ重新定義，該定義為規則性定義，包括：

1)若δ(q，a)＝p，即在狀態q下，當讀入記號a時，將當前狀態q壓入棧頂，其中a代表需要進行入棧動作的記號；

2)若δ(q，b)＝trace，即在狀態q下，當讀入記號b時，并且狀態棧不為空時，彈出狀態棧棧頂p，并且控制轉向p狀態，其中b代表需要進行回溯動作的記號；

3)若δ(q，c)＝p，即在狀態q下，當讀入記號c時，不需要進行棧操作，其中c代表不需要進行棧操作的記號；

4)若δ(q，d)，若d是空白字符(空白字符不屬于輸入字符集，表示字符串結束)，則停機并且在q∈F時接受輸入字符串，在?時拒絕接受；

5)若δ(q，e)無定義，則停機并拒絕接受輸入字符串。

2.根據權利要求1所述的基于回溯自動機語法分析的JSAX解析器，其特征在于：與改進回溯自動機相等價的文法形式為：

A→aβ

其中a∈T(a屬于終結符T)，β∈{N⁰∪N¹∪N²}(β是零個、一個或者兩個非終結符N的串)；并且當β中含有兩個非終結符時，產生式的結構為：A→aCA，該結構要求產生式右部第二個非終結符和產生式左邊的非終結符相同，其中A、C是非?終結符；

該文法的描述能力比正規文法RG強，但比上下文無關文法CFG弱，是CFG的子集，介于RG與CFG之間。

3.根據權利要求2所述的基于回溯自動機語法分析的JSAX解析器，其特征在于：用與改進回溯自動機等價的文法來描述XML語法定義，得到描述XML文檔的語法規則，根據這些語法規則構造改進回溯自動機，用改進回溯自動機識別XML文檔記號流中的語言結構，判斷是否符合語法規范，完成語法分析，同時將相應事件信息傳遞給事件處理器。

4.根據權利要求3所述的基于回溯自動機語法分析的JSAX解析器，其特征在于：用權利要求2所述的文法形式構建用于描述XML語法定義的語法規則包括：

document::＝prolog?element?Misc*

element::＝EmptyElemTag|A

A::＝STag?B?A

Content_item::＝CharData|Reference|CDSect|PI|Comment|EmptyElemTag

B::＝Content_item?B

B::＝STag?B?B

B::＝ETag

A::＝Miscs

Miscs::＝ε|Misc?Miscs

其中，document表示XML文檔；prolog用來描述聲明信息及文檔類型聲明doctypedecl；element描述的是嵌套的具有層次結構的標記匹配串，要求出現在element中的標記必須正確嵌套和匹配；STag表示開始標記；CharData表示字符數據；Reference表示引用；CDSect表示CDATA段；PI表示處理指令；Comment表示注釋；EmptyElemTag表示空元素標記；STag表示開始標記；Misc*表示XML文檔中的空白、處理指令及注釋；B是一個非終結符，可以替換為結束標記ETag或者STag?B?B；A是一個非終結符，可以替換為Miscs或者STag?B?A。