Compiler Construction - Bison 2.3 Manual

Bison is a general-purpose parser generator that converts an annotated context-free grammar into an LALR(1) or GLR parser for that grammar. Once you are proficient with Bison, you can use it to develop a wide range of language parsers, from those used in simple desk calculators to complex programming languages.

Bison is upward compatible with Yacc: all properly-written Yacc grammars ought to work with Bison with no change. Anyone familiar with Yacc should be able to use Bison with little trouble. You need to be fluent in C or C++ programming in order to use Bison or to understand this manual.

We begin with tutorial chapters that explain the basic concepts of using Bison and show three explained examples, each building on the last. If you don't know Bison or Yacc, start by reading these chapters. Reference chapters follow which describe specific aspects of Bison in detail.

Bison was written primarily by Robert Corbett; Richard Stallman made it Yacc-compatible. Wilfred Hansen of Carnegie Mellon University added multi-character string literals and other features.

This edition corresponds to version 2.3 of Bison.

The distribution terms for Bison-generated parsers permit using the parsers in nonfree programs. Before Bison version 2.2, these extra permissions applied only when Bison was generating LALR(1) parsers in C. And before Bison version 1.24, Bison-generated parsers could be used only in programs that were free software.

The other GNU programming tools, such as the GNU C compiler, have never had such a requirement. They could always be used for nonfree software. The reason Bison was different was not due to a special policy decision; it resulted from applying the usual General Public License to all of the Bison source code.

The output of the Bison utility—the Bison parser file—contains a verbatim copy of a sizable piece of Bison, which is the code for the parser's implementation. (The actions from your grammar are inserted into this implementation at one point, but most of the rest of the implementation is not changed.) When we applied the GPL terms to the skeleton code for the parser's implementation, the effect was to restrict the use of Bison output to free software.

We didn't change the terms because of sympathy for people who want to make software proprietary. Software should be free. But we concluded that limiting Bison's use to free software was doing little to encourage people to make other software free. So we decided to make the practical conditions for using Bison match the practical conditions for using the other GNU tools.
This exception applies when Bison is generating code for a parser. You can tell whether the exception applies to a Bison output file by inspecting the file for text beginning with “As a special exception...”. The text spells out the exact terms of the exception.

Click to Download/Read More

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

Advanced Compiler Construction

By Professor Keith D. Cooper and Dr. Timothy J. Harvey

This advanced compiler construction ebook describes compiler design techniques in a wonderful way. Following are the various compiler construction topics covered in this ebook.

• Introduction to Optimization
• The Fortran H Compiler
• Value Numbering as an Introduction to Optimization,
• Global Analysis (& Optimization)
• More on Data-flow Analysis
• Allen-Cocke Interval Analysis
• Proliferation of Data-flow Analysis Problems
• Static Single Assignment Form
• Using SSA: Dead Code Elimination and Constant Propagation
• Order from Chaos: The COMP 512 Taxonomy
• Profile-guided Code Positioning
• CLEAN: Removing Useless Control Flow
• Operator Strength Reduction
• Lazy Code Motion
• Algebraic Reassociation of Expressions
• Code Replication
• Code Motion of Control Structures
• Optimization of Range Checking
• IBM's PL.8 Compiler
• Compiling for Reduced Energy Consumption
• Register Allocation Via Graph Coloring
• Instruction Scheduling: Introduction & Local List Scheduling
• Instruction Scheduling: Randomization, Register Pressure, and More,
• Balanced scheduling
• Instruction Scheduling: Software Pipelining
• Instruction Scheduling: More Software Pipelining and Other Superlocal Techniques
• Ten Hardware Features that Affect Optimization
• Register Allocation via Hierarchical Graph Coloring
• Interprocedural Analysis and Optimization
• Dynamic Compilation in an OOL: The Deutsch-Schiffman Impementation of Smalltalk-80
• Dynamic (or runtime) Optimization

Click to Read More/Download

Design and Evaluation of a Compiler Algorithm for Prefetching

By Todd C. Mowry, Monica S. Lam and Anoop Gupta

Software-controlled data prefetching is a promising technique for improving the performance of the memory subsystem to match today's high-performance processors. While prefetching is useful in hiding the latency, issuing prefetches incurs an instruction overhead and can increase the load on the memory subsystem. As a result, care must be taken to ensure that such overheads do not exceed the bene ts.

This paper proposes a compiler algorithm to insert prefetch instructions into code that operates on dense matrices. Our algorithm identi es those references that are likely to be cache misses, and issues prefetches only for them. We have implemented our algorithm in the SUIF (Stanford University Intermediate Form) optimizing compiler. By generating fully functional code, we have been able to measure not only the improvements in cache miss rates, but also the overall performance of a simulated system. We show that our algorithm signi cantly improves the execution speed of our benchmark programssome of the programs improve by as much as a factor of two. When compared to an algorithm that indiscriminately prefetches all array accesses, our algorithm can eliminate many of the unnecessary prefetches without any signi cant decrease in the coverage of the cache misses.

Click to Download

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

Principles of Compiler Design

By Clifford Wolf

In this presentation I will discuss:

• A little introduction to Brainf*ck
• Components of a compiler, overview
• Designing and implementing lexers
• Designing and implementing parsers
• Designing and implementing code generators
• Tools (Lex, bison, iburg, etc.)
• Overview of more complex code generators
• Abstract syntax trees
• Intermediate representations
• Basic block analysis
• Backpatching
• Dynamic programming
• Optimizations
• Design and implementation of the Brainf*ck Compiler
• Implementation of and code generation for stack machines
• Design and implementation of the SPL Project
• Design and implementation of LL(regex) parsers

After this presentation, the auditors ..

• should have a rough idea of how compilers are working.
• should be able to implement parsers for complex conguration files.
• should be able to implement code-generators for stack machines.
• should have a rough idea of code-generation for register machines.

Click to Download