一个测试程序自动生成器的设计与实现

本文介绍了一个用于编译程序测试的程序自动生成器,该生成器以编译程序对象语言的前后文无关文法作为输入,根据该语言的具体特点,对语言的数据对象采用了一种表结构的描述方式,并通过对表的操作,有效的解决了语言的前后文相关问题,该生成器不但可按语言文法的描述自动生成覆盖该语言各种语法现象的程序,而且还可按用户要求生成具有某种语法现象的程序,另外,该生成器在生成策略、生成算法及推导机制等方面也有自己显著的特色。     

编译程序的范式结构及用属性文法进行编译程序设计(上)

本文将介绍编译程序自动生成的方法,该方法在NCI(华北计算技术研究所)用来发展编译程序自动生成系统(CSG).本文还详细地讨论属性文法以及如何使用属性文法进行编译程序设计.     

LR分析法在词法分析器自动构造中的应用

提出了一种新的自动构造编译程序词法分析器的方法,LR分析法通常用于语法分析,但只要适当修改LR分析总控程序,就可将LR分析法用于词法分析器的自动构造。该方法的优点不仅在于将词法分析器自动构造方法与语法分析器自动构造方法统一,简化了编译程序的设计和构造,而且该方法自动化程序较高,只要确定描述单词的文法和词形编码表,便可自动生成任何程序设计语言编译程序的词法分析器。     

AGDL——一个属性文法定义语言

AGDL是一个属性文法定义语言,用来进行编译程序自动生成的说明。AGDL具有抽象数据类型的定义的施用型(Applicative language)语言,因此属性文法规则简明易读,是用来发展编译程序生成的重要工具语言。     

基于UML顺序图的测试用例生成

为生成覆盖测试需求的测试用例集,提出一种基于UML顺序图自动生成测试用例的方法。通过分析待测系统的功能用例,对其进行顺序图建模。在基于该顺序图生成测试用例的过程中,对顺序图添加规约条件,解析顺序图,得到场景测试树,再遍历该树,得到场景的输入、预期输出、约束条件以及场景环境,这4部分组成了测试用例,同时对如何处理复杂的顺序图及如何满足测试用例充分性等问题进行分析总结,提出有效的解决策略。     

SQL测试用例集的自动生成

编写SQL语句是测试数据库管理系统的一个重要部分。自动生成SQL语句可以有效减少测试人员的工作量,而目前没有直接生成SQL语句的自动化工具。通过模拟产生式的直接推导过程,根据SQL文法,给出生成符合该文法的SQL语句,用作测试用例的方法;研究从表示文法的BNF文件生成SQL测试用例集合的自动化过程。这个过程包括几个阶段:将SQL文法的每一个非终结符转换成一个对应的解析函数,所有解析函数的集合构成规则库;遍历文法的产生式自动生成SQL测试用例;使用权值数组结合随机数,加大生成测试用例的灵活性;使用非终结符的最大调用次数来终止SQL测试用例的生成。通过介绍的工具原型,可以得到符合SQL语法的SQL测试用例。     

一种从UML模型生成测试用例方法的研究与实现

测试用例生成是软件自动化测试的基础与关键。随着UML的广泛应用,基于UML模型来自动生成用例的技术日益受到关注。在UML模型中,顺序图描述了软件系统的动态行为,是软件集成测试中一个重要的来源。文中提出一种基于UML顺序图与类图相结合的方法来自动生成测试用例,定义了相应的测试覆盖准则及测试衡量标准,并用一个具体实例验证了测试用例的生成过程。最后给出了测试用例自动生成工具的框架。     

一种图文法制导的软件体系结构开发环境Artemis-GADE

图形化、集成化的软件体系结构开发环境对于推动软件体系结构相关技术的研究和应用具有重要的意义.提出了一种基于图文法的可视化编辑环境生成机制.对于给定的软件体系结构风格的图文法描述,可以自动生成相应的图文法制导的体系结构编辑工具.与常见的基于Meta-Model的开发环境相比,这种图文法制导的开发方式更多地利用了相应软件体系结构风格的内在语义,从而提高了环境的易用性和可靠性.设计并实现了一个原型系统Artemis-GADE(graph grammar-directed architecture development environment),初步验证了上述途径的可行性.     

