使用 XML: 编译路径和自动化测试

文档选项 未显示需要 JavaScript 的文档选项

级别： 初级

Benoit Marchal (bmarchal@pineapplesoft.com), 顾问, Pineapple Software

2002 年 1 月 01 日

接着上一篇文章继续研究 HC，SAX ContentHandler 编译器。本月，我们的专栏作家要讨论编译算法。他还花了一点时间来用 JUnit 进行自动测试。

在“使用 XML”这个专栏中，作者每月都会针对 XML 开发者讨论他的开放源码项目的进展，其范围包括从设计决策到编码挑战在内的多方面内容。这个名为 HC（处理程序编译器 ― Handler Compiler 的缩写）的新项目通过自动为 XPath 列表生成 SAX ContentHandler 来承担基于事件的 XML 解析中的一些繁重任务。

接着上一篇文章继续研究 HC，处理程序编译器。本专栏上个月所介绍的 HC 旨在消除 SAX ContentHandler 中跟踪状态的需要。跟踪状态是一件既繁琐又易出错的工作。通过编译代理 ContentHandler （由其来负责状态管理，并且在符合应用程序逻辑的地方调用应用处理程序），HC 使跟踪状态这个过程自动化。

虽然乍一看，HC 需要程序员做更多的工作，但应该要理解，从应用处理程序角度讲，编译代理是自动进行的。这里不需要编程。

编译代理

如上个月所讨论的，我计划用确定性有限自动机（Deterministic Finite Automaton，DFA）来编译该代理。由于 DFA 非常有效，所以很令人感兴趣。并且，构造 DFA 的算法也是一些成文的算法。虽然我将使用的这个算法最初被设计成编译正则表达式，但我确信，这个算法能够方便地应用到 XPath。

我将详细描述 Compilers: Principles, Techniques and Tools（请参阅 参考资料）一书中的这个算法，在编译器构造方面，这本书是一本具有权威性的参考书。如果您手边有这本书，那么这个 DFA 构造使用的是这本书中所讲的算法 3.5。

算法基本知识

回忆上个月我们所讨论的，DFA 是一个转换图。 图 1 显示了 simpara/ulink XPath 的转化图。圆圈表示代理将经过的状态；用一些促使 DFA 转换的元素来标注箭头。粗边框的圆圈标志成功地识别了 XPath。

为了更好地理解该算法，可以将该转换图与堆栈相比较。当代理遇到 simpara 元素时，必定会将该元素压入堆栈中。接着，当代理遇到 ulink ，它也会将 ulink 压入该堆栈。现在，该堆栈有两个元素： simpara 和 ulink ，这是对 simpara/ulink 的配置。

在该图中的各种状态中，每一种表示了该堆栈的一种配置。状态 0 表示空堆栈，状态 1 表示只有一个元素： simpara 的堆栈。状态 2 是具有两个元素： simpara 和 ulink 的堆栈。

换句话说，要构建 DFA，需要分配的状态数量与可能的堆栈配置数量相同，并且需要计算所有这些状态间的转换函数。

可以想象，图 1 过于简单。实际的代理将并行地处理几个转换图，因为它将试图识别几个 XPath，而不是一个。例如，一个代理可能查找以下三个 XPath 中的任何一个：

simpara/ulink
/
/article/articleinfo/title

当 DFA 试图识别更多的 XPath 时，状态的数量也会随之增长。事实上，按照堆栈来考虑，识别那三个 XPath 比识别 simpara/ulink 需要更多堆栈配置。

QName

XML 元素是由名称空间 URI 和本地名称的组合来标识的。为了更有效地操作 URI 和本地名称，我创建了 QName 类。为了完整地标识 XML 节点， QName 还记录了该节点的性质：元素、属性或根（ / ）。 QName 的代码在 清单 1中。

为了与散列表兼容， QName 实现了 equals() 和 hashCode() 。

HCNode

该算法处理这组 XPath，并编译三样东西：转换图可能经过的一组状态，从一种状态迁移到另一种状态的转换函数，以及表明哪些状态成功地识别了 XPath 的标记。

该算法期望前端（请重新阅读 上一篇专栏文章以了解更多有关前端和后端的信息）返回一个包含所有要识别的 XPath 的解析树。 清单 2 是 HCNode ，出现在该树中的元素。然而，请注意，在 HC 开发中的这个阶段，该清单是不完整的；在下一篇专栏文章中，我将给出更完整的版本。

HCNode 在 org.ananas.hc.compiler 包中，因为它是具体针对该编译器的。 QName 在 org.ananas.hc 中，因为我希望该代理使用它。

节点可以属于以下几种情形之一（这取决于它的 type 属性）：

• 由 QName 表示的 XML 节点
• XPath 中的 / 分隔符，它表明 XML 节点之间的“……的父节点（parent of）”关系
• 当代理识别两个或多个 XPath 时，XPath 的组合
• 标志解析树结束的特殊节点

