easwari engineering college, chennai

EASWARI ENGINEERING COLLEGE, CHENNAI-600 089
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
LESSON PLAN
SUBJECT CODE
: CS 2352
SUBJECT TITLE
: PRINCIPLES OF COMPILER DESIGN
HOURS DISTRIBUTION
: (L T P C 3 0 2 4)
COURSE/ BRANCH
: B.E. (CSE)
SEMESTER
: VI
ACADEMIC YEAR
: 2014 - 2015
FACULTY NAME
: DR.G.S.ANANDHA MALA
OBJECTIVE OF COURSE
:
To understand the principles of compiler design. This goal will be achieved by
introducing compiler design and implementation techniques and theory, reading current
compiler development literature, and discussing the design and implementation of
components of a compiler. This course will emphasize the implementation of a compiler
through the development of a large, complex, well-structured software system that
implements phases of a compiler such as the scanner, parser, and code generator.
Additionally, students will be able to describe the design of a compiler including its
phases and components, describe current developments in compiler design and
implementation, identify similarities and differences among various parsing techniques,
and transform grammars into parable forms.
1
OUTCOME OF COURSE
:
At the end of the course, the student should be able to:

Ability to create lexical rules and grammars for a programming language.

Ability to implement a parser such as a bottom-up SLR parser without using Yacc
or any other compiler-generation tools.

Ability to implement semantic rules into a parser that performs attribution while
parsing.

Be familiar with compiler architecture.

Ability to design a compiler for a concise programming language.
PREREQUISTE
UNITS
TOPIC
NO
: KNOWLEDGE IN THOREY OF COMPUTATION
TOPIC
PERIOD
BOOKS
Page
REFERRED No
UNIT-I (9+6)
LEXICAL ANALYSIS
I
1
OBJECTIVE: To learn the basic concepts, phases and types of various translators and to
design and implement a lexical analyzer.
Introduction to Compilers
1-4
1
T1
2
Analysis of the Source Program
2
T1
4-8
3
Phases of a Compiler
3
T1
8-13
4
Cousins of a Compiler, Grouping of the Phases
4
T1
13-16
5
Compiler Construction Tools
5
T1
16-18
6
Lexical Analysis
6
T1
18-19
7
Role of Lexical Analyzer
7
T1
69-70
8
Input Buffering- Specification of Tokens
8
T1
70-73
9
Recognition of Tokens, A language for specifying lexical
analyzer
Program implementation of Token separation for
keyword/special character /function
9
T1
73-80
10
12
LAB
11
Program implementation of Token separation for
identifier and constants
2
15
II
UNIT-II (9+6)
SYNTAX ANALYSIS and RUN-TIME ENVIRONMENTS
1
OBJECTIVE: To learn the role of a parser and to study the different ways of recognizing
and parsing of tokens.
Role of Parsers
130-134
16
T1
2
Grammars-CFGs
17
T1
135-140
3
Top Down Parsing-RD Parsing
18
T1
147-149
4
Bottom Up Parsing, Shift Reduce Parsing
19
T1
158-164
5
LR Parsing
20
T1
174-178
6
SLR Parsing
21
T1
179-185
7
Type checking, Specifications of simple type checker
22
T1
277-281
8
Run time environments, Source language issues
23
T1
297-302
9
24
T1
303-308
10
Storage organization, Storage allocation strategies, Static
allocation
Program implementation of Top down parser
11
Program implementation of Bottom up parser
30
27
LAB
UNIT-III (9+6)
INTERMEDIATE CODE GENERATION
OBJECTIVE: To study the process of Intermediate Code generation
III
1
Intermediate Languages
31
T1
334-339
2
Implementation of three address statements
32
T1
339-341
3
Declarations in a procedure
33
T1
341-343
4
Declarations-keeping track of scope & records
34
T1
343-345
5
Assignment Statements
35
T1
346-350
6
Boolean Expressions
36
T1
354-361
7
Case Statements
37
T1
361-364
8
Back Patching
38
T1
364-366
9
Procedure Calls
39
T1
366-368
10
Program implementation of Intermediate code generation
as Quadruple
Program implementation of Intermediate code generation
continued
42
11
3
LAB
45
UNIT-IV (9+6)
CODE GENERATION
OBJECTIVE: To study the concepts of code generation, Run time storage management
and different approaches of Compiler development.
IV
1
Issues in the design of Code Generator
46
T1
371-375
2
The Target Machine
47
T1
375-378
3
Runtime Storage Management
48
T1
378-383
4
Basic Blocks and Flow Graphs
49
T1
383-388
5
Next Use Information
50
T1
388-389
6
A simple Code Generator
51
T1
389-394
7
Register allocation and Assignment
52
T1
394-397
8
DAG Representation of Basic Blocks
53
T1
398-403
9
Generating code from DAGs
54
T1
403-407
10
Program implementation of generation of object code
from Intermediate code
Program implementation of Code generation continued
57
LAB
11
60
UNIT-V (9+6)
CODE OPTIMIZATION
OBJECTIVE: To study the concepts of Code Optimization
V
1
Introduction to Code optimization
61
T1
427-432
2
Principle of Sources of Optimization
62
T1
432-438
3
Peep hole Optimization
63
T1
438-441
4
Optimization of basic Blocks
64
T1
441-444
5
Loops in flow graphs
65
T1
444-449
6
Intro. Global Data Flow Analysis
66
T1
449-455
7
Dealing with loops
67
T1
456-461
8
Code improving transformations
68
T1
469-475
9
Alternative code motion
69
T1
476-483
10
Program implementation of code optimization
72
11
Program implementation of code optimization continued
75
4
LAB
ASSIGNMENT TOPICS
Sl. NO
ASSIGNMENT TOPICS
SUBMISSION DUE
1
ASSIGNMENT PROBLEM IN NFA TO DFA
January 29 2015
2
ASSIGNMENT PROBLEM IN TOP DOWN AND BOTTOM
UP PARSER
ASSIGNMENT PROBLEM IN INTERMEDIATE CODE
GENERATOR
February 16 2015
3
March 16 2015
CONTENT BEYOND SYLLABUS
SL.NO
1
2
ADDITIONAL TOPICS
LEX COMPILER
PARSER GENERATOR YACC
TEXT BOOK
T1.
Alfred Aho, Ravi Sethi, Jeffrey D Ullman, “Compilers Principles, Techniques
and Tools”, Pearson Education Asia, 2007.
REFERENCE BOOKS
R1. David Galles, “Modern Compiler Design”, Pearson Education Asia, 2007.
R2. Steven S. Muchnick, “Advanced Compiler Design & Implementation”,Morgan
Kaufmann Pulishers, 2000..
R3. C. N. Fisher and R. J. LeBlanc “Crafting a Compiler with C”, Pearson Education,
2000
5
PROGRAMME EDUCATIONAL OBJECTIVES
1. Graduates will have sound foundation in the mathematical, scientific and engineering fundamentals,
necessary to formulate, analyze and solve engineering problems.
2. Graduates will possess the ability to think logically and have capacity to understand technical
problems and to design optimal solutions for a successful career in industry or academia.
3. Graduates will have the potential to apply current industry practices and technologies to analyze,
design, implement, test and verify computing systems with emphasis on security to address research
problems and real world challenges
4. Graduates will have the ability to work as a team in both national and multinational environments and
will be able to promote the design and implementation of products and services through strong
interpersonal skills, leadership quality and entrepreneurial skills.
5. Graduates will possess an urge to learn continuously and to be responsive to the demands of the
progressive industrial world by carrying out researches in frontier areas of computer science and
engineering.
6. Graduates will be able to provide solutions to engineering problems with an understanding of its
impact on economical, environmental, ethical, and societal considerations by ensuring professional
standards.
PROGRAMME OUTCOMES (a-l)
(a) Apply the knowledge of mathematics, science and engineering fundamentals.
(b) Ability to analyze a problem, identify and define the computing requirements appropriate to its
solution.
(c) Ability to design, implements, and evaluate a computer-based system, process, component, or
program to meet desired needs.
(d) Apply the research-based knowledge and research methods to identify, formulate and solve
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
engineering problems.
Ability to use the techniques, skills, and modern engineering tools necessary for engineering practice,
with an understanding of the limitations.
Demonstrate understanding of the societal, health, safety, legal and cultural issues and the
consequent responsibilities relevant to engineering practice.
Understand the impact of professional engineering solutions in a societal and environmental context
and demonstrate the need for sustainable development.
Understand and commit to professional ethics and responsibilities.
Function effectively as an individual, and as a member in multi-disciplinary settings.
Communicate effectively with the engineering community and with society at large, such as being able
to comprehend, write effective reports and design documentation, make effective presentations, and
give/ receive clear instructions.
Demonstrate knowledge and understanding of the engineering and management principles, and apply
these to one’s own work, as a member and leader in a team, to manage projects in multidisciplinary
environments.
Recognize the need for, and have the ability to engage in independent and life-long learning
6
MAPPING OF COURSE OUTCOMES WITH PEO & THE PROGRAMME OUTCOME-PRINCIPLES OF COMPILER DESIGN
(CS2352)
UNITS
Unit –I
LEXICAL
ANALYSIS
Unit –II
SYNTAX
ANALYSIS and
RUN-TIME
ENVIRONMENTS
Unit-III
INTERMEDIATE
CODE
GENERATION
Unit –IV
CODE
GENERATION
Unit –V
CODE
OPTIMIZATION
Content
Beyond
Syllabus
COURSE
OUTCOME
Ability to create
lexical rules and
grammars for a
programming
language
Ability
to
implement
a
parser such as
a
bottom-up
SLR
parser
without
using
Yacc or any
other compilergeneration tools
Ability to
implement
semantic rules
into a parser
that performs
attribution while
parsing
Be familiar with
compiler
architecture
Ability to design
a compiler for a
concise
programming
language
Be familiar with
compiler
architecture
Ability to design
a compiler for a
concise
programming
language
PROGRAMME
EDUCATIONAL
OBJECTIVES
PROGRAMME OUTCOMES
1
2
3
4
5
6
a
b
c
d
e
SS
SS
S
S
M
M
SS
SS
SS
S
S
SS
SS
S
S
M
M
SS
SS
SS
MS
M
SS
SS
S
S
M
M
SS
SS
SS
MS
SS
SS
S
S
M
M
SS
SS
SS
SS
SS
S
S
M
M
SS
SS
SS
SS
S
S
M
M
SS
SS
SS
S
S
M
M
SS
SS
SS
S
M
M
STRONG
MEDIUM
WEAK
7
h
i
M
M
M
MS
SS
SS
SS
SS
S
M
W
f
g
j
k
l
S
M
S
S
SS
M
SS
M
S
SS
M
SS
M
M
S
SS
M
SS
MS
M
M
S
SS
M
SS
SS
MS
M
M
S
SS
M
SS
SS
SS
MS
M
M
S
SS
M
SS
SS
SS
MS
M
M
S
SS
M
SS