一种编译优化测试用例自动生成方法的设计与实现

编译器的质量保证对提高软件产品的质量有着重要作用,对编译优化的测试是其中的核心部分.对编译优化的测试需要大量的测试用例程序.要构造这些测试用例,使用传统手工构造方法面临着效率低的问题,而基于文法的构造方法则针对性不足.从对优化的形式化描述出发来自动构造测试用例能克服这些缺点.本文设计并实现了一种基于形式化描述的编译优化测试用例程序生成方法.该方法基于编译优化的时序逻辑描述构造关键顶点控制流图,逐步转换为控制流图并得到用例程序.针对GCC(版本4.1.1)进行的覆盖率测试实验表明,该方法可以生成具有较高针对性的测试用例,并达到相当的覆盖程度.     

UML活动图在组件系统测试用例生成中的应用研究

近年来，基于UML的测试成为组件系统测试的研究热点。为了从UML活动图模型中自动生成组件系统的测试用例，本文采用灰盒测试方法，给出了活动图的形式化描述。分析了活动图并发特征所引起的测试场景集数量爆炸问题，提出增加约束条件的解决方法，减少了测试场景集数量。提出了一种基于活动图的组件系统测试场景与测试用例生成方法，使自动化生成测试用例可行性有一定的提高。     

Compile-time scheduling of multithread data localities on multiple vector processors

A large class of loop programs applied in solving differential equations, Fourier transforms, image processing and neural processing can be translated or rewritten into a vector execution form with a π-block dependence graph. In the paper we propose a multithreading strategy to partition such vectorized loops into multithread execution form. Each partitioned thread consists of instances of statements with localities in vector registers. The multithreading scheme gives a novel combination of loop unrolling, statement instances reordering, index shifting, vector register reuse exploiting and multithreading. For some cases of loop program with π-block dependence graph, experimental results show that our scheme assists vector compilers of the Convex C38 series to reduce the number of memory accesses and synchronizations among CPUs.     

Decomposed software pipelining: A new perspective and a new approach

Software pipelining is an efficient instruction-level loop scheduling technique, but existing software pipelining approaches have not been widely used in practical and commercial compilers. This is mainly because resource constraints and the cyclic data dependencies make software pipelining very complicated and difficult to apply. In this paper we present a new perspective on software pipelining in which it is decomposed into two subproblems—one is free from cyclic data dependencies and can be effectively solved by the list scheduling technique, and the other is free from resource constraints and can be easily solved by classical polynomial-time algorithms of graph theory. Based on this new perspective, we develop a new instruction-level loop scheduling approach, call DEcomposed Software Pipelining (DESP).     

Automatic detection and diagnosis of faults in generated code for procedure calls

In this paper, we present a compiler testing technique that closes the gap between existing compiler implementations and correct compilers. Using formal specifications of procedure-calling conventions, we have built a target-sensitive test suite generator that builds test cases for a specific aspect of compiler code generators: the procedure-calling sequence generator. By exercising compilers with these specification-derived target-specific test suites, our automated testing tool has exposed bugs in every compiler tested on the MIPS and one compiler on the SPARC. These compilers include some that have been in heavy use for many years. Once a fault has been detected, the system can often suggest the nature of the problem. The testing system is an invaluable tool for detecting, isolating, and correcting faults in today's compilers.     

UCB策略在Prolog中的应用

Prolog(Programming in Logic)程序语言是一种逻辑程序设计语言.它是在逻辑学理论基础上建立起来的并广泛应用在人工智能研究中.这几十年已经出现了各具特色的Prolog编译器,而且各种编译器也都很成功.虽然在现阶段已经出现了各种版本Prolog编译器,但是Prolog编译器的发展空间还是很大.本文先通过现代Prolog编译器的不足,介绍了新Prolog编译器的特点,然后简单叙述了Prolog编译器词法分析和语法分析的过程,最后介绍了UCB策略.     

XDP: A compiler intermediate language extension for the representation and optimization of data movement

