Compiler Construction

Compiler Construction

by K.V.N Sunitha
Released June 2013
Publisher(s): Pearson India
ISBN: 9789332520134

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Designed for an introductory course, this text encapsulates the topics essential for a freshman course on compilers. The book provides a balanced coverage of both theoretical and practical aspects. The text helps the readers understand the process of compilation and proceeds to explain the design and construction of compilers in detail. The concepts are supported by a good number of compelling examples and exercises.

Table of contents

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

Product information

  • Title: Compiler Construction
  • Author(s): K.V.N Sunitha
  • Release date: June 2013
  • Publisher(s): Pearson India
  • ISBN: 9789332520134