|Compiler Design||Learning Schedule|
|Pre-requisites: OS and CAO||3||1||0||4|
The goal of the course is to provide an introduction to the system software like assemblers, compilers, and macros. It provides the complete description about inner working of a compiler. This course focuses mainly on the design of compilers and optimization techniques. It also includes the design of Compiler writing tools. This course also aims to convey the language specifications, use of regular expressions and context free grammars behind the design of compiler.
The objective of this course is to:
- Provide an understanding of the fundamental principles in compiler design
- Provide the skills needed for building compilers for various situations that one may encounter in a career in Computer Science.
- Learn the process of translating a modern high-level language to executable code required for compiler construction.
At the end of course students will be able to:
- Understand fundamentals of compiler and identify the relationships among different phases of the compiler.
- Understand the application of finite state machines, recursive descent, production rules, parsing, and language semantics.
- Analyze & implement required module, which may include front-end, back-end, and a small set of middle-end optimizations.
- Use modern tools and technologies for designing new compiler.
Unit I: Introduction
Introduction to Compiler, Phases and passes, Bootstrapping, Finite state machines and regularexpressions and their applications to lexical analysis, Optimization of DFA-Based PatternMatchers implementation of lexical analyzers, lexical-analyzer generator, LEX-compiler,Formal grammars and their application to syntax analysis, BNF notation, ambiguity, YACC.The syntactic specification of programming languages: Context free grammars, derivation andparse 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, the canonical Collection of LR (0) items, constructing SLR parsing tables, constructing Canonical LR parsing tables, Constructing LALR parsing tables, using ambiguous grammars, an automatic parser generator, and 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, quadruple & triples, translation of assignment statements, Boolean expressions, statements that alter the flow of control, postfix translation, translation with a top down parser. More about translation: Array references in arithmetic expressions, procedures call, declaration sand case statements.
Unit IV: Symbol Tables
Data structure for symbols tables, representing scope information. Run-Time Administration: Implementation of simple stack al-location scheme, storage allocation in block structured language. Error Detection & Recovery: Lexical Phase errors, syntactic phase errors semantic errors.
Unit V: Code Generation
Selected Topics: Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NP-completeness, Approximation algorithms and Randomized algorithms..
- ALFRED V AUTOR AHO, JEFFREY D AUTOR ULLMAN “Principles of Compiler Design”.
- V Raghvan, “ Principles of Compiler Design”, TMH
- Kenneth Louden,” Compiler Construction”, Cengage Learning.
- Aho, Sethi & Ullman, “Compilers: Principles, Techniques and Tools”, Pearson Education2
- Charles Fischer and Ricard LeBlanc,” Crafting a Compiler with C”, Pearson Education