The ability to represent, manipulate, and optimize data placement and movement between processors in a distributed address space machine is crucial in allowing compilers to generate efficient code. Data placement is embodied in the concept of dataownership. Data movement can include not just the transfer of data values but the transfer of ownership as well. However, most existing compilers for distributed address space machines either represent these notions in a language-or machine-dependent manner, or represent data or ownership transfer implicitly. In this paper we describe XDP, a set of intermediate language extensions for representing and manipulating data and ownership transfers explicitly in a compller. XDP is supported by a set of per-processor structures that can be used to implement ownership testing and manipulation at run-time, XDP provides a uniform framework for translating and optimizing sequential, data parallel, and message-passing programs to a distributed address space machine. We describe analysis and optimization techniques for this explicit representation. Finally, we compare the intermediate languages of some current distributed address space compilers with XDP.     

Computing SSA Form with Matrices

Static Single-Assignment (SSA) form is an efficient intermediate representation used in virtual machines and modern compilers. It provides data flow information that simplifies the implementation of standard program optimisations such as constant propagation, dead code elimination, and partial redundancy elimination. Constructing SSA form involves the computation of graph relations such as dominance, and non-iterated and iterated dominance frontier. Although there exist efficient graph algorithms for these relations, the algorithms are elaborate to implement. In this paper we introduce a new approach to compute the dominance relation, the dominance frontiers, and the iterated dominance frontiers based on Boolean matrix calculus. We implemented our approach in an optimising backend for LCC bytecode and compared its performance with the state-of-the-art approaches. We use the Spec95 benchmark suite for our experimental evaluation.     

Testing syntax and semantic coverage of Java language compilers

Software testing is a critical and important stage of the application software development life-cycle. Testing is a verification activity that affects the overall software quality. The verification of critical and dependable computer software such as real-time safety-critical software systems consumes about 50% of the project time. In this work, we consider testing compilers. Since a compiler is a highly usable software, an increased emphasis on reliability requires a careful testing before releasing the compiler. In compiler testing, the compiler implementation is verified to conform to the specified language syntax and semantic available in the standard language documentation. In this work, an algorithm is designed and a tool is developed to automate the generation of test cases to check the language syntax. In addition, we propose a heuristic approach to cover language semantics. Since Java is a relatively new programming language, we concentrate on testing the adherence of new Java compilers to the language syntax and semantics.     

基于DBTNN算法的场景调度策略研究

构建了一种能有效描述大规模虚拟环境的场景图和基于该场景图的场景多叉树,以此为基础提出了基于改进的动态二叉树神经网络(Dynamical Binary-tree Based Neural Network,DBTNN)进行场景调度的新方法,并给出了神经网络挖掘装配过程中视点变化的规律.同时,通过该网络输出预测下一步或下几步的视点状态信息,使场景调度具有一定的容错性,提高了场景调度的实时性并使调度更加智能化.最后给出了不同场景的测试结果,表明该算法对于大规模复杂场景有非常好的优化效果.     

Student models: the genetic graph approach

In this paper we examine the student model component of an intelligent computer-assisted instruction (ICAI) system. First, we briefly discuss the desirable capabilities of the student model and then describe, in detail, one approach to student modelling which is based on Goldstein's genetic graph. We expand Goldstein's definition and test it's feasibility in new domains, since his original domain was a limited, straightforward adventure game. In addition to modelling two diverse domains, subtraction and ballet, we also discuss the role of certain ICAI components in generating and maintaining the genetic graph.     

Optimizing compilation with preservation of structural code coverage metrics to support software testing

Code‐coverage‐based testing is a widely‐used testing strategy with the aim of providing a meaningful decision criterion for the adequacy of a test suite. Code‐coverage‐based testing is also mandated for the development of safety‐critical applications; for example, the DO178b document requires the application of the modified condition/decision coverage. One critical issue of code‐coverage testing is that structural code coverage criteria are typically applied to source code whereas the generated machine code may result in a different code structure because of code optimizations performed by a compiler. In this work, we present the automatic calculation of coverage profiles describing which structural code‐coverage criteria are preserved by which code optimization, independently of the concrete test suite. These coverage profiles allow to easily extend compilers with the feature of preserving any given code‐coverage criteria by enabling only those code optimizations that preserve it. Furthermore, we describe the integration of these coverage profile into the compiler GCC. With these coverage profiles, we answer the question of how much code optimization is possible without compromising the error‐detection likelihood of a given test suite. Experimental results conclude that the performance cost to achieve preservation of structural code coverage in GCC is rather low. Copyright © 2012 John Wiley & Sons, Ltd.