The GENTLE Compiler Construction System

By Friedrich Wilhelm Schröer, R. Oldenbourg Verlag, Munich and Vienna

The GENTLE Compiler Construction System is available in two editions:

• GENTLE 97 was published in 1997 together with the first edition of this manual (Oldenbourg Verlag, Munich and Vienna, 1997)
• GENTLE 21 is distributed since 2001 by Metarga and is continuously maintained according to the requirements of its users

This manual covers the common functionality of both editions.

However, GENTLE 21 provides additional features such as a powerful parsing strategy that overcomes the limitations of Yacc, iteration statements that simplify the traversal of data structures, a compact notation to embed target text into code generation rules, and more. These extensions are described in a companion manual.

Gentle provides a uniform framework for specifying the components of a compiler.

The Gentle language was designed around a specific paradigm: recursive definition and structural induction. Input and internal data structures are defined by listing alternative ways to construct items from given constituents. Then the properties of these items are described by giving rules for the possible alternatives. These rules recursively follow the structure of items by processing their constituents. Experience has shown that this is the underlying paradigm of virtually all translation tasks.

The same concepts apply to analysis, transformation, and synthesis. They can be used to describe the backend of a compiler as a simple unparsing scheme such as sufficies for most source-to-source translations. They can also be used to specify a cost-augmented mapping to a low-level language which is used for optimal rule selection.

The rule-based approach follows the principle of locality: complex interactions are avoided and a system can be understood by understanding small pieces in isolation. Individual constructs are described independently.

The paradigm leads to a data-oriented methodology: the structure of data is mirrored by the structure of algorithms. This methodology proves to be a useful guideline in compiler projects.

Click to Download/Read More

Behavioral Compiler Tutorial

This tutorial is an introduction to the Synopsys Behavioral Compiler. It shows you the advantages of technology-independent and architecture-independent behavioral designing methodology and

• How to start and use Behavioral Compiler
• How to use BCView to graphically analyze a design
• How to code for synthesis
• How to simulate a design for pre-synthesis and post-synthesis verification

The estimated completion time for the tutorial is 1 to 3 hours. After completing this introduction to Behavioral Compiler, you can take the Synopsys 3 or 4 day class to learn about behavioral synthesis in greater depth.

Two excellent reference books on behavioral synthesis are the following:

1. Understanding Behavioral Synthesis, A Practical Guide to High Level Design by John P Elliott; Kluwer Academic Publishers ISBN 0-7923-8542-X
2. Behavioral Synthesis, Digital System Design Using the Synopsys Behavioral Compiler by David W. Knapp, Prentice Hall, ISBN 0-13-569252-0

Optimal Use of the TutorialFor optimal use of the tutorial, display the tutorial and run Behavioral Compiler on the same UNIX workstation. This gives you the advantage of copying and pasting examples and commands from the tutorial into the Behavioral Compiler command line interface (bc_shell).

Behavioral Compiler Inputs and Outputs

The following drawing illustrates the inputs you provide to Behavioral Compiler, user-created Verilog or VHDL designs, user-defined constraints (timing, area, throughput, etc), and data from a technology library and [optionally] a DesignWare library. Behavioral Compiler creates output RTL and HDL files for synthesis and simulation. Behavioral Compiler also provides reports and the Behavioral Compiler View tool for design analysis prior to simulation.

Click to Read More

Compiler Design and Implementation

By Johan E. Thelin

I've begun designing my own compiler lately after reading 'Let's Build a Compiler' by Crenshaw (see links). This page will contain the compiler source code, a text concerning the implementation of each part (the compiler will be created gradually) and useful links concerning compilers, compiler design, and other close subjects (OS specifics, hardware specifics, etc.). I hope that you will enjoy reading this page.

This tutorial is written 'as I go'. It is strongly influenced by 'Let's Build a Compiler' but is also flavored by myself. The language defined is a pseudo-pascal with the following features:
The variable types word and byte.

• No automatic type conversion, i.e. control.
• The control structures if-else, while-wend and repeat-until.
• Support of the following unary operators +,- and the following binary operators +,-,/,* and parenthesis.The language supports functions and procedures (even recursive ones).
• Other thing that we find necessary later.

1. Chapter I - How is the compiler supposed to work and how should the language look?
2. Chapter II - Let's get Compiling
3. Chapter III - Get the Compiler Counting
4. Chapter IV - Our First Control Structure
5. Chapter V - Variables, Procedures and Functions
6. Chapter VI - More About Variables, Procedures and Functions

