Compiler Design (MCA554) – Unit 4: Type Checking and Run Time Environments
Published: June 21, 2026
Author: Adarsh verma
Compiler Design (MCA554) – Unit 4: Type Checking and Run Time EnvironmentsBased on MCA Semester III Syllabus
---
Introduction to Type Checking
Type Checking is the process of verifying that operands and expressions are used with compatible data types.
Its purpose is to detect type errors before program execution.Example:
int x;
x = 10;
Valid Assignment.
Example:
int x;
x = "Hello";
Type Error.
---
Need for Type Checking
Type checking helps:
Detect programming errors
Improve reliability
Ensure correct operations
Prevent invalid assignments
---
Type Expressions
A Type Expression represents the type of a variable, function, or expression.
Examples:
int a;
float b;
char c;
Type Expressions:
a → int
b → float
c → char
---
Primitive Data Types
Basic data types available in programming languages.
Examples:
int
float
char
double
boolean
---
Constructed Data Types
Created using primitive types.
Examples:
Array
Pointer
Structure
Function
---
Type Equivalence
Determines whether two type expressions represent the same type.
---
Name Equivalence
Two variables are equivalent if they have the same declared type name.
Example:
typedef int Marks;
Marks m1;
Marks m2;
Equivalent types.
---
Structural Equivalence
Two types are equivalent if their structures are identical.
Example:
struct A
{
int x;
};
struct B
{
int x;
};
Structurally equivalent.
---
Type Conversion
Converting one data type into another.
---
Implicit Type Conversion
Performed automatically by compiler.
Example:
int a = 10;
float b;
b = a;
Integer automatically becomes float.
---
Explicit Type Conversion
Performed by programmer.
Example:
float a = 10.5;
int b = (int)a;
Result:
b = 10
---
Static Type Checking
Type checking performed during compilation.
Examples:
int a;
a = 20;
Compiler verifies types before execution.
Advantages:
Faster execution
Early error detection
---
Dynamic Type Checking
Type checking performed during execution.
Examples:
x = 10
x = "Hello"
Type determined at runtime.
Advantages:
Flexibility
Disadvantages:
Slower execution
---
Comparison of Static and Dynamic Type Checking
Static Checking Dynamic Checking
Compile Time Run Time
Faster Slower
Early Detection Late Detection
C, C++ Python, JavaScript
---
Specification of a Simple Type Checker
A Type Checker:
1. Reads declarations
2. Stores type information
3. Verifies assignments
4. Reports errors
Example:
int x;
float y;
x = y;
Possible warning:
Possible Loss of Data
---
Run Time Environment
The Run Time Environment manages memory and resources during program execution.
Responsibilities:
Memory allocation
Function calls
Parameter passing
Stack management
Variable storage
---
Source Language Issues
Different programming languages have different requirements.
Examples:
Dynamic arrays
Recursion
Pointers
Garbage collection
Compiler must support these features.
---
Storage Organization
Memory is divided into different sections.
+----------------+
| Code Segment |
+----------------+
| Data Segment |
+----------------+
| Heap |
+----------------+
| Stack |
+----------------+
---
Code Segment
Stores:
Program Instructions
Example:
printf("Hello");
Compiled instructions are stored here.
---
Data Segment
Stores:
Global Variables
Static Variables
Example:
int total = 100;
---
Stack
Stores:
Function calls
Local variables
Return addresses
Example:
void display()
{
int x = 10;
}
Variable x is stored on the stack.
---
Heap
Stores dynamically allocated memory.
Example:
int *p;
p = malloc(sizeof(int));
Memory allocated from heap.
---
Storage Allocation Strategies
Methods used to allocate memory.
---
Static Allocation
Memory assigned during compilation.
Example:
static int count;
Advantages:
Simple
Fast
Disadvantages:
Less flexible
---
Stack Allocation
Memory allocated during function calls.
Example:
void test()
{
int x;
}
Advantages:
Fast allocation
Automatic deallocation
---
Heap Allocation
Memory allocated dynamically.
Example:
malloc()
new
Advantages:
Flexible
Disadvantages:
Slower
Memory leaks possible
---
Access to Non-Local Names
Occurs when a function accesses variables declared outside its scope.
Example:
int global = 10;
void display()
{
printf("%d", global);
}
Compiler must locate the variable correctly.
---
Parameter Passing
Method of transferring values to functions.
---
Call By Value
A copy of the variable is passed.
Example:
void fun(int x)
{
x = 100;
}
Original variable remains unchanged.
---
Call By Reference
Address of variable is passed.
Example:
void fun(int *x)
{
*x = 100;
}
Original variable changes.
---
Symbol Table
One of the most important compiler data structures.
Stores information about identifiers.
---
Information Stored
Variable Name
Data Type
Scope
Memory Address
Example:
Identifier Type
age int
salary float
---
Functions of Symbol Table
Store identifiers
Type checking
Scope management
Memory allocation
---
Dynamic Storage Allocation
Memory allocated during execution.
Examples:
malloc()
calloc()
realloc()
free()
Benefits:
Efficient memory usage
Flexible allocation
---
Language Facilities for Dynamic Storage Allocation
Programming languages provide built-in support.
Examples:
C
malloc()
free()
C++
new
delete
Java
Objects created dynamically
---
Applications of Runtime Environment
Program execution
Memory management
Function calls
Dynamic allocation
---
Important Exam Questions
Short Questions
1. Define Type Checking.
2. What is Type Conversion?
3. Define Static Type Checking.
4. What is Dynamic Type Checking?
5. What is a Symbol Table?
6. Define Heap Memory.
7. What is Stack Allocation?
8. What is Call By Reference?
---
Long Questions
1. Explain Type Checking with examples.
2. Differentiate Static and Dynamic Type Checking.
3. Explain Storage Allocation Strategies.
4. Discuss Runtime Environment.
5. Explain Symbol Tables and their functions.
6. Explain Parameter Passing mechanisms.
---
Quick Revision Notes
Type Checking = Verification of data types.
Static Checking = Compile-time checking.
Dynamic Checking = Run-time checking.
Type Conversion = Data type transformation.
Stack = Local variables and function calls.
Heap = Dynamic memory allocation.
Symbol Table = Stores identifier information.
Call By Value = Copy passed.
Call By Reference = Address passed.
Runtime Environment = Manages execution resources.
---
Next Blog: Compiler Design (MCA554) – Unit 5: Code Generation, Register Allocation, Peephole Optimization, Basic Blocks, Flow Graphs, DAG Representation and Code Optimization.
x
Adarsh verma
Adarsh verma
CodeWithAV publishes practical technology tutorials, study resources, programming guides, and cybersecurity learning content.
Compiler Design (MCA554) – Unit 3: Syntax Directed Translation and Intermediate Code Generation
Published: June 21, 2026
Author: Adarsh verma
Compiler Design (MCA554) – Unit 3: Syntax Directed Translation and Intermediate Code Generation
Based on MCA Semester III Syllabus
---
Introduction to Syntax Directed Translation
Syntax Directed Translation (SDT) is a method in which semantic actions are associated with grammar rules.
It helps the compiler:
Generate intermediate code
Perform type checking
Build syntax trees
Translate source code into machine-independent representation
---
Need for Syntax Directed Translation
A parser only checks syntax.
The compiler must also:
Understand meaning
Generate code
Perform semantic analysis
Syntax Directed Translation helps achieve these tasks.
---
Syntax Directed Definition (SDD)
A Syntax Directed Definition is a Context Free Grammar (CFG) with attributes and semantic rules attached to productions.
General Form:
A → B C
Semantic Rule:
A.val = B.val + C.val
---
Attributes
Attributes store information about grammar symbols.
Types:
Information flows upward in the parse tree.
Example:
E.val = E1.val + T.val
---
Information flows downward or sideways.
Example:
T.type = E.type
---
Syntax Tree
A Syntax Tree is a compact representation of a program structure.
Unlike Parse Trees:
Keywords are omitted
Grammar symbols are reduced
Example Expression:
a + b * c
Syntax Tree:
+
/ \
a *
/ \
b c
---
Advantages of Syntax Trees
Compact representation
Easy code generation
Used in optimization
---
S-Attributed Definition
Uses only Synthesized Attributes.
Characteristics:
Easy implementation
Suitable for Bottom-Up Parsing
Example:
E → E1 + T
E.val = E1.val + T.val
---
L-Attributed Definition
Uses:
Synthesized Attributes
Limited Inherited Attributes
Characteristics:
Suitable for Top-Down Parsing
Widely used in compilers
---
Translation Schemes
A Translation Scheme is a CFG with semantic actions embedded within productions.
Example:
E → E + T { print('+') }
Semantic actions execute during parsing.
---
Intermediate Code Generation
Intermediate Code is generated between source code and machine code.
Compiler Structure:
Source Code
↓
Intermediate Code
↓
Machine Code
Benefits:
Machine independent
Easier optimization
Simplifies compiler design
---
Intermediate Forms of Source Programs
Common intermediate representations:
1. Syntax Tree
Tree representation.
Operator appears before operands.
Example:
+ A B
---
Operator appears after operands.
Example:
A B +
---
4. Three Address Code
Most important intermediate representation.
---
Three Address Code (TAC)
Each statement contains at most three addresses.
General Form:
x = y op z
Example:
a = b + c * d
Three Address Code:
t1 = c * d
t2 = b + t1
a = t2
---
Advantages of TAC
Easy optimization
Easy machine code generation
Simple representation
---
Types of Three Address Statements
Assignment
a = b
---
Unary Operation
t1 = -a
---
Binary Operation
t2 = a + b
---
Conditional Jump
if a < b goto L1
---
Unconditional Jump
goto L2
---
Representation of TAC
Three common representations:
---
Structure:
(op, arg1, arg2, result)
Example:
(+, a, b, t1)
---
Structure:
(op, arg1, arg2)
Example:
0: (+, a, b)
---
Indirect Triples
Uses pointers to triples.
Advantage:
Easier code optimization
---
Translation of Simple Statements
Expression:
x = a + b
TAC:
t1 = a + b
x = t1
---
Boolean expressions evaluate to:
TRUE
FALSE
Examples:
a > b
x == y
age >= 18
---
Intermediate Code for Boolean Expressions
Example:
if(a > b)
TAC:
if a > b goto L1
goto L2
---
Flow control determines program execution order.
Examples:
if
if-else
while
do-while
for
---
Translation of IF Statement
Source Code:
if(a>b)
x=y;
Three Address Code:
if a>b goto L1
goto L2
L1:
x=y
L2:
---
Translation of IF-ELSE Statement
Source Code:
if(a>b)
x=y;
else
x=z;
Three Address Code:
if a>b goto L1
goto L2
L1:
x=y
goto L3
L2:
x=z
L3:
---
Translation of WHILE Loop
Source Code:
while(a<b)
{
a=a+1;
}
Three Address Code:
L1:
if a<b goto L2
goto L3
L2:
a=a+1
goto L1
L3:
---
Translation of FOR Loop
Source Code:
for(i=1;i<=10;i++)
Intermediate representation:
i=1
L1:
if i<=10 goto L2
goto L3
L2:
statement
i=i+1
goto L1
L3:
---
Applications of Intermediate Code
Compiler construction
Code optimization
Program analysis
Machine code generation
---
Important Exam Questions
Short Questions
1. Define Syntax Directed Translation.
2. What is SDD?
3. What is a Syntax Tree?
4. Define TAC.
5. What are Synthesized Attributes?
6. What is Polish Notation?
7. Define Translation Scheme.
8. What is Quadruple Representation?
---
Long Questions
1. Explain Syntax Directed Definitions with examples.
2. Differentiate S-Attributed and L-Attributed Definitions.
3. Explain Syntax Trees and their applications.
4. Explain Three Address Code and its representations.
5. Generate TAC for arithmetic expressions.
6. Explain translation of Boolean expressions and control statements.
---
Quick Revision Notes
SDT = Syntax + Semantic Actions.
SDD = CFG + Attributes + Rules.
Syntax Tree = Compact program structure.
S-Attributed = Only Synthesized Attributes.
L-Attributed = Synthesized + Inherited Attributes.
TAC = Three Address Code.
Quadruple = (op, arg1, arg2, result).
Triple = (op, arg1, arg2).
Boolean Expressions = TRUE/FALSE.
TAC is the most important intermediate representation for exams.
---
Adarsh verma
Adarsh verma
CodeWithAV publishes practical technology tutorials, study resources, programming guides, and cybersecurity learning content.
Compiler Design (MCA554) – Unit 2: Parsing and Syntax Analysis
Published: June 21, 2026
Author: Adarsh verma
Compiler Design (MCA554) – Unit 2: Parsing and Syntax Analysis
Based on MCA Semester III Syllabus---
Introduction to Parsing
Parsing is the second phase of a compiler.
After Lexical Analysis generates tokens, the Parser checks whether the sequence of tokens follows the grammar rules of the programming language.
Example
Source Code:
a = b + c;
Tokens:
id = id + id ;
Parser verifies whether the token sequence is grammatically correct.
---
Role of Parser
The parser performs the following tasks:
Checks syntax errors
Builds parse trees
Verifies grammar rules
Reports syntax violations
Position in Compiler
Source Program
↓
Lexical Analyzer
↓
Parser
↓
Semantic Analyzer
---
Context Free Grammar (CFG)
A Context Free Grammar is used to describe the syntax of programming languages.
A CFG consists of:
Terminals
Non-terminals
Productions
Start Symbol
Example Grammar
E → E + T
E → T
T → id
Where:
E = Expression
T = Term
id = Identifier
---
Derivation
Derivation means generating a string using grammar rules.
Example
Grammar:
E → E + T
E → T
T → id
Derivation:
E
→ E + T
→ T + T
→ id + T
→ id + id
---
Parse Tree
A Parse Tree is a graphical representation of derivation.
Example
E
/ | \
E + T
| |
T id
|
id
Parse Trees help understand the structure of expressions.
---
Ambiguous Grammar
A grammar is ambiguous if one string can have multiple parse trees.
Example
E → E + E
E → E * E
E → id
Expression:
id + id * id
Can have multiple interpretations.
---
Left Recursion
A grammar is left recursive when a non-terminal appears first on the right side of its own production.
Example
E → E + T
E → T
This is left recursive.
---
Elimination of Left Recursion
Original Grammar:
E → E + T | T
Converted Grammar:
E → T E'
E' → + T E' | ε
Advantages:
Suitable for top-down parsing
Avoids infinite recursion
---
Left Factoring
Used when multiple productions share common prefixes.
Example
Original:
A → if E then S
A → if E then S else S
After Left Factoring:
A → if E then S A'
A' → else S | ε
Benefits:
Simplifies parsing
Reduces ambiguity
---
Dangling Else Problem
Consider:
if(condition1)
if(condition2)
statement1;
else
statement2;
Question:
Which "if" does the "else" belong to?
This ambiguity is called the Dangling Else Problem.
---
Top Down Parsing
Top-down parsers start from the root and construct the parse tree downward.
Methods:
1. Recursive Descent Parsing
2. Predictive Parsing
---
Recursive Descent Parsing
Uses recursive procedures for each grammar rule.
Example:
E()
T()
F()
Advantages:
Easy to implement
Disadvantages:
Cannot handle left recursion
---
Predictive Parsing
A special recursive descent parser without backtracking.
Requirements:
No left recursion
Left factored grammar
Advantages:
Fast
Efficient
---
Bottom Up Parsing
Bottom-up parsers start from input symbols and build toward the start symbol.
Process:
Input String
↓
Reductions
↓
Start Symbol
---
Shift Reduce Parsing
Most important Bottom-Up Parsing technique.
Operations:
Shift
Push input symbol onto stack.
Reduce
Replace symbols using grammar rules.
Accept
Parsing successful.
Error
Invalid input.
---
Example
Input:
id + id
Actions:
Shift id
Reduce T→id
Reduce E→T
Shift +
Shift id
Reduce T→id
Reduce E→E+T
Accept
---
Handle
A Handle is a substring that matches the right side of a production and can be reduced.
Example:
E → E + T
Handle:
E + T
---
Handle Pruning
Process of repeatedly reducing handles until the start symbol is obtained.
---
Shift Reduce Conflicts
Two common conflicts:
Shift-Reduce Conflict
Parser cannot decide:
Shift?
or
Reduce?
---
Reduce-Reduce Conflict
Parser cannot decide which reduction to apply.
---
LR Parsers
LR means:
L = Left to Right Scanning
R = Rightmost Derivation in Reverse
LR Parsers are powerful Bottom-Up Parsers.
---
Types of LR Parsers
1. SLR Parser
Simple LR Parser
Advantages:
Easy implementation
Disadvantages:
Less powerful
---
2. CLR Parser
Canonical LR Parser
Advantages:
Most powerful
Disadvantages:
Large parsing tables
---
3. LALR Parser
Look Ahead LR Parser
Advantages:
Compact tables
Widely used
Used in:
Compiler construction tools
---
Parsing Ambiguous Grammars
Ambiguous grammars create multiple parse trees.
Solutions:
Rewrite grammar
Use precedence rules
Use associativity rules
---
YACC
YACC stands for:
Yet Another Compiler Compiler
Used to generate parsers automatically.
Input:
Grammar Rules
Output:
Parser Program
Works together with:
LEX
LEX → Token Generator
YACC → Parser Generator
---
Important Exam Questions
Short Questions
1. Define Parsing.
2. What is CFG?
3. Define Parse Tree.
4. What is Left Recursion?
5. What is Left Factoring?
6. Define Handle.
7. What is Shift Reduce Parsing?
8. What is YACC?
---
Long Questions
1. Explain Context Free Grammar with examples.
2. Explain Parse Tree and Derivation.
3. Discuss Left Recursion and its elimination.
4. Explain Predictive Parsing.
5. Explain Shift Reduce Parsing with example.
6. Compare SLR, CLR and LALR Parsers.
7. Explain YACC and its role in compiler design.
---
Quick Revision Notes
Parsing = Syntax checking phase.
CFG = Context Free Grammar.
Parse Tree = Graphical representation of derivation.
Left Recursion = Non-terminal appears first on RHS.
Left Factoring = Removes common prefixes.
Top Down = Root → Leaves.
Bottom Up = Leaves → Root.
Shift Reduce = Most common Bottom-Up technique.
LR = Left-to-right scan, Rightmost derivation reverse.
SLR < LALR < CLR (Power).
LEX = Scanner Generator.
YACC = Parser Generator.
Adarsh verma
Adarsh verma
CodeWithAV publishes practical technology tutorials, study resources, programming guides, and cybersecurity learning content.
Compiler Design (MCA554) Unit 1: Introduction to Compilers & Lexical Analysis
Published: June 21, 2026
Author: Adarsh verma
Unit 1: Introduction to Compilers & Lexical Analysis
From your MCA Semester III syllabus.
---
What is a Compiler?
A Compiler is a software that translates a program written in a high-level language into machine language.
Example:
printf("Hello");
Compiler converts it into machine code that the computer understands.
---
Language Translators
1. Compiler
Converts the entire program at once.
Source Program
↓
Compiler
↓
Object Code
Advantages:
Faster execution
Errors shown after compilation
Examples:
C
C++
Go
---
2. Interpreter
Translates line by line.
Source Program
↓
Interpreter
↓
Execute Line by Line
Advantages:
Easy debugging
Disadvantages:
Slower execution
Examples:
Python
JavaScript
---
3. Assembler
Converts Assembly Language to Machine Language.
Assembly Code
↓
Assembler
↓
Machine Code
---
Difference Between Compiler and Interpreter
Compiler Interpreter
Entire program compiled Line by line
Faster execution Slower
Generates object code No object code
Errors after compilation Errors immediately
---
Structure of a Compiler
A compiler consists of several phases.
Source Program
↓
Lexical Analysis
↓
Syntax Analysis
↓
Semantic Analysis
↓
Intermediate Code Generation
↓
Code Optimization
↓
Code Generation
↓
Target Program
---
Phases of Compiler
1. Lexical Analysis
First phase.
Tasks:
Read source code
Remove spaces/comments
Generate tokens
Example:
int a=10;
Tokens:
int
a=10;
---
2. Syntax Analysis
Checks grammatical correctness.
Uses:
Parse Trees
Context Free Grammar
Example:
a = + 5
Syntax Error
---
3. Semantic Analysis
Checks meaning.
Example:
int x;
x = "Hello";
Semantic Error
---
4. Intermediate Code Generation
Creates intermediate representation.
Example:
a = b + c
becomes
t1 = b + c
a = t1
---
5. Code Optimization
Improves efficiency.
Example:
a = 5 + 3
Optimized to:
a = 8
---
6. Code Generation
Produces machine code.
---
Front End and Back End of Compiler
Front End
Handles:
Lexical Analysis
Syntax Analysis
Semantic Analysis
Purpose:
Understand source code
---
Back End
Handles:
Optimization
Code Generation
Purpose:
Produce efficient machine code
-----
Linker
Combines object files.
Example:
main.obj
math.obj
file.obj
↓
Linker
↓
program.exe
---
Loader
Loads executable program into memory.
Program.exe
↓
Loader
↓
Memory
---
Types of Compiler
Single Pass Compiler
Only one scan.
Advantage:
Fast
---
Multi Pass Compiler
Multiple scans.
Advantage:
Better optimization
---
Cross Compiler
Runs on one machine but generates code for another.
Example:
Windows → ARM Processor
---
Lexical Analyzer
Also called:
Scanner
First phase of compiler.
Responsibilities:
Read characters
Form tokens
Remove comments
Ignore spaces
---
Token
Smallest meaningful unit.
Example:
int age=20;
Tokens:
int age = 20;
---
Lexeme
Actual sequence of characters.
Example:
count
Here:
Lexeme = count
---
Pattern
Rule describing a token.
Example:
[a-zA-Z][a-zA-Z0-9]*
Represents identifiers.
---
Recognition of Tokens
Lexical Analyzer identifies:
Keywords
Identifiers
Operators
Constants
Delimiters
---
Examples
Keywords
int
float
while
if
return
---
Identifiers
count
salary
marks
---
Operators
+
-
*
/
=
---
Delimiters
;
,
()
{}
---
Input Buffering
Improves reading efficiency.
Without buffering:
Character by character reading
With buffering:
Reads blocks of data
Benefits:
Faster compilation
---
Issues in Lexical Analysis
1. Removing comments
2. Handling white spaces
3. Detecting invalid tokens
4. Efficient scanning
---
Lexical Analyzer Generator
Tool used to generate lexical analyzers automatically.
Example:
LEX
Input:
Token Rules
Output:
Lexical Analyzer Program
---
Important Exam Questions
Short Questions
1. Define Compiler.
2. Define Token.
3. Define Lexeme.
4. What is a Loader?
5. What is a Linker?
6. What is Input Buffering?
7. What is Lexical Analysis?
8. What is LEX?
---------------
Long Questions
1. Explain structure and phases of a compiler.
2. Differentiate Compiler and Interpreter.
3. Explain Lexical Analysis with examples.
4. Explain Front End and Back End of Compiler.
5. Discuss Tokens, Lexemes and Patterns.
6. Explain Linker and Loader.
--------------
Quick Revision
Compiler = High-level → Machine code.
Interpreter = Line-by-line translation.
Assembler = Assembly → Machine code.
Lexical Analysis = First phase.
Token = Smallest meaningful unit.
Lexeme = Actual text.
Pattern = Rule for token.
Linker = Combines object files.
Loader = Loads program into memory.
LEX = Lexical analyzer generator.
Adarsh verma
Adarsh verma
CodeWithAV publishes practical technology tutorials, study resources, programming guides, and cybersecurity learning content.