Description
This book seeks to provide a clear understanding of the concepts of compiler design. Various phases in the design of compilers are discussed with examples. A detailed explanation of each phase is given with its driving factors (regular expression, context free grammar, parse tree, syntax-directed translations, intermediate code generation, code generation algorithm and optimization techniques). The appendix contains a collection of Question Papers from Anna University which gives students a clear idea on important topics to be covered from the examination point of view.
Table of Content
Chapter 1 Introduction to Compilers
1.1 Compilation and Interpretation
1.1.1 Compiler
1.1.2 Interpreter
1.1.3 Assembler
1.2 Language Processing System
1.3 Structure of a Compiler
1.3.1 Lexical Analysis
1.3.2 Syntax Analysis
1.3.3 Semantic Analysis
1.3.4 Intermediate Code Generation
1.3.5 Code Optimization
1.3.6 Code Generation
1.3.7 Symbol Table Management
1.3.8 Error Handling
1.4 Errors Encountered in Different Phases
1.4.1 Lexical Errors
1.4.2 Syntactical Errors
1.4.3 Semantical Errors
1.5 Grouping of Phases
1.5.1 Front End
1.5.2 Back End
1.5.3 Passes
1.5.4 Reducing the Number of Passes
1.6 Compiler Construction Tools
1.6.1 Parser Generators
1.6.2 Scanner Generators
1.6.3 Syntax-directed Translation Engines
1.6.4 Automatic Code Generators
1.6.5 Data-flow Analysis Engines
1.6.6 Compiler Construction Toolkits
1.7 Programming Language Basics
1.7.1 Static/Dynamic Distinction
1.7.2 Parameter Passing Mechanisms
1.8 Lexical Analysis
1.8.1 Token, Pattern and Lexeme
1.8.2 Role of Lexical Analyzer
1.8.3 Lexical Errors
1.9 Input Buffering
1.9.1 Buffer Pairs
1.9.2 Sentinels
1.10 Specification of Token
1.10.1 Strings and Languages
1.10.2 Operations on Languages
1.10.3 Regular Expressions
1.10.4 Regular Definition
1.11 Recognition of Tokens
1.11.1 Transition Diagrams
1.11.2 Recognition of Reserved Words and Keywords
1.12 Lex
1.12.1 Use of Lex
1.12.2 Structure of Lex Programs
1.12.3 Conflict Resolution in Lex
1.12.4 Lookahead Operator
1.13 Design of Lexical Analyzer
1.13.1 Structure of Generated Analyzer
1.13.2 Pattern Matching based on NFAs
1.13.3 DFAs for Lexical Analyzers
1.13.4 Implementing Lookahead Operator
1.14 Finite Automata
1.15 Regular Expressions to DFA
1.15.1 Rules for Conversion of Regular Expression to NFA
1.15.2 ε-closure
1.15.3 Sub-set Construction
1.15.4 Direct Method
1.16 Minimization of DFA
Points to remember
Two Mark Questions with Answers
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.3 Error Recovery Strategies
2.3.1 Panic Mode Recovery
2.3.2 Phrase Level Recovery
2.3.3 Error Production
2.3.4 Global Correction
2.4 Grammars
2.4.1 Context Free Grammar
2.4.2 Writing a Grammar
2.5 Derivations
2.5.1 Leftmost Derivation
2.5.2 Rightmost Derivation
2.6 Parse Tree
2.6.1 Yield of Parse Tree
2.7 Ambiguity
2.7.1 Eliminating Ambiguity
2.8 Top-down Parsing
2.8.1 General Strategies
2.8.2 Recursive Descent Parser
2.8.3 Predictive Parser / LL(1) Parser
2.8.4 Non-recursive Predictive Parser
2.8.5 Error Recovery in Predictive Parsing
2.9 Bottom-up Parsing
2.9.1 Handles
2.9.2 Handle Pruning
2.9.3 Shift-reduce Parsing
2.10 LR Parsers
2.10.1 Model of LR Parser
2.10.2 LR Parsing Algorithm
2.10.3 LR(0) Items
2.10.4 LR(0) Parser / SLR(1) Parser
2.10.5 LR(1) Parser / Canonical LR (CLR)
2.10.6 Introduction to LALR Parser
2.10.7 Operator Precedence Parser
2.11 Error Handling and Error Recovery in Syntax Analyzer
2.12 YACC
2.12.1 Conventions in YACC Productions
2.12.2 Creating YACC Lexical Analyzers with Lex
2.13 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.5.1 Bottom-up Evaluation of S-Attribute Definition
3.6 Design of Predictive Translator
3.7 Intermediate Languages
3.7.1 Syntax Tree
3.7.2 Three-address Code
3.8 Declarations
3.9 Translation of Expressions
3.10 Specification of Simple Type Checker
3.10.1 Type Systems
3.10.2 Type Checking
3.10.3 Type Expressions
3.11 Equivalence of Type Expressions
3.11.1 Type Expression
3.11.2 Equivalence
3.12 Type Conversions
3.12.1 Types of Conversion
3.12.2 Rules for Type Conversions
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 Storage Organization
4.2.1 Sub-division of Runtime Memory
4.3 Source Language Issues
4.3.1 Scope and Lifetime of Variables
4.3.2 Procedures
4.3.3 Activation Trees
4.3.4 Control Stacks
4.3.5 Scope of Declarations
4.3.6 Binding of Names
4.4 Storage Allocation Strategies
4.4.1 Static Allocation
4.4.2 Dynamic Allocation
4.5 Storage Allocation in Fortran
4.6 Parameter Passing
4.7 Symbol Table
4.7.1 Information Associated with Variables
4.7.2 Implementation
4.8 Code Generator
4.8.1 Introduction
4.8.2 Issues in the Design of a Code Generator
4.9 Register Allocation and Register Assignment
4.9.1 Global Register Allocation
4.9.2 Register Assignment for Outer Loops
4.9.3 Register Allocation by Graph Coloring
4.10 Design of a Simple Code Generator
4.10.1 Register and Address Descriptors
4.10.2 Code Generation Algorithm
Points to remember
Two Mark Questions with Answers
Solved Problems
University Questions
Chapter 5 Code Optimization
5.1 Optimization
5.2 Basic Block and Flow Graphs
5.2.1 Partitioning Three-address Statements into Basic Block
5.2.2 Transformations on Basic Block
5.2.3 Next-use Information
5.2.4 Flow Graph
5.2.5 Loops
5.3 Principal Sources of Optimization
5.3.1 Function Preserving Transformations
5.3.2 Loop Optimizations
5.4 Peep-hole Optimizations
5.4.1 Redundant Instruction Elimination
5.4.2 Eliminating Unreachable Code
5.4.3 Flow of Control Optimizations
5.4.4 Algebraic Simplification
5.4.5 Reduction in Strength
5.4.6 Use of Machine Idioms
5.5 DAG
5.6 Optimization of Basic Blocks
5.6.1 DAG Representation of Basic Block
5.7 Global Data-flow Analysis
5.7.1 Constraints
5.7.2 Reaching Definitions
5.7.3 Live Variable Analysis
5.7.4 Available Expressions
5.8 Efficient Data-flow Algorithms
5.8.1 Iterative Algorithm for Reaching Definitions
5.8.2 Iterative Algorithm to Compute Live-variables
5.8.3 Iterative Algorithm to Compute Available Expressions
5.8.4 Iterative Algorithm for General Frameworks
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
About The Authors
Godfrey Winster S, is Professor, Department of Computer Science and Engineering, Saveetha Engineering College, affiliated to Anna University, Chennai. He completed his Doctorate of Philosophy in Web Mining from Anna University. He has published numerous papers in international journals and conferences. He is a certified EMC2 Academic Associate in Cloud Infrastructure and Services, and Data Science and Big Data Analytics. He is also an active member in professional bodies like IEEE, CSI, ISTE, CSTA and IACSIT. He is also a reviewer for various International journals like JWS, JDCTA, JCIT, etc.
Aruna Devi S, is Assistant Professor, Department of Computer Science and Engineering, Saveetha Engineering College affiliated to Anna University, Chennai. She has published papers in various international journals and conferences.
Sujatha R, is Assistant Professor, Department of Computer Science and Engineering, Saveetha Engineering College affiliated to Anna University, Chennai. She has published papers in various international journals and conferences.
New Product Tab
Here's your new product tab.
Josef Peele –
This is a topic close to my heart cheers, where are your contact details though?
http://www.vorbelutrioperbir.com