摘要 本文介紹一種文本解析的方法:狀態切換法 (狀態機), 並給出C/C++下的實現.
這是我3年前寫的代碼,用C++實現一個XML解析器.現在再翻出來看,覺得還是有些可取之處,尤其是實現XML文本解析時采用的狀態切換法 (姑且先這麼叫吧,後文有詳細解釋這個方法的實現)不僅僅可以用來解析XML,幾乎所有的文本流都可以用這種方法來解析 (我記得以前上編譯原理時,講到過詞法分析器,用狀態機 ,方法類似, 看來上課還是要認真聽講,不定什麼時候就用上了.) 同時也有一些不足,主要是當時對UNICODE編程還懵懵懂懂,導致接口全是多字節的.所以要把我的代碼加到UNICODE環境下還要做一些修改. 還有很重要的一點要事先說明:我對XML標准並沒有做太多研究,寫這些代碼以實用為主,為的就是讓我的程序有一個很簡單快捷的方式讀取,修改,保存XML文件,所以可能有相當一部分的XML特性沒有實現,如果只是使你的C++程序可以使用XML文件作為你的配置文件,(INI文件過於簡單了)那麼我這個XML解析器還是很方便的.
XML文檔的基本概念
字符存儲要面對編碼問題,我們在中文環境下,最常碰到的就3種編碼方式: GB2312, UTF8 和Unicode. 根據XML標准,XML文件應該在第一行標明編碼方式: <?xml version="1.0" encoding="gb2312" ?>. 我的做法是:不管它存儲為什麼編碼方式,讀到內存後,統統給它轉化為寬字符(UNICDOE). 現在就可以把XML文件看作一個寬字符流 ,這點很重要,是我實現解析器的前提.
XML文檔是一個結構化的文檔,一個XML文檔對應一棵樹.XML樹由節點構成,XML裡有以下幾種節點:
enum xmlnode_type
{
et_none = 0,
et_xml, // <?xml ...?>
et_comment, // <!-- ... -->
et_normal, // <tag />
et_text, // content text
et_cdata, // <![CDATA[ ... ]]>
};
我們以這樣一個XML文件作為范例,以方便後面的解說:
<?xml version="1.0" encoding="gb2312" ?>
<company name="Que's C++ studio">
<sales>
<salesman age="28" level="1">小王</salesman>
</sales>
<develop>
<programmer>小張</programmer>
</develop>
</company>
一個很重要的概念是: 一棵XML樹往往只有2個節點 1. XML節點,就是文件的第一行 <?xml ...?> 2. XML根節點<company>,<sales>和<develop>只是<company>的子節點.而文件的第一行,我們也把它看成一個節點. 這樣理解的話,只要我們能解析一個節點,我們就可以解析整棵樹.
狀態分析法
所謂狀態分析法,就是指一個解析函數,它可以根據不同的狀態,運行不同的代碼.對於解析xml文檔,我設計了如下狀態:
enum xmlnode_state // 分析狀態
{
st_begin, // 開始
st_tagstart, // /*tag開始 - "<"後的第一個字符*/
st_tagend, // tag結束 - />,>,?> 前的第一個字符
st_attrnamestart, // 屬性名開始 - tag後的第一個非空格字符
st_attrnameend, // 屬性名結束 - =, ,前的第一個字符
st_attrvaluestart, // 屬性值開始 - ',",後的第一個字符
st_attrvalueend, // 屬性值結束 - ',",前的第一個字符
st_child, // 開始分析子節點
st_contentstart, // 內容開始 - >後的第一個字符
st_contentend, // 內容結束 - <前的第一個字符
st_commentstart, // 注釋開始 <!--後的第一個字符
st_commentend, // 注釋結束 -->前的第一個字符
st_endtagstart, // 結束TAG 開始 </,<?後的第一個字符
st_endtagend, // 結束TAG 結束 >前的第一個字符
st_cdatastart,
st_cdataend,
st_end, // 分析結束
};
假設pCur指向XML文檔的輸入流的當前位置, 現在來模擬一下解析過程: 在初始狀態st_begin下,一直移動pCur,直到pCur[0] = '<',意味著節點開始了. 此時根據後面字符切換狀態: 如果後面連續3個字符時 "!--" 那麼說明這是一個注釋節點,形如"<!-- ... -->",把狀態切換為st_commentstart並繼續運行相應代碼; 如果後面一個字符是'?', 那麼說明它是這種節點的開始 "<? ...",應該把狀態切換為st_tagstart; 如果後面的字符是"![CDATA[",則說明這是一個CDATA節點的開始 "<![CDATA[ ... ]]>" (圖1中沒有標明CDATA節點的情況,因為作圖的時候沒有考慮到CDATA節點);如果是其他字符,則說明開始讀取節點名, "<company> ..."
根據圖1所示,其他的代碼都類似:從輸入流不斷讀出字符,根據當前狀態,把讀到的內容解析為XML文檔中不同的項.
(圖1)
特別說明: 我把節點的內容理解為當前節點的一個子節點,比如 "<company>這裡是節點內容</company>"這一段XML文本會被解析為一個父節點"company"和一個子節點"這裡是節點內容". 這樣做是有好處的,看這個例子"<company>這裡是節點內容<any></any>另一段節點內容</company>"如果只是把節點內容作為節點的一個屬性,在碰到剛剛這種情況時就束手無策了.