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

有效

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

技術領域

本發明屬于Web技術領域，主要涉及可擴展標記語言XML(eXtensible?Markup?Language)文檔的解析技術，尤其涉及基于簡單應用程序接口SAX(Simple?API?for?XML)的XML文檔解析技術，具體是一種基于回溯自動機語法分析的JSAX解析器和解析方法，可應用于對XML文檔的解析。

背景技術

近幾年來，XML以其應用簡單、使用靈活的優勢，被廣泛應用于Web環境下的數據傳輸與交換、數據集成、文檔存儲等領域中，最典型的就是Web服務Web?Service，Web?Service中的SOAP協議及WSDL都是基于XML的，此外，XML在數學、化學、物理等諸多領域中也有很多應用，如化學領域中用于描述分子信息的化學標記語言CML。XML文檔解析器在現階段Web應用技術中對通用數據交換與處理起著關鍵性的作用。隨著基于XML的應用越來越廣泛，各類工業應用和科學研究對XML文檔解析器的性能也提出了越來越高的要求，一個高性能的XML解析器對于提高解析XML文檔的速度和系統吞吐量至關重要。

目前針對各類不同需求，陸續出現了文檔對象模型DOM、SAX等解析接口標準。

SAX接口是一種基于事件的解析API(應用程序接口)，SAX解析器采用了基于事件的模型，它在解析XML文檔時可以觸發一系列的事件供用戶處理，常用的事件類型有：startDocument，表示文檔的開始；endDocument，表示文檔的結束；startElement，表示標記的開始；endElement，表示標記的結束；characters，表示文本內容事件；ignoreWhitespace，表示空白事件。處理完的事件會從內存中刪除，并釋放掉它所占有的資源，因為它的性能優勢和簡單易用，已被開發者和用戶廣為使用。

當SAX解析器在解析XML文檔時，需要對XML文檔進行詞法分析和語法分析。最為通用的進行詞法分析的模型是有限自動機FA，根據XML規范可知，構成XML的記號是用正規文法來描述的，FA可以識別用正規文法描述的記號，由于FA易于構造、分析效率高的優點，所以FA被廣泛應用于詞法分析器的設計。進行語法分析的方法則有多種選擇，Van?Engelen曾采用遞歸下降分析recursive?descent?parsers對XML文檔進行語法分析，但是由于遞歸實現的過程需要維護系統堆棧，空間上消耗較大，而且遞歸也帶來了大量的函數調用，導致了額外的時間開銷，所以遞歸下降分析效率不高。另外一種通用的進行語法分析的工具是下推自動機PDA，下推自動機的識別能力比有限自動機強，但是下推自動機構造起來比較復雜，在進行語法分析時的每一步動作都要根據當前狀態、當前輸入和下推棧中的內容來確定改變格局的動作，改變下推棧和剩余輸入的狀態從而進入到下一格局，導致分析效率不高。

因此，提高XML解析器的語法分析器的效率勢在必行，一個高性能的XML解析器對于提高解析XML文檔的速度會有很大的提高，可以有效提高系統的響應速度和吞吐量。

本發明項目對國內外專利文獻和公開發表的期刊論文檢索，尚未發現與本發明密切相關和一樣的報道或文獻。

發明內容

本發明主要針對XML解析器的語法分析器效率低下難于實現等問題，通過對回溯自動機進行改進，提供一種新的高效率、能夠識別具有嵌套結構的標記匹配串語言并易于實現的基于回溯自動機語法分析JSAX解析器和解析方法。本發明可應用于對XML文檔的解析。

下面對本發明進行詳細說明。

本發明是一種基于SAX接口的XML解析器和解析方法，本發明目前不支持對帶有名字空間的XML文檔的解析，本發明屬于標準XML解析器。

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

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