Compact recursive-descent parsing of expressions

Compiler writing tools, such as parser generators, are-commonly used to build new operators. Nevertheless, constructing compilers by hand remains common. Such compilers are often built using recursive-descent parsing for most of the language and operator-precedence parsing for expressions. This paper describes a simple technique for parsing expressions using recursive descent that avoids the usual proliferation of procedures that occurs when recursive descent is used to parse expressions. By taking advantage of the similarity of the productions describing expressions in most languages, the n + 1 procedures usually required to parse expressions with n precedence levels can be replaced with a table and two procedures.     

Modelling of space-efficient one-pass translation using attribute grammars

Automatic production of one-pass compilers from attribute grammars is considered. An examination of a one-pass grammar for the programming language Euclid shows that the present definition of one-pass grammars is too general: the space behaviour of the produced compilers differs from that found in conventional hand-written compilers. A new class of attribute grammars is defined. The class models naturally the use of space in a hand-written compiler. This implies that the compiler produced automatically on the basis of the grammar uses space in the same way as a practical hand-written recursive descent compiler. Furthermore, a graphical notation is introduced as a design tool for obtaining grammars in the proposed class.     

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.     

Visual language implementation through standard compiler–compiler techniques

We present a technique for implementing visual language compilers through standard compiler generation platforms. The technique exploits eXtended Positional Grammars (XPGs, for short) for modeling the visual languages in a natural way, and uses a set of mapping rules to translate an XPG specification into a translation schema. This lets us generate visual language parsers through standard compiler–compiler techniques and tools like YACC. The generated parser accepts exactly the same set of visual sentences derivable through the application of XPG productions. The technique represents an important achievement, since it enables us to perform visual language compiler construction through standard compiler–compilers rather than specific compiler generation tools. This makes our approach particularly appealing, since compiler–compilers are widely used and rely on a well-founded theory. Moreover, the approach provides the basis for the unification of traditional textual language technologies and visual language compiler technologies.     

Combinator-based compilation of recursive functions with different parameter passing modes

Summary Wand's technique of deriving compilers from denotational semantics is applied to a block structured language with recursive functions. The emphasis is on compilation of different parameter passing modes and a simple storage management. The technique starts by eliminating -variables from semantic equations through the introduction of special-purpose combinators. The final code consists of combinators equivalent to target-machine instructions (running-system procedures). The method enables us to derive a compiler and a running system directly from the denotational semantics of a language.     

An assessment of the XR project for compiler development and transportation

A software engineering project, the XR project, is described, and its results assessed. The goal of the XR project is to contribute to the mechanical development and transportation of compilers on widely used Chinese-made computers. The basic tools are the compiler writing language XHY and the intermediate language CJY. All the compilers are written in XHY and produce code in CJY form. In this paper, experiences, statistics and lessons of practising this project are given, together with an overview and a conclusion.     

The portability of the BCPL compiler

Methods of achieving program portability are discussed, with particular reference to the mobility of compilers. The method of transferring the BCPL compiler is then described including the specification of OCODE which is the language used as an interface between the machine independent and machine dependent parts of the compiler.     

RUGRAT: Evaluating program analysis and testing tools and compilers with large generated random benchmark applications

Benchmarks are heavily used in different areas of computer science to evaluate algorithms and tools. In program analysis and testing, open‐source and commercial programs are routinely used as benchmarks to evaluate different aspects of algorithms and tools. Unfortunately, many of these programs are written by programmers who introduce different biases, not to mention that it is very difficult to find programs that can serve as benchmarks with high reproducibility of results. We propose a novel approach for generating random benchmarks for evaluating program analysis and testing tools and compilers. Our approach uses stochastic parse trees, where language grammar production rules are assigned probabilities that specify the frequencies with which instantiations of these rules will appear in the generated programs. We implemented our tool for Java and applied it to generate a set of large benchmark programs of up to 5M lines of code each with which we evaluated different program analysis and testing tools and compilers. The generated benchmarks let us independently rediscover several issues in the evaluated tools. Copyright © 2014 John Wiley & Sons, Ltd.     