Click to Read More

Learning compiler design as a research activity

By Francisco Moreno-Seco, Mikel L. Forcada

This paper describes the application of a pedagogical model called "learning as a research activity" [D. Gil-P'erez and J. Carrascosa-Alis, Science Education 78 (1994) 301{315] to teach a two-semester course on compiler design for Computer Engineering students. In the new model, the classical pattern of classroom activity based mainly on one-way knowledge transmission/reception of pre-elaborated concepts is replaced by an active working environment that resembles that of a group of novel researchers under the supervision of an expert. The new model, rooted in the now commonly-accepted constructivist postulates, strives for meaningful acquisition of fundamental concepts through problem solving in close parallelism to their construction through history.

Introduction

This paper describes the implementation of an adapted version of the learning as a research activity model ([1, 2, 3, 4, 5]) to the subject of compiler design at the University of Alacant. The need for trying a new teaching model arose two years ago when we con rmed our realization that the combination of classical lecturing of theory and solved problems in the classroom and open laboratory assignments was insufficient for most students to learn the basic skills needed to successfully tackle new problems in the eld. The learning as a research activity model, which has been successfully applied to the teaching of science in secondary school, was adopted, adapted, and applied to our subject. We have found the new model to be more adequate, more successful, and more consistent with an engineering education style.

The classical model used in most universities in Spain to teach computer engineering subjects such as compiler design could be simpli ed (in its extreme form) as follows. In the classroom, the teacher tries his or her best to explain carefully the theoretical and conceptual aspects of the subject, usually assuming but seldom carefully checking that the students are familiar with a set of basic concepts on which the new material is based.

After that, some more lecturing time is devoted to showing, with as much detail as possible, the teacher's or a book's solution to a handful of selected (intendedly representative) problems or exercises. Laboratory work may be organized either around an open or closed structure, but usually consists either in building one or more programs that implement the algorithms and techniques taught in the classroom to solve a set of selected problems or in writing applications according to some speci ed requirements. In addition, the teacher is available during some scheduled office hours to assist students with their personal work.

Of course, signi cant deviations from this simpli ed model are observed: a few students may interact with the teacher during an explanation, usually to ask him to repeat something, or explain some passage better, or to point out a minor blunder; teachers may ask questions to the students to try to make sure that they are following the explanation; the teacher's solution to a given problem may only be explained after students have had some time to think about it, etc.

Click to Download

Compilers and Compiler Generators an introduction with C++

By P.D. Terry

This book has been written to support a practically oriented course in programming language translation for senior undergraduates in Computer Science. More specifically, it is aimed at students who are probably quite competent in the art of imperative programming (for example, in C++, Pascal, or Modula-2), but whose mathematics may be a little weak; students who require only a solid introduction to the subject, so as to provide them with insight into areas of language design and implementation, rather than a deluge of theory which they will probably never use again; students who will enjoy fairly extensive case studies of translators for the sorts of languages with which they are most familiar; students who need to be made aware of compiler writing tools, and to come to appreciate and know how to use them. It will hopefully also appeal to a certain class of hobbyist who wishes to know more about how translators work.

The reader is expected to have a good knowledge of programming in an imperative language and, preferably, a knowledge of data structures. The book is practically oriented, and the reader who cannot read and write code will have difficulty following quite a lot of the discussion. However, it is difficult to imagine that students taking courses in compiler construction will not have that sort of background!

There are several excellent books already extant in this field. What is intended to distinguish this one from the others is that it attempts to mix theory and practice in a disciplined way, introducing the use of attribute grammars and compiler writing tools, at the same time giving a highly practical and pragmatic development of translators of only moderate size, yet large enough to provide considerable challenge in the many exercises that are suggested.

Click to Read More

Compiler Construction

By Niklaus Wirth

This book has emerged from my lecture notes for an introductory course in compiler design at ETH Zürich. Several times I have been asked to justify this course, since compiler design is considered a somewhat esoteric subject, practised only in a few highly specialized software houses. Because nowadays everything which does not yield immediate profits has to be justified, I shall try to explain why I consider this subject as important and relevant to computer science students in general.

It is the essence of any academic education that not only knowledge, and, in the case of an engineering education, know-how is transmitted, but also understanding and insight. In particular, knowledge about system surfaces alone is insufficient in computer science; what is needed is an understanding of contents. Every academically educated computer scientist must know how a computer functions, and must understand the ways and methods in which programs are represented and interpreted. Compilers convert program texts into internal code. Hence they constitute the bridge between software and hardware.

Now, one may interject that knowledge about the method of translation is unnecessary for an understanding of the relationship between source program and object code, and even much less relevant is knowing how to actually construct a compiler. However, from my experience as a teacher, genuine understanding of a subject is best acquired from an in-depth involvement with both concepts and details. In this case, this involvement is nothing less than the construction of an actual compiler.

Click to Read More/Download pdf book

Compilers: Backend to Frontend and Back to Front Again

By Abdulaziz Ghuloum

Compilers are percieved to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. This paper attempts to dispel this myth. We build a simple compiler for a simple language in a step-by-step fashion. The input language accepted by the compiler starts minimal, and grows as our knowledge of how to build compilers grows. The final language is almost Scheme.

Although the compiler is written in the Scheme programming language, only minimal knowledge of Scheme is required. Essentially, the reader is assumed to be comfortable reading and writing recursive Scheme functions to the level presented in The Little Schemer. Additionally, we recommend the freely available tutorial Teach Yourself Scheme in Fixnum Days for people familiar with other programming languages but not Scheme. The Scheme Programming Language is an invaluable resource for understanding Scheme’s semantics. You will find it most useful when you give up in thinking how list? detects circular data structures.

Our compiler targets the Intel-386 architecture, the dominant architecture for personal computing. The output of our compiler is assembly code that can be assembled by gas, the GNU assembler, which is freely available for most operating systems. No knowledge of assembly language or the Intel-386 architecture is assumed beyond the basics: binary numbers, memory layout, and basic pointers. If you are familiar with arrays in C, and know how the bit-level operations (and, or, xor, and not) work, then you’re good to go.

Click to Read More

Let's Build a Compiler

by Jack Crenshaw

This series of articles is a tutorial on the theory and practice of developing language parsers and compilers. Before we arefinished, we will have covered every aspect of compiler construction, designed a new programming language, and built a working compiler.

Though I am not a computer scientist by education (my Ph.D. is in a different field, Physics), I have been interested in compilers for many years. I have bought and tried to digest the contentsof virtually every book on the subject ever written. I don't mind telling you that it was slow going. Compiler texts arewritten for Computer Science majors, and are tough sledding for the rest of us. But over the years a bit of it began to seep in. What really caused it to jell was when I began to branch off onmy own and begin to try things on my own computer. Now I plan to share with you what I have learned. At the end of this series you will by no means be a computer scientist, nor will you knowall the esoterics of compiler theory. I intend to completely ignore the more theoretical aspects of the subject. What you_WILL_ know is all the practical aspects that one needs to know to build a working system.

This is a "learn-by-doing" series. In the course of the series I will be performing experiments on a computer. You will be expected to follow along, repeating the experiments that I do, and performing some on your own. I will be using Turbo Pascal4.0 on a PC clone. I will periodically insert examples written in TP. These will be executable code, which you will be expected to copy into your own computer and run. If you don't have a copy of Turbo, you will be severely limited in how well you will be able to follow what's going on. If you don't have a copy, I urge you to get one. After all, it's an excellent product, good formany other uses!

Some articles on compilers show you examples, or show you (as inthe case of Small-C) a finished product, which you can then copy and use without a whole lot of understanding of how it works. I hope to do much more than that. I hope to teach you HOW the things get done, so that you can go off on your own and not only reproduce what I have done, but improve on it.

This is admittedly an ambitious undertaking, and it won't be donein one page. I expect to do it in the course of a number ofarticles. Each article will cover a single aspect of compiler theory, and will pretty much stand alone. If all you're interested in at a given time is one aspect, then you need tolook only at that one article. Each article will be uploaded asit is complete, so you will have to wait for the last one before you can consider yourself finished. Please be patient.

The average text on compiler theory covers a lot of ground that we won't be covering here. The typical sequence is:

• An introductory chapter describing what a compiler is.
• A chapter or two on syntax equations, using Backus-Naur Form (BNF).
• A chapter or two on lexical scanning, with emphasis on deterministic and non-deterministic finite automata.
• Several chapters on parsing theory, beginning with top-down recursive descent, and ending with LALR parsers.
• A chapter on intermediate languages, with emphasis on P-code and similar reverse polish representations.
• Many chapters on alternative ways to handle subroutines and parameter passing, type declarations, and such.
• A chapter toward the end on code generation, usually for some imaginary CPU with a simple instruction set. Most readers (and in fact, most college classes) never make it this far.
• A final chapter or two on optimization. This chapter often goes unread, too...........

Click to Read More