用状态机实现XML解析器 - C++环境

文章由LinuxBoy分享于2019-03-31 10:03:18热评（447）

用状态机实现XML解析器 - C++环境

摘要本文介绍一种文本解析的方法:状态切换法 (状态机), 并给出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_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文档中不同的项.

XML语法分析机(优化)

(图1)

特别说明: 我把节点的内容理解为当前节点的一个子节点,比如 "<company>这里是节点内容</company>"这一段XML文本会被解析为一个父节点"company"和一个子节点"这里是节点内容". 这样做是有好处的,看这个例子"<company>这里是节点内容<any></any>另一段节点内容</company>"如果只是把节点内容作为节点的一个属性,在碰到刚刚这种情况时就束手无策了.

推荐文章：

用状态机实现XML解析器 - C++环境