XML 节点拥有对 QName 的引用。其它类型的节点拥有左 HCNode 和右 HCNode 的引用，以便于构造树。

如前一篇专栏文章中所解释的，DFA 构造算法将该解析树转换成一组状态。为实现该目的，该算法计算在一个给定节点会出现多少个 XML 节点。如果您记得每种状态表示一个堆栈配置，则理解算法的这一部分是较容易的。该算法必须计算所有可能的、可通向解析树中给定节点的堆栈配置。

为了完成这个算法， HCNode 提供了以下方法：

• n.firstpos() ：与根在节点 n 上的 XPath 的第一个元素匹配的 XML 节点集
• n.lastpost() ：与根在节点 n 上的 XPath 的最后一个元素匹配的 XML 节点集
• n.nullable() ：如果节点 n 是 XPath（其可以为空）的根，则为真。否则，为假

让我们举几个示例。从 XPath simpara 开始。将该 XPath 解析成单节点，类型 XML_NODE 的 n 。它的 n.firstpos() 和 n.lastpos() 将是 simpara ，因为 simpara 是唯一与 XPath simpara 匹配的 XML 节点。

在类型 PARENT_OF （带有各自指向 simpara 和 ulink 的左右节点）的节点 n 中解析 XPath simpara/ulink 。 n.firstpos() 方法是 simpara ，而 n.lastpost() 是 ulink ，因为与 XPath 的开头相匹配的 XML 节点是 simpara ，与 XPath 尾部相匹配的是 ulink 。

表 1 清楚地说明了计算 firstpos() 和 nullable() 的规则。 lastpos() 类似于 firstpos() ，但 left 和 right 的规则相反。顺便说一句，您可能想知道 nullable 究竟是什么；在我于以后的专栏文章中讨论相对 XPath 的处理之后，您就会逐渐明白了。

表 1. 计算 firstpos() 和 nullable()

如果您感到困惑，那只要记住状态表示堆栈配置。 firstpos() 和 lastpos() 是给定堆栈配置中 XML 节点集。最后，我将给这些集合中的每一个分配唯一的号码以将其转成一种状态。

计算 DFA

给定解析树，可以应用 清单 3 中的算法来计算转换函数。可以将转换函数表示为两维矩阵 dtran ，它会返回给定 XML 节点的下一个状态。请注意，清单 3 中的算法是伪代码，不是实际的 Java 代码。

dstates <- root.firstpos()
for-each s as a state in dstates
   for-each a as an XML node in the input vocabulary
       U <- s.followpos(a)
        if U is not empty and is not in dstates
           dstates.append(U)
       dtran[s,a] <- U

followpos(a) 告诉在 XPath 中给定 XML 节点后有哪些 XML 节点。可以应用以下规则来计算它：

• 如果 n 是 PARENT_OF 节点，且 a 是 left.lastpos() 中的 XML 节点，那么 right.firstpos() 中的所有节点在 followpos(a) 中
• 如果 n 表示相对路径，且 a 在 n.lastpos() 中，那么 n.firstpos() 中的所有节点在 followpos(a) 中

回页首

JUnit

我希望在这篇专栏文章中完整地实现该算法，但我必须花一些时间来了解 JUnit。JUnit 是用于自动化测试的开放源码框架（请参阅 参考资料）。我已经发现在编写编译器时绝对需要自动化测试，但这种自动化测试的过程是艰难的。

自动化测试

在任何软件项目中存在的一个普遍事实是，程序员在他们的软件中引入了错误。我看到过一篇统计，指出一般的程序员在每 10 行代码中会出现一个错误。因此设计测试来查找和修正这些错误。测试通常是一件重复性很高且令人厌烦的工作。测试软件时几乎没有什么创造性：给予某个确定的值，然后观察结果。如果结果与所期望的不一样，则您已经找到了一个错误。

由于测试是如此枯燥且重复性之高，以至于应该自动化这些测试（或至少某些测试应该这样）。毕竟，计算机要比程序员有耐心。所以，对于这些枯燥而重复的工作，计算机是理想的候选人。

自动化测试意味着编写一个软件来测试其它软件。这种方法的美妙之处在于：每当需要时，就可以运行测试软件。我们时常仅测试应用程序中发生更改的部分。当然，问题是要确定更改了什么。对某部分代码的更改会造成其它部分的代码出现错误，这种情况一般很常见。除非您记得这两部分是有联系的，否则不可能会因这个条件来测试。

另一方面，自动化测试采取一种蛮力的方法。在每次运行测试软件时，其可能会测试整个应用程序，这使得找到代码不相关部分中的错误的几率会增加。

自动化测试的另一个好处是，应用程序中的错误一般会重复出现。每当修正完一个错误，最好写一个测试程序来检查代码中是否还有这样的错误。在整个项目生存期中，当这个错误重新出现时，这个测试有可能会失败几次。

