编译器测试技术研究

《编译器测试技术研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、示为L(Ｇ)．这些符号串叫做语言的短语。文法＜Ｎ，Ｔ，ｓ，Ｐ＞被称作与上下文无关如果有一条规则ｎ，满足ｎ－＞ｗ，其中ｎ∈Ｎ，ｗ∈（ＮＵＴ）＊．正规的文法是规定语言句法的方便的手段。上下文无关的文法机制不足以定义编程语言的语义。现在公认把编程语言得语义分为静态和动态语义。静态语义解决程序中类型的正确使用，标识符的作用范围，和程序的其它不运行就能确定的属性。描述静态语义的最常用的方法是状态文法。在状态文法中，文法的每个符号被设定为与一个有限的状态集对应，且每个文法规则对应一个规则，以便评估对应于规则的符号的属性。用这些规则，我们可以评估分析树中每个节点的属性。每条规则可

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

7、序文本被分析，分析树被创建。2.静态语义分析。在这个阶段，分析数被分析，树中所有节点的属性被计算出来，程序的静态正确性被证实。3.优化转换。在这个阶段，按照选择的标准（代码长度，操作率）对程序的内部表示进行各种转换以提高程序的质量。4.代码生成。代码生成就是通过给定的内部的程序表示创建一个可执行文件。通常，对大部分编译器进行功能性分解会和以上方案对应，尽管每个特定的实现有自己的特点。例如，有些编译阶段被分解成几个更好的子阶段。一些阶段可以在系统的一个组件实施，而不是几个组件。让我们更细致地考虑编译其输入数据的结构（如图所示），讨论如何用这个结构的子集来测试编译的