Compiler Design 3e


Author: S Godfrey Winster

ISBN Print Book: 9789388005500

Copy Right Year: 2024

Pages: 520

Binding: Soft Cover

Publisher:  Yes Dee Publishing

SKU: 9789388005500 Category:


This book seeks to provide a clear understanding of the concepts of compiler design. Various phases in the design of compilers are discussed with examples. A detailed explanation of each phase is given with its driving factors (regular expression, context free grammar, parse tree, syntax-directed translations, intermediate code generation, code generation algorithm and optimization techniques). The appendix contains a collection of Question Papers from Anna University which gives students a clear idea on important topics to be covered from the examination point of view.

Key Features

  • Short and precise explanations enable students to understand the concepts clearly.
  • Detailed explanations are given with examples for each and every topic.
  • Problems are solved step-by-step to enable better understanding for learners.

Table of Contents

Chapter 1 Introduction to Compilers

1.1 Translators

1.2 Compilation and Interpretation

1.2.1 Compiler

1.2.2 Interpreter

1.2.3 Assembler

1.3 Language Processors

1.4 The Phases of Compiler

1.4.1 Lexical Analysis

1.4.2 Syntax Analysis

1.4.3 Semantic Analysis

1.4.4 Intermediate Code Generation

1.4.5 Code Optimization

1.4.6 Code Generation

1.4.7 Symbol Table Management

1.4.8 Error Handling

1.4.9 Errors Encountered in Different Phases

1.4.10 Grouping of Phases

1.4.11 Compiler Construction Tools

1.4.12 Programming Language Basics

1.5 Lexical Analysis

1.5.1 Token, Pattern and Lexeme

1.6 Role of Lexical Analyzer

1.6.1 Lexical Errors

1.7 Input Buffering

1.7.1 Buffer Pairs

1.7.2 Sentinels

1.8 Specification of Tokens

1.8.1 Strings and Languages

1.8.2 Operations on Languages

1.8.3 Regular Expressions

1.8.4 Regular Definition

1.9 Recognition of Tokens

1.9.1 Transition Diagrams

1.9.2 Recognition of Reserved Words and Keywords

1.10 Finite Automata

1.11 Regular Expressions to Automata NFA, DFA

1.11.1 Rules for Conversion of Regular Expression to NFA

1.11.2 ε-closure

1.11.3 Sub-set Construction

1.11.4 Direct Method

1.12 Minimization of DFA

1.13 Language for Specifying Lexical Analyzers

1.13.1 Use of Lex

1.13.2 Structure of Lex Programs

1.13.3 Conflict Resolution in Lex

1.13.4 Look ahead Operator

1.13.5 Design of Lexical Analyzer

Points to Remember

Two Mark Questions with Answers

Review Questions

Solved Problems

University Questions



Chapter 2 Syntax Analysis

2.1 Parser

2.1.1 Types of Parser

2.2 Role of Parser

2.2.1 Need for Parser

2.2.2 Error Recovery Strategies

2.3 Grammars

2.4 Context Free Grammar

2.5 Writing a Grammar

2.5.1 Derivations

2.5.2 Leftmost Derivation

2.5.3 Rightmost Derivation

2.5.4 Parse Tree

2.5.5 Yield of Parse Tree

2.5.6 Ambiguity

2.5.7 Eliminating Ambiguity

2.6 Top-down Parsing

2.7 General Strategies

2.8 Recursive Descent  Parser

2.8.1 Predictive Parser / LL(1) Parser

2.8.2 Non-recursive Predictive Parser

2.8.3 Error Recovery in Predictive Parsing

2.8.4 Bottom-up Parsing

2.9 Shift-reduce Parsing

2.10 LR Parsers

2.10.1 Model of LR Parser

2.10.2 LR Parsing Algorithm

2.11 LR (0) Items

2.11.1 LR (0) Parser / SLR (1) Parser

2.11.2 LR (1) Parser / Canonical LR (CLR)

2.12 Introduction to LALR Parser

2.12.1 Operator Precedence Parser

2.13 Error Handling and Error Recovery in Syntax Analyzer

2.14 YACC

2.14.1 Conventions in YACC Productions

2.14.2 Creating YACC Lexical Analyzers with Lex

2.15 Design of Syntax Analyzer for a Sample Language

Points to Remember

Two Mark Questions with Answers

Solved Problems

University Questions


Chapter 3 Intermediate Code Generation

3.1 Syntax-directed Definition (SDD)

3.2 Types of Syntax-directed Definitions

3.2.1 S-attributed Definitions

3.2.2 L-attributed Definitions

3.3 Attribute Grammar

3.3.1 S-attributed Grammar

3.3.2 L-attributed Grammar

3.4 Annotated Parse Tree