DSP分块内存和多AGU的编译指示优化

分块内存和多地址生成器(AGU)是DSP普遍采用的体系结构.传统的C语言编译器没有针对分块内存和多AGU结构进行代码优化,导致生成代码无法满足性能需求,影响了C语言编译器在数字信号处理领域的应用.为了解决这个问题,提出基于编译指示,与分块内存和多AGU结构相关的编译优化算法.该算法利用定义引用链和引用定义链中的数据流信息,为地址计算指令和访存指令分配AGU,从而提高生成代码的指令级并行度.实验结果表明此算法能够达到较好的优化效果.     

Babel and SOAP applications of extensible compilers

This paper describes a method of writing compilers which can easily be extended or altered. Two applications of the method are described; the first is a conventional programming language called Babel and the second is a program called SOAP which documents ALGOL 60 programs. Two important features have made extensions practicable; the compiler has a modular construction and was initially written in ALGOL 60.     

SLR(1)词/语法分析的自动构造

主要讨论了SLR（1）词／语法分析器的自动构造，自动生成的SLR（1）语法分析器可从自动生成的SLR（1）词法分析器中获得测试数据进行语法分析，论文相关的软件除可用于编译原理课程教学演示外，还可用于实际编译程序的SLR（1）词／语法分析器的自动构造。由于具有SLR（1）分析表自动构造功能，因此该软件还可作为软件工具用于程序设计语言本身的设计和构造。     

Automatic Parallelization of Recursive Procedures

Parallelizing compilers have traditionally focussed mainly on parallelizing loops. This paper presents a new framework for automatically parallelizing recursive procedures that typically appear in divide-and-conquer algorithms. We present compile-time analysis, using powerful, symbolic array section analysis, to detect the independence of multiple recursive calls in a procedure. This allows exploitation of a scalable form of nested parallelism, where each parallel task can further spawn off parallel work in subsequent recursive calls. We describe a runtime system which efficiently supports this kind of nested parallelism without unnecessarily blocking tasks. We have implemented this framework in a parallelizing compiler, which is able to automatically parallelize programs like quicksort and mergesort, written in C. For cases where even the advanced compile-time analysis we describe is not able to prove the independence of procedure calls, we propose novel techniques for speculative runtime parallelization, which are more efficient and powerful in this context than analogous techniques proposed previously for speculatively parallelizing loops. Our experimental results on an IBM G30 SMP machine show good speedups obtained by following our approach.     

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.     

An optimizing compiler for the icon programming language

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal-directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run-time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type-checking and conversion requirements. A translator converts code written in the run-time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.     

The ilem project: Pascal to algol in easy stages. I: Outward bound

Most academic institutions have Pascal compilers coming out of their ears. Most academic institutions have Algol compilers only on their dinosaur mainframes. The Ilem project consists of designing a sequence of intermediate languages, IL₀, IL₁, IL₂, …, IL_N–1, IL_N, where IL₀ is Pascal and IL_N is Algol, and where any two consecutive languages differ so little that a one-man spare-time project suffices to convert a compiler for one language into a compiler for the next.     

Deriving a compiler from an operational semantics written in VDL

This paper addresses the issue of compiler correctness. The approach taken is to systematically construct a correct compiler for a language from a formal semantic definition of the language. For this purpose, an operational semantics of a language is chosen as the basis for the approach. That is, the compiler for a language is derived from an interpreter of the language. The derivation process uses the notion of mixed computation proposed by Ershov. Briefly stated, one begins interpreting and when a primitive state changing instruction is about to be executed, the instruction is emitted as code instead. The correctness of all compilers produced by the method is guaranteed by proving the derivation rules correct. This proof is a one-time task for each specification language. The specification language studied in this paper is the Vienna Definition Language (VDL). The object code generated by the compiler is in an intermediate language close to an assembly language. Therefore, the translation from the intermediate language into the assembly language should be straightforward.