Compiler Construction

Cover
Dedication
Brief Contents
Contents
Preface
Acknowledgements
Chapter 1 : Introduction
	1.1 What is a Compiler?
		1.1.1 History
		1.1.2 What is the Challenge?
	1.2 Compiler vs. Interpreter
	1.3 Typical Language-Processing System
		1.3.1 Preprocessor
		1.3.2 Loader/Linker
	1.4 Design Phases
		1.4.1 The Lexical Analysis
		1.4.2 Intermediate Code Generator
		1.4.3 Code Optimizer
		1.4.4 Target Code Generator
		1.4.5 Symbol Table Manager and Error Handler
		1.4.6 Compiler Front End
		1.4.7 Compiler Back End
	1.5 Design of Passes
	1.6 Retargeting
	1.7 Bootstrapping
		1.7.1 T-diagram
		1.7.2 Advantages of Bootstrapping
	1.8 Compiler Design Tools
	1.9 Modern Compilers—Design Need for Compilers
	1.10 Application of Compiler Design Principles
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 2 : Lexical Analyzer
	2.1 Introduction
	2.2 Advantages of Separating Lexical Analysis from Syntax Analysis
	2.3 Secondary Tasks of a Lexical Analyzer
	2.4 Error Recovery in Lexical Analysis
	2.5 Tokens, Patterns, Lexemes
	2.6 Strategies for Implementing a Lexical Analyzer
	2.7 Input Buffering
	2.8 Specification of Tokens
		2.8.1 Operations on Language
	2.9 Recognition of Tokens
	2.10 Finite State Machine
		2.10.1 Finite Automaton Model
		2.10.2 Properties of the Transition Function “δ”
		2.10.3 Transition Diagram
		2.10.4 Transition Table
		2.10.5 Language Acceptance
		2.10.6 Finite Automation is of Two Types
		2.10.7 Deterministic Finite Dutomaton (DFA)
		2.10.8 Nondeterministic Finite Automaton (NFA)
		2.10.9 Equivalence of DFAs and NFAs
		2.10.10 Converting NFA (MN) to DFA (MD)—Subset Construction
		2.10.11 NFA with Epsilon (ε)-Transitions
		2.10.12 Epsilon Closure (ε-closure)
		2.10.13 Eliminating ε-Transitions
		2.10.14 Converting NFA with ε-Transition to NFA Without ε-Transition
		2.10.15 Converting NFA with ε-Transition to DFA
		2.10.16 Comparison Method for Testing Equivalence of Two FAs
		2.10.17 Reduction of the Number of States in FA
		2.10.18 Minimization of DFA
		2.10.19 Minimization of DFA Using the Myhill Nerode Theorem
	2.11 Lex Tool: Lexical Analyzer Generator
		2.11.1 Introduction
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 3 : Syntax Definition – Grammars
	3.1 Introduction
	3.2 Types of Grammars—Chomsky Hierarchy
	3.3 Grammar Representations
	3.4 Context Free Grammars
	3.5 Derivation of CFGs
	3.6 Language Defined by Grammars
		3.6.1 Leftmost and Rightmost Derivation
		3.6.2 Derivation Tree
		3.6.3 Equivalence of Parse Trees and Derivations
	3.7 Left Recursion
	3.8 Left-Factoring
	3.9 Ambiguous Grammar
	3.10 Removing Ambiguity
	3.11 Inherent Ambiguity
	3.12 Non-context Free Language Constructs
	3.13 Simplification of Grammars
	3.14 Applications of CFG
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 4 : Syntax Analysis—Top-Down Parsers
	4.1 Introduction
	4.2 Error Handling in Parsing
		4.2.1 Panic Mode Error Recovery
		4.2.2 Phrase Level Recovery
		4.2.3 Error Productions
		4.2.4 Global Correction
	4.3 Types of Parsers
		4.3.1 Universal Parsers
		4.3.2 Top-Down Parsers (TDP)
		4.3.3 Bottom-Up Parsers
	4.4 Types of Top-Down Parsers
		4.4.1 Brute Force Technique
	4.5 Predictive Parsers
		4.5.1 Recursive Descent Parser
		4.5.2 Nonrecursive Descent Parser—LL(1) Parser
		4.5.3 Algorithm for LL(1) Parsing
		4.5.4 First(α), Where α is Any String of Grammar Symbols
		4.5.5 Follow(A) Where ‘A’ is a Nonterminal
	4.6 Construction of Predictive Parsing Tables
	4.7 LL(1) Grammar
	4.8 Error Recovery in Predictive Parsing
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 5 : Bottom-Up Parsers
	5.1 Bottom-Up Parsing
	5.2 Handle
	5.3 Why the Name SR Parser
	5.4 Types of Bottom-Up Parsers
	5.5 Operator Precedence Parsing
		5.5.1 Precedence Relations
		5.5.2 Recognizing Handles
		5.5.3 Parsing Algorithm for Operator Precedence Parser
		5.5.4 Construction of the Precedence Relation Table
		5.5.5 Mechanical Method of Constructing Operator Precedence Table
		5.5.6 Calculating Operator Precedence Relation ⋖ ⋗ =
		5.5.7 Error Recovery in Operator Precedence Parser
		5.5.8 Procedure for Converting Precedence Relation Table to Precedence Function Table
	5.6 LR Grammar
	5.7 LR Parsers
	5.8 LR Parsing Algorithm
		5.8.1 Task of LR Parser: Detect Handle and Reduce Handle
	5.9 Construction of the LR Parsing Table
		5.9.1 Augmented Grammar
		5.9.2 LR(0) Item
		5.9.3 Closure(I)
		5.9.4 Goto(I,X)
		5.9.5 Creating Canonical Collection “C” of LR(0) Items
		5.9.6 Construction of DFA with a Set of Items
	5.10 LR(0) Parser
		5.10.1 Advantages of the LR(0) Parser
		5.10.2 Disadvantages of the LR(0) Parser
		5.10.3 LR(0) Grammar
		5.10.4 Conflicts in Shift-Reduce Parsing
	5.11 SLR(1) Parser
	5.12 Canonical LR(1) Parsers CLR(1)/LR(1)
		5.12.1 Closure(I) Where I is a Set of LR(1) Items
		5.12.2 Goto(I,X)
		5.12.3 Creating Canonical Collection “C” of LR(1) Items
		5.12.4 Constructing CLR(1) Parsing Table
		5.12.5 CLR(1) Grammar
	5.13 LALR(1) Parser
	5.14 Comparison of Parsers: Top-Down Parser vs.Bottom-Up Parser
	5.15 Error Recovery in LR Parsing
	5.16 Parser Construction with Ambiguous Grammars
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 6 : Syntax-Directed Translation
	6.1 Introduction
	6.2 Attributes for Grammar Symbols
	6.3 Writing Syntax-Directed Translation
	6.4 Bottom-Up Evaluation of SDT
	6.5 Creation of the Syntax Tree
	6.6 Directed Acyclic Graph (DAG)
	6.7 Types of SDTs
	6.8 S-Attributed Definition
	6.9 Top-Down Evaluation of S-Attributed Grammar
	6.10 L-Attributed Definition
	6.11 Converting L-Attributed to S-Attributed Definition
	6.12 YACC
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 7 : Semantic Analysis
	7.1 Introduction
	7.2 Type Systems
	7.3 Type Expressions
	7.4 Design of Simple Type Checker
	7.5 Type Checking of Expressions
	7.6 Type Checking of Statements
	7.7 Type Checking of Functions
	7.8 Equivalence of Type Expressions
		7.8.1 Structural Equivalence
		7.8.2 Encoding of Type Expressions
		7.8.3 Name Equivalence
		7.8.4 Type Graph
	7.9 Type Conversion
	7.10 Overloading of Functions and Operators
	7.11 Polymorphic Functions
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 8 : Intermediate Code Generation
	8.1 Introduction
	8.2 Intermediate Languages
		8.2.1 Syntax Trees
		8.2.2 Directed Acyclic Graph (DAG)
		8.2.3 Postfix Notation
		8.2.4 Three Address Code
	8.3 Types of Three Address Statements
	8.4 Representation of Three Address Code
		8.4.1 Quadruple
		8.4.2 Triple
		8.4.3 Indirect Triples
		8.4.4 Comparison of Representations
	8.5 Syntax-Directed Translation into Three Address Code
		8.5.1 Assignment Statement
		8.5.2 Addressing Array Elements
		8.5.3 Logical Expression
		8.5.4 Control Statements
			Solved Problems
			Summary
			Fill in the Blanks
			Objective Question Bank
			Exercises
			Key for Fill in the Blanks
			Key for Objective Question Bank