极端编程（extreme programing）活动（请参阅 参考资料）已经推动自动化测试的普及。我承认我没有系统地使用自动化测试，这是因为我的经验表明，对于那些其公共接口不经常更改的类，自动化测试是最有效的。而对那些其公共接口更改很多以及包含大多数用户接口代码的类来说，这些测试就不怎么有效了。

自动化测试中最重要的词是 自动化，除非您希望经常使用它，否则自动化任何事情都是无用的。出于同样的原因，编写那些您知道将要经常运行的测试程序会更有效些。对于相当晦涩的代码（如，对树的操作，尤其是编译器），自动化测试也是较理想的。

JUnit

不要愚蠢地认为自动化测试是不耗费劳动及不费力的。在编写测试案例方面，必须花费一些时间，当然，您需要经常运行这个测试应用程序。事实上，如果不是在自动化测试方面花了大量的时间，我可能认为在这个月本可以编写完一个还有一些错误且没有经过良好测试的 DFA 编译器的版本。公平地讲，我在自动化测试方面花费了比我预计要多很多的时间，这是因为我选择了要了解 JUnit。

对于项目的整个生存期，自动化测试仍然是一项有收益的投资。运行一个测试要比试图自动化测试快得多。例如，在对给定类编写测试案例所耗费的工作量可能比手工地对该类进行一次测试所耗费的工作量多五倍以上。当然，如果您运行这个测试的次数超过六次，则编写这个测试案例是有收益的。比方说，如果运行该测试 50 次（即使对于一个中等规模的项目，这个次数也不算多），则收益是巨大的。

实际上讲，可以采用两种策略中某一种来编写自动化测试程序。一种策略是，在编写正在测试的代码时，编写测试程序；另一种策略是，让另一个开发者小组来编写测试程序。我暂时将采用第一种策略，但是如果您自愿编写测试套件，那么请一定张贴在 ananas 讨论邮件列表中。

过去，我以纯 Java 类的形式编写自己的测试程序。然而，一位朋友建议我测试一下 JUnit。HC 似乎是用来测试 JUnit 的一个很好的项目，所以我下载了 JUnit。JUnit 是一个用于编写自动化测试程序的简单且小型的框架。JUnit 没有很多功能（它只是一些类），但它确实对形式化测试过程有帮助。

清单 4 是我编写用来练习 QName 的测试过程。如您所见，这个测试类继承了 TestCase （JUnit 定义的类）。我在 testXXX() 方法中编写我的测试过程。我有三个方法来执行软件的各个方面：测试构造器、测试读方法（getters）以及测试 equals() 和 hashCode() 方法。由 JUnit 声明的 setUp() 方法初始化这个测试对象。

我选择将测试程序放在一个单独的包（ org.ananas.hc.test ）中，这不同于 JUnit 作者所建议的。我也许会后悔那种选择，但我喜欢将测试程序与实际代码分开，因为这很容易从分发版中除去该测试程序。

使用 JUnit 的美妙之处在于，该框架负责装入测试类、运行测试以及报告结果。该框架还支持测试套件的概念，这使我能以逻辑单元来组织测试。最后，该框架提供了图形化的界面和控制台管理者。图形化的控制台很适合于交互式测试一个或两个类，而该控制台以批处理方式运行所有的测试，例如，完全重构过程，这一部分。

回页首

下一步

我还没有将 HC 的代码张贴在 ananas.org 资源库，因为还没到恰当的时候。在值得张贴一些新东西之前，我需要最终处理 DFA 编译。然而，我确信花在构建自动化测试（以及了解 JUnit）上的时间是值得的；在这个项目的生存期里，将会有收益的。到下个月，我期望有一个该编译器可以运行的版本（但不是经过优化的），并且期望能继续研究这个代理。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文.
  
  
• 请参加关于本文的 论坛。
  
  
• 所谓的“ 龙书”（ Compilers: Principles, Techniques and Tools，由 A. Aho, R. Sethi 和 J. Ullman 合著）是一本有关编译器设计和构造方面具有权威性的文档。
  
  
• JUnit是用于运行自动化测试的开放源码框架。
  
  
• 极端编程（extreme programming，XP）是关于实现更高质量的软件的一组建议。
  
  
• 实用程序员（Pragmatic Programmers）是最近在方法论领域出现了另一位竞争者。
  

关于作者

		Beno顃 Marchal 是住在比利时那慕尔的顾问和作家。他是 XML by Example 、 Applied XML Solutions 和 XML and the Enterprise 的作者。同时是 Gamelan 的专栏作家。 marchal.com上有其最新项目的详细信息。可以通过 bmarchal@pineapplesoft.com 与 Beno顃 联系。 作者在此向 Fr閐閞ic George 表示特别感谢，因为是他向作者介绍了 SAXTransformerFactory 。

对本文的评价

太差！ (1) 需提高 (2) 一般；尚可 (3) 好文章 (4) 真棒！(5) 建议？

回页首