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).