Survey of compiler testing methods

Compilers are used for creating executable modules for programs written in high-level languages; therefore, the presence of errors in a compiler is a serious danger for the quality of the software developed with the use of this compiler. As in the case of any other software, testing is one of the most important methods of quality control and error detection in compilers. The survey is devoted to methods for generating, running, and checking the quality of compiler test suites, which are based on formal specifications of the programming language syntax and semantics.Translated from Programmirovanie, Vol. 31, No. 1, 2005.Original Russian Text Copyright © 2005 by Kossatchev, Posypkin.     

Tice: A real-time language compilable using C++ compilers

Model-based development (MBD) holds the promise to capture potential timing problems in embedded software during the early phases of the development, securing the production of bug-free embedded software. For most MBD approaches, the source code is just an intermediate artifact that can be generated automatically from the models. This assumption clashes with an undeniable fact: a large share of the commercial embedded software exploits existing libraries or is developed using C/C++ natively. A way to reconcile the ambitions of MBD with the use of a programming language is by offering new language constructs and an innovative compilation tool-chain that prevents model error and timing problems “by construction.” However, the persistent popularity of C/C++ among embedded programmers and the limited availability of tools have severely limited the uptake of alternative programming languages for embedded software. Therefore, we propose an original route. Our language proposal, named Tice, has been shaped as a C++ active library. Tice retains full compatibility with existing C++ code, which can be integrated easily into new Tice-based projects. The enforcement of Tice syntax and semantics can be made by a standard C++ compiler, forgoing the need for new tools. In this article, we describe Tice's syntax, semantics, and model of computation and communication. We demonstrate Tice's practical applicability on an industrial scale use-case and give ample evidence for Tice's efficient compilation using off-the-shelf C++ compilers. Finally, we show Tice's code generation process.     

SystemJ: A GALS language for system level design

In this paper we present the syntax, semantics, and compilation of a new system-level programming language called SystemJ. SystemJ is a multiclock language supporting the Globally Asynchronous Locally Synchronous (GALS) model of computation. The synchronous reactive (SR) model is used for synchronous parts of the modelled system, and those parts, which represent individual clock-domains, are coupled asynchronously each to the other on the top-level of system design. SystemJ is based on Java language, which is used to describe “instantaneous” data transformations. Hence, SystemJ is well suited for both software-based embedded and distributed systems. SystemJ offers effective modelling of (1) data transformations through the power of Java, (2) control and synchronous concurrency through the SR paradigm and (3) asynchronous concurrency through clock domains and rendezvous. The language is based on semantics that is amenable to efficient code generation and partial automatic verification. The SystemJ micro-step semantics provide asynchronous and synchronous extensions over the semantics of other SR languages such as Esterel and provide an ideal platform for efficient software implementation.     

An algebraic approach to the design of compilers for object-oriented languages

In this paper we describe an algebraic approach to construct provably correct compilers for object-oriented languages; this is illustrated for programs written in a language similar to a sequential subset of Java. It includes recursive classes, inheritance, dynamic binding, recursion, type casts and test, assignment, and class-based visibility, but a copy semantics. In our approach, we tackle the problem of compiler correctness by reducing the task of compilation to that of program refinement. Compilation is identified with the reduction of a source program to a normal form that models the execution of object code. The normal form is generated by a series of correctness-preserving transformations that are proved sound from the basic laws of the language; therefore it is correct by construction. The main advantages of our approach are the characterisation of compilation within a uniform framework, where comparisons and translations between semantics are avoided, and the modularity and extensibility of the resulting compiler.     

嵌入式Java编译器的研究与设计

提出用编译的方法设计一款能直接生成 MCS-51系列单片机的目标代码,不依赖操作系统和JVM的嵌入式Ja-va编译器,使得Java语言在低档嵌入式系统中应用更加广泛,实现成本低廉的工业环境及家庭电器与 Internet 相结合实现远程监测和控制.详细分析了Java语言与嵌入式系统的特点,以实时版jRate及 sun公司的GJC编译系统为参考,采用单遍扫描语法制导翻译模式,以语法分析程序单元为核心,构建嵌入式Java 编译器的词法分析器、语法/语义分析器和代码生成器,并对测试方法进行了探讨.     

A type-safe embedding of SQL into Java using the extensible compiler framework J%

J% is an extension of the Java programming language that efficiently supports the integration of domain-specific languages. In particular, J% allows the embedding of domain-specific language code into Java programs in a syntax-checked and type-safe manner. This paper presents J%׳s support for the sql language. J% checks the syntax and semantics of sql statements at compile-time. It supports query validation against a database schema or through execution to a live database server. The J% compiler generates code that uses standard jdbc api calls, enhancing runtime efficiency and security against sql injection attacks.     