3.5 Evaluation Orders for Syntax Directed Definitions

3.6 Bottom-up Evaluation of S-Attribute Definition

3.7 Design of Predictive Translator

3.8 Type Systems

3.9 Specification of Simple Type Checker

3.9.1 Type Checking

3.9.2 Type Expressions

3.10 Equivalence of Type Expressions

3.10.1 Type Expression

3.10.2 Equivalence

3.11 Type Conversions

3.11.1 Types of Conversion

3.11.2 Rules for Type Conversions

3.12 Intermediate Languages

3.12.1 Syntax Tree

3.12.2 Three-address Code

3.13 Declarations

3.14 Translation of Expressions

3.15 Backpatching

Points to Remember

Two Mark Questions with Answers

Solved Problems

University Questions


Chapter 4 Run-Time Environment and Code Generation

4.1 Runtime Environment

4.2 Source Language Issues

4.2.1 Scope and Lifetime of Variables

4.2.2 Procedures

4.2.3 Activation Trees

4.2.4 Control Stacks

4.2.5 Scope of Declarations

4.2.6 Binding of Names

4.3 Storage Organization

4.3.1 Sub-division of Runtime Memory

4.4 Storage Allocation Strategies

4.4.1 Static Allocation

4.4.2 Dynamic Allocation

4.4.3 Storage Allocation in Fortran

4.5 Parameter Passing

4.6 Symbol Table

4.6.1 Information Associated with Variables

4.6.2 Implementation

4.7 Code Generator

4.7.1 Introduction

4.7.2 Issues in the Design of a Code Generator

4.8 Basic Block and Flow Graphs

4.8.1 Partitioning Three-address Statements into Basic Block

4.8.2 Transformations on Basic Block

4.8.3 Next-use Information

4.8.4 Flow Graph

4.8.5 Loops

4.9 Design of a Simple Code Generator

4.9.1 Register and Address Descriptors

4.9.2 Code Generation Algorithm

4.10 Optimal Code Generation for Expressions

4.10.1 Considerations for Optimal Code Generation

4.10.2 Algorithm for Optimal Code Generation for Expressions

4.10.3 Ershov Number

4.10.4 Generating Code from Labeled Expression Trees

4.11 Dynamic Programming Code Generation

4.11.1 Contiguous Evaluation

4.11.2 The Dynamic Programming Algorithm

4.12 Register Allocation and Register Assignment

4.12.1 Global Register Allocation

4.12.2 Register Assignment for Outer Loops

4.12.3 Register Allocation by Graph Coloring

Points to Remember

Two Mark Questions with Answers

Solved Problems

University Questions


Chapter 5 Code Optimization

5.1 Optimization

5.2 Principal Sources of Optimization

5.2.1 Function Preserving Transformations

5.2.2 Loop Optimizations

5.3 Peep-hole Optimizations

5.3.1 Redundant Instruction Elimination

5.3.2 Eliminating Unreachable Code

5.3.3 Flow of Control Optimizations

5.3.4 Algebraic Simplification

5.3.5 Reduction in Strength

5.3.6 Use of Machine Idioms

5.4 DAG

5.5 Optimization of Basic Blocks

5.5.1 DAG Representation of Basic Block

5.6 Global Data flow Analysis

5.6.1 Constraints

5.6.2 Reaching Definitions

5.6.3 Live Variable Analysis

5.6.4 Available Expressions

5.7 Efficient Data-flow Algorithms

5.7.1 Iterative Algorithm for Reaching Definitions

5.7.2 Iterative Algorithm to Compute Live-variables

5.7.3 Iterative Algorithm to Compute Available Expressions

5.7.4 Iterative Algorithm for General Frameworks

5.8 Recent Trends in Compiler Design

5.9 Loops

5.9.1 Dominators

5.9.2 Immediate Dominator

5.9.3 Dominator Tree

5.9.4 Back Edges

5.9.5 Reducibility

5.10 Depth First Ordering

5.10.1 Depth of Flow Graph

5.11 Natural Loops

Points to Remember

Two Mark Questions with Answers

Solved Problems

University Questions

Appendix A Solved University Question Papers

Appendix B University Question Papers


About the Author

Godfrey Winster S, is Associate Professor, department of Computing Technologies, SRM Institute of Science and Technology, Kattankulathur, Chengalpattu. He completed his Doctorate of Philosophy in Web Mining from Anna University. He has published numerous papers in international journals and conferences. He is a certified EMC2 Academic Associate in Cloud Infrastructure and Services, and Data Science and Big Data Analytics. He is also an active member in professional bodies like IEEE, CSI, ISTE, CSTA and IACSIT. He is also a reviewer for various International journals like JWS, JDCTA, JCIT, etc.

New Product Tab

Here's your new product tab.