Chapter 9 : Symbol Table
	9.1 Introduction
	9.2 Symbol Table Entries
	9.3 Operations on the Symbol Table
	9.4 Symbol Table Organization
	9.5 Non-block Structured Language
		9.5.1 Linear List in Non-block Structured Language
		9.5.2 Linked List or Self-organizing Tables
		9.5.3 Hierarchical List
		9.5.4 Hash Tables
	9.6 Block Structured Language
		9.6.1 Stack Symbol Tables
		9.6.2 Stack-Implemented Tree-structured Symbol Tables
		9.6.3 Stack-Implemented Hash-Structured Symbol Table
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Chapter 10 : Code Optimization
	10.1 Introduction
	10.2 Where and How to Optimize
	10.3 Procedure to Identify the Basic Blocks
	10.4 Flow Graph
	10.5 DAG Representation of Basic Block
	10.6 Construction of DAG
		10.6.1 Algorithm for Construction of DAG
		10.6.2 Application of DAG
	10.7 Principle Source of Optimization
	10.8 Function-Preserving Transformations
		10.8.1 Common Sub-expression Elimination
		10.8.2 Copy Propagation
		10.8.3 Dead Code Elimination
		10.8.4 Constant Propagation
	10.9 Loop Optimization
		10.9.1 A Loop Invariant Computation
		10.9.2 Induction Variables
	10.10 Global Flow Analysis
		10.10.1 Points and Paths
		10.10.2 Reaching Definition
		10.10.3 Use Definition Chains
		10.10.4 Live Variable Analysis
		10.10.5 Definition Use Chains
		10.10.6 Data Flow Analysis of Structured Programs
		10.10.7 Representation of Sets
		10.10.8 Iterative Algorithm for Reaching Definition
	10.11 Machine-Dependent Optimization
		10.11.1 Redundant Loads and Stores
		10.11.2 Algebraic Simplification
		10.11.3 Dead Code Elimination
		10.11.4 Flow-of-Control Optimization
		10.11.5 Reduction in Strength
		10.11.6 Use of Machine Idioms
			Solved Problems
			Summary
			Fill in the Blanks
			Objective Question Bank
			Exercises
			Key for Fill in the Blanks
			Key for Objective Question Bank
Chapter 11 : Code Generation
	11.1 Introduction
	11.2 Issues in the Design of a Code Generator
		11.2.1 Input to the Code Generator
		11.2.2 Target Programs
		11.2.3 Memory Management
		11.2.4 Instruction Selection
		11.2.5 Register Allocation
		11.2.6 Choice of Evaluation Order
	11.3 Approach to Code Generation
		11.3.1 Algorithm for Code Generation Using Three Address Code
	11.4 Instruction Costs
	11.5 Register Allocation and Assignment
		11.5.1 Fixed Registers
		11.5.2 Global Register Allocation
		11.5.3 Usage Count
		11.5.4 Register Assignment for Outer Loop
		11.5.5 Graph Coloring for Register Assignment
	11.6 Code Generation Using DAG
		Solved Problems
		Summary
		Fill in the Blanks
		Objective Question Bank
		Exercises
		Key for Fill in the Blanks
		Key for Objective Question Bank
Recommended Readings and Websites
Index