DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> XML學習教程 >> XML詳解
XML 文法分析:詞法規則、正則式與下推自動機
編輯:XML詳解     

要為 XML 寫一個解析器,第一步是把文法講清楚。本文從詞法與句法兩個層次整理 XML 的規則,並據此構造正則式與下推自動機。

一、詞法特徵

1)大小寫敏感。元素名在起始與結束標記中必須一致,<mytag>…</mytag> 可以,寫成 </Mytag> 就錯了。保留字串也必須符合大小寫要求,如 <?xml …?>、<!ENTITY>。

2)保留標記字元為 <、>、&。這三個字元不允許出現在元素名、元素文字、屬性名與屬性值中。< 用於開啟標記,> 用於關閉標記,& 用於轉義。常見的實體引用為 &lt; 產生 <、&gt; 產生 >、&amp; 產生 &、&apos; 產生 '、&quot; 產生 "。

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)*

元素名與屬性名的規則完全相同,這也是為什麼實作時可以共用同一個命名判斷函式。屬性值與元素文字則只是「排除保留字元的任意序列」。

四、句法結構(BNF 形式)

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 驗證——驗證需要在解析完成後另跑一層。第四,屬性值結束時以「同型引號」判斷才算嚴謹,表中把兩種引號並列,實作時應記錄起始引號種類。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved