Compiler Design (with CD)

The book commences with an overview of system software and briefly describes the evolution, design, and implementation of compilers. Detailed explanation of the various phases involved in the design of a compiler such as lexical analysis, syntax analysis, runtime storage organization, intermediate code generation, optimization of code, and final code generation is provided in various chapters of the book. The last chapter describes in brief all the frequently used compiler writing tools with examples and program codes. Written in a lucid manner, the book provides numerous examples, algorithms, pseudocodes and C codes in support of the text. Chapter-end exercises, appendices and the companion CD are provided to help readers revise and practice the learnt concepts.

Table of Contents:
Preface; In the CD; Features of the Book; Brief Contents; 1. OVERVIEW OF COMPUTER HARDWARE AND SYSTEM SOFTWARE; 1.1 Introduction; 1.2 Computer Hardware and Types of System Software; 1.2.1 Hardware; 1.2.2 Overview of System Software; 1.3 Man-machine Communication Spectrum; 1.3.1 Machine Language; 1.3.2 Assembly Language; 1.3.3 High-level Language; 1.3.4 User-level Language; 1.3.5 Natural Language; 1.3.6 Interpreted vs Compiled Languages; 2. INTRODUCTION TO COMPILERS; 2.1 Introduction; 2.2 Theory of Computer Languages; 2.2.1 Natural Languages vs Formal Languages; 2.2.2 Language and Grammar; 2.2.3 Notations and Conventions; 2.2.4 Hierarchy of Formal Languages; 2.3 Design of a Language; 2.3.1 Features of a Good Language; 2.3.2 Representation of Languages; 2.3.3 Grammar of a Language; 2.4 Evolution of Compilers; 2.4.1 History of Compilers; 2.4.2 Development of Compilers; 2.5 Stages of Compilation; 2.5.1 Lexical Analysis; 2.5.2 Syntactic Analysis; 2.5.3 Semantic Analysis; 2.5.4 Intermediate Code Generation; 2.5.5 Code Optimization; 2.5.6 Code Generation; 2.5.7 Symbol Table Management; 2.5.8 Error Management; 3. LEXICAL ANALYSIS; 3.1 Introduction; 3.2 Alphabets and Tokens in Computer Languages; 3.2.1 Tokens and Their Structure; 3.2.2 Operators on Strings and Languages; 3.3 Representation of Tokens and Regular Expression; 3.3.1 Representation of Tokens; 3.3.2 Regular Expression; 3.3.3 Regular Definitions; 3.3.4 Regular Grammar and Regular Expressions; 3.4 Token Recognition and Finite State Automata; 3.4.1 Recognition of Tokens; 3.4.2 Finite Automata; 3.5 Implementation; 3.5.1 Input Buffering; 3.5.2 Design of Data Structures; 3.5.3 States and Event Processing; 3.5.4 Code Development; 3.5.5 Lexical Analysis Tool; 3.6 Error Recovery; 4. SYNTAX ANALYSIS; 4.1 Introduction; 4.2 Context-free Grammar and Structure of Language; 4.2.1 Structure of a Language; 4.2.2 Why Is Context-free Grammar Used for Syntax Checking; 4.2.3 Representations of Grammar and Examples; 4.2.4 Limitations of Context-free Grammar; 4.2.5 Ambiguous Grammar; 4.3 Parser and its Types; 4.3.1 Role of Parser; 4.3.2 Issues in Designing a Parser; 4.4 Top-down Parser; 4.4.1 Recursive Grammar and Difficulties in its Implementation; 4.4.2 Recursive Descent Parser; 4.4.3 Predictive Parser; 4.5 Bottom-up Parser; 4.5.1 Simple Stack-based Parser; 4.5.2 Operator Grammar and Parser; 4.5.3 LR Parser; 4.5.4 Parsers Handling Ambiguous Grammar; 4.6 Implementation; 4.6.1 Design of Data Structure; 4.6.2 Predictive Parser; 4.6.3 SLR Parser; 4.7 Parser Generator Tool (Yacc); 4.7.1 Structure of Yacc Specification; 4.7.2 Parser Generation; 4.7.3 Grammar Specification; 4.7.4 YACC Program Compilation; 4.7.5 Linking Yacc and Lex; 4.8 Error Handling; 4.8.1 Categories of Error; 4.8.2 Error Location; 4.8.3 Error Recovery; 4.8.4 Error Reporting; 5. RUN-TIME STORAGE ORGANIZATION; 5.1 Introduction; 5.2 Scope and Lifetime of Variables; 5.2.1 Scope of Variables; 5.2.2 Persistence of Variables; 5.3 Symbol Table; 5.3.1 Information Associated with Symbols; 5.3.2 Data Structure for Symbol Table; 5.4 Storage Allocation; 5.4.1 Static Allocation; 5.4.2 Dynamic Allocation; 5.5 Access to Non-local Names from Stack; 5.6 Heap Allocation; 5.6.1 Hierarchical Organization of Memory; 5.6.2 Optimization in Memory Usage; 5.6.3 Implicit and Explicit Memory Allocation Request; 5.6.4 Memory Allocation Strategies; 5.7 Garbage Collection; 5.7.1 Performance Factors; 5.7.2 Role of Object References; 5.7.3 Mark-and-Sweep Collectors; 6. INTERMEDIATE CODE GENERATION; 6.1 Introduction; 6.2 Need for Intermediate Code; 6.3 Types of Intermediate Code; 6.3.1 Syntax Trees; 6.3.2 Polish Notation; 6.3.3 Three-address Code; 6.4 Representations of All Language Constructs by Three-address Code; 6.5 Grammar Symbols and Attributes; 6.5.1 Synthesized Attributes; 6.5.2 Inherited Attributes; 6.6 Semantic Analysis; 6.6.1 Type Checking; 6.6.2 Strictly Typed Languages; 6.6.3 Operator Overloading and Function Overloading; 6.7 Semantic Routines for Intermediate Code Generation; 6.7.1 Declarative Statements; 6.7.2 IC Generation for Expressions and Assignment Statement; 6.7.3 IC Generation for Control Statements; 7. OPTIMIZATION; 7.1 Introduction; 7.1.1 Need for Optimization; 7.1.2 Objectives of Optimization; 7.1.3 Places of Optimization; 7.1.4 Performance Factors Deciding the Running Program; 7.2 Hints on Writing Optimized Code at User Level; 7.2.1 Restricted Usage of Local Variable and Parameter Passing; 7.2.2 Usage of Switch-case Statement; 7.2.3 Accessing Memory Elements; 7.2.4 Usage of Constructor in C++; 7.3 Construction of Basic Blocks and Processing; 7.3.1 Basic Blocks; 7.3.2 Linking of Basic Blocks; 7.4 Data-flow Analysis Using FlowGraph; 7.4.1 Reachable Definitions; 7.5 Data-flow Equations for Blocks with Backward Flow Control; 7.5.1 Computing Definitions; 7.5.2 Available Expression; 7.5.3 Live Variables; 7.6 Principal Sources of Optimization and Transformations; 7.6.1 Identification of Common Subexpression and Elimination; 7.6.2 Compile Time Evaluation; 7.6.3 Copy Propagation; 7.6.4 Dead Code Elimination; 7.7 Alias; 7.8 Procedural Optimization; 7.8.1 Recursive vs Iterative Procedure; 7.8.2 Inlining Function; 7.9 Loops in Flow Graphs; 7.9.1 Dominator; 7.9.2 Detection of Loop; 7.9.3 Reducible Graph; 7.10 Loop Optimization; 7.10.1 Loop-invariant Computations; 7.10.2 Code Motion; 7.10.3 Index Variable Elimination and Strength Reduction; 8. CODE GENERATION; 8.1 Introduction; 8.2 Issues in Code Generation; 8.2.1 Type of Input; 8.2.2 Type of Output; 8.2.3 Selection of Instructions; 8.2.4 Selection of Register; 8.2.5 Order of Evaluation; 8.3 Target Machine Architecture; 8.3.1 Registers; 8.3.2 Memory; 8.3.3 Data Format; 8.3.4 Instruction Format; 8.3.5 Addressing Modes; 8.3.6 Instruction Set; 8.3.7 Input/Output Code Generation; 8.4 Subsequent Use Information; 8.4.1 Computing Subsequent Use of Data; 8.4.2 Storage Compaction for Temporary Names; 8.5 Simple Code Generator; 8.5.1 Register List for Variables; 8.5.2 Code Generation Procedure; 8.5.3 Sample Code Generation for 8086 Family Processor; 8.6 Register Allocation; 8.6.1 Register Allocation across Basic Blocks; 8.6.2 Usage Count of Registers; 8.6.3 Register Assignment to Outer Loops; 8.6.4 Register Reallocation; 8.7 Directed Acyclic Graph Representation of Basic Blocks; 8.8 Code Generation From Intermediate Code; 8.8.1 Code Generation from Quadruple; 8.8.2 Code Generation from Syntax Tree; 8.8.3 Code Generation from Directed Acyclic Graph; 8.8.4 Code Generation from Common Intermediate Language; 8.9 Peephole Optimization; 8.10 Code Scheduling; 8.10.1 Parallelism; 8.10.2 Very Long Instruction Word; 8.10.3 Straight-line Scheduling; 8.10.4 List Scheduling; 8.10.5 Trace Scheduling; 8.10.6 Superblock Scheduling; 8.10.7 Software Pipelining; 9. COMPILER WRITING TOOLS; 9.1 Introduction; 9.2 Lexical Tools; 9.2.1 Types of Scanner Generator Tools; 9.2.2 JavaCC-Tool for Scanner Generator; 9.3 Syntactic Tools; 9.3.1 Accent; 9.3.2 AYacc; 9.3.3 Attribute-logic Engine; 9.3.4 Yacc++; 9.3.5 JavaCC; Appendix A: Parsing C Language using Lex and Yacc; Appendix B: Parsing C Language using JavaCC; Appendix C: Additional Solved Problems; Appendix D: Model Question Papers; Index

About the Author :
K. Muneeswaran is presently the Head of the Department of Computer Science and Engineering at Mepco Schlenk Engineering College, Sivakasi. A PhD from M.S. University, Tirunelveli, Dr Muneeswaran has more than 24 years of teaching experience and has published various national and international level papers in reputed journals. He is also a life member of organizations such as Computer Society of India (CSI) and Indian Society for Technical Education (ISTE).