Compiler Verification and Compiler Architecture

We study issues in verifying compilers for modern imperative and object-oriented languages. We take the view that it is not the compiler but the code generated by it which must be correct. It is this subtle difference that allows for reusing standard compiler architecture, construction methods and tools also in a verifying compiler.Program checking is the main technique for avoiding the cumbersome task of verifying most parts of a compiler and the tools by which they are generated. Program checking remaps the result of a compiler phase to its origin, the input of this phase, in a provably correct manner. We then only have to compare the actual input to its regenerated form, a basically syntactic process. The correctness proof of the generation of the result is replaced by the correctness proof of the remapping process. The latter turns out to be far easier than proving the generating process correct.The only part of a compiler where program checking does not seem to work is the transformation step which replaces source language constructs and their semantics, given, e.g., by an attributed syntax tree, by an intermediate representation, e.g., in SSA-form, which is expressing the same program but in terms of the target machine. This transformation phase must be directly proven using Hoare logic and/or theorem-provers. However, we can show that given the features of today's programming languages and hardware architectures this transformation is to a large extent universal: it can be reused for any pair of source and target language. To achieve this goal we investigate annotating the syntax tree as well as the intermediate representation with constraints for exhibiting specific properties of the source language. Such annotations are necessary during code optimization anyway.     

Java中异常结构的语法分析研究

为了提高Java的运行速度,人们对Java编译器进行了深入研究,发现异常结构对编译器的语法分析、语义分析及代码优化都有一定的影响。为了降低异常结构带来的不利影响,文中针对Java中的异常结构提出了一种语法分析方法。该方法采用G树作为语法分析树,较传统的语法分析树的时空效率有明显提高,不仅提高了语法分析的效率,而且提高了语义分析的效率。     

一种用于Java虚拟机的类型化低级语言

为了能够减小运算系统的需信任计算基础、描述较小粒度的安全策略，目前的研究倾向于从程序设计语言和编译器入手来提高软件的安全性．基于以上研究背景设计了一种类型化的低级语言TLL,TLL是一种为Java虚拟机即时编译器设计的类型安全中间语言，以构造一个具有更小需信任计算基础的Java虚拟机系统为目的．TLL的类型系统基于多态的类型化λ演算，它具有丰富的表现力且能够编码各种高级语言的抽象．基于TLL的一个虚拟机原型系统已经实现，它可以作为实现一个高安全且面向多种源语言的运行时系统的起点．     

UCB策略在Prolog中的应用

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

An operational semantics for object-oriented concepts based on the class hierarchy

The formalisation of object-oriented languages is essential for describing the implementation details of specific programming languages or for developing program verification techniques. However there has been relatively little formalisation work aimed at abstractly describing the fundamental concepts of object-oriented programming, separate from specific language considerations or suitability for a particular verification style. In this paper we address this issue by formalising a language that includes the core object-oriented programming language concepts of field tests and updates, methods, constructors, subclassing, multithreading, and synchronisation, built on top of standard sequential programming constructs. The abstract syntax is relatively close to the core of typical object-oriented programming languages such as Java. A novel aspect of the syntax is that objects and classes are encapsulated within a single syntactic term, including their fields and methods. Furthermore, class terms are structured according to the class hierarchy, and objects appear as subterms of their class (and method instances as subterms of the relevant object). This helps to narrow the gap between how a programmer thinks about their code and the underlying mathematical objects in the semantics. The semantics is defined operationally, so that all actions a program may take, such as testing or setting local variables and fields, or invoking methods on other objects, appear on the labels of the transitions. A process-algebraic style of interprocess communication is used for object and class interactions. A benefit of this label-based approach to the semantics is that a separation of concerns can be made when defining the rules of the different constructs, and the rules tend to be more concise. The basic rules for individual commands may be composed into more powerful rules that operate at the level of classes and objects. The traces generated by the operational semantics are used as the basis for establishing equivalence between classes.     

Semantic equivalence of covering attribute grammars

This paper investigates some methods for proving the equivalence of different language specifications that are given in terms of attribute grammars. Different specifications of the same language may be used for different purposes, such as language definition, program verification, or language implementation. The concept of syntactic coverings is extended to the semantic part of attribute grammars. Given two attribute grammars, the paper discusses several propositions that give sufficient conditions for one attribute grammar to be semantically covered by the other one. These tools are used for a comparison of two attribute grammars that specify syntax and semantics of mixed-type expressions. This example shows a trade-off between the complexity of syntactic and semantic specifications. Another example discussed is the equivalence of different attribute grammars for the translation of the while-statement, as used in compilers for top-down and bottom-up syntax analysis.This work was in part supported by the National Research Council of Canada.     

