Preface

Every computing device built today needs a compiler. It enables us to use a programming language by translating programs into machine code. It is essential for a good programmer to understand how a compiler works. The study of compilers entails an analysis of theoretical ideas in translation and optimization with sparse resources. The purpose of this book is to cover the underlying concepts and techniques used in compiler design. Some of these techniques can also be used in software design and natural language processing.

Intended as an introductory reading material in the subject, the book uses enough examples and algorithms to effectively explain the various phases in compiler design, besides covering the design of each component of a compiler in detail. As part of the course, students can implement each phase of a compiler. The programming languages used in the examples are in C. The eleven chapters in the book are organized as explained below:

• Chapter 1 gives an overview of compiler design and covers all the phases in a compiler.
• Chapter 2 covers lexical analysis, formal language theory, regular expressions and finite-state machines and the automated tool LEX.
• Chapter 3 discusses syntax definition. The basic notations and concepts of grammars and languages such as ambiguity, left recursion and left factoring are unraveled. This is useful in the design of parsers.
• Chapter 4 on syntax analysis elaborates on the types of parsing and types of top-down parsers and its design.
• Chapter 5 describes bottom-up parsers and their design. Problems and solution in each design are explained.
• Chapter 6 delineates syntax-directed translation. Methods to perform top-down translation and bottom-up translations are examined.
• Chapter 7 based on semantic analysis provides the main ideas for static type checking, typing rules, type expressions and the design of simple type checker.
• Chapter 8 expounds on intermediate code generation and the translation of different language constructs into their address code. It also elucidates runtime support required for design of compilers and the different storage allocations.
• Chapter 9 analyzes symbol tables. The important functions of a symbol table and symbol table organization for block-structured and non-block structured languages are spelt out in detail.
• Chapter 10 on optimization reveals the various machine-dependent and machine-independent optimization techniques. It also depicts register allocation using graph coloring and data flow equations.
• Chapter 11 rationalizes target code generation, enumerates the methods to design a simple code generator and points out the issues in design.

The problems denoted by asterisks in the examples and exercises have appeared in GATE examinations.