COMPILER DESIGN

160611
Total
L T P
Credits
2 1 2 4

COURSE OBJECTIVES

● To learn finite state machines and context free grammar.

● To learn, various phases of compiler

● To understand process of compiler implementation.

----------------------------------------------------------------------------------------------------------------

Unit-I
Overview of Translation Process: Introduction to Compiler, Translator, Interpreter and
Assembler, Overview and use of Linker and Loader, Major Data Structures in Compiler,
Other Issues in Compiler Structure, BOOT Strapping and Porting, Compiler Structure:
Analysis-Synthesis Model of Compilation, Various Phases of a Compiler, Tool Based
Approach to Compiler Construction.
Unit-II
Lexical Analysis: Input Buffering, Symbol Table, Token, Recognition of Tokens,
Lexeme and Patterns, Difficulties in Lexical Analysis, Error Reporting and
Implementation. Regular Grammar & Language Definition, Transition Diagrams, Design
of a Typical Scanner using LEX.
Unit-III
Syntax Analysis: Context Free Grammars (CFGs), Ambiguity, Basic Parsing
Techniques: Top Down Parsing, Recursive Descent Parsing, Transformation on the
Grammars, Predictive Parsing LL(1) Grammar, Bottom-UP Parsing, Operator Precedence
Parsing, LR Parsers (SLR, CLR, LALR), Design of a Typical Parser Using YACC.
Unit-IV
Semantic Analysis and Intermediate code: Syntax-directed translation schemes,
Implementation of syntax-directed translators, Compilation of Expression, Control,
Structures, Conditional Statements, Various Intermediate Code Forms, Syntax Directed
 Translation, Memory Allocation and Symbol Table Organizations, Static and Dynamic
Array Allocation, String Allocation, Structure Allocation etc., Error Detection Indication
and Recovery, Routines or Printing Various Lexical, Syntax and Semantic Errors.
Unit-V
Code Generation and Code Optimization: Issues, Basic Blocks and Flow Graphs,
Register Allocation, Code Generation, DAG Representation of Programs, Code
Generation from DAGS, Peep-hole Optimization, Code Generator Generators,
Specification of Machine. Code Optimization: Source of Optimizations, Optimization of
Basic Blocks, Loops, Global Data Flow Analysis, Solution to Iterative Data Flow
Equations, Code Improving Transformations, Dealing with Aliases, Data Flow Analysis
of Structured Flow Graphs.
----------------------------------------------------------------------------------------------------------------
RECOMMENDED BOOKS

● Compilers: Principles, Techniques and Tools, V. Aho, R. Sethi and J. D. Ullman,

Pearson Education.

● Compiler Construction: Principles and Practice, K.C. Louden, Cengage Learning.

----------------------------------------------------------------------------------------------------------------

COURSE OUTCOMES
After completion of this course, the students would be able to:
CO1. define the concepts of finite automata and context free grammar. Discuss fundamentals of
language translator and compiler design.
CO2. build explain the concept of working of compiler.
CO3. examine various parsing techniques and their comparison.
CO4. compare analyse various code generation and code optimization techniques.
CO5. analyze test different tools and techniques for designing a compiler.
CO6. design various phases of compiler.
---------------------------------------------------------------------------------------------------------------------
 COMPILER DESIGN LAB
160611

LIST OF PROGRAMS
1. Write a program to convert NFA to DFA.
2. Write a program to minimize DFA.
3. Develop a lexical analyzer to recognize a few patterns.
4. Write a program to parse using Brute force technique of Top down parsing.
5. Develop LL (1) parser (Construct parse table also).
6. Develop an operator precedence parser (Construct parse table also).
7. Develop a recursive descent parser.
8. Write a program for generating for various intermediate code forms.
i. Three address code
ii. Polish notation
9. Write a program to simulate Heap storage allocation strategy.
10. Generate Lexical analyzer using LEX.
11. Generate YACC specification for a few syntactic categories.
12. Given any intermediate code form implement code optimization techniques.
----------------------------------------------------------------------------------------------------------------
COURSE OUTCOMES
After completion of this course, the students would be able to:
CO1. discuss the knowledge of patterns, tokens & regular expressions in programming for
problem solving.
CO2. design and Implement various parsing techniques.
CO3. operate different types of compiler tools.
CO4. develop programs for implementing code optimization techniques.
CO5. build symbol table and intermediate codes.
CO6. demonstrate the functionalities of different phases of the compilation process.
----------------------------------------------------------------------------------------------------------------

COMPILER DESIGN LAB

160611
SKILL BASED MINI PROJECTS

1. Design a Lexical scanner to recognize keyword, identifier and its total count presented in
source program.
2. Design a Lexical scanner to identify operators, digits (0-9) and numbers (like integer,
floating point, fractional and exponential) in source program.
3. Design a Lexical scanner to count no. of words, character, small characters, capital
characters and capital words within source program.
4. Design a Lexical analyzer to ignore comments, redundant spaces, tabs and new lines
form input source program.
5. Design a Lexical scanner to recognize and count the number of vowels and consonants in
a sentence.
6. Design a YACC analyzer to implement a Calculator and recognize a valid Arithmetic
expression.
7. Design a YACC analyzer to recognize string with grammar {a nbn | n>=0} and { anb |
n>=5}.
8. Design a YACC that accepts strings that starts and ends with Zero or One.
----------------------------------------------------------------------------------------------------------------
 Micro program list

1. Study of JFLAP (Java Formal Languages and Automata Package) tools.

2. Design a Program to recognize constant.
3. Design a Program to recognize keyword.
4. Design a Program to recognize identifier.
5. Design a Program to recognize operator.
6. Design a program to recognize identifier.
7. Design a Program to recognize a delimiters/punctuators.

Note: Use JFLAP (Java Formal Languages and Automata Package) tools.

Macro program list

1. Convert finite automata to regular expression.

2. Convert regular expression to finite automata.
3. Convert CFG to PDA (LL).
4. Convert CFG to PDA (LR).
5. Convert Regular Grammar to FSA
6. Build LL(1) parsing table.
7. Build SLR(1) parsing table.
Note: Use JFLAP (Java Formal Languages and Automata Package) tools.