Learn Compiler Design: From B. K.
Sharma
UNIT I
Major Data Structures in Compiler
Learn Compiler Design: From B. K. Sharma
Unit I: Syllabus
• Introduction to Compiler
• Major Data Structures in Compiler
• Types of Compiler
• Front-End and Back-End of Compiler
• Compiler Structure:
– Analysis-synthesis model of compilation
• Various phases of Compiler
Learn Compiler Design: From B. K. Sharma
Unit I: Syllabus
• Lexical Analysis:
– Input Buffering
– Specification and Recognition of Tokens
– Design of a Lexical Analyzer Generator
• Lex
Learn Compiler Design: From B. K. Sharma
Summary of Lecture 4: Types of Compilers:
1: Various types of compilers are One-Pass, two-pass and multi-
pass compilers, incremental compiler, native compiler, cross-
compiler and JIT compilers
2: The compiler which performs the recompilation of only
modified source program rather than compiling the whole
source program is called incremental compiler.
3: The compiler used to compile the source program for
same type of platform only is called native compiler.
4: A cross compiler is a compiler capable of creating
executable code for a platform other than the one on
which the compiler is running.
5: In JIT-compiler, applications are delivered in byte code,
which is compiled to native machine code just prior to
execution.
Learn Compiler Design: From B. K. Sharma
Mapping of Lesson with Course Outcome
(CO)
Lesson CO
Lesson 4: Major Data Understand compiler
Structures in and various phases in
Compiler compilation.
Learn Compiler Design: From B. K. Sharma
Lesson 4: Major Data Structures in Compiler
: Learning Outcomes
At the end of this lesson, students will be able to
1: List major data structures used in compiler.
2: Explain in own words with examples major data
structures in compiler.
3: List the main entries of Symbol table.
Learn Compiler Design: From B. K. Sharma
Active Learning Activity: Diagnostic
Assessment
One- Minute Paper
When did you hear the word Data
Structures first time?
Define data structure.
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
Tokens
The Syntax Tree
The Symbol Table
The Literal Table
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
Tokens
A token is a group or sequence of
characters having collective meaning: such
as identifiers, keywords , delimiters ,etc,
separated by a lexical analyzer and passed
to a parser.
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
The Syntax Tree
A syntax tree describes the syntactic structure of
string according to context free grammar omitting
the non-terminals from the parse tree.
The sentence a := x + y + 2.5 is represented as
syntax tree as follows:
Learn Compiler Design: From B. K. Sharma
Active Learning Activity
One- Minute Paper
Characters are grouped into tokens in which
of the following phase of the compiler
design?
a) Code generation b) Lexical analysis
c) Syntax Analysis d) Code optimization
Learn Compiler Design: From B. K. Sharma
The Translation Process: Phases of Compiler
Source Program
1. Lexical Analysis
Literal 2. Syntax Analysis
Table
3. Semantic Analysis Error Handler
& Recovery
4. IR Code Gen
Symbol 5. Code Optimization
Table
6. Target Code Generation
Target Program
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
The Symbol Table
A data structures called symbol table is used to
store essential information about every symbol
contained within the program.
Keeps information associated with all kinds of
identifiers:
Constants, variables, fonctions, parameters,
types, etc.
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
Main entries in the Symbol Table
Keywords Variables
Data Types Constants
Operators Literals
Functions Scope information
Storage information, size
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
The Symbol Table
int value=10;
void sum_num() void sum_id
{ {
int num_1; int id_1;
int num_2; int id_2;
{
int num_3; {
int num_4; int id_3;
} int id_4;
int num_5; }
{ int id_5;
int num _6; }
int num _7;
}
}
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
The Symbol Table
Learn Compiler Design: From B. K. Sharma
Major Data Structures in Compiler
Literal Table
Stores constant values and string literals in a
program.
Literal Category Attribute Memory
Location
60 const int 1200
Learn Compiler Design: From B. K. Sharma
Summary of Lecture 4: Major Data Structures in
Compiler
1:Major Data Structures used in Compiler are tokens, Syntax
Tree, Symbol Table and Literal Table.
2: A token is a group or sequence of characters having
collective meaning: such as identifiers, keywords ,
delimiters ,etc, separated by a lexical analyzer and
passed to a parser.
3: A syntax tree describes the syntactic structure of
string according to context free grammar omitting the non-
terminals from the parse tree.
4: Symbol table is used to store essential information about
every symbol contained within the program.
5: Literal Table stores constant values and string literals in
a program.
Learn Compiler Design: From B. K. Sharma
Active Learning Activity
One- Minute Paper
What is the use of a symbol table in
compiler design?
a) Finding name’s scope b) Type checking
c) Keeping all of the names of all entities in one place
d) All of the mentioned
