book

Compiler Construction

by K.V.N Sunitha

June 2013

Beginner to intermediate

466 pages

10h 50m

English

Pearson India

Read now

Unlock full access

1.1 What Is a Compiler1.1.1 History 1.1.2 What Is the Challenge?1.2 Compiler vs. Interpreter1.3 Typical Language Processing System1.3.1 Preprocessor1.3.2 Loader/Linker1.4 Design Phases1.4.1 The Lexical Analysis 1.4.2 Intermediate Code Generator1.4.3 Code Optimizer1.4.4 Target Code Generator1.4.5 Symbol Table Manager and Error Handler1.4.6 Compiler Front End1.4.7 Compiler Back End1.5 Design Passes1.6 Retargeting1.7 Bootstrapping1.7.1 T-diagram1.7.2 Advantages of Bootstrapping1.8 Compiler Design Tools1.9 Modern Compilers—Design Need for Compilers1.10 Application of Compiler Design PrinciplesSolved ProblemsSummaryFill in the BlanksObjective Question Bank ExercisesKey for Fill in the Blanks Key for Objective Question Bank
2.1 Introduction2.2 Advantages of Separating Lexical Analysis from Syntax Analysis2.3 Secondary Tasks of a Lexical Analyzer2.4 Error Recovery in Lexical Analysis2.5 Tokens, Patterns, Lexemes2.6 Strategies for Implementing a Lexical Analyzer2.7 Input Buffering2.8 Specification of Tokens2.8.1 Operations on Language2.9 Recognition of Tokens2.10 Finite State Machine2.10.1 Finite Automaton Model2.10.2 Properties of the Transition Function "S"2.10.3 Transition Diagram2.10.4 Transition Table2.10.5 Language Acceptance2.10.6 Finite Automation Is of Two Types2.10.7 Deterministic Finite Dutomaton (DFA)2.10.8 Nondeterministic Finite Automaton (NFA)2.10.9 Equivalence of DFAs andNFAs2.10.10 Converting NFA (MN) to DFA (MD)—Subset Construction2.10.11 NFA with Epsilon (ε)-Transitions2.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 DFA2.10.16 Comparison Method for Testing Equivalence of Two FAs 2.10.17 Reduction of the Number of States in FA2.10.18 Minimization of DFA2.10.19 Minimization of DFA Using the Myhill Nerode Theorem2.11 Lex Tool: Lexical Analyzer Generator2.11.1 IntroductionSolved ProblemsSummary Fill in the BlanksObjective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank
3.1 Introduction3.2 Types of Grammars—Chomsky Hierarchy3.3 Grammar Representations3.4 Context Free Grammars3.5 Derivation of CFGs3.6 Language Defined by Grammars3.6.1 Leftmost and Rightmost Derivation3.6.2 Derivation Tree3.6.3 Equivalence of Parse Trees and Derivations3.7 Left Recursion3.8 Left-Factoring3.9 Ambiguous Grammar3.10 Removing Ambiguity3.11 Inherent Ambiguity3.12 Non-context Free Language Constructs3.13 Simplification of Grammars3.14 Applications of CFGSolved ProblemsSummaryFill in the BlanksObjective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank
4.1 Introduction4.2 Error Handling in Parsing4.2.1 Panic Mode Error Recovery4.2.2 Phrase Level Recovery4.2.3 Error Productions4.2.4 Global Correction 4.3 Types of Parsers4.3.1 Universal Parsers 4.3.2 Top-Down Parsers (TDP4.3.3 Bottom-Up Parsers4.4 Types of Top-Down Parsers4.4.1 Brute Force Technique4.5 Predictive Parsers4.5.1 Recursive Descent Parser4.5.2 Nonrecursive Descent Parser—LL(1) Parser4.5.3 AIgorithm for LL(1) Parsing4.5.4 First(α), Where a Is Any String of Grammar Symbols4.5.5 Follow (A) Where 'A'is a Nonterminal4.6 Construction of Predictive Parsing Tables4.7 LL(1) Grammar4.8 Error Recovery in Predictive ParsingSolved ProblemsSummaryFill in the BlanksObjective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank

5.1 Bottom-Up Parsing5.2 Handle5.3 Why the Name SRParser5.4 Types of Bottom-Up Parsers5.5 Operator Precedence Parsing5.5.1 Precedence Relations5.5.2 Recognizing Handles5.5.3 Parsing Algorithm for Operator Precedence Parser5.5.4 Construction of the Precedence Relation Table5.5.5 Mechanical Method of Constructing Operator Precedence Table5.5.6 Calculating Operator Precedence Relation <..>5.5.7 Error Recovery in Operator Precedence Parser5.5.8 Procedure for Converting Precedence Relation Table to Precedence Function Table5.6 LR Grammar5.7 LR Parsers5.8 LR Parsing Algorithm5.8.1 Task of LR Parser: Detect Handle and Reduce Handle5.9 Construction of the LR Parsing Table5.9.1 Augmented Grammar5.9.2 LR(0) Item5.9.3 Closure (I)5.9.4 Goto(I,X) 5.9.5 Creating Canonical Collection "C" of LR(O) Items5.9.6 Construction of DFA with a Set of Items5.10 LR(0) Parser5.10.1 Advantages of the LR(0) Parser5.10.2 Disadvantages of the LR(0) Parser5.10.3 LR(0) Grammar5.10.4 Conflicts in Shift-Reduce Parsing5.11 SLR(l) Parser5.12 Canonical LR(1) Parsers CLR(1)/LR(1)5.12.1 Closure (I) Where I Is a Set ofLR(l) Items5.12.2 Goto(I,X)5.12.3 Creating Canonical Collection "C" of LR(1) Items5.12.4 Constructing CLR(l) Parsing Table5.12.5 CLR(l) Grammar5.13 LALR(1) Parser5.14 Comparison of Parsers: Top-Down Parser vs. Bottom-Up Parser5.15 Error Recovery in LR Parsing5.16 Parser Construction with Ambiguous GrammarsSolved ProblemsSummaryFill in the BlanksObjective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank
6.1 Introduction6.2 Attributes for Grammar Symbols6.3 Writing Syntax-Directed Translation6.4 Bottom-Up Evaluation of SDT6.5 Creation of the Syntax Tree6.6 Directed Acyclic Graph (DAG)6.7 Types of SDTs6.8 S-Attnbuted Definition6.9 Top-Down Evaluation of S-Attributed Grammar6.10 L-Attributed Definition6.11 Converting L-Attributed to S-Attributed Definition6.12 YACCSolved ProblemsSummaryFill in the BlanksObjective Question BankKey for Fill in the BlanksKey for Objective Question Bank
7.1 Introduction7.2 Type Systems7.3 Type Expressions7.4 Design of Simple Type Checker7.5 Type Checking of Expressions7.6 Type Checking of Statements7.7 Type Checking of Functions7.8 Equivalence of Type Expressions7.8.1 Structural Equivalence7.8.2 Encoding of Type Expressions7.8.3 Name Equivalence7.8.4 Type Graph7.9 Type Conversion7.10 Overloading of Functions and Operators7.11 Polymorphic FunctionsSolved ProblemsSummaryFill in the BlanksObjective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank
8.1 Introduction8.2 Intermediate Languages8.2.1 Syntax Trees8.2.2 Directed Acyclic Graph (DAG)8.2.3 Postfix Notation8.2.4 Three Address Code8.3 Types of Three Address Statements8.4 Representation of Three Address Code8.4.1 Quadruple8.4.2 Triple8.4.3 Indirect Triples8.4.4 Comparison of Representations8.5 Syntax-Directed Translation into Three Address Code8.5.1 Assignment Statement8.5.2 Addressing Array Elements8.5.3 Logical Expression8.5.4 Control StatementsSolved Problems SummaryFill in the Blanks Objective Question BankExercisesKey for Fill in the BlanksKey for Objective Question Bank
9.1 Introduction9.2 Symbol Table Entries9.3 Operations on the Symbol Table9.4 Symbol Table Organization9.5 Non-block Structured Language9.5.1 Linear List in Non-block Structured Language 9.5.2 Linked List or Self-organizing Tables9.5.3 Hierarchical List 9.5.4 Hash Tables9.6 Block Structured Language9.6.1 Stack Symbol Tables9.6.2 Stack-Implemented Tree-structured Symbol Tables9.6.3 Stack-Implemented Hash-structured Symbol Table SummaryFill in the BlanksObjective Question Bank ExercisesKey for Fill in the BlanksKey for Objective Question Bank
10.1 Introduction10.2 Where and How to Optimize10.3 Procedure to Identify the Basic Blocks10.4 Flow Graph10.5 DAG Representation of Basic Block10.6 Construction of DAG10.6.1 Algorithm for Construction of DAG10.6.2 Application of DAG10.7 Principle Source of Optimization10.8 Function-Preserving Transformations10.8.1 Common Sub-expression Elimination10.8.2 Copy Propagation10.8.3 Dead Code Elimination10.8.4 Constant Propagation10.9 Loop Optimization10.9.1 A Loop Invariant Computation 10.9.2 Induction Variables 10.10 Global Flow Analysis10.10.1 Points and Paths 10.10.2 Reaching Definition 10.10.3 Use Definition Chains 10.10.4 Live Variable Analysis10.10.5 Definition Use Chains10.10.6 Data Flow Analysis of Structured Programs 10.10.7 Representation of Sets 10.10.8 Iterative Algorithm for Re aching Definition 10.11 Machine-Dependent Optimization10.11.1 Redundant Loads and Stores10.11.2 Algebraic Simplification10.11.3 Dead Code Elimination 10.11.4 Flow-of -Control Optimization10.11.5 Reduction in Strength10.11.6 Use of Machine IdiomsSolved ProblemsSummaryFill in the Blanks Objective Question Bank Exercises Key for Fill in the Blanks Key for Objective Question Bank
11.1 Introduction11.2 Issues in the Design of a Code Generator11.2.1 Input to the Code Generator11.2.2 Target Programs11.2.3 Memory Management11.2.4 Instruction Selection11.2.5 Register Allocation11.2.6 Choice of Evaluation Order 11.3 Approach to Code Generation11.3.1 Algorithm for Code Generation Using Three Address Code11.4 Instruction Costs11.5 Register Allocation and Assignment11.5.1 Fixed Registers11.5.2 Global Register Allocation11.5.3 Usage Count11.5.4 Register Assignment for Outer Loop11.5.5 Graph Coloring for Register Assignment11.6 Code Generation Using DAGSolved ProblemsSummaryFill in the Blanks Objective Question BankExercisesKey for Fill in the Blanks Key for Objective Question Bank

Content preview from Compiler Construction

Preface

Every computing device built today needs a compiler. It enables us to use a programming language by translating programs into machine code. It is essential for a good programmer to understand how a compiler works. The study of compilers entails an analysis of theoretical ideas in translation and optimization with sparse resources. The purpose of this book is to cover the underlying concepts and techniques used in compiler design. Some of these techniques can also be used in software design and natural language processing.

Intended as an introductory reading material in the subject, the book uses enough examples and algorithms to effectively explain the various phases in compiler design, besides covering the design of each component of ...