编译器测试技术研究.docVIP

编译器测试技术研究摘要编译器是用来为高级语言编写的程序创建可执行模块的；因此编译器中出现错误是对用这种编译器开发的程序的品质的严重威胁。像其它软件一样，测试是对编译器进行质量控制和错误检测的最重要的方法之一。这项研究致力于编译器测试组件的生成，运行和质量检查，这些是基于对编程语言语法和语义的正式的详细的描述。1. 引言高级语言已经成为软件开发的一项基本工具。这解释了为什么支持这个开发过程的软件（即编译器）被广泛使用。编译器把程序从高级语言转化为可被机器执行的表示。如果编译器中有错误，原始程序转化成的可执行模块的行为与原始程序的语义定义的行为将不一致。这种错误难以检测和纠正，而且错误的出现是对编译器生成的组件的质量的质疑。毫无疑问，编译器的正确性对使用这种编译器开发的软件的可信操作是至关重要的，并且编译器的正确性检查对提高软件可靠性至关重要。像其它软件一样，测试是对编译器进行质量控制和错误检查的最重要的方法之一。传统来讲，测试方法分为两组：白盒测试和黑盒测试。白盒测试中，测试样例的创建是基于测试部分源代码具体实现的信息。而黑盒测试中，测试样例的生成仅基于功能性描述，功能性描述也称为具体计划。两种计划各有利弊。白盒测试的优点是它可以对将要执行的源程序文本的有效性进行全面的检验。这样的检测是我们可以检测出实现中的很多错误，但无法保证需要的功能在系统中执行。为此，黑盒测试被使用，旨在检查程序实现是否与被检测系统的要求一致。黑盒测试方法的一个缺点是它们需要额外开发产品详细说明。对编译器而言，这种缺点不是很重要，因为，对于每种语言都存在非正式的语法和语义描述（语言标准）和一种正式的句法描述（语法）。在一些特定情况下，一种正式的，完整的或者部分的，语义描述也存在。这使得黑盒测试方法对测试编译器很有吸引力。这项研究就是在讨论这些方法。2. 编译原理的基本概念编译，用最通俗的话讲，就是一个将用输入语言编写的源程序转换成输出语言的程序的过程。传统上，输入语言通过正规的文法描述。一个文法是一个四元组，其中N是非终结符的有限集合；T是一个终结符的集合，且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()这些符号串叫做语言的短语。文法，被称作与上下文无关如果有一条规则，满足，其中，（）正规的文法是规定语言句法的方便的手段。上下文无关的文法机制不足以定义编程语言的语义。现在公认把编程语言得语义分为静态和动态语义。静态语义解决程序中类型的正确使用，标识符的作用范围，和程序的其它不运行就能确定的属性。描述静态语义的最常用的方法是状态文法。在状态文法中，文法的每个符号被设定为与一个有限的状态集对应，且每个文法规则对应一个规则，以便评估对应于规则的符号的属性。用这些规则，我们可以评估分析树中每个节点的属性。每条规则可以被赋予一个上下文条件，这个条件是规则属性确定的一个断言。一个程序被认为是静态正确的，如果分析所有属性后发现，分析树上所有节点的上下文条件都得到满足；即，对应的断言取真值。属性可以被继承，即通过树中的父亲节点的属性估计，或者被综合，即成为子节点属性的函数。这些属性被设定为与程序的各种静态性质对应，被用于分析数据和表达式的类型，内存的类，和常量表达式的值。一种程序语言的动态语义定义了用这种语言编写的程序运行时的意义。不像语法和静态语义，目前动态语义不存在一个统一的正式的被广泛接受的描述。传统来讲，编译过程被划分成以下几个阶段1：1. 词法和语法分析。在这个阶段，源程序文本被分析，分析树被创建。2. 静态语义分析。在这个阶段，分析数被分析，树中所有节点的属性被计算出来，程序的静态正确性被证实。3. 优化转换。在这个阶段，按照选择的标准（代码长度，操作率）对程序的内部表示进行各种转换以提高程序的质量。4. 代码生成。代码生成就是通过给定的内部的程序表示创建一个可执行文件。通常，对大部分编译器进行功能性分解会和以上方案对应，尽管每个特定的实现有自己的特点。例如，有些编译阶段被分解成几个更好的子阶段。一些阶段可以在系统的一个组件实施，而不是几个组件。让我们更细致地考虑编译其输入数据的结构（如图所示），讨论如何用这个结构的子集来测试编译的不同阶段。一种语言的语法是通过包含终结符,非终结符和产生式的文法来制订的。从文法的开始符可导出的终结符串被称为语法正确的程序。语法正确的程序的集合是所有终结符号串集合的子集。它们用于检测语法分析阶段是否能识别一个正确的测试样例。这些程序通常被称为正面测试样例。那些不能从起始符推出的符号串，即反面测试样例，用于检测编译器识别一个语法错误的能力。静态语义仅为语法正确的程序设计；它为程序那些不需要运行就能确定的性质定义规则。这些性质包括，如变量和表达式的类型。除了运算规则，还制订了检查静态程序正确性，或者说检查上下文条件的规则，这些规则限定了静态程序性质取值的可能组合。从测试的角度，满足上下文条件的程序(正面测试样例)和不满足的程序(反面测试样例)都有意义。那些满足上下文条件的程序叫做静态正确的程序。静态正确的程序组成一个语法正确的程序集合的子集。他们用于测试编译器的静态分析阶段能否正确识别良好的程序。语法正确但违背上下文条件的程序用于检测编译器识别静态语法错误的能力。一种程序设计语言的动态语义定义了用这种语言编写的静态语义正确的程序的运行时意义。为了检测它在编译器中的实现，静态语义正确的程序被使用，由待测的编译器编译；获得的可加载模块被执行，它们的可观测的行为与动态语义决定的参考行为进行对比。显然，如果程序的可观测行为是模糊的，那这样一种对比将是一项复杂的任务。因此，为了检测编译器中动态语义的实现，静态语义正确且有不模糊可观测的行为的程序被使用。这样的程序组成一个静态语义正确的程序集合的子集。根据哪一阶段需要检测，研究的目标是图中所示结构的一个或者说另一个子集。进一步深入进行这项研究，对每个以上列举的子集，我们考虑各种不同的方法解决下列测试问题：(1) 测试样例生成(写)；(2) 当测试进行完后返回一个判断(测试预言)；(3) 测试套件的质量评估(覆盖原则)。3. 语法分析测试程序设计语言的语法或许是程序设计语言唯一被公认需要正式定义的部分。文法，由于他们的特质，是一个产生程序文本的理想工具:他们将语言定义为可以从起始符通过连续运用规则而生成的短语的集合。因此，一个产生用一种程序设计语言编写的程序的算法可以通过运用和组合(用一种随机或有规律的方式)各种文法规则容易地被构造出来。从文法的广泛应用-作为描述语言的方法的角度，以及它们的“生成”本质，基本上使用文法为编译器生成测试程序。这个领域的基本工作是这篇论文2。后来，它被许多其它研究者用作一个出发点，他们要么修改这篇文章中推荐的Purdom的算法要么将它与他们自己的算法结合。Purdom算法的输入数据是一个起始符只在规则的左边出现一次的上下文无关文法。这种约束并没有限制考虑的语言的种类，因为任何上下文无关的文法都可以缩减为这种形式。这个算法构造了一个文法中每一个文法规则至少使用一次推导出的短语集。在这样做过程中，问题被转移到最小化这个集合。这个算法以下列方式工作。首先，对于每一个非终结符，得到一串终结符形成的推导树的最小长度被构造出来。这个信息在算法的第二部分被使用。算法的第二部分用一个栈来存储产生的短语。开始，这个栈包含文法的开始符。然后，开始进行一下循环:如果栈顶符号是终结符则打印出来，如果栈顶符号是非终结符，则用左边含有此符号的规则的右边替换该符号。在替换中将要使用的规则从那些没有使用的规则中挑选(如果不可能，则再从剩下的规则中挑选)按照最小推导长度的准则。这些步骤不断重复直到栈空为止。产生的短语被添加进测试组件内，起始符被放入栈内，然后重复第二部分的生成算法。当每个文法规则都至少被使用一次后循环中止。Purdom算法实际上为文法产生紧凑的测试套件。论文3中提供了用这种算法编写的应用程序为C和C+文法生成的测试文本。对于包含211条规则的C文法，生成了11条短语；对于包含824条规则的C+文法，测试套件包含81个短语。这个算法可以产生满足规则覆盖准则的短语，这项准则要求减少测试套件中短语的数量时每条规则至少使用一次。每个测试套件都需要满足这个条件。后来，Lmmel在论文4中说明了基于规则覆盖准则的测试套件不能揭示文法规则中的简单错误并推荐了一个更强大的上下文独立规则覆盖准则。要介绍这个准则，我们需要以下定义:定义一: 设G= 是一个上下文无关文法。一个非终结符n在文法中的直接出现是指任意一个右部包含n的规则。覆盖标准自身定义如下。定义2 设G=是一个上下文无关文法。短语w T*对于符号的直接出现覆盖规则，如果存在这样的推导：s * xmy qxunvy p xuzvy * w短语集对于文法满足上下文独立规则覆盖标准，如果对于任何一个规则和任意一个符号的直接出现，都包含一个短语对于出现覆盖规则。Lmmel指出上下文独立规则覆盖标准比规则覆盖标准能创建揭示更多类错误的测试套件。论文推荐了另一个考虑到了文法规则使用的上下文的覆盖准则。该文法表示法利用了变量，借助括号将选择符分组。每个子短语和所有非终结符被称作分支点。每个分支点与属于它可推导出的短语的终结符组成的集合相关联。这个集合被称为分支点的前向集。由二元组（，），其中是分支点，是的前向集中的一个终结符，组成的集合被称为该文法的情况集。该覆盖标准按如下方式制订。定义短语对于给定文法覆盖情况（，）如果存在推导s *m r m * w使得且规则的右侧包含分支点。短语集满足情况覆盖标准，如果对于给定文法情况集中的每个情况中都有一个短语覆盖它。这个覆盖标准是面向分析器的，对于分析器来讲对分支点的分析是语法分析算法的一个重要部件。其它针对基于文法的测试生成的工作没有引入任何关于测试质量分析的覆盖标准。如果不使用一种覆盖准则，那么测试生成何时完成就不明确。由于几乎所有实际程序语言的文法都是递归的，所以必须要有一个防止无限递归的机制。基于此目的，对规则使用数量的限制或概率方法被引入。Guilmette一个上下文无关的短语生成算法，该算法基于从启始符开始的短语展开。首先，最左边的非终结符被展开。这个符号被完全展开后，它被获得的一串符号替代，然后算法又被用在下一个最左边非终结符上。沿着正在展开的分支，每次使用一条规则，该规则在下一次展开中被选择的概率就会减小。由于使用规则将一个非终结符展开成一系列非终结符会终止生成过程，这个方法会逐渐减少其它规则在展开过程中的应用并保证这一个过程在有限时间内中止。另一个基于stochastic文法的方法在7, 8, 12的工作被使用。Stochastic文法和普通文法的不同在于前者的每个规则都是以一个数，规则的权重来标记的，这个数决定了在生成过程中选择这条规则的相对频率。一个Stochastic文法被认为是连续的如果它定义的一个Stochastic语言具有以下性质：对于任意小的一个数，都存在一个正数，使得这种语言的一个短语的长度比大的总概率小于。这个性质保证了生成算法在有限时间内中止。论文11研究了Stochastic文法的连续性。以上提到的工作是致力于一个语言的短语的生成的，即满足语法要求的终结符串。这些短语用于检测语法分析器能否正确识别一个良好的程序。从实践中可以知道，检测语法分析器能否正确处理包含语法错误的程序也是非常重要的。为了达到这个目的，来自语法正确的程序的集合在所有可能的终结符串的集合中的补集的程序（图中语法的反面测试样例）被使用。论文13中考虑了这样的程序的自动化生成和针对它们的覆盖准则。论文13中推荐的方法是基于创建一个，对于每个终结符，在该语言的短语中可以紧跟在之后的终结符集合Ft。这个方法同时也用到了Ft在所有终结符集合中的补集Nt。这个集合包含的是那些在该语言的短语中不能紧跟在之后的符号。这项工作中推荐的正向测试的覆盖标准是要覆盖在各种文法上下文下的所有可能的由两个连续的终结符组成的序列。与此相对的，对于反面测试，可能的不被接受的组合也要被考虑。这篇论文描述了产生集合Ft和Nt的算法从而证明了这种算法的存在。静态语义分析阶段测试为了测试编译器的静态语义分析阶段，静态语义正确的程序，以及那些属于静态语义正确的程序集合在语法正确的程序集合中的补集的程序（即静态语义的反面测试）将被使用（如图所示）。为了制订静态语义，属性文法最常被使用。属性文法通过包含各种变量属性，语义函数和上下文条件，扩展了上下文无关文法。每个文法规则都和一个语义函数的集合对应，这些语义函数从父亲节点的属性和其它后代的属性（继承属性）的方面表达一个节点的属性值。同时，每个规则也和一个上下文条件对应，这个上下文条件决定了这个节点属性的可能取值。一个程序被认为是静态正确的，如果在计算出抽象语法树上的所有属性值后发现所有上下文条件都为真。在论文14中，提出了一个基于语义的描述创建程序静态语义测试的方法。作者提出了一个基于上下文条件覆盖的测试套件完整性标准。满足这个标准意味着测试套件包含所有使得上下文条件都为真的属性值组合。为了实现这个目标，上下文条件被表示成一组逻辑或后的一个逻辑与，并且所有使得每个在公式中的逻辑或取真值的属性值组合都被选择。在论文15,提出了一个通过以属性文法形式描述语言的静态语义来生成测试程序的算法。对于每个文法规则，一个使用这条规则推出的静态正确的测试程序都将被生成。对于每条规则，测试的创建都是从一系列包含同一个元素，这条规则的右部得字符串开始的。在每个迭代的过程中，算法会从创建的字符串中选择一个字符串，这个字符串转化为一串终结符所需要的推导长度的估计值最小。如果这个字符串是一个程序，即一串可从开始符推出的终结符串，则算法中止。否则，从用下列方法之一给定的短语中获得一个短语集，将其补充进列表中。(1) 通过将一个语法产生式规则中的非终结字符串替换成某一字符串能得到的所有字符串的集合被创建。(2) 字符串中的一个非终结符被选中，并被替换为一个字符串集，这个字符串集由所有通过如下方式获得的字