要為 XML 寫一個解析器,第一步是把文法講清楚。本文從詞法與句法兩個層次整理 XML 的規則,並據此構造正則式與下推自動機。
1)大小寫敏感。元素名在起始與結束標記中必須一致,<mytag>…</mytag> 可以,寫成 </Mytag> 就錯了。保留字串也必須符合大小寫要求,如 <?xml …?>、<!ENTITY>。
2)保留標記字元為 <、>、&。這三個字元不允許出現在元素名、元素文字、屬性名與屬性值中。< 用於開啟標記,> 用於關閉標記,& 用於轉義。常見的實體引用為 < 產生 <、> 產生 >、& 產生 &、' 產生 '、" 產生 "。
3)命名規則。元素名必須以下劃線或字母起始,後續可包含字母、數字、句點、連字號、下劃線、冒號與其他語言的擴充字元;名稱中不得含任何空白字元(空格、定位字元、換行、歸位字元)。名稱可帶命名域前置詞,如 <mytag>、<dt:mytag>。元素文字則可以是除保留字元以外的字元集合,例如 <mytag>my money is $2000</mytag>。
4)屬性。屬性名規則同元素名,屬性值必須由單引號或雙引號括起,內容為除保留字元以外的字串,例如 <mytag myprop="proper value">。屬性名帶 xmlns 前置詞時,表示該屬性定義了一個命名域,如 <mytag xmlns:ns="https://www.myweb.com/myschema">。
1)文件組成。一份 XML 文件由一個 XML 宣告、多個選擇性的文件型別宣告、多個選擇性的處理指令、多個選擇性的註釋,以及一個根元素構成的資料體所組成;此外還可在語句中嵌入 CDATA 段。
<?xml …?> /* XML 宣告 */
<!DOCTYPE …> /* 文件型別宣告 */
<!-- … --> /* 註釋 */
<?xml-stylesheet …?> /* 處理指令 */
<root> /* 根資料元素 */
<child>
…<![CDATA[…]]>
</child>
</root>
2)XML 宣告由 <?xml 開啟、?> 關閉,內含版本、編碼等選擇性說明,如 <?xml version="1.0" encoding="UTF-8"?>。
3)文件型別宣告由 <! 加保留字串開啟、> 關閉,如 <!DOCTYPE mydoc SYSTEM "mydoc.dtd">。
4)處理指令由 <? 加保留字串開啟、?> 關閉,如 <?xml-stylesheet type="text/xsl" href="mystyle.xsl"?>。
5)註釋由 <!-- 開啟、--> 關閉,如 <!-- this is my XML document -->。
6)元素由 <元素名> 開啟,由 /> 或 </元素名> 關閉,兩者必須匹配,如 <mytag … /> 或 <mytag>…</mytag>。元素允許巢狀,因此還必須維持層次上的匹配,如 <mytag><subtag>…</subtag></mytag>。
7)CDATA 段由 <![CDATA[ 開啟、]]> 關閉,用於讓其中的語句繞過 XML 解析規則。例如 <![CDATA[select * from mytable where thefield <= '100']]>——SQL 語句裡的 <= 不必轉義。
先定義字元類別:
digit = [0-9] /* 數字 */ letter = [a-zA-Z] /* 字母 */ signs = [~ ! @ # % ^ & * ( ) ? : ; " ' , . / - _ + = \ ] /* 符號 */ ascii2 = [0x80-0xFF] /* ASCII 表第二部分擴充字元 */ space = [0x20, \t, \r, \n] /* 空格、定位、歸位、換行 */ reserve = [< > &] /* 保留字元 */
據此可得四條正則式:
element_name -> (_ | letter | ascii2) (ε | _ | - | : | . | digit | letter | signs | ascii2)* element_text -> (ε | not reserve)* attr_name -> (_ | letter | ascii2) (ε | _ | - | : | . | digit | letter | signs | ascii2)* attr_value -> (ε | not reserve)*
元素名與屬性名的規則完全相同,這也是為什麼實作時可以共用同一個命名判斷函式。屬性值與元素文字則只是「排除保留字元的任意序列」。
xml_document -> xml_header (ε | xml_declare | xml_instruct | xml_comments)* xml_element
xml_header -> [<?xml] (space)* (prop_token)* (space)* [?>]
xml_declare -> [<!] reserve_word (space)* (token)* (space)* [>]
xml_instruct -> [<?] reserve_word (space)* (prop_token)* (space)* [?>]
xml_comments -> [<!--] (ε | digit | letter | signs | ascii2 | space)* [-->]
xml_element -> [<] element_name (space)* (ε | prop_token)* (space)* [/>]
| [<] element_name (space)* (ε | prop_token)* (space)* [>]
(ε | <![CDATA[ element_text ]]>)
(ε | xml_element)* (space)* [</] element_name [>]
prop_token -> prop_name (space)* [=] (space)*
[ε <![CDATA[]] | ['"] prop_value ['"] | ε ]]>
reserve_word -> [DOCTYPE | ELEMENT | NOTATION | …]
token -> (ε | not reserve)*
1) STACK_DFA mata_XML_doc = <Q, Σ, σ, q, Γ, S>
Q : 狀態集合(詳見後述)
Σ : 指向待解析的 XML 元素詞串
σ : Q × Σ -> Q 狀態轉移函數
q : {NIL_SKIP} 初始狀態
Γ : {NIL_FAILED, NIL_SUCCEED} 終結狀態集合
S : {<Q /*狀態*/, N /*DOM 節點*/>, <…>} 下推堆疊
2) 堆疊頂符集合(反映當前分析節點的型別)
T : {NIL /*空*/, TG /*標記*/, NS /*元素*/, IS /*指令*/,
DS /*宣告*/, CD /*CDATA 界段*/, CM /*註釋*/}
3) 狀態集合(與堆疊頂符對應)
NIL: NIL_FAILED /*失敗*/ NIL_SKIP /*忽略*/ NIL_SUCCEED /*成功*/
CM : CM_BEGIN /*註釋開始*/ CM_END /*註釋結束*/
TG : TG_OPEN /*標記打開*/ TG_INT_CLOSE /*標記中斷*/
TG_PRE_CLOSE /*標記準備關閉*/ TG_CLOSE /*標記關閉*/
NS : NS_NAME_BEGIN / NS_NAME_END /*元素名起訖*/
NS_KEY_BEGIN / NS_KEY_END /*屬性名起訖*/
NS_ASIGN /*屬性賦值*/
NS_VAL_BEGIN / NS_VAL_END /*屬性值起訖*/
NS_TEXT_BEGIN / NS_TEXT_END /*元素文字起訖*/
IS : IS_OPEN / IS_CLOSE /*指令起訖*/
IS_NAME_BEGIN / IS_NAME_END /*指令名起訖*/
IS_KEY_BEGIN / IS_KEY_END /*指令鍵起訖*/
IS_ASIGN /*賦值符*/
IS_VAL_BEGIN / IS_VAL_END /*指令值起訖*/
DS : DS_OPEN /*宣告打開*/ DS_SKIP /*跳過宣告節*/ DS_CLOSE /*宣告關閉*/
CD : CD_BEGIN /*CDATA 界段開始*/ CD_END /*CDATA 界段結束*/
4) 堆疊頂動作
PUSH : 將當前節點與狀態壓入堆疊
POP : 出堆疊並恢復當前節點與狀態
NOP : 無堆疊操作
5) 讀寫頭動作
NEXT : 移至下一字元
SKIP : 跳過轉義串或保留名串
PAUSE : 暫停於當前字元
STOP : 停機於當前字元
說明:space 指符合空白定義的字元;name 指符合命名定義的字元;namepre 指符合命名起始的字元;token 指除保留字元以外的字元;other 指其他剩餘字元。每列格式為「(狀態) 輸入字元 → (堆疊動作, 新狀態, 讀寫頭動作)」。
(NIL_SKIP) 初始化 space -> (NOP, NIL_SKIP, NEXT) 忽略起始空白 < -> (NOP, TG_OPEN, NEXT) 遇到標記 '\0' -> (NOP, NIL_SUCCEED, STOP) 結束字元,成功 other -> (NOP, NIL_FAILED, STOP) 無效字元 (TG_OPEN) ! -> (NOP, DS_OPEN, NEXT) 宣告符 ? -> (NOP, IS_OPEN, NEXT) 指令符 / -> (POP, TG_PRE_CLOSE, NEXT) 準備關閉標記 namepre -> (NOP, NS_NAME_BEGIN, PAUSE) 元素名開始 other -> (NOP, NIL_FAILED, STOP) (DS_OPEN) other -> (NOP, DS_SKIP, PAUSE) 忽略宣告內容 (DS_SKIP) > -> (NOP, DS_CLOSE, PAUSE) 宣告結束 other -> (NOP, DS_SKIP, NEXT) (DS_CLOSE) > -> (NOP, TG_CLOSE, PAUSE) 標記關閉 (CM_BEGIN) - -> (NOP, CM_END, SKIP) 註釋開始 token -> (NOP, CM_BEGIN, NEXT) (CM_END) > -> (NOP, DS_CLOSE, PAUSE) 註釋關閉 (CD_BEGIN) ] -> (NOP, CD_END, SKIP) 界段結束候選 token -> (NOP, CD_BEGIN, NEXT) (CD_END) > -> (NOP, DS_CLOSE, PAUSE) CDATA 關閉 (IS_OPEN) namepre -> (NOP, IS_NAME_BEGIN, PAUSE) 指令名開始 (IS_NAME_BEGIN) space -> (NOP, IS_NAME_END, PAUSE) ? -> (NOP, IS_NAME_END, PAUSE) & -> (NOP, IS_NAME_BEGIN, SKIP) 字元轉義 name -> (NOP, IS_NAME_BEGIN, NEXT) (IS_NAME_END) space -> (NOP, IS_NAME_END, NEXT) ? -> (NOP, IS_CLOSE, NEXT) namepre -> (NOP, IS_KEY_BEGIN, PAUSE) 指令屬性名開始 (IS_KEY_BEGIN) space -> (NOP, IS_KEY_END, PAUSE) = -> (NOP, IS_KEY_END, PAUSE) & -> (NOP, IS_KEY_BEGIN, SKIP) name -> (NOP, IS_KEY_BEGIN, NEXT) (IS_KEY_END) space -> (NOP, IS_KEY_END, NEXT) = -> (NOP, IS_ASIGN, NEXT) (IS_ASIGN) space -> (NOP, IS_ASIGN, NEXT) " 或 ' -> (NOP, IS_VAL_BEGIN, NEXT) (IS_VAL_BEGIN) " 或 ' -> (NOP, IS_VAL_END, NEXT) & -> (NOP, IS_VAL_BEGIN, SKIP) token -> (NOP, IS_VAL_BEGIN, NEXT) (IS_VAL_END) space -> (NOP, IS_VAL_END, NEXT) ? -> (NOP, IS_CLOSE, NEXT) other -> (NOP, IS_KEY_BEGIN, PAUSE) 回到屬性名 (IS_CLOSE) > -> (NOP, TG_CLOSE, NEXT) 標記關閉 (NS_NAME_BEGIN) space -> (NOP, NS_NAME_END, PAUSE) > -> (NOP, NS_NAME_END, PAUSE) / -> (NOP, NS_NAME_END, PAUSE) & -> (NOP, NS_NAME_BEGIN, SKIP) name -> (NOP, NS_NAME_BEGIN, NEXT) (NS_NAME_END) space -> (NOP, NS_NAME_END, NEXT) > -> (NOP, TG_INT_CLOSE, NEXT) 標記中斷(有內容) / -> (NOP, TG_PRE_CLOSE, NEXT) 空元素 other -> (NOP, NS_KEY_BEGIN, PAUSE) 屬性名開始 (NS_KEY_BEGIN) space -> (NOP, NS_NAME_END, PAUSE) = -> (NOP, NS_KEY_END, PAUSE) & -> (NOP, NS_KEY_BEGIN, SKIP) name -> (NOP, NS_KEY_BEGIN, NEXT) (NS_KEY_END) space -> (NOP, NS_KEY_END, NEXT) = -> (NOP, NS_ASIGN, NEXT) (NS_ASIGN) space -> (NOP, NS_ASIGN, NEXT) " 或 ' -> (NOP, NS_VAL_BEGIN, NEXT) (NS_VAL_BEGIN) " 或 ' -> (NOP, NS_VAL_END, NEXT) & -> (NOP, NS_VAL_BEGIN, SKIP) token -> (NOP, NS_VAL_BEGIN, NEXT) (NS_VAL_END) space -> (NOP, NS_VAL_END, NEXT) > -> (NOP, TG_INT_CLOSE, NEXT) other -> (NOP, NS_KEY_BEGIN, PAUSE) (TG_INT_CLOSE) < -> (PUSH, TG_OPEN, NEXT) 子標記開始 other -> (NOP, NS_TEXT_BEGIN, PAUSE) 元素文字開始 (NS_TEXT_BEGIN) < -> (NOP, NS_TEXT_END, PAUSE) & -> (NOP, NS_TEXT_BEGIN, SKIP) token -> (NOP, NS_TEXT_BEGIN, NEXT) (NS_TEXT_END) < -> (PUSH, TG_OPEN, NEXT) (TG_PRE_CLOSE) > -> (NOP, TG_CLOSE, PAUSE) name -> (NOP, TG_PRE_CLOSE, NEXT) 繼續讀結束標記的元素名 (TG_CLOSE) > -> (POP, NIL_SKIP, NEXT) 標記關閉,出堆疊
自動機的關鍵設計是用堆疊處理巢狀:遇到 < 且非結束標記時 PUSH,遇到完整的結束標記時 POP。這正是 XML 巢狀結構必須靠下推自動機(而非有限狀態機)才能處理的原因——單純的狀態機無法記住「我現在在第幾層」。而 TG_PRE_CLOSE 這個狀態的存在,讓它能同時處理 </name> 與 <name/> 兩種關閉形式。
幾點限制值得留意。第一,本文對 XML 宣告只做忽略處理;若要真正解析版本與編碼,需要再擴充 IS 系列的狀態與轉移規則。第二,轉移表中註釋與 CDATA 的結束都導向 DS_CLOSE,實作時應依堆疊頂符區分是哪一種結構結束,否則會混淆。第三,這套自動機只檢查格式良好性,不做 DTD/Schema 驗證——驗證需要在解析完成後另跑一層。第四,屬性值結束時以「同型引號」判斷才算嚴謹,表中把兩種引號並列,實作時應記錄起始引號種類。