Compiler Design

Unit I

Introduction to Compiler: Phases and Passes, Bootstrapping, Finite State Machines and Regular Expressions and Their Applications to Lexical Analysis, Optimization of DFA-Based Pattern Matchers, Implementation of Lexical Analyzers, Lexical-Analyzer Generator, LEX Compiler, Formal Grammars and Their Application to Syntax Analysis, BNF Notation, Ambiguity, YACC. Syntactic Specification of Programming Languages: Context Free Grammars, Derivation and Parse Trees, Capabilities of CFG.

Unit II

Basic Parsing Techniques: Parsers, Shift Reduce Parsing, Operator Precedence Parsing, Top-Down Parsing, Predictive Parsers. Automatic Construction of Efficient Parsers: LR Parsers, Canonical Collection of LR(0) Items, Constructing SLR Parsing Tables, Canonical LR Parsing Tables, LALR Parsing Tables, Using Ambiguous Grammars, Automatic Parser Generator, Implementation of LR Parsing Tables.

Unit III

Syntax-Directed Translation: Syntax-Directed Translation Schemes, Implementation of Syntax-Directed Translators, Intermediate Code, Postfix Notation, Parse Trees & Syntax Trees, Three Address Code, Quadruples & Triples, Translation of Assignment Statements, Boolean Expressions, Statements That Alter Flow of Control, Postfix Translation, Translation with a Top-Down Parser, Array References in Arithmetic Expressions, Procedure Calls, Declarations and Case Statements.

Unit IV

Symbol Tables & Error Recovery: Data Structures for Symbol Tables, Representing Scope Information. Run-Time Administration: Simple Stack Allocation Scheme, Storage Allocation in Block-Structured Languages. Error Detection & Recovery: Lexical Phase Errors, Syntactic Phase Errors, Semantic Errors.

Unit V

Code Generation & Optimization: Design Issues, Target Language, Addresses in the Target Code, Basic Blocks and Flow Graphs, Optimization of Basic Blocks, Code Generator. Code Optimization: Machine-Independent Optimizations, Loop Optimization, DAG Representation of Basic Blocks, Value Numbers and Algebraic Laws, Global Data-Flow Analysis.