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
References
