Skip to main content

About this book

This book provides a practically-oriented introduction to high-level programming language implementation. It demystifies what goes on within a compiler and stimulates the reader's interest in compiler design, an essential aspect of computer science. Programming language analysis and translation techniques are used in many software application areas.

A Practical Approach to Compiler Construction covers the fundamental principles of the subject in an accessible way. It presents the necessary background theory and shows how it can be applied to implement complete compilers. A step-by-step approach, based on a standard compiler structure is adopted, presenting up-to-date techniques and examples. Strategies and designs are described in detail to guide the reader in implementing a translator for a programming language.

A simple high-level language, loosely based on C, is used to illustrate aspects of the compilation process. Code examples in C are included, together with discussion and illustration of how this code can be extended to cover the compilation of more complex languages. Examples are also given of the use of the flex and bison compiler construction tools. Lexical and syntax analysis is covered in detail together with a comprehensive coverage of semantic analysis, intermediate representations, optimisation and code generation. Introductory material on parallelisation is also included.

Designed for personal study as well as for use in introductory undergraduate and postgraduate courses in compiler design, the author assumes that readers have a reasonable competence in programming in any high-level language.

Table of Contents

Chapter 1. Introduction

The high-level language is the central tool for the development of today’s software. The techniques used for the implementation of these languages are therefore very important. This book introduces some of the practicalities of producing implementations of high-level programming languages on today’s computers. The idea of a compiler, traditionally translating from the high-level language source program to machine code for some real hardware processor, is well known but there are other routes for language implementation.
Des Watson

Chapter 2. Compilers and Interpreters

Before looking at the details of programming language implementation, we need to examine some of the characteristics of programming languages to find out how they are structured and defined.
Des Watson

Chapter 3. Lexical Analysis

It is appropriate to start the details of compiler implementation by considering the lexical analyser. The place of the lexical analyser in the complete compiler has already been discussed in Chap. 2. Because it is the first phase of source code analysis, the format of its input is governed by the specification of the programming language being compiled. The output of the lexical analyser has to satisfy the needs of the next phase of compilation (syntax analysis) and details of this interface will be examined later in this chapter.
Des Watson

Chapter 4. Approaches to Syntax Analysis

The heart of the analysis phase of the compiler is the syntax analyser. It takes a stream of lexical tokens from the lexical analyser and groups them together according to the rules of the language, thus determining the syntactic structure of the compiler’s input. The syntax analyser creates data structures reflecting this syntactic structure and then it is up to later phases of compilation to traverse these structures and finally to generate target code.
Des Watson

Chapter 5. Practicalities of Syntax Analysis

In this chapter we adopt a practical approach to syntax analysis and we look in detail at the two most popular techniques used for the construction of syntax analysers for programming language compilers and similar tools.
Des Watson

Chapter 6. Semantic Analysis and Intermediate Code

The semantic analysis phase of a compiler is the last phase directly concerned with the analysis of the source program. The syntax analyser has produced a syntax tree or some equivalent data structure and the next step is to deal with all those remaining analysis tasks that are difficult or impossible to do in a conventional syntax analyser. These tasks are principally concerned with context-sensitive analysis.
Des Watson

Chapter 7. Optimisation

The generation of high-quality code is a key objective in the development of compilers. It is of course true that a usable compiler can be written with little or no provision for optimisation, but the performance of the generated code may be disappointing. Today’s production compilers can generate code of outstanding quality, normally much better than even handwritten target assembly code produced by an expert.
Des Watson

Chapter 8. Code Generation

The process of code generation takes the intermediate representation generated by the front-end of the compiler, with or without any optimisation performed by the machine-independent optimisation phase, and generates code for the target machine. Writing a good code generator is not easy. There is too much choice. There will be infinitely many ways of translating a piece of intermediate code to target code and there is no standard way of performing the translation. The translation process can involve many different algorithms, all interacting with each other in seemingly unpredictable ways, and ensuring that the code produced is of sufficiently high quality is something of a challenge.
Des Watson

Chapter 9. Implementation Issues

This book has concentrated on a traditional and intuitive view of a compiler as a program to translate from a high-level source language to a low-level target machine language, with a potentially visible intermediate representation between a front-end and a back-end. This form of compiler is in essence specified by the source and target languages and also by the language in which the compiler should be coded. But this book has also stressed that the view of a compiler as a single, monolithic piece of code is not helpful. Instead, regarding it as a collection of phases, at least by separating a front-end from a back-end, is very helpful. These issues become particularly important when considering a strategy for a programming language implementation project.
Des Watson
Additional information