B.
Tech CSE(Artificial Intelligence) Effective from 2022(Batch 2022-2026)
Annexure 29.1.1
COMPILER DESIGN
Course Code: AI303 Course Credits: 3
Course Category: CC Course (U / P) U
Course Year (U / P): 3U Course Semester (U / P): 5U
No. of Lectures + Tutorials 03 + 00 Mid Sem. Exam Hours: 1.5
(Hrs/Week):
Total No. of Lectures (L + T): 45 + 00 End Sem. Exam Hours: 3
COURSE OBJECTIVES
1 Understand the basic principles of compiler design, its various constituent parts,
algorithms and data structures required to be used in the compiler.
2 Understand relations between computer architecture and how its understanding is useful
in design of a compiler.
3 How to construct efficient algorithms for compilers.
4 Provide an understanding of the fundamental principles in compiler design.
5 Learn the process of translating a modern high-level-language to executable code required
for compiler construction.
COURSE OUTCOMES
At the end of the course the students should be able to:
1 Acquire knowledge of different phases and passes of the compiler and also able to use the
compiler tools like LEX, YACC, etc. Students will also be able to design different types of
compiler tools to meet the requirements of the realistic constraints of compilers.
2 Understand the parser and its types i.e. Top-Down and Bottom-up parsers and
construction of LL, SLR, CLR, and LALR parsing table.
3 Implement the compiler using syntax-directed translation method and get knowledge
about the synthesized and inherited attributes.
4 Acquire knowledge about run time data structure like symbol table organization and
different techniques used in that.
5 Understand the target machine’s run time environment, its instruction set for code
generation and techniques used for code optimization.
UNIT I INTRODUCTION TO COMPILER:
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. The syntactic specification of programming languages: Context free
grammars, derivation and parse trees, Capabilities of CFG.
64/148 29thBOS | Mar 25, 2023
[Link] CSE(Artificial Intelligence) Effective from 2022(Batch 2022-2026)
Annexure 29.1.1
UNIT II BASIC PARSING TECHNIQUES:
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, implementation of LR parsing tables.
UNIT III SYNTAX-DIRECTED TRANSLATION:
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, declarations and case statements.
UNIT IV SYMBOL TABLES:
Symbol Tables: Data structure for symbols tables, representing scope information. Run-
Time Administration: Implementation of simple stack allocation scheme, storage allocation
in block structured language. Error Detection & Recovery: Lexical Phase errors, syntactic
phase errors semantic errors.
UNIT V CODE GENERATION:
Code Generation: Design Issues, the 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.
Text books:
1. K. Muneeswaran, CompilerDesign,FirstEdition,Oxford University Press.
2. J.P. Bennet, “Introduction to Compiler Techniques”, Second Edition, Tata McGraw-Hill,
2003.
3. Henk Alblas and Albert Nymeyer, “Practice and Principles of Compiler Building with C”,
PHI, 2001.
4. Aho, Sethi & Ullman, "Compilers: Principles, Techniques and Tools”, Pearson Education
5. V Raghvan, “ Principles of Compiler Design”, TM
65/148 29thBOS | Mar 25, 2023