XML文法分析 - 王朝网络

在进行XML文法分析之前，首先有必要了解XML语法的基本规则：

词法特征：1）XML区分大小写，如元素名在打开和关闭标记中应保持大小写一致<mytag>…</mytag>，XML的保留词串应符合大小写要求<?xml …> <!ENTITY>…。

2）XML保留标记字符为：< > &，保留字符不允许出现在元素名、元素文本、属性名、属性值中，< 用户打开标记，>用于关闭标记，&用于转意，常见的转意为 &lt生成<，&gt生成>，&amp生成&，&apos生成’，&quot生成”

3）元素名以下划线或字母开始，可包含字母、数字、句点、连字符、下划线、冒号和用于其他语言的扩展字符，元素名中不能有空格符（分格符、跳格符、换行符、回车符），元素名可以由名域前缀。如：<mytag> <dt:mytag> 元素文本可以是除XML保留字符外的字符集合，如<mytag> my money is $2000 </mytag>

4）属性名的规则同元素名，属性值由单引号或双引号括约其中，可由除XML保留字符以外的字符串组成，如：<mytag myprop=”proper value”>。属性名有xmlns前缀，表明该属性定义了一个名域，如：<mytag xmlns:ns=”http://www.myweb.com/myschema”>

句法特征：1）XML文档由一个XML说明、多个可选的文档说明、多个可选的XML指令、多个可选的XML注释和一个根元素的数据体组成，此外还可以有嵌入语句中的CDATA段，如：

<?xml …?> /*XML说明*/

<!DOCTYPE …> /*XML文档说明*/

/*XML注释*/

<?xml-stylesheet …?> /*XML指令*/

<root> /*根数据元素*/

<child>

…<![CDATA[…]]>

</child>

</root>

2）XML说明由<?xml打开，由?>标关闭，其中包含版本、编码等可选说明，如：<?xml version=”1.0” encoding=”UTF-9”?>

3）XML文档说明由<!和保留串打开，由>关闭，如：<!DOCTYPE mydoc SYSTEM “mydoc.dtd”>

4)XML指令由<?和保留串打开，由?>关闭，如：<?xml-stylesheet type=”text/xsl” href=”mystyle.xsl”?>

5）XML注释由<!――打开，由――>关闭，如：

6）XML元素由<元素名>打开，由/>，或</元素名>关闭，元素的打开和关闭标记相互匹配，如<myteg ../>或<mytag>…</myteg>，XML的元素允许嵌套，应此还应保持层次上的匹配，如<myteg><subtag>..</subtag></mytag>。

7）CDTATA段由<![CDATA[>打开，由]]>关闭，用于使居于其中的语句规避XML解析规则。如：<![CDATA[ select * from mytable where thefield <= ‘100’ ]]>

根据以上的XML文法特征，可以构造出用于词法分析的正则式和用于句法分析的下推自动机结构。

XML词法正则式：

#define digit [1,2,…,9] /*数字字符*/

#define letter [a,b,…,z,A,B,…,Z] /*字母字符*/

#define signs [~, ! , @, #, %, ^, &,*,(, ), ?, :, ;, “, ‘, ,, ., /,-, _, +, =, |, \] /*符号字符*/

#define ascii2 [0x80,…,0xFF] /*ASCII chart2 扩展字符*/

#define space [0x20, \t, \r, \n] /*空格符，跳格符，回车符，换行符*/

#define reserve [< , >, &] /*XML保留字符*/

1）元素名的正则式：

2）元素文本的正则式：

element_text -> (ε| not reserve)*

3）属性名的正则式：

4）属性文本的正则式：

proper_value -> (ε| not reserve)*

XML句法结构：

xml_document -> xml_header (ε| xml_declare | xml_instruct | xml_comments)* xml_element

xml_header -> [<?xml](space)*(proper_token)*(space)* [?>]

xml_declare -> [<!]reserve_word(space)*(token)*(space)*[>]

xml_instruct -> [<?]reserve_word(space)* (proper_token)* (space)*[?>]

xml_element -> [<]element_name (space)*( ε| proper_token)*(space)*[/>] |

[<]element_name(space)*( ε | proper_token)*(space)*[>]

[ε| <![CDATA[ ]element_text[ε| ]]>]

(ε | xml_element)*(space)*[</]element_name[>]

proper_token -> proper_name(space)*[=](space)* [ε| <![CDATA[ ] [‘ | “]proper_value[‘ | “] [ε| ]]>]

reserve_word -> [DOCTYPE | ELEMENT | NOTATION | …]

token -> (ε| not reserve)*

分析XML文法需要构造一个下推自动机，它的结构定义如下：

1）STACK_DFA mata_xml_doc = <Q,Σ，σ，q,Γ,T,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_NAME_BEGIN /*指令名开始*/