On the reification of Java wildcards

Providing runtime information about generic types–that is, reifying generics–is a challenging problem studied in several research papers in the last years. This problem is not tackled in current version of the Java programming language (Java 6), which consequently suffers from serious safety and coherence problems. The quest for finding effective and efficient solutions to this problem is still open, and is further made more complicated by the new mechanism of wildcards introduced in Java J2SE 5.0: its reification aspects are currently unexplored and pose serious semantics and implementation issues.In this paper, we discuss an implementation support for wildcard types in Java. We first analyse the problem from an abstract viewpoint, discussing the issues that have to be faced in order to extend an existing reification technique so as to support wildcards, namely, subtyping, capture conversion and wildcards capture in method calls. Secondly, we present an implementation in the context of the EGO compiler. EGO is an approach for efficiently supporting runtime generics at compile-time: synthetic code is automatically added to the source code by the extended compiler, so as to create generic runtime type information on a by need basis, store it into object instances, and retrieve it when necessary in type-dependent operations. The solution discussed in this paper makes the EGO compiler the first reification approach entirely dealing with the present version of the Java programming language.     

Accurate garbage collection in uncooperative environments revisited

Implementing a concurrent programming language such as Java by means of a translator to an existing language is attractive as it provides portability over all platforms supported by the host language and reduces development time—as many low‐level tasks can be delegated to the host compiler. The C and C++ programming languages are popular choices for many language implementations due to the availability of efficient compilers on a wide range of platforms. For garbage‐collected languages, however, they are not a perfect match as no support is provided for accurately discovering pointers to heap‐allocated data on thread stacks. We evaluate several previously published techniques and propose a new mechanism, lazy pointer stacks, for performing accurate garbage collection in such uncooperative environments. We implemented the new technique in the Ovm Java virtual machine with our own Java‐to‐C/C++ compiler using GCC as a back‐end compiler. Our extensive experimental results confirm that lazy pointer stacks outperform existing approaches: we provide a speedup of 4.5% over Henderson's accurate collector with a 17% increase in code size. Accurate collection is essential in the context of real‐time systems, we thus validate our approach with the implementation of a real‐time concurrent garbage collection algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

Compiler testing: a systematic literature analysis

Compilers are widely-used infrastructures in accelerating the software development,and expected to be trustworthy.In the literature,various testing technologies have been proposed to guarantee the quality of compilers.However,there remains an obstacle to comprehensively characterize and understand compiler testing.To overcome this obstacle,we propose a literature analysis framework to gain insights into the compiler testing area.First,we perform an extensive search to construct a dataset related to compiler testing papers.Then,we conduct a bibliometric analysis to analyze the productive authors,the influential papers,and the frequently tested compilers based on our dataset.Finally,we utilize association rules and collaboration networks to mine the authorships and the communities of interests among researchers and keywords.Some valuable results are reported.We find that the USA is the leading country that contains the most influential researchers and institutions.The most active keyword is“random testing”.We also find that most researchers have broad interests within small-scale collaborators in the compiler testing area.     

Godel语言延迟声明语句的语义及其实现方法

Gdel语言因语言成份复杂而缺乏严格的语义基础和成熟的编译器,因此推出后它一直发展缓慢。对此采用进化代数描述了其主要语言成分延迟声明语句的过程性语义,然后介绍了依据该语义的具体实现方法并给出运行流程图和C语言描述。最后通过一个例子来具体说明延迟计算在基于扩展Warren机的编译系统中的执行情况。实验结果表明了其可行性。     

Compiling lazy functional programs to Java bytecode

The Java Virtual Machine (JVM) was designed as the target for Java compilers, but there is no reason why it cannot be used as the target for other languages. We describe the implementation of a compiler which translates a lazy, weakly‐typed functional program into Java class files. We compare the performance of our compiler to the only other known compiler from a lazy functional language to the JVM. The results are broadly similar, suggesting that to get a significant performance speed‐up using this compilation paradigm will come only from increasing the performance of the JVM, rather than enhancing the compiler itself. Copyright © 1999 John Wiley & Sons, Ltd.     

Use of a formal notation for static semantics in compiler design

Formal notations for the specification of the syntax and the dynamic semantics of languages exist and are of great benefit to the compiler writer. However, formal notations for the static semantics of languages have tended to be tools of the language designer and of little practical significance to the compiler writer. This paper describes how a particular notation was used to assist in the implementation of a Cobol compiler and of an interpreter for a simulation language.