编译器测试技术研究

《编译器测试技术研究》由会员分享，可在线阅读，更多相关《编译器测试技术研究（5页珍藏版）》请在金锄头文库上搜索。

1、编译器测试技术研究 摘要 编译器是用来为高级语言编写的程序创建可执行模块的；因此编译器中出现错误是对用这 种编译器开发的程序的品质的严重威胁。像其它软件一样，测试是对编译器进行质量控制 和错误检测的最重要的方法之一。这项研究致力于编译器测试组件的生成，运行和质量检 查，这些是基于对编程语言语法和语义的正式的详细的描述。 1.引言 高级语言已经成为软件开发的一项基本工具。这解释了为什么支持这个开发过程的软件 （即编译器）被广泛使用。 编译器把程序从高级语言转化为可被机器执行的表示。如果编译器中有错误，原始程序转 化成的可执行模块的行为与原始程序的语义定义的行为将不一致。这种错误难以检测和纠 正，

2、而且错误的出现是对编译器生成的组件的质量的质疑。毫无疑问，编译器的正确性对 使用这种编译器开发的软件的可信操作是至关重要的，并且编译器的正确性检查对提高软 件可靠性至关重要。 像其它软件一样，测试是对编译器进行质量控制和错误检查的最重要的方法之一。传统来 讲，测试方法分为两组：白盒测试和黑盒测试。白盒测试中，测试样例的创建是基于测试 部分源代码具体实现的信息。而黑盒测试中，测试样例的生成仅基于功能性描述，功能性 描述也称为具体计划。 两种计划各有利弊。白盒测试的优点是它可以对将要执行的源程序文本的有效性进行全面 的检验。这样的检测是我们可以检测出实现中的很多错误，但无法保证需要的功能在系统 中

3、执行。为此，黑盒测试被使用，旨在检查程序实现是否与被检测系统的要求一致。 黑盒测试方法的一个缺点是它们需要额外开发产品详细说明。对编译器而言，这种缺点不 是很重要，因为，对于每种语言都存在非正式的语法和语义描述（语言标准）和一种正式 的句法描述（语法） 。在一些特定情况下，一种正式的，完整的或者部分的，语义描述也存 在。这使得黑盒测试方法对测试编译器很有吸引力。这项研究就是在讨论这些方法。 2.编译原理的基本概念 编译，用最通俗的话讲，就是一个将用输入语言编写的源程序转换成输出语言的程序的过 程。传统上，输入语言通过正规的文法描述。 一个文法是一个四元组，其中N是非终结符的有限集合；T是一个终

4、结符的集合， 且T与N不相交；S是N中的一个初始符号；P是集合NT)*N(NT)*(NT)*的一个有限子集。 集合P中的二元组被称为文法规则。一个规则（n,m）通常被写成n-m. W为一个符号串，如果有u=abc, w=adc, and b-dP,那么就称w可以从u推导得到。这种直接 的推演关系被这样表示upw,其中p=b-d. 推演关系被定义为直接推演关系的可传递，可反身的闭包，并被表示为=*.表达式u=*w读 作“w可从u推导得到” 。 可从文法G的起始符号推导得到并且只含终结符的符号串的集合称为语法G产生的语言，表 示为L()这些符号串叫做语言的短语。 文法，被称作与上下文无关如果有一条

5、规则，满足，其中 ，（） 正规的文法是规定语言句法的方便的手段。上下文无关的文法机制不足以定义编程语言的 语义。 现在公认把编程语言得语义分为静态和动态语义。静态语义解决程序中类型的正确使用， 标识符的作用范围，和程序的其它不运行就能确定的属性。 描述静态语义的最常用的方法是状态文法。在状态文法中，文法的每个符号被设定为与一个有限的状态集对应，且每个文法规则对应一个规则，以便评估对应于规则的符号的属性。 用这些规则，我们可以评估分析树中每个节点的属性。 每条规则可以被赋予一个上下文条件，这个条件是规则属性确定的一个断言。一个程序被 认为是静态正确的，如果分析所有属性后发现，分析树上所有节点的上