IS_NAME_END /*指令名结束*/

IS_KEY_BEGIN /*指令键开始*/

IS_KEY_END /*指令键结束*/

IS_ASIGN /*赋值符*/

IS_VAL_BEGIN /*指令值开始*/

IS_VAL_END /*指令值结束*/

IS_CLOSE /*指令关闭*/

DS: DS_OPEN /*声明打开*/

DS_SKIP /*越过申明节*/

DS_CLOSE /*声明关闭*/

CD: CD_BEGIN /*CDATA界段开始*/

CD_END /*CDATA界段结束*/

4）栈顶动作：PUSH: 将当前节点和状态压入栈

POP：出栈并恢复当前节点和状态

NOP：无栈操作

5）读写头动作：NEXT: 移动至下一字符

SKIP: 越过转义串或保留名串

PAUSE: 暂定于当前字符

STOP：停机于当前字符

6）状态转移列表：

说明： space 指符合空格定义的字符

name 指符合命名定义的字符

namepre 指符合命名的第一个字符

token 指除去保留字符外字符

other 指除去已判断以外的字符

（状态）输入符（栈操作，状态，读写头动作）

(NOP,NIL_SKIP,NEXT)/*初始化*/

(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) /*标记关闭*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(CM_BEGIN)

- (NOP,CM_END,SKIP) /*注释开始*/

token (NOP,CM_BEGIN,NEXT) /*继续注释串*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(CM_END)

> (NOP,DS_CLOSE,PAUSE) /*注释关闭*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(CD_BEGIN)

] (NOP,CD_END,SKIP) /*界段开始*/

token (NOP,CD_BEGIN,NEXT) /*继续界段*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(CD_END)

> (NOP,DS_CLOSE,PAUSE) /*声明关闭*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(IS_OPEN)

namepre (NOP,IS_NAME_BEGIN,PAUSE) /*指令名开始*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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) /*继续指令名*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(IS_NAME_END)

space (NOP,IS_NAME_END,NEXT) /*忽略空格*/

? (NOP,IS_CLOSE,NEXT) /*标记中断*/

namepre (NOP,IS_KEY_BEGIN,PAUSE) /*指令属性名开始*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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) /*继续属性名*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(IS_KEY_END)

space (NOP,IS_KEY_END,NEXT) /*忽略空格*/

= (NOP,IS_ASIGN,NEXT) /*属性赋值符*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(IS_ASIGN)

space (NOP,IS_ASIGN,NEXT) /*忽略空格*/

“ (NOP,IS_VAL_BEGIN,NEXT) /*属性赋值打开*/

‘ (NOP,IS_VAL_BEGIN,NEXT) /*属性赋值打开*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(IS_VAL_BEGIN)

“ (NOP,IS_VAL_END,NEXT) /*属性值结束*/

‘ (NOP,IS_VAL_END,NEXT) /*属性值结束*/

& (NOP,IS_VAL_BEGIN,SKIP) /*字符转义*/

token (NOP,IS_VAL_BEGIN,NEXT) /*继续属性值*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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) /*标记关闭*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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) /*元素名继续*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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) /*继续属性名*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(NS_KEY_END)

space (NOP,NS_KEY_END,NEXT) /*忽略空格*/

= (NOP,NS_ASIGN,NEXT) /*属性赋值符*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(NS_ASIGN)

space (NOP,NS_ASIGN,NEXT) /*忽略空格*/

“ (NOP,NS_VAL_BEGIN,NEXT) /*属性赋值打开*/

‘ (NOP,NS_VAL_BEGIN,NEXT) /*属性赋值打开*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(NS_VAL_BEGIN)

“ (NOP,NS_VAL_END,NEXT) /*属性值结束*/

‘ (NOP,NS_VAL_END,NEXT) /*属性值结束*/

& (NOP,NS_VAL_BEGIN,SKIP) /*字符转义*/

token (NOP,NS_VAL_BEGIN,NEXT) /*继续属性值*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(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_BEGIN,SKIP) /*字符转义*/

token (NOP,NS_TEXT_BEGIN,NEXT) /*继续元素文本*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(NS_TEXT_END)

< (PUSH,TG_OPEN,NEXT) /*标记开始*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

(TG_PRE_CLOSE)

> (NOP,TG_CLOSE,PAUSE)/*标记结束*/

name (NOP,TG_PRE_CLOSE,NEXT) /*继续关闭标记的元素名*/

other (NOP,NIL_FAILED,STOP) /*无效字符*/

(TG_CLOSE)

> (POP,NEXT) /*标记关闭，出栈*/

other (NOP,NIL_FAILED,STOP) /*非法字符*/

对XML声明，本文只做了忽略处理，可以通过增加XML声明的状态和状态转移列表，进而支持XML声明的分析。