《支持stax的高效xml解析器的设计与实现》由会员分享，可在线阅读，更多相关《支持stax的高效xml解析器的设计与实现（6页珍藏版）》请在金锄头文库上搜索。
1、） 本文工作受国家 973 项目 （编号 2002CB3l2005） 、 国家 863 项目 （编号 200lAAll30l0） 的资助。任 鑫 硕士研究生， 研究方向： 分布式计算、 软件工程； 曹冬磊 博士研究生， 研究方向： 分布式计算、 软件工程； 金蓓弘 博士， 副研究员， 研究方向： 分布式计算、 软件工程。计算机科学 2006VoI. 33N. 6支持 StAX 的高效 XML 解析器的设计与实现）任 鑫 曹冬磊 金蓓弘 （中国科学院软件研究所软件工程技术中心 北京 l00080）摘 要 StAX 是 JCP 提出的一种新的 XML 解析方式， 它提供给用户更多的解析控制权。本文
2、给出了用于 XML 语法分析的下推自动机模型的设计以及 StAX 解析器 OnceStAXParser 的实现。OnceStAXParser 在经过了严格的 XML 兼容性测试和 StAX API 兼容性测试之后， 还从多个方面进行了性能优化， 包括自动机实现优化、 有计划的预分配和延迟处理策略以及适度封装策略等。性能测试数据表明， OnceStAXParser 的吞吐量比 Sun SJSXP 平均高5%， 比 BEA StAX RI平均高 38%。关键词 XML 解析器， StAX， 性能优化Design and Implementation of an Efficient StAX Bas
3、ed XML ParserREN Xin CAO Dong-Lei JIN Bei-hong（TechnoIogy Center of Software Engineering， Institute of Software， Chinese Academy of Sciences， Beijing l00080）Abstract StAX is presented by JCP JSR-l73 specification which supports XML puII parsing and gives more parsing controI tousers. This paper desc
4、ribes the design of pushdown automaton modeI for XML syntax anaIysis and iIIustrates the impIementa-tion of StAX parser OnceStAXParser. After passing the rigorous XML conformance tests and StAX API conformance tests， On-ceStAXParser is optimized from many aspects such as the impIementation of pushdo
5、wn automaton， arranged pre-aIIocation andIazy processing， appropriate encapsuIation strategy， etc. The performance test resuIts from XML Test suite show that thethroughput of OnceStAXParser is 5% more than that of SJSXP on the average， and is 38% more than that of BEA StAX RI onthe average.Keywords
6、XML parser， StAX， Performance optimization!“ 引言作为一种数据表示和数据交换的标准， XML 广泛应用于文档处理领域 （例如 XhTML、 XSLT） 、 数据库领域 （例如 XML数据库） 、 Web 服务领域 （例如 SOAP 消息、 WSDL 等） 。在某些应用场合， 例如在 Web 服务领域， 因为系统传递的消息是基于 XML 的， 当系统的消息比较密集、 并发程度比较高的时候， XML 解析会成为整个系统性能的一个瓶颈。所以， 提高XML 解析效率具有非常重要的实际意义。目前常用的解析 XML 的 API 是 SAX （SimpIe API
7、 for XMLprocessing） 和 DOM （Document Object ModeI） 。尽管这两种方法都存在各自的优点， 但也有很明显的缺点。DOM 解析器需要将整个文档解析一遍， 并将解析结果以树型结构保存到内存中 （这棵树被称为 DOM 树） ， 然后才把程序的控制权交给用户。这导致了 DOM 方式不够灵活， 需要占用大量的资源。解析 XML 文档所用的内存大小和 XML 文档大小一般要达到l0： l 的比例l。也有一些 DOM 解析器采用延迟节点展开技术， 这样可以实现部分解析文档的功能， 但这种实现方式也要占用大量的资源， 开销很大， 解析效率依然不高。SAX 解析器在解
8、析过程中触发事件并激活用户预定义的回调 （caIIback） 方法。用户不能对解析过程加以控制， 不能进行迭代的处理， 使用上不够灵活。与 DOM、 SAX 相比， StAX （The Streaming API for XML） 是以拉 （PULL） 方式解析 XML 的 Java API， 目前已经通过了 JCP的审核， 成为了 JSR-l73 规范。StAX 接口具有灵活小巧的特点， 用户可以控制 StAX 的解析过程， 比较适合于网络计算和移动环境的应用需求， 有利于实现高效地解析 XML 文档。BEA 公司提供了 StAX 的参考实现 BEA StAX RI， 但该实现并不完全符合
9、StAX 规范的要求， 存在功能缺陷， 它只通过了大部分的 XML 兼容性测试。SJSXP 是 Sun 公司开发的基于StAX 的高效 XML 解析器， 符合 XML l. 0 和 Namespace l. 0 规范。Woodstox 是一个开源的 StAX XML 解析器， 目前的版本是 2. 0。Microsoft 在. NET 框架中提供的 XmITextReader， 尽管不支持 StAX 接口， 但也是一种拉方式的解析器。总之， XML拉式解析正在成为工业界关注的热点。我们按照 XML l. 02和 Namespace l. 03规范， 构造了支持 StAX 接口的 XML 解析器
10、OnceStAXParser。它支持 XML 的良构性约束 （weII-formedness constraint， WFC） 的验证， 但不进行有效性约束 （vaIidity constraint） 的验证。本文给出了 OnceStAXParser 的设计和实现， 按如下方式组织： 第 2 节描述了实现 XML 语法分析的下推自动机模型，第 3 节给出了 StAX 的接口实现， 第 4 节总结了我们在性能优化方面所采取的措施， 第 5 节介绍了性能测试方法和测试结果， 最后是全文小结。82l!“ XML 的语法分析这一节在分析 XML 语言的基础上， 构造了 XML 语言自动机， 然后将它应
11、用到 StAX 接口中， 设计符合 StAX 规范要求的状态机模型。!.#“ XML 语言自动机设计XML 语法采用 EBNF （Extended Backus NormaI Form） 表示， 其中以大写字母开头的符号都是正则语言的开始符号， 因此， 可以构造确定的有穷状态自动机 （deterministic finite auto-mation， DFA） 来识别它们。例如对于一个注释 （Comment） ， 可以通过 “ ！-” 来判断一个标记 （markup） 是注释， 然后调用词法分析器中的 getComment 的方法来得到注释中的字符。图 l 给出了解析 Comment 的状态转
12、移图。图 l 解析 Comment 的状态转移图我们以这些大写字母开头的符号作为最基本的语法符号， 对以小写字母开头的非终结符做推导， 并做产生式的替换， 消除左递归， 尽量使产生式由大写字母开头的符号、 终结符和有穷语言运算 （并、 乘、 KIeene 闭包） 组成， 同时进行化简。最后， 构造下推自动机， 自顶向下对 XML 文档进行语法分析和处理。与语法分析有关的 XML 语法产生式有下面几条：（数字对应 XML 规范中语法产生式的序号）l document = proIog eIement Misc22 proIog = XMLDecI？Tisc （doctypedecI Misc）
13、？27 Misc = CommentIpIIS39 eIement = EmptyEIem TagISTagcontentETag43 content = CharData？ （ （eIementIreferenceICDSectIpIIComment） CharData？ ）图 2 XML 语言自动机的状态转移图其中， 产生式 27 是一个正则表达式， 所以可以构造有穷状态自动机来识别它们； 考虑到 OnceStAXparser 是非验证型XML 处理器， 可以简化对某些产生式 （例如产生式 45 eIe-mentdecI） 的解析， 于是可以将产生式 22 变换为正则表达式，从而也可以用有
14、穷状态自动机来识别； 对于产生式 39、 43， 根据泵引理 （pumping Iemma）3， 它们是上下文无关文法， 所以可以构造一个下推自动机来识别它们。为了区分 proIog 中的Misc， 将这里的 Misc 改称 EndDocument。图2 给出了语法分析得出的完整的 XML 语言自动机的状态转移图。为了简洁起见， 图上没有标明异常情况。!.!“ XMLstreamreader 状态机设计StAX 规范将 XML 语言中的每个标记和一种事件类型相对应4。用户每调用一次 XMLStreamreader 提供的 next 方法， XMLStreamreader 就向前解析一个事件，
15、并返回事件类型。用户在下一次调用 next 方法之前， 可以通过调用 XML-Streamreader 的 getXXX 方法得到当前事件的属性。按照上一小节得出的状态转移图， 我们设计了符合 StAX 规范的解析XML 语言的状态机 （受用户调用 next 方法的驱动） ， 如图 3 所示。图 3 描述符合 StAX 规范的 XML 解析过程的状态图!.$“ 良构性约束的实现在语法分析器的设计过程中， 除了要求满足语法定义以外， 还要实现 XML 规范中定义的良构性约束。例如， WFC 要求 XML 文档必须符合产生式 document 的定义。语法解析自动机的设计可以保证这一点。WFC （
16、EIement Type Match） 要求： ETag 中的元素名应该与 STag 中的元素名对应。那么，OnceStAXparser 在创建解析器对象的同时创建一个栈， 用于在解析 STag 的时候记录元素名字； 在解析 ETag 时， 通过核对栈顶元素的元素名完成该项 WFC 的检查。WFC （Unigue AttSpec） 要求： 一个属性名不应该在同一个元素或空元素中多次出现。那么， OnceStAXparser 在处理完 STag 中的所有属性后， 对于属性列表统一进行该项约束的检查， 判断是否有重名的属性。为了增加对于名字空间的支持， 我们创建了 Namespace-ContextImpI 类对 XML 文档中出现的名字空间声明进行管理。Namespacel. 0 规范也列出了一些良构性约束， 我们在 XML-Streamreader 的名字空间版本的设计中增加了对这些约束的验证。关于名字空间主要的约束内容与解决方法如下：WFC （NCName 产生式） ： XML 规范中的 Name 产生式更换为 NCN