6、下文条件都得到满 足；即，对应的断言取真值。 属性可以被继承，即通过树中的父亲节点的属性估计，或者被综合，即成为子节点属性的 函数。这些属性被设定为与程序的各种静态性质对应，被用于分析数据和表达式的类型， 内存的类，和常量表达式的值。 一种程序语言的动态语义定义了用这种语言编写的程序运行时的意义。不像语法和静态语 义，目前动态语义不存在一个统一的正式的被广泛接受的描述。 传统来讲，编译过程被划分成以下几个阶段1： 1.词法和语法分析。在这个阶段，源程序文本被分析，分析树被创建。 2.静态语义分析。在这个阶段，分析数被分析，树中所有节点的属性被计算出来，程序 的静态正确性被证实。 3.优化转换。

7、在这个阶段，按照选择的标准（代码长度，操作率）对程序的内部表示进 行各种转换以提高程序的质量。 4.代码生成。代码生成就是通过给定的内部的程序表示创建一个可执行文件。 通常，对大部分编译器进行功能性分解会和以上方案对应，尽管每个特定的实现有自己的 特点。例如，有些编译阶段被分解成几个更好的子阶段。一些阶段可以在系统的一个组件 实施，而不是几个组件。 让我们更细致地考虑编译其输入数据的结构（如图所示） ，讨论如何用这个结构的子集来测 试编译的不同阶段。 一种语言的语法是通过包含终结符,非终结符和产生式的文法来制订的。从文法的开始符可 导出的终结符串被称为语法正确的程序。语法正确的程序的集合是所有

8、终结符号串集合的 子集。它们用于检测语法分析阶段是否能识别一个正确的测试样例。这些程序通常被称为 正面测试样例。那些不能从起始符推出的符号串，即反面测试样例，用于检测编译器识别 一个语法错误的能力。 静态语义仅为语法正确的程序设计；它为程序那些不需要运行就能确定的性质定义规则。 这些性质包括，如变量和表达式的类型。除了运算规则，还制订了检查静态程序正确性， 或者说检查上下文条件的规则，这些规则限定了静态程序性质取值的可能组合。 从测试的角度，满足上下文条件的程序(正面测试样例)和不满足的程序(反面测试样例)都有 意义。那些满足上下文条件的程序叫做静态正确的程序。静态正确的程序组成一个语法正 确

9、的程序集合的子集。他们用于测试编译器的静态分析阶段能否正确识别良好的程序。语 法正确但违背上下文条件的程序用于检测编译器识别静态语法错误的能力。 一种程序设计语言的动态语义定义了用这种语言编写的静态语义正确的程序的运行时意义。 为了检测它在编译器中的实现，静态语义正确的程序被使用，由待测的编译器编译；获得 的可加载模块被执行，它们的可观测的行为与动态语义决定的参考行为进行对比。显然， 如果程序的可观测行为是模糊的，那这样一种对比将是一项复杂的任务。因此，为了检测 编译器中动态语义的实现，静态语义正确且有不模糊可观测的行为的程序被使用。这样的 程序组成一个静态语义正确的程序集合的子集。 根据哪一

10、阶段需要检测，研究的目标是图中所示结构的一个或者说另一个子集。进一步深 入进行这项研究，对每个以上列举的子集，我们考虑各种不同的方法解决下列测试问题： (1) 测试样例生成(写)； (2) 当测试进行完后返回一个判断(测试预言)；(3) 测试套件的质量评估(覆盖原则)。 3.语法分析测试 程序设计语言的语法或许是程序设计语言唯一被公认需要正式定义的部分。文法，由于他 们的特质，是一个产生程序文本的理想工具:他们将语言定义为可以从起始符通过连续运用 规则而生成的短语的集合。因此，一个产生用一种程序设计语言编写的程序的算法可以通 过运用和组合(用一种随机或有规律的方式)各种文法规则容易地被构造出来

11、。从文法的广 泛应用-作为描述语言的方法的角度，以及它们的“生成”本质，基本上使用文法为编译 器生成测试程序。 这个领域的基本工作是这篇论文2。后来，它被许多其它研究者用作一个出发点，他们要 么修改这篇文章中推荐的Purdom的算法要么将它与他们自己的算法结合。 Purdom算法的输入数据是一个起始符只在规则的左边出现一次的上下文无关文法。这种约 束并没有限制考虑的语言的种类，因为任何上下文无关的文法都可以缩减为这种形式。这 个算法构造了一个文法中每一个文法规则至少使用一次推导出的短语集。在这样做过程中， 问题被转移到最小化这个集合。 这个算法以下列方式工作。首先，对于每一个非终结符，得到一串

