一种XML解析器技术的研究与实现

摘 要： 介绍了XML解析的详细过程，设计并实现了一个特定Schema的XML解析器的自动生成工具。该生成工具以一个XML Schema文件作为输入，输出一个JavaCC词法和语法规格说明文件，然后在JavaCC工具的帮助下，生成一个基于特定XML Schema的XML解析器。实验证明，这个生成解析器能够对XML文档进行解析的同时，验证其有效性。
关键词： XML解析器；基于特定模式；验证；解析器生成器；JavaCC

　XML[1](Extensible Markup Language)是一种可扩展标记语言，可以用来定义其他的标记语言。自从XML成为W3C推荐标准以来，XML以其简单、可扩展性、自描述性、平台中立的特点，正迅速成为Web上信息表示与数据交换的标准[2]。目前众多国际著名公司都宣称其产品中支持XML，促使XML成为下一代Web的发展方向。越来越多的网站和Web的应用使用XML技术进行信息发布和数据交换，XML已成为一种备受瞩目的技术，甚至被誉为互联网上的世界语。XML现已被广泛应用在各种领域，如电子商务、企业协作、Web服务等。XML解析器是XML应用的基础，XML本身只是以纯文本对数据进行编码的一种格式，要想利用XML，或是利用XML文件中所编码的数据，必须先将数据从纯文本中解析出来。因此，要求必须有一个能够识别XML文档信息的文本文件阅读器(即XML解析器)，用来解析XML文档并提取其中的内容。为了提高数据的正确性和提高系统的可靠性，XML解析器还要检查XML实例文档是否符合模式的定义和约束，这个过程称为XML文档的有效性验证[3]。但带有验证功能的解析器通常效率比较低[4]。近年来，有很多旨在提高XML的解析和基于Schema 验证性能的研究，本文在详细分析了XML解析器的解析过程的基础上，设计并实现了一个特定Schema解析器的生成工具。生成器根据特定的Schema，自动产生一个递归下降的XML解析器。这个生成解析器能够对XML文档同时进行解析和有效性验证。
1 XML与Schema简介
　可扩展标记语言XML是由World Wide Web Consortium(W3C)于1998年2月发布的一种基于文本的数据描述语言的通行标准，与HTML类似，XML是一种标记语言，两者在语法上有密切的联系。不同的是，HTML着重于如何显示数据，而XML的设计宗旨是存储和传输数据，着重于如何描述数据。XML来源于标准通用标记语言SGML(Standard Generalized Markup Language)，是SGML的一个精简子集[5]。XML有如下的特点：
　(1)可扩展性：XML是一种元标记语言，即XML可用来设计和定义标记语言，XML强大的功能体现在它可以用来制定自己的标记语言。不同的具体应用领域可以制定专用的标记语言，作为该领域共享数据和交换信息的基础。
　(2)内容与表现分离：XML使得用户界面和结构数据之间保持独立。XML描述数据的内容(即数据是什么)，而数据呈现方式则通过样式单来表示。内容与表现分离，使相同的数据可以不同的格式在不同的媒体上表现。
　(3)结构化：XML以结构化的方式描述数据。这个特点使得XML能够描述复杂的数据结构，同时也为关系数据和层次数据提供一种方便的描述方式。
　(4)可验证：XML文档的结构和内容由XML模式语言(如DTD，XML Schema等)定义。利用XML文档所对应的DTD或Schema，可以对XML文档有效性进行验证，提高了数据的可靠性和可用性。
　XML模式(Schema)指的是一类XML文档的结构或是模型，这个模型描述了一个有效XML文档内的元素层次结构和允许的内容。模式定义了一个XML词汇表，包括元素名称、属性名称等。模式规定了一个XML文档允许出现的元素、相应的元素允许出现的属性以及这些元素的层次结构关系。XML的模式语言有很多，其中包括文档类型定义DTD(Document Type Definition)、XML Schema、XML规则语言描述RELAX(REgular LAnguage description for XML)、XML树形规则表示TREX(Tree Regular Expressions for XML)和下一代RELAX NG(RELAX Next Generation)[6]。
　XML Schema是一种使用XML语法的XML模式语言。DTD曾是描述、约束XML文档最广泛的方法，但在应用的过程中，DTD体现出一些局限性。主要表现在语法与XML语法不一致，只支持有限的数据类型而不支持命名空间等方面。作为DTD的后继者，XML Schema克服了这些缺陷。XML Schema区别于DTD的主要特性表现在[7]：
　(1)XML Schema本身就是XML文档，使得XML Schema的处理可以与XML一样，一些用来处理XML的技术也可以用来处理XML Schema。
　(2)定义了丰富的数据类型，如布尔型、整型、日期时
间、URI、十进制数等简单数据类型。
　(3)支持用户自定义数据类型。XML Schema支持从现有的数据类型派生出新的数据类型，类似于面向对象中的继承。
　(4)充分支持命名空间。
　因此，XML Schema成为W3C的正式推荐标准，并正逐步取代XML DTD。
2 Schema解析器生成工具的设计与实现
　基于特定Schema的XML解析器的基本思想是根据某一特定的Schema，构造一个专用的解析器，这个解析器能够对输入的XML文档进行良构检查，同时验证其有效性。基于特定Schema解析器将XML的解析和验证结合在一起，在一定程度上提高了基于XML应用的效率和性能。但这个解析器只适用于由这个Schema定义的XML实例文档，对于由其他Schema定义的XML实例文档则无能为力。当Schema改变时或者需要另外一个Schema定义时，必须重新构造一个解析器。而本文设计并实现了利用JavaCC工具自动生成一个特定Schema解析器的方法。该方法以一个Schema文件为输入，生成一个基于这个Schema的解析器。
自动生成特定解析器的基本流程如图1所示。由于Schema文档本身也是一种XML文档，所以完全可以使用通用的XML解析器对其解析，也可以构造一个专用于解析Schema的解析器，但由于Schema的语法比较复杂，构造起来比较困难。一种较容易实现的方法是先将Schema转化为XML树模型的表示，再转换为Schema的抽象模型表示。基于特定Schema的XML解析器生成工具的基本步骤如下：
　(1)首先利用JavaCC构造一个通用的XML解析器(GeneralParser)。
　(2)通用XML解析器将Schema输入文件解析成一个XML语法的元素节点树。
　(3)遍历这一XML语法的树模型，将其转换为Schema语法的抽象模型。
　(4)根据Schema抽象模型，生成特定解析器的词法和语法规格说明。
　(5)利用JavaCC，生成基于输入Schema的专用XML解析器。
2.1 构造XML解析器
　构造XML解析器的目的在于解析Schema文档，提取其描述和约束XML文档结构和内容的信息。XML Schema遵循XML语法，因此可以使用任何通用的XML解析器对其解析。下面介绍一个用于解析XML Schema文档的XML解析器的构造。
　由于XML文档是可以包含DTD声明和DTD子集的，所以处理XML文档时也应该包含DTD的语法的处理。但是XML Schema也是一种XML文档，一般不会包含DTD声明和定义。另外，由XML Schema定义的XML实例文档通常也不会再用DTD定义，所以也不会包含DTD的声明或DTD子集。因此，在处理XML Schema文档时不考虑DTD语法的处理；在生成这个Schema定义的XML实例文档的解析器时，也不考虑DTD语法的处理。这样有助于简化设计和实现。
2.1.1 构造词法分析器
　JavaCC能根据输入的词法规格说明，产生一个基于DFA的词法分析器。因此需要提供一个合适的词法规格说明。
　JavaCC的词法规格说明使用正则表达式定义词法结构，每一个词法记号(Token)名称对应着一个正则表达式，例如：<S：(""|"t"|"n"|"r")+>表示空白空间的词法构成，其中S是助记符，而(""|"t"|"n"|"r")+是相应的正则表达式，表示由一个或多个分隔字符组成的字符串，分隔字符包括空格、制表符′t′、换行符′n′和′r′。
XML规范中表示词法结构的表达式，很多可以比较容易地转换为JavaCC词法规格说明的正则表达式形式。但有一些需要特殊的处理才能转换为JavaCC可以识别的表示形式。
　JavaCC的词法规格说明由一些词法状态和定义在各个词法状态内的正则表达式组成。生成的词法分析器在分析词法的任何时候都只能处于一个词法状态中。这种机制能够有效地解决多个正则表达式发生冲突的问题。例如，识别标记间的字符数据的正则表达式可以表示为：<CHAR_DATA：(~["<"，"&"，"]"]|"]"~["<"，"&"，"]"]|"]"("]")+~["<"，"&"，">"])+("]")*>，这与其他很多记号的正则表达式相冲突，包括标记中的元素名 <IDENTIFIER：<NAME>>。这是因为两个正则表达式表示的语言有公共子集，当出现公共子集中的一个串时，词法分析器不知道应该匹配哪一个正则表达式。实际上JavaCC只将其匹配为在词法规格文件中较早出现的那个表达式。利用词法状态可以解决这类问题，使元素名只会出现在标记中，而字符数据只出现在标记外，因而可以定义两种词法状态：在标记中的状态和标记外状态，使它们分别在这两个词法状态中识别。词法状态之间的转移可以通过在匹配一个记号后，指定要转移的下一个词法状态来实现。另一种更灵活的方法是在执行词法动作(定义在匹配表达式后执行的Java代码)时，调用词法分析器的SwitchTo()方法，转移到某一指定的状态中。
2.1.2 构造语法分析器
　JavaCC使用自顶向下递归下降的分析方法，并且在需要选择候选式的地方默认向前看一个符号进行判断，因此JavaCC使用的也是一种LL(1)的分析方法。XML标准中的EBNF不是LL(1)的文法，这样会导致一些选择的冲突，使得语法分析器不能正确地分析语法。虽然JavaCC也支持LL(k)(k>1)的分析方法，即在所有的选择点向前看k个符号，但这样会很大程度地降低解析的效率。解决的方法是对XML标准中的EBNF表示的文法进行改写，使其成为LL(1)文法。将非LL(1)文法改写为LL(1)的过程包括消除左递归和提取左因子。XML标准中的文法几乎不存在左递归，因此只需要提取左因子。
　XML标准中语法的产生式存在公共左因子的典型例子是元素的产生式。元素及其相关的EBNF表达式如表1所示。

　元素产生式的右部是空元素标记或开始标记后跟元素内容和结束标记。其中空元素标记和开始标记有比较长的公共左因子′<′Name(S Attribute)*S？，当语法分析器当前的输入符号为′<′时，无法确定选择EmptyElemTag还是STag content ETag进行推导，这时解析器就会报错，因此首先要将左因子提取出来。改写元素的产生式为：
　element：：=′<′Name(S Attribute)*S？(′/>′|′>′content ETag) (1)
　这样语法分析器遇到′<′时，就不存在选择的问题，当遇到′/>′或′>′时也能确定唯一的子式。但产生式还不是LL(1)的。其原因在于子式(S Attribute)*S？也存在选择的冲突。因为FIRST((S Attribute)*)∩FOLLOW((S Attribute)*)={S}，当语法分析器遇到S符号时，不知道应将其匹配为(S Attribute)*中的S，还是匹配为后面的S？中的S。因此还需要对产生式进行进一步的改写。
　先将子式AttS：：=((S Attribute)*S？)改写为等价的上下文无关文法，然后如图2所示提取左因子。