loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

小写了个XML解析器

    开始用FLEX做词法分析,然后在此基础上稍微做些符号匹配(实在称不上语法分析),即完成了XML
文件的简单解析。
    我把XML文件拆分成:<, >, />, </, =, ID, STRING 等token。这样一整理,用FLEX直接生成词法
分析程序。每一次getToken就返回这些token。上层的语法匹配就变得比较简单。例如当得到"/>"token
时,我就可以判断这是一个节点的结束;当得到ID token时,就可以推测下一个token为"=",再下一个
是个STRING。不过对于部分token,也需要做一两个token的回溯,例如当遇到"<"时,并不一定表示一个
新节点的开始,它可能是新节点的开始,同样也可能是上一个节点的结束("</")。
    以我薄弱的编译原理知识来看,解析XML变得非常容易。除此之外,还需要写一些上层代码来保存
XML结构,以方面更上层代码获取XML文件的配置信息。因为我打算用纯C来写这个东西,所以数据结构方
面只有自己处理。这里我以一种变相的树结构来保存:每一个节点有两个域:first child, sibling。
其实这样做是一个很明显的通用做法,因为XML种每一个节点都可能拥有不定数量的children节点,如果
让parent直接去保存,显然很笨。例如:
    <Resource>
        <bmp file="1.bmp"/>
        <bmp file="2.bmp"/>
    </Resource>
    可以使用这样的数据结构来存储:
    struct xmlNode
    {
        ...
        struct xmlNode *child;
        struct xmlNode *sibling;
    };
    对于Resource这个node而言,其child域指向第一个bmp节点(file属性为1.bmp那个节点);对于第一
个bmp节点而言,其sibling域则指向了第二个bmp节点。
    这个简单的xml解析器是在公司外网机器上写的,没有VC,没有任何IDE。代码我是用VIM敲的,敲好
后写makefile,用mingw里的gcc、make来生成程序,用gdb来调试程序。这算是第一次离开VC写的一个非
练习程序(起码用makefile来组织工程)。- -| makefile写的比较烂,gdb用得很不熟,不过好歹调试出来
了。越来越想换个平台,只可惜工作还是得在windows vc下,很扫兴。
    后来发觉词法分析也很简单,用FLEX的时候正则表达式都写出来了。前段时间一直在看编译原理,虽然不
用功。但是就这里而言,基本可以直接根据正则表达式画出DFA。终于不用接触那恶心的从NFA转DFA的
过程,因为我至今不会,更不会写代码转。- - 总而言之,自己手写了词法分析。边写边参考编译原理
与实践中附带的tiny-c编译器的词法分析部分,最终发现我抄了一遍。MD,一点技术含量都没有。

附上全部源代码(对于代码我还是比较满意的:D),下载

posted on 2008-12-10 16:22 Kevin Lynx 阅读(4577) 评论(9)  编辑 收藏 引用 所属分类: 通用编程编译原理

评论

# re: 小写了个XML解析器 2008-12-10 18:20 肥仔

struct xmlNode
{
...
struct xmlNode *child;
struct xmlNode *sibling;
};
==================
这种结构处理起来,好累的。我的xml解析器采用下面这种结构
struct xmlNode
{
...
vector<xmlNode*> childs;
struct xmlNode* parent;
};  回复  更多评论   

# re: 小写了个XML解析器[未登录] 2008-12-10 19:40 908971

up  回复  更多评论   

# re: 小写了个XML解析器 2008-12-11 08:50 Kevin Lynx

@肥仔
- -!
我恰好说了,如果parent直接保存children,好占空间的,例如你这个vector,虽然我的处理方式累了点。- -!   回复  更多评论   

# re: 小写了个XML解析器 2008-12-11 11:06 momor

@Kevin Lynx
@肥仔
- -!
我恰好说了,如果parent直接保存children,好占空间的,例如你这个vector,虽然我的处理方式累了点。- -!
===============================================
没错,而且使用vector虽然方便了,但是除了增加内存消耗以外,还有性能损耗,附加的库会加剧你的移植问题,虽然说是标准模板库,但是在底层的工具类实现里,最好还是符合KISS原则够用就好^^比如TinyXML就提供了支持和不支持使用STL的选项用以折衷
  回复  更多评论   

# re: 小写了个XML解析器 2008-12-13 18:03 dell笔记本

不错,谢谢,省得我自己写了  回复  更多评论   

# re: 小写了个XML解析器 2009-01-04 02:06 胖dudu

c 的东西,还加了个vector就不太好了吧,我推荐自己封一个c版本的vector或者list  回复  更多评论   

# re: 小写了个XML解析器 2009-01-08 09:07 Kevin Lynx

@胖dudu
不用自己做了。BSD(相关组织)早使用宏写了一套数据结构,链表,树,等等。  回复  更多评论   

# re: 小写了个XML解析器 2009-04-29 11:41 gua

直接使用TinyXML就可以了!  回复  更多评论   

# re: 小写了个XML解析器[未登录] 2011-08-12 17:07 dophi

@gua
hacker为啥要自己写工具来用而不是用现成的工具?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理