12、终结符形成的推导树的 最小长度被构造出来。这个信息在算法的第二部分被使用。 算法的第二部分用一个栈来存储产生的短语。开始，这个栈包含文法的开始符。然后，开 始进行一下循环:如果栈顶符号是终结符则打印出来，如果栈顶符号是非终结符，则用左边 含有此符号的规则的右边替换该符号。在替换中将要使用的规则从那些没有使用的规则中 挑选 (如果不可能，则再从剩下的规则中挑选)按照最小推导长度的准则。这些步骤不断重复直 到栈空为止。产生的短语被添加进测试组件内，起始符被放入栈内，然后重复第二部分的 生成算法。当每个文法规则都至少被使用一次后循环中止。 Purdom算法实际上为文法产生紧凑的测试套件。论文3中提供

13、了用这种算法编写的应用程 序为C和C+文法生成的测试文本。对于包含211条规则的C文法，生成了11条短语；对于包 含824条规则的C+文法，测试套件包含81个短语。 这个算法可以产生满足规则覆盖准则的短语，这项准则要求减少测试套件中短语的数量时 每条规则至少使用一次。每个测试套件都需要满足这个条件。后来，Lmmel在论文4中说 明了基于规则覆盖准则的测试套件不能揭示文法规则中的简单错误并推荐了一个更强大的 上下文独立规则覆盖准则。 要介绍这个准则，我们需要以下定义: 定义一: 设G= N, T, s, P是一个上下文无关文法。一个非终结符n在文法中的直接出现是指 任意一个右部包含n的规则。 覆

14、盖标准自身定义如下。 定义2 设G=是一个上下文无关文法。短语w T*对于符号的直接出现 覆盖规则，如果存在这样的推导：s * xmy q xunvy p xuzvy * w短语集对于文法满足上下文独立规则覆盖标准，如果对 于任何一个规则和任意一个符号的直接出现，都包含一个短语对于出 现覆盖规则。 Lmmel指出上下文独立规则覆盖标准比规则覆盖标准能创建揭示更多类错误的测试套 件。 论文推荐了另一个考虑到了文法规则使用的上下文的覆盖准则。该文法表示法利用 了变量，借助括号将选择符分组。每个子短语和所有非终结符被称作分支点。 每个分支点与属于它可推导出的短语的终结符组成的集合相关联。这个集合被称

15、为分支点的前向集。由二元组（，） ，其中是分支点，是的前向集中的一个终结符，组成 的集合被称为该文法的情况集。该覆盖标准按如下方式制订。 定义短语对于给定文法覆盖情况（，）如果存在推导s *m r m * w使得且规则的右侧包含分支点。短语集满足情况覆盖标准，如果对于给定文法 情况集中的每个情况中都有一个短语覆盖它。 这个覆盖标准是面向分析器的，对于分析器来讲对分支点的分析是语法分析算法 的一个重要部件。 其它针对基于文法的测试生成的工作没有引入任何关于测试质量分析的覆盖 标准。如果不使用一种覆盖准则，那么测试生成何时完成就不明确。由于几乎所有实际程 序语言的文法都是递归的，所以必须要有一个防

16、止无限递归的机制。基于此目的，对规则 使用数量的限制或概率方法被引入。 Guilmette一个上下文无关的短语生成算法，该算法基于从启始符开始的短语展 开。首先，最左边的非终结符被展开。这个符号被完全展开后，它被获得的一串符号 替代，然后算法又被用在下一个最左边非终结符上。沿着正在展开的分支，每次使用 一条规则，该规则在下一次展开中被选择的概率就会减小。由于使用规则将一个非终 结符展开成一系列非终结符会终止生成过程，这个方法会逐渐减少其它规则在展开过 程中的应用并保证这一个过程在有限时间内中止。 另一个基于stochastic文法的方法在7, 8, 12的工作被使用。Stochastic文法和普通文法的 不同在于前者的每个规则都是以一个数，规则的权重来标记的，这个数决定了在生成 过程中选择这条规则的相对频率。一个