COMPILER DESIGN
[R20A0512]
LECTURE NOTES
B T C III AR – I S (R )
(2021-22)
DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING
MALLA REDDY COLLEGE OF
ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
Recognized under 2(f) and 12 (B) of UGC ACT 1956
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, India
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
III Year B. Tech CSE - I Sem
L T/P/D C
3 1/0/- 4
(R20A0512) Compiler Design
Objectives:
• To provide an initial Understanding of language translators, Knowledge of various techniques used
in compiler construction and also use of the automated tools available in compilers construction.
UNIT – I:
Language Translation: Basics, Necessity, Steps involved in atypical language processing system,
Types of translators, Compilers: Overview and Phases of a Compiler, Pass and Phases of
translation, bootstrapping, data structures in compilation
Lexical Analysis (Scanning): Functions of Lexical Analyzer, Specification of tokens: Regular
expressions and Regular grammars for common PL constructs. Recognition of Tokens: Finite
Automata in recognition and generation of tokens. Scanner generators: LEX-Lexical Analyzer
Generators. Syntax Analysis (Parsing) : Functions of a parser, Classification of parsers. Context
free grammars in syntax specification, benefits and usage in compilers.
UNIT – II:
Top down parsing –Definition, types of top down parsers: Backtracking, Recursive descent,
Predictive, LL (1), Preprocessing the grammars to be used in top down parsing, Error recovery, and
Limitations. Bottom up parsing: Definition, types of bottom up parsing, Handle pruning. Shift
Reduce parsing, LR parsers: LR(0), SLR, CALR and LALR parsing, Error recovery, Handling
ambiguous grammar, Parser generators: YACC-yet another compiler compiler. .
UNIT – III:
Semantic analysis: Attributed grammars, Syntax directed definition and Translation schemes, Type
checker: functions, type expressions, type systems, types checking of various constructs.
Intermediate Code Generation: Functions, different intermediate code forms- syntax tree, DAG,
Polish notation, and Three address codes. Translation of different source language constructs into
intermediate code.
Symbol Tables: Definition, contents, and formats to represent names in a Symbol table. Different
approaches used in the symbol table implementation for block structured and non block structured
languages, such as Linear Lists, Self Organized Lists, and Binary trees, Hashing based STs.
UNIT – IV:
Runtime Environment: Introduction, Activation Trees, Activation Records, Control stacks.
Runtime storage organization: Static, Stack and Heap storage allocation. Storage allocation for
arrays, strings, and records etc.
Code optimization: goals and Considerations for Optimization, Scope of Optimization: Local
optimizations, DAGs, Loop optimization, Global Optimizations. Common optimization techniques:
Folding, Copy propagation, Common Sub expression eliminations, Code motion, Frequency
reduction, Strength reduction etc.
UNIT – V:
Control flow and Data flow analysis: Flow graphs, Data flow equations, global optimization:
Redundant sub expression elimination, Induction variable eliminations, Live Variable analysis.
Object code generation: Object code forms, machine dependent code optimization, register
allocation and assignment generic code generation algorithms, DAG for register allocation.
,TEXT BOOKS:
1. Compilers, Principle, Techniques, and Tools. – Alfred.V Aho, Monica S.Lam, Ravi Sethi, Jeffrey
D. Ullman ; 2nd Edition, Pearson Education.
2. Modern Compiler implementation in C , - Andrew N.Appel Cambridge University Press.
REFERENCES:
1. lex & yacc , -John R Levine, Tony Mason, Doug Brown; O’reilly.
2. Compiler Construction,- LOUDEN, Thomson.
3. Engineering a compiler – Cooper & Linda, Elsevier
4. Modern Compiler Design – Dick Grune, Henry E.Bal, Cariel TH Jacobs, Wiley Dreatech
Outcomes:
By the end of the semester, the student will be able to:
Understand the necessity and types of different language translators in use.
Apply the techniques and design different components (phases) of a compiler by hand.
Solve problems, Write Algorithms, Programs and test them for the results.
Use the tools Lex, Yacc in compiler construction.
, INDEX
UNIT NO TOPIC PAGE NO
Language Translation 01 – 03
Compilers 03 – 08
I
Lexical Analysis (Scanning) 09 – 14
Syntax Analysis (Parsing) 15 – 17
Top down parsing 18 – 33
II
Bottom up parsing 34 – 58
Semantic analysis 59 – 65
III Intermediate Code Generation 66 – 90
Symbol Tables 91 – 106
Runtime Environment 107 – 122
IV
Code optimization 122 - 134
Control flow and Data flow analysis 135 - 141
V
Object code generation 142 - 152
[R20A0512]
LECTURE NOTES
B T C III AR – I S (R )
(2021-22)
DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING
MALLA REDDY COLLEGE OF
ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
Recognized under 2(f) and 12 (B) of UGC ACT 1956
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, India
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
III Year B. Tech CSE - I Sem
L T/P/D C
3 1/0/- 4
(R20A0512) Compiler Design
Objectives:
• To provide an initial Understanding of language translators, Knowledge of various techniques used
in compiler construction and also use of the automated tools available in compilers construction.
UNIT – I:
Language Translation: Basics, Necessity, Steps involved in atypical language processing system,
Types of translators, Compilers: Overview and Phases of a Compiler, Pass and Phases of
translation, bootstrapping, data structures in compilation
Lexical Analysis (Scanning): Functions of Lexical Analyzer, Specification of tokens: Regular
expressions and Regular grammars for common PL constructs. Recognition of Tokens: Finite
Automata in recognition and generation of tokens. Scanner generators: LEX-Lexical Analyzer
Generators. Syntax Analysis (Parsing) : Functions of a parser, Classification of parsers. Context
free grammars in syntax specification, benefits and usage in compilers.
UNIT – II:
Top down parsing –Definition, types of top down parsers: Backtracking, Recursive descent,
Predictive, LL (1), Preprocessing the grammars to be used in top down parsing, Error recovery, and
Limitations. Bottom up parsing: Definition, types of bottom up parsing, Handle pruning. Shift
Reduce parsing, LR parsers: LR(0), SLR, CALR and LALR parsing, Error recovery, Handling
ambiguous grammar, Parser generators: YACC-yet another compiler compiler. .
UNIT – III:
Semantic analysis: Attributed grammars, Syntax directed definition and Translation schemes, Type
checker: functions, type expressions, type systems, types checking of various constructs.
Intermediate Code Generation: Functions, different intermediate code forms- syntax tree, DAG,
Polish notation, and Three address codes. Translation of different source language constructs into
intermediate code.
Symbol Tables: Definition, contents, and formats to represent names in a Symbol table. Different
approaches used in the symbol table implementation for block structured and non block structured
languages, such as Linear Lists, Self Organized Lists, and Binary trees, Hashing based STs.
UNIT – IV:
Runtime Environment: Introduction, Activation Trees, Activation Records, Control stacks.
Runtime storage organization: Static, Stack and Heap storage allocation. Storage allocation for
arrays, strings, and records etc.
Code optimization: goals and Considerations for Optimization, Scope of Optimization: Local
optimizations, DAGs, Loop optimization, Global Optimizations. Common optimization techniques:
Folding, Copy propagation, Common Sub expression eliminations, Code motion, Frequency
reduction, Strength reduction etc.
UNIT – V:
Control flow and Data flow analysis: Flow graphs, Data flow equations, global optimization:
Redundant sub expression elimination, Induction variable eliminations, Live Variable analysis.
Object code generation: Object code forms, machine dependent code optimization, register
allocation and assignment generic code generation algorithms, DAG for register allocation.
,TEXT BOOKS:
1. Compilers, Principle, Techniques, and Tools. – Alfred.V Aho, Monica S.Lam, Ravi Sethi, Jeffrey
D. Ullman ; 2nd Edition, Pearson Education.
2. Modern Compiler implementation in C , - Andrew N.Appel Cambridge University Press.
REFERENCES:
1. lex & yacc , -John R Levine, Tony Mason, Doug Brown; O’reilly.
2. Compiler Construction,- LOUDEN, Thomson.
3. Engineering a compiler – Cooper & Linda, Elsevier
4. Modern Compiler Design – Dick Grune, Henry E.Bal, Cariel TH Jacobs, Wiley Dreatech
Outcomes:
By the end of the semester, the student will be able to:
Understand the necessity and types of different language translators in use.
Apply the techniques and design different components (phases) of a compiler by hand.
Solve problems, Write Algorithms, Programs and test them for the results.
Use the tools Lex, Yacc in compiler construction.
, INDEX
UNIT NO TOPIC PAGE NO
Language Translation 01 – 03
Compilers 03 – 08
I
Lexical Analysis (Scanning) 09 – 14
Syntax Analysis (Parsing) 15 – 17
Top down parsing 18 – 33
II
Bottom up parsing 34 – 58
Semantic analysis 59 – 65
III Intermediate Code Generation 66 – 90
Symbol Tables 91 – 106
Runtime Environment 107 – 122
IV
Code optimization 122 - 134
Control flow and Data flow analysis 135 - 141
V
Object code generation 142 - 152
