COMPILER DESIGN

CS-603(C) — [Link] VI Semester

Complete Question Bank with Answers
RGPV Examinations: May 2023 | May 2024 | Dec 2024 | Jun 2025
UNIT I — Compiler Overview & Lexical Analysis

Q1. Structure of a Compiler and Phases — with id₁=id₂+id₃*50

A compiler is a program that reads source code in one language and translates it into an equivalent
program in another language (usually machine code), reporting errors detected in the process.

Phases of a Compiler:
A compiler works in 6 main phases:
1. Lexical Analysis (Scanner)
2. Syntax Analysis (Parser)
3. Semantic Analysis
4. Intermediate Code Generation
5. Code Optimization
6. Code Generation

Output of each phase for: id₁ = id₂ + id₃ * 50

Phase Output
Lexical Analysis <id,1> <=> <id,2> <+> <id,3> <*> <50>
Syntax Analysis Parse tree representing the expression
structure
Semantic Analysis Type-checked tree; 50 converted to float if
needed
Intermediate Code Gen t1 = id3 * 50 t2 = id2 + t1 id1 = t2
Code Optimization t1 = id3 * 50.0 id1 = id2 + t1
Code Generation MOV R1, id3 MUL R1, 50.0 MOV R2, id2 ADD
R2, R1 MOV id1, R2

Structure of Compiler (Diagram Description):

Source Program → [Lexical Analyzer] → Tokens → [Syntax Analyzer] → Parse Tree → [Semantic
Analyzer] → Annotated Tree → [Intermediate Code Generator] → IR → [Code Optimizer] →
Optimized IR → [Code Generator] → Target Code
The Symbol Table and Error Handler interact with all phases throughout compilation.

Q2. Analysis and Synthesis Model — a = (b+c)*(b+c)*2

Analysis Phase (Front End):
The analysis phase breaks down source code into pieces and creates an intermediate
representation.
• Lexical Analysis: Scans 'a = (b + c) * (b + c) * 2' → tokens: <id,a>, <=>, <(>, <id,b>, <+>,
<id,c>, <)>, <*>, ..., <2>
 • Syntax Analysis: Builds parse tree confirming grammar rules are satisfied
• Semantic Analysis: Checks types are compatible, operators match operands

Synthesis Phase (Back End):

• Intermediate Code: t1=b+c; t2=t1*t1; t3=t2*2; a=t3
• Code Optimization: t1=b+c; a=t1*t1*2 (eliminating common sub-expression)
• Code Generation: Produces target assembly/machine code

Q3. Various Phases of a Compiler

1. Lexical Analysis:
Reads characters from source, groups them into tokens (identifiers, keywords, operators, literals).
Removes whitespace and comments. Produces a token stream.
2. Syntax Analysis (Parsing):
Takes token stream, checks syntactic structure using grammar rules (CFG). Produces a parse tree
or Abstract Syntax Tree (AST). Reports syntax errors.
3. Semantic Analysis:
Checks semantic consistency: type checking, undeclared variables, type mismatches, function
argument counts. Uses symbol table.
4. Intermediate Code Generation:
Generates a machine-independent IR like Three-Address Code (TAC) or quadruples. Easier to
optimize.
5. Code Optimization:
Improves IR to run faster or use less memory. Techniques: constant folding, dead code elimination,
common sub-expression elimination.
6. Code Generation:
Translates optimized IR to target machine code. Handles register allocation, instruction selection.

Q4. Translator — Compiler vs Interpreter

Translator:
A translator is a program that converts source code from one language to another. Types: Compiler,
Interpreter, Assembler.

Feature Compiler Interpreter

Translation Method Translates entire program at Translates and executes line-
once before execution by-line
Memory Requirement Requires more memory (stores Requires less memory (no
entire object code) separate object code)
Speed Faster execution (compiled Slower execution (translates
once) each time)
Error Detection All errors reported after Errors reported immediately,
complete scan stops at first error
 Output Produces separate No separate output file
object/executable file produced
Examples C, C++, Java (javac) Python, Ruby, BASIC

Q5. Frontend and Backend Model of Compiler

Frontend:
The front end is machine-independent and deals with language-specific features: lexical analysis,
parsing, semantic analysis, and IR generation.
Backend:
The back end is machine-dependent and deals with target architecture: code optimization and code
generation.

Model Advantages Disadvantages

Frontend Portable — same front end Interface between front/back
works with different back ends; end can be complex
Easier to maintain
Backend Target-specific optimizations Not portable; Changes to
possible; Efficient machine hardware require rewriting
code
Combined Tight coupling allows better Not reusable; Hard to port to
global optimization new hardware

Q6. Compiler Construction Tools

• LEX / Flex: Lexical analyzer generator. Takes regular expression specifications and
produces C code for a scanner.
• YACC / Bison: Yet Another Compiler Compiler. Generates a parser from BNF grammar
specifications. Handles LALR(1) parsing.
• SDT Tools: Tools to specify semantic actions and generate attribute evaluators.
• Code Generator Generators: Take machine descriptions and generate code generators
(e.g., BURG).
• Data-Flow Analysis Engines: Automate creation of data-flow analyzers for optimizations.
• Compiler Construction Frameworks: Like LLVM, GCC — provide complete infrastructure.

Q7. LEX Tool

LEX is a lexical analyzer generator. It takes a specification file (.l) containing regular expressions
and associated actions, and produces a C program ([Link].c) that implements the scanner.
Structure of a LEX Program:
%{ declarations %}
%%
pattern1 { action1 }
pattern2 { action2 }
%%
user subroutines
How LEX Works:
• Reads the specification file
• Converts regular expressions to NFA then DFA
• Generates yylex() function that tokenizes input
• Returns token type values for use by parser

Q8. LEX Program for C Language Tokens

%{
#include <stdio.h>
#define ID 1
#define NUM 2
#define KEYWORD 3
#define OP 4
%}
%%
int|float|char|void|if|else|while|for|return|do { printf("KEYWORD: %s\n",
yytext); return KEYWORD; }
[a-zA-Z_][a-zA-Z0-9_]* { printf("ID: %s\n", yytext); return ID; }
[0-9]+(\.?[0-9]+)? { printf("NUM: %s\n", yytext); return NUM; }
[+\-*/=<>!&|] { printf("OP: %s\n", yytext); return OP; }
[;,(){}\[\]] { printf("PUNCT: %s\n", yytext); }
[ \t\n]+ { /* skip whitespace */ }
. { printf("UNKNOWN: %s\n", yytext); }
%%
int main() { yylex(); return 0; }

Q9. Issues in Lexical Analyzer Design & Input Buffering

Issues in Lexical Analyzer Design:
• Tokenization: Deciding how to divide character stream into tokens
• Handling comments and whitespace: Must ignore these efficiently
• Error handling: What to do with unrecognized characters
• Lookahead: Some tokens need 1 or more characters of lookahead (e.g., '>' vs '>=')
• String literals: Handling escape sequences like \n, \t
• Case sensitivity: Some languages are case-sensitive (C) others not (Pascal)

Why Buffering is Used:

Reading one character at a time from disk is very slow. Buffering reads a large block (e.g., 4096
bytes) at once into a buffer. Two-buffer scheme is used:
• Buffer 1 and Buffer 2 alternate. Each holds one block (e.g., 4096 chars).
• Two pointers: lexemeBegin (start of current token) and forward (scanner position).
• When forward hits end of Buffer 1, Buffer 2 is loaded and scanning continues.
• This allows efficient one-character-at-a-time scanning with O(1) lookahead.
Q10. Pre-processing and Input Buffering
Pre-processing:
Pre-processing tasks handled before or during lexical analysis:
• Strip comments from source
• Recognize and process #include, #define directives (in C)
• Handle continuation lines (backslash-newline sequences)
• Handle conditional compilation (#ifdef, #endif)
In many systems, a separate preprocessor (like cpp) handles these before the compiler.

Input Buffering:
Two-Buffer Scheme: Two buffers of size N (typically 4096) are used.
• eof sentinel is placed at the end of each buffer to detect buffer boundaries
• 'lexemeBegin' pointer marks start of current lexeme
• 'forward' pointer scans ahead to find the end of the lexeme
• When forward reaches sentinel at end of buffer 1, buffer 2 is loaded and forward moves
there
• Advantage: Efficient — disk reads are large blocks, not single characters
UNIT II — Syntax Analysis (Parsing)

Q11. Top-Down vs Bottom-Up Parser

Feature Top-Down Parser Bottom-Up Parser
Approach Starts from start symbol, Starts from input, reduces to
expands to match input start symbol
Direction Left to right, leftmost derivation Left to right, rightmost
derivation (reversed)
Parsing Method Predictive / Recursive Descent Shift-Reduce (SLR, LALR,
CLR)
Grammar LL(1) grammars LR(0), LR(1), LALR grammars
Backtracking May require backtracking No backtracking
Example Recursive Descent Parser, SLR parser, LALR parser,
LL(1) parser Operator precedence
Power Less powerful More powerful — handles
wider grammar class

Top-Down Example — Grammar: S → aA | b, A → bc

• Input: abc — Expand S→aA, match 'a', expand A→bc, match 'bc' — SUCCESS

Bottom-Up Example — Grammar: S→aA, A→b:

• Input: ab — Shift 'a', shift 'b', reduce b→A, reduce aA→S — SUCCESS

Q12. Parser — Backtracking and Non-Backtracking Parsers

Parser:
A parser takes a stream of tokens from the lexical analyzer and checks whether the token stream
conforms to the grammar of the language. It builds a parse tree.

Backtracking Parsers:
Try one production rule; if it fails, undo (backtrack) and try another.
• Slow — exponential time in worst case
• Example: Recursive descent with backtracking
• Used when grammar is ambiguous or choices cannot be predicted

Non-Backtracking Parsers:
Use lookahead symbol(s) to determine the correct production — no backtracking needed.
• LL(1) Parser (Top-Down): Uses 1 lookahead. Builds predictive parsing table.
• LR Parsers (Bottom-Up): SLR, LALR, CLR — most powerful. Uses parsing table + stack.
• Operator Precedence Parser: Uses precedence relations between operators.
Q13. Recursive Descent Parser with Backtracking — S → aSbS | bSaS | ε
Grammar:
S → aSbS | bSaS | ε

Recursive Descent Parser with Backtracking (Pseudocode):

int pos; // global input position

bool S() {
int save = pos;
// Try S → aSbS
if (match('a') && S() && match('b') && S()) return true;
pos = save; // backtrack
// Try S → bSaS
if (match('b') && S() && match('a') && S()) return true;
pos = save; // backtrack
// Try S → ε
return true;
}

bool match(char c) {
if (input[pos] == c) { pos++; return true; }
return false;
}

Trace for input 'ab':

S() tries aSbS: match('a')→ok, S()→ε, match('b')→ok, S()→ε → SUCCESS. String 'ab' is accepted.

Q14. Left Factoring in Grammar

Definition:
Left factoring is a grammar transformation used to make a grammar suitable for predictive parsing
by eliminating common prefixes in productions.

When it is needed:
When two or more productions for the same non-terminal begin with the same terminal(s), the
parser cannot choose between them with one lookahead.

Example — Before Left Factoring:

A → αβ₁ | αβ₂
After Left Factoring:
A → α A'
A' → β₁ | β₂
Concrete Example:
S → iEtS | iEtSeS | a
Both first two alternatives start with 'iEt'. After left factoring:
S → iEtSS' | a
S' → eS | ε

Q15. Ambiguity and Left Recursion

(i) Ambiguity:
A grammar is ambiguous if there exists a string that can be derived using more than one parse tree
(or equivalently, more than one leftmost derivation or rightmost derivation).
Example:
E → E + E | E * E | (E) | id
The string 'id + id * id' has two parse trees — one where + is applied first, another where * is applied
first. This grammar is ambiguous.
Ambiguity is usually resolved by specifying operator precedence and associativity rules.

(ii) Left Recursion:

A grammar is left-recursive if a non-terminal A can derive a string beginning with A itself.
Direct: A → Aα | β
Indirect: A → Bα, B → Aβ
Left recursion causes infinite loops in top-down parsers. It must be eliminated.
Elimination of Direct Left Recursion:
A → Aα | β becomes:
A → β A'
A' → α A' | ε

Q16. Eliminate Left Recursion from:

S → Aa | b
A → Ac | Sd | ε

Step 1 — Arrange in order: S, A

Substitute S into A's productions where A derives Sd:
S → Aa | b (no left recursion in S directly)
A → Ac | Sd | ε
Substitute S = Aa | b into Sd:
Sd = (Aa | b)d = Aad | bd
So: A → Ac | Aad | bd | ε

Step 2 — Eliminate left recursion from A:

A has left-recursive productions: A → Ac | Aad
 Non-left-recursive: bd, ε
Left-recursive suffixes: c, ad

Result:
S → Aa | b
A → bd A' | A'
A' → c A' | ad A' | ε

Q17. Leftmost, Rightmost Derivation and Parse Tree

Grammar:
S → a | ∧ | (T)
T → T,S | S
String: (((a,a),∧(a)),a)

Leftmost Derivation (abbreviated):

S ⟹ (T)
⟹ (T,S)
⟹ (T,a)
⟹ ((T),a)
⟹ ((T,S),a)
⟹ ((T,∧(a)),a)
⟹ (((T),∧(a)),a)
⟹ (((T,S),∧(a)),a)
⟹ (((T,a),∧(a)),a)
⟹ (((a,a),∧(a)),a) ✓

Rightmost Derivation:
Similar to above but rightmost non-terminal is always replaced first.

Parse Tree Description:

Root S → (T). The T derives T,S. The right S→a. Left T→(T). Inner T→T,S. Right S→ ∧(a) where
T→a. Left T→T,S with S→a and T→a. This builds the nested structure for (((a,a), ∧(a)),a).

Q18. FIRST and FOLLOW Sets

Grammar:
S → aAB | bA | ε
A → aAb | ε
B → bB | ε

FIRST Sets:
• FIRST(S) = {a, b, ε}
• FIRST(A) = {a, ε}
 • FIRST(B) = {b, ε}

Derivations:
FIRST(S): From S→aAB, first terminal is 'a'. From S→bA, first is 'b'. From S→ε, add ε. So
FIRST(S)={a, b, ε}.
FIRST(A): From A→aAb, first is 'a'. From A→ε, add ε. So FIRST(A)={a, ε}.
FIRST(B): From B→bB, first is 'b'. From B→ε, add ε. So FIRST(B)={b, ε}.

FOLLOW Sets:
(Assume S is start symbol, $ is end marker)
• FOLLOW(S) = {$} (S is start symbol)
• FOLLOW(A): A appears in S→aAB and S→bA. After A in aAB, compute FIRST(B)={b,ε}.
Since ε∈FIRST(B), add FOLLOW(S)={$}. After A in bA, add FOLLOW(S)={$}. So
FOLLOW(A) = {b, $}.
• FOLLOW(B): B appears in S→aAB. After B, add FOLLOW(S)={$}. Also B→bB: after B add
FOLLOW(B). So FOLLOW(B) = {$}.
UNIT III — LR Parsing & Parsing Tables

Q19. LR(0) Items and SLR Parser Table

Grammar:
S' → S
S → L=R | R
L → *R | id
R → L

Augmented Grammar with item numbering:

(0) S' → S
(1) S → L=R
(2) S → R
(3) L → *R
(4) L → id
(5) R → L

LR(0) Canonical Collection of Items:

I0: S'→.S, S→.L=R, S→.R, L→.*R, L→.id, R→.L
I1: S'→S. [ACCEPT]
I2: S→L.=R, R→L.
I3: S→R.
I4: L→*.R, R→.L, L→.*R, L→.id
I5: L→id.
I6: S→L=.R, R→.L, L→.*R, L→.id
I7: L→*R.
I8: R→L. (inside I4)
I9: S→L=R.

FOLLOW Sets (needed for SLR):

• FOLLOW(S') = {$}
• FOLLOW(S) = {$}
• FOLLOW(L) = {=, $}
• FOLLOW(R) = {$}

SLR Parsing Table:

State id * = $ S L R
0 s5 s4 1 2 3

1 acc

2 s6 r5
 3 r2

4 s5 s4 8 7

5 r4 r4

6 s5 s4 2 9

7 r3

8 r5 r5

9 r1

Q20. SLR Parsing Table for E→E+T, T→TF/F, F→F*/a/b

Augmented Grammar:
E' → E
E → E+T | T
T → TF | F
F → F* | a | b

LR(0) Items are computed similarly. The SLR table structure:

States are built from the closure of items. Actions are determined by:
• Shift: When dot is before a terminal, shift and go to next state
• Reduce: When dot is at end of production, reduce using FOLLOW sets
• Accept: When S'→S. is reached

Key FOLLOW sets:

• FOLLOW(E) = {+, $}
• FOLLOW(T) = {+, a, b, $}
• FOLLOW(F) = {+, a, b, *, $}

Q21. LALR Parsing Table and Verification for id+id*id

Grammar:
E → E+T | T
T → T*F | F
F → (E) | id

Augmented Grammar:
E' → E (0)
E → E+T (1)
E → T (2)
T → T*F (3)
T → F (4)
F → (E) (5)
F → id (6)
FOLLOW Sets:
• FOLLOW(E) = {$, +, )}
• FOLLOW(T) = {$, +, *, )}
• FOLLOW(F) = {$, +, *, )}

LALR Parsing Table (key entries):

State id + * ( ) $ E T F
0 s5 s4 1 2 3

1 s6 acc

2 r2 s7 r2 r2

3 r4 r4 r4 r4

4 s5 s4 8 2 3

5 r6 r6 r6 r6

6 s5 s4 9 3

7 s5 s4 10

8 s6 s11

9 r1 s7 r1 r1

10 r3 r3 r3 r3

11 r5 r5 r5 r5

Verification: id+id*id
Stack Input Action
0 id+id*id$ Shift 5
05 +id*id$ Reduce F→id (r6)
03 +id*id$ Reduce T→F (r4)
02 +id*id$ Reduce E→T (r2)
01 +id*id$ Shift 6
016 id*id$ Shift 5
0165 *id$ Reduce F→id
0163 *id$ Reduce T→F
0169 *id$ Shift 7
01697 id$ Shift 5
016975 $ Reduce F→id
0 1 6 9 7 10 $ Reduce T→T*F
0169 $ Reduce E→E+T
01 $ ACCEPT
The string id+id*id is ACCEPTED by the grammar.

Q22. LALR Parsing Table for E→E+T/T, T→T*F/F, F→(E)/id

This grammar is the same as Q21. The LALR parsing table is identical to that constructed in Q21.
Please refer to the table in Q21.
LALR parsers are constructed by merging LR(1) states that have the same core (same LR(0)
items). If no conflicts arise after merging, the LALR table is valid.

Q23. Conflicts in Shift-Reduce Parsing

1. Shift-Reduce Conflict:
Occurs when a state has both a shift action and a reduce action for the same lookahead symbol.
The parser cannot decide whether to shift the next input symbol or reduce the current stack
contents.
Example:
S → if E then S | if E then S else S
When 'else' is seen, parser can either shift (associate 'else' with nearest 'if') or reduce (close the
current if-then). The 'dangling else' problem.
Resolution: Usually prefer shift over reduce (associates else with nearest if).

2. Reduce-Reduce Conflict:
Occurs when a state has two different reduce actions for the same lookahead symbol — two
different productions can be used to reduce the same string.
Example:
A → α
B → α
When both A→α and B→α can reduce the same α, the parser doesn't know which to choose. This
usually indicates a grammar design problem.
Resolution: Typically resolved by grammar restructuring or using a more powerful parser (LALR vs
SLR).
UNIT IV — Syntax Directed Translation & Intermediate Code

Q24. DAG for a = (a*b+c) – (a*b+c)

DAG (Directed Acyclic Graph):
A DAG is a compact representation of an expression that identifies common sub-expressions.
Unlike a parse tree, common sub-expressions appear only once.

Expression: a = (a*b+c) – (a*b+c)

Sub-expressions:
• Node 1: a (leaf)
• Node 2: b (leaf)
• Node 3: c (leaf)
• Node 4: a*b → children: Node1 (*) Node2
• Node 5: a*b+c → children: Node4 (+) Node3
• Node 6: (a*b+c)–(a*b+c) → children: Node5 (–) Node5 [SAME node, not repeated!]
• Node 7: a = Node6

Key insight:
(a*b+c) appears twice but the DAG has only ONE node for it (Node5), with Node6 pointing to it
twice. This saves computation at code generation time — the sub-expression is computed once.

Q25. DAG for Basic Block: D:=B*C; E:=A+B; B:=B+C; A:=E-D

Step-by-step DAG construction:

7. D := B*C — Create leaf B, leaf C, node (*) with children B,C. Label this node D.
8. E := A+B — Create leaf A, reuse leaf B, node (+) with children A,B. Label this node E.
9. B := B+C — Create node (+) with children B(old),C. Label this node B (B is now updated).
10. A := E-D — Reuse E node and D node. Create node (-) with children E,D. Label this node A.

DAG Nodes:
• Leaves: A₀, B₀, C (original values)
• n1: B₀ * C → D
• n2: A₀ + B₀ → E
• n3: B₀ + C → B (new B)
• n4: n2 – n1 → A (new A)

Q26. Algorithm to Construct a DAG from a Basic Block

Algorithm (for three-address instructions x := y op z):
 For each instruction in basic block:
1. Check if node for y exists; if not, create leaf node y.
2. Check if node for z exists; if not, create leaf node z.
3. Check if there exists a node m with children (y_node op z_node).
If yes, set node(x) = m. (common sub-expression found!)
If no, create new node m with operator op,
left child = node(y), right child = node(z).
Add x to the label list of m.
4. If x was previously a label of another node, remove it from there.
5. node(x) = m

For assignment x := y (copy):

1. Find/create node for y.
2. Add x to label list of node(y). [No new node needed]

Output:
A DAG where each node either is a leaf (identifier/constant) or has an operator and children.
Multiple variable names may label the same node (aliases).

Q27. DAG for T₁=A+B; T₂=C+D; T₃=E–T₂; T₄=T₁–T₃

11. T₁ = A+B: Create leaves A, B. Create node n1: (+, A, B). Label: T₁
12. T₂ = C+D: Create leaves C, D. Create node n2: (+, C, D). Label: T₂
13. T₃ = E–T₂: Create leaf E. Create node n3: (–, E, n2). Label: T₃
14. T₄ = T₁–T₃: Create node n4: (–, n1, n3). Label: T₄

DAG Structure:
n4: (-)
/ \
n1:(+) n3:(-)
/ \ / \
A B E n2:(+)
/ \
C D

No common sub-expressions exist in this basic block, so the DAG has the same structure as the
expression tree.

Q28. Synthesized and Inherited Attributes

Synthesized Attributes:
An attribute is synthesized if its value at a parse tree node is determined from the attribute values of
its children.
Production: E → E₁ + T
 SDT rule: [Link] = E₁.val + [Link]
Here [Link] is a synthesized attribute — computed from children E₁ and T. Information flows bottom-
up.

Inherited Attributes:
An attribute is inherited if its value at a node is determined from the attribute values of its parent or
siblings.
Production: D → T L
SDT rule: [Link] = [Link]
L → L₁, id { L₁.in = [Link]; addType(id, [Link]) }
Here [Link] is an inherited attribute — passed down from D to L. Information flows top-down.

Key Differences:
Feature Synthesized Inherited
Information flow Bottom-up Top-down or sideways
Value comes from Children Parent or siblings
S-attributed grammar Yes (all synthesized) No
Evaluation Post-order traversal Requires pre/in-order traversal
Example [Link] for expressions type attribute for declarations

Q29. Differences between Synthesized and Inherited Attributes

Feature Synthesized Attributes Inherited Attributes
Definition Computed from children Computed from parent/siblings
Data flow Bottom-up Top-down/Lateral
Parse tree traversal Post-order Pre-order or mixed
S-attribute grammar Form S-attributed grammar Cannot be used alone in S-
attributed
L-attribute grammar Allowed Allowed if siblings are to the
left
Use case Expression values, types Scope info, type context for
declarations
Complexity Simpler to evaluate More complex
Example E→E+T: [Link]=[Link]+[Link] D→TL: [Link]=[Link]

Q30. Synthesized Attributes, Annotated Parse Tree, Dependency Graph

(i) Synthesized Attributes:
Already covered in Q28. An attribute whose value is computed from children nodes.
E → E₁ + T { [Link] = E₁.val + [Link] }

(ii) Annotated Parse Tree:

A parse tree where each node is annotated with the values of its attributes is called an annotated
parse tree (or decorated parse tree).
Example for 3+4*5:
[Link]=23
/ \
[Link]=3 [Link]=20
| / \
[Link]=3 [Link]=4 [Link]=5

(iii) Dependency Graph:

A dependency graph is a directed graph showing dependencies between attribute instances. An
edge from b.a to c.b means that in computing attribute a of node b, attribute a of node c is needed.
Used to determine a valid evaluation order. If the graph is acyclic, attributes can be evaluated in
topological order. A cycle indicates a semantic error.

Q31. S-Attributed and L-Attributed SDT

S-Attributed SDT:
An SDT where all attributes are synthesized. Semantic rules only use attribute values of symbols to
the right in the production body (i.e., children). Can be evaluated bottom-up during LR parsing.

L-Attributed SDT:
An SDT where each inherited attribute of a symbol on the RHS depends only on: (1) inherited
attributes of the head (left side) non-terminal, or (2) attributes of symbols to the left of it in the RHS.
Can be evaluated top-down.

SDT Rules for the given grammar:

S → S*A { [Link] = [Link] * [Link] }
S → A { [Link] = [Link] }
A → A+B { [Link] = [Link] + [Link] }
A → B { [Link] = [Link] }
B → (S) { [Link] = [Link] }
B → id { [Link] = [Link] }

These are all synthesized attributes → S-attributed SDT. Also qualifies as L-attributed.

Q32. SDT to Convert Infix to Postfix

Grammar and Translation Rules:
E → E₁ + T { [Link] = E₁.post || [Link] || '+' }
E → E₁ - T { [Link] = E₁.post || [Link] || '-' }
E → T { [Link] = [Link] }
T → T₁ * F { [Link] = T₁.post || [Link] || '*' }
T → T₁ / F { [Link] = T₁.post || [Link] || '/' }
T → F { [Link] = [Link] }
 F → (E) { [Link] = [Link] }
F → id { [Link] = [Link] }

Example: a+b*c → postfix abc*+

• id 'a' → [Link] = 'a'
• id 'b' → [Link] = 'b'
• id 'c' → [Link] = 'c'
• b*c → [Link] = 'b' 'c' '*' = bc*
• a+b*c → [Link] = 'a' 'bc*' '+' = abc*+

Q33. Intermediate Code Generation Techniques

1. Three-Address Code (TAC):
Each instruction has at most one operator and three operands (result, operand1, operand2).
Forms: x = y op z | x = op y | x = y | goto L | if x relop y goto L
Representations: Quadruples, Triples, Indirect Triples

2. Quadruples:
(op, arg1, arg2, result)
e.g., (+, a, b, t1) means t1 = a + b

3. Triples:
(op, arg1, arg2) — result referenced by statement number
e.g., (0): (+, a, b) means (0) = a + b

4. Syntax Trees / DAG:

Abstract representation. DAG compactly represents expressions with common sub-expressions.

5. Postfix Notation:
Operators follow their operands. Example: a+b → ab+. Easy to evaluate with a stack.

Q34. Three-Address Code for While Loop

Source code:
while (a < c and b < d) do
if a = 1 then c = c + 1
else
while (a <= d) do
a = a + 3

Three-Address Code:
L1: if a < c goto L2 // check a < c
goto LEND // exit outer while
L2: if b < d goto L3 // check b < d
 goto LEND // exit outer while
L3: if a = 1 goto L4 // if a=1
goto L5 // else
L4: t1 = c + 1
c = t1
goto L1 // back to outer while
L5: if a <= d goto L6 // inner while condition
goto L1 // inner while done, back to outer
L6: t2 = a + 3
a = t2
goto L5 // repeat inner while
LEND: // outer while exit

Q35. Three-Address Code for P := (X+Y) + (X-C)

Three-Address Code:
t1 = X + Y
t2 = X - C
t3 = t1 + t2
P = t3

As Quadruples:
No. Op Arg1 Arg2 Result
(0) + X Y t1
(1) - X C t2
(2) + t1 t2 t3
(3) = t3 P

Q36. Compute [Link] for 2«3 & 5#6 & 4

Translation rules:
E → E1 # T { [Link] = [Link] * [Link] }
E → T { [Link] = [Link] }
T → T1 & F { [Link] = [Link] + [Link] }
T → F { [Link] = [Link] }
F → num { [Link] = [Link] }

Expression: 2«3 & 5#6 & 4

Assumption: '«' appears to be a token that acts like a number separator; the expression structure
based on grammar is: E # T where T → T & F.
Re-reading: Expression = (2«3) & 5 # (6) & 4. With # as product operator and & as addition:
Parse: E → E1 # T
E1 → T → T1 & F → F & F → 2 & 5 — but 2«3 seems like num=2, then ?,
skipping '«' as separator
Treating '2«3' as meaning T=T1 & F with F=2 and F=3: T=2+3=5. '5' on right of &: T=5+5=10.
Left of #: [Link] = 10. Right of #: T → T1 & F → 6 & 4 → 6+4 = 10.
[Link] = [Link] * [Link] = 10 * 10 = 100
UNIT V — Type Checking & Storage Allocation

Q37. Role of a Type Checker in Compiler

Type Checker:
A type checker verifies that each operation in the source program receives operands of the correct
type according to the type system of the language. It is part of the semantic analysis phase.

Roles of Type Checker:

• Type Inference: Determines the type of an expression from its context
• Type Verification: Checks that operators receive operands of compatible types
• Coercion Detection: Identifies implicit type conversions (e.g., int to float)
• Declaration Checking: Verifies variables are declared before use
• Function Checking: Verifies function calls have correct number and types of arguments
• Array Checking: Ensures array subscripts are integers, array dimensions are correct
• Pointer Checking: Validates pointer operations

Type Rules Examples:

If E1: integer and E2: integer then E1+E2: integer
If E1: float and E2: integer then E1+E2: float (coercion of E2)
if E: boolean then 'if E then S' is valid

Type Error Handling:

When a type error is found, the type checker can: report error and stop, report error and attempt
recovery, or insert type coercions.

Q38. Equivalence of Type Expressions

Type Expressions:
Types are expressed as type expressions. Basic types (int, char, float) are type expressions.
Constructors (array, pointer, function→, records) build complex types.

Structural Equivalence:
Two types are structurally equivalent if they have the same structure — same basic types combined
with the same constructors in the same way.
array(10, integer) ≡ array(10, integer) [structurally equivalent]
pointer(integer) ≡ pointer(integer)

Name Equivalence:
Two types are name-equivalent only if they have the same name. Even if structures are identical,
different names mean different types.
type A = record { x: int }
 type B = record { x: int }
A and B are NOT name-equivalent even though structurally equal.

Algorithm for Structural Equivalence:

equiv(s, t):
if s and t are same basic type: return true
if s = array(m,s1) and t = array(n,t1): return m==n and equiv(s1,t1)
if s = s1→s2 and t = t1→t2: return equiv(s1,t1) and equiv(s2,t2)
return false

Q39. Sources of Optimization of Basic Blocks

A basic block is a maximal sequence of instructions with: one entry point, one exit point, no
branches in or out except at start/end.

Sources of Optimization:
1. Common Sub-Expression Elimination:
If the same expression is computed more than once and operands haven't changed, compute it only
once.
t1 = a + b; t2 = a + b → t1 = a+b; t2 = t1

2. Dead Code Elimination:

Remove code that computes values that are never used.
x = 5; x = 10; // first assignment is dead

3. Constant Folding:
Evaluate constant expressions at compile time.
t = 3 * 4 → t = 12

4. Copy Propagation:
Replace use of copy targets with the copied value.
x = y; z = x + 1 → z = y + 1

5. Algebraic Simplification:
x = x + 0 → (remove) | x = x * 1 → (remove)

6. Strength Reduction:
x = y * 2 → x = y + y (addition faster than multiplication)

Q40. Storage Allocation Strategies

1. Static Storage Allocation:
Memory is allocated at compile time. Size and layout of all data objects is known at compile time.
• Storage bound to program names before execution begins
 • No runtime overhead for allocation
• Examples: FORTRAN global variables, C static variables
• Limitation: Cannot support recursion, dynamic data structures

2. Stack (Dynamic) Storage Allocation:

Memory is managed using a runtime stack. Each procedure call pushes an activation record; return
pops it.
• Supports recursion naturally
• Local variables, parameters, return addresses stored in activation record
• LIFO order — efficient with stack pointer
• Limitation: Cannot be used for objects that outlive the procedure call

3. Heap Storage Allocation:

Memory is dynamically allocated and freed at runtime in arbitrary order using malloc/free or
new/delete.
• Flexible — objects can have dynamic lifetimes
• Used for data structures like linked lists, trees
• Overhead: Fragmentation, garbage collection needed
• Examples: malloc in C, new in C++/Java

Strategy When Allocated Supports Flexible Size Overhead

Recursion
Static Compile time No No None
Stack Runtime (call) Yes Limited Low (push/pop)
Heap Runtime (explicit) Yes Yes High

Q41. Stack vs Heap Storage Allocation

Stack Allocation:
Uses a stack data structure (LIFO). Each procedure invocation creates an activation record pushed
on the stack.
Activation Record contains:
• Return address
• Local variables
• Parameters
• Saved registers
• Temporaries

Merits of Stack:
• Efficient — O(1) allocation and deallocation
• Automatic — no programmer effort
• Supports recursion
Demerits of Stack:
 • Cannot allocate memory that outlives procedure call
• Fixed size — may cause stack overflow

Heap Allocation:
A region of memory where blocks can be allocated and freed in any order.
Merits of Heap:
• Objects can have arbitrary lifetimes
• Dynamic sizes
• Supports complex data structures
Demerits of Heap:
• Fragmentation (internal and external)
• Overhead of allocator
• Memory leaks if not freed
• Need garbage collection in managed languages

Q42. Activation Record and its Model

Activation Record (AR):
An activation record (also called a stack frame) is a block of memory allocated on the runtime stack
when a procedure is called. It stores all information needed for that invocation.

Model of Activation Record (from high to low address):

Field Purpose
Return Value Space for function's return value
Actual Parameters Values passed by caller
Optional Control Link Pointer to caller's activation record
Optional Access Link For accessing non-local variables (in nested
procedures)
Saved Machine Status Saved registers, program counter
Local Data Local variables of the procedure
Temporaries Values needed temporarily during expression
evaluation

Access Patterns:
• sp (stack pointer): points to top of stack
• fp (frame pointer): points to fixed location in current AR
• Local variables accessed as fp + offset (negative offsets)
• Parameters accessed as fp + offset (positive offsets)

Q43. Polymorphic Functions

Polymorphism:
Polymorphism allows a single function to work with arguments of different types.

Types of Polymorphic Functions:

1. Parametric Polymorphism:
A function is parametrically polymorphic if it works uniformly for all types.
function length<T>(list: List<T>): int
The function works for List<int>, List<string>, etc.

2. Ad-hoc Polymorphism (Overloading):

Same function name has different implementations for different types.
int add(int a, int b) { return a+b; }
float add(float a, float b){ return a+b; }

3. Subtype Polymorphism (Inclusion):

A function that works on type T also works on any subtype S of T.
void print(Shape s) // works for Circle, Rectangle (subtypes of Shape)

4. Coercion Polymorphism:
Type is automatically converted to match the expected type.
void f(float x); f(3); // 3 (int) coerced to 3.0 (float)
UNIT VI — Code Optimization

Q44. Flow Graph for i=1; sum=0; while(i<=10){sum+=i;i++;}

Three-Address Code:
i = 1
sum = 0
L1: if i > 10 goto L2
t1 = sum + i
sum = t1
t2 = i + 1
i = t2
goto L1
L2: [exit]

Basic Blocks:
• B1: i=1; sum=0 (entry block)
• B2: if i>10 goto L2 (loop condition — header)
• B3: t1=sum+i; sum=t1; t2=i+1; i=t2; goto L1 (loop body)
• B4: exit

Flow Graph Edges: B1→B2, B2→B3 (false), B2→B4 (true), B3→B2

Sources of Optimization of Basic Blocks:

(See Q39 for detailed answer — Common Sub-expression Elimination, Dead Code Elimination,
Constant Folding, Copy Propagation, Algebraic Simplification, Strength Reduction)

Q45. Flow Graph for prod=0; i=1; t₁=4*i; etc.

Three-Address Code given:
prod=0; i=1; t₁=4*i; t₂=a[t₁]; t₃=4*j; t₄=b[t₃]; t₅=t₃*t₄; t₆=prod+t₅;
prod=t₆

Leaders (start of each basic block):

• Instruction 1 (prod=0) — first instruction
Since there are no branches or labels in this code, it is all ONE basic block B1.

Flow Graph:
Entry → B1 → Exit
B1 contains all instructions. No loops or branches.

Flow Graph Definition:

A flow graph is a directed graph where nodes represent basic blocks and edges represent possible
control flows between blocks. An edge from B1 to B2 means control can pass from B1 to B2.

Q46. Flow Graph — Definition and Construction

Flow Graph:
A flow graph is a directed graph G = (N, E, n₀) where N is set of nodes (basic blocks), E is set of
edges (control flow), and n₀ is the initial node.

Steps to Convert Program to Flow Graph:

15. Generate Three-Address Code for the program
16. Partition TAC into basic blocks: Find leaders (first statement, target of goto, statement after
conditional goto). Each leader starts a new basic block.
17. Determine edges: If block B1 ends with 'goto L', add edge B1→block starting at L. If B1 ends
with 'if cond goto L', add edge B1→L-block AND B1→next block. Otherwise, add edge to
next block.
18. Add ENTRY and EXIT nodes

Example:
Code: Leaders: Blocks:
a=1 a=1 B1: a=1, if a<5 goto L1
if a<5 L1: B2: b=2
goto L1 b=2 B3: c=3
b=2 Edges: B1→B3(true to L1), B1→B2(false)
L1: c=3

Q47. Principle Sources of Optimization

1. Function-Preserving Transformations:
• Common Sub-expression Elimination (CSE): Avoid redundant computation
• Copy Propagation: Replace copies with original values
• Dead Code Elimination: Remove unreachable or unused code
• Constant Folding: Evaluate constant expressions at compile time

2. Loop Optimizations:
• Code Motion (Loop Invariant Removal): Move loop-invariant computations outside the loop
• Induction Variable Elimination: Replace induction variable expressions with simpler ones
• Strength Reduction: Replace expensive operations (multiplication) with cheaper ones
(addition) inside loops

3. Global Optimizations:
• Global CSE: Across basic blocks
• Global Data Flow Analysis: Propagate information across the entire program

4. Peephole Optimizations:
 • Redundant instruction elimination
• Flow of control optimizations
• Algebraic simplification in machine code

Q48. Common Sub-expression Elimination, Copy Propagation, Loop Invariant

Removal
1. Common Sub-expression Elimination (CSE):
An expression E is a common sub-expression if E was previously computed and values of variables
in E have not changed since previous computation.
Before: t1 = a + b; t2 = a + b
After: t1 = a + b; t2 = t1 (save one computation)

2. Copy Propagation:
After a copy statement x=y, use y in place of x wherever x is used (before x is redefined).
Before: x = y; z = x + 1; w = x * 2
After: x = y; z = y + 1; w = y * 2 (x may become dead, eliminated)

3. Loop Invariant Code Motion:

If an expression inside a loop produces the same result on every iteration (loop-invariant), move it to
a pre-header block before the loop.
Before:
while (i < n) {
x = a * b; // loop invariant!
arr[i] = x + i;
}
After:
t = a * b; // moved outside
while (i < n) {
arr[i] = t + i;
}

Q49. Local and Global Transformation

Local Transformation:
Optimizations performed within a single basic block, without considering other blocks.
• Local CSE: Find common sub-expressions within a block
• Local constant folding: Evaluate constants within a block
• Algebraic simplification within a block
• Easy to implement, limited scope
• Uses DAG of the basic block

Global Transformation:
Optimizations that consider multiple basic blocks across the entire flow graph.
 • Global CSE: Find common sub-expressions across basic blocks
• Global constant propagation across blocks
• Loop optimizations (requires loop identification in flow graph)
• Requires data flow analysis (reaching definitions, available expressions)
• More powerful but more complex

Feature Local Global

Scope Single basic block Entire flow graph
Data flow needed No Yes
Complexity Low High
Power Limited More powerful
Examples Local CSE, constant folding Global CSE, loop invariant
removal

Q50. Three Areas of Code Optimization

1. Local Optimization (Within a Basic Block):
Optimizations applied to a single basic block:
• Common sub-expression elimination (local)
• Dead code elimination
• Constant folding and propagation
• Strength reduction
• Algebraic identities (x+0=x, x*1=x)

2. Global Optimization (Across Basic Blocks):

Optimizations applied to the entire function/program flow graph:
• Global common sub-expression elimination
• Global copy propagation
• Global dead code elimination
• Loop optimizations: code motion, induction variable elimination
• Requires data flow analysis

3. Peephole Optimization (Machine Code Level):

Examines a small 'window' (peephole) of target instructions and replaces them with shorter/faster
sequences:
• Redundant load/store elimination
• Unreachable code removal
• Flow of control optimization (replace jump to jump)
• Algebraic simplification in machine code
• Use of machine idioms (special instructions)
Q51. Peephole Optimization
Definition:
Peephole optimization examines a small sliding window (peephole) of generated target code and
tries to replace instruction sequences with equivalent but more efficient sequences.

Techniques:
1. Redundant Instruction Elimination:
MOV R0, a
MOV a, R0 // redundant — a already in R0
Optimized: MOV R0, a (remove second)

2. Unreachable Code:
goto L1
x = y + 1 // unreachable
L1: ...
Optimized: remove x = y+1

3. Flow of Control:
goto L1 where L1: goto L2
Optimized: goto L2 (jump chaining)

4. Algebraic Simplification:
x = x + 0 → remove
x = x * 1 → remove
x = x ** 2 → x = x * x

5. Use of Machine Idioms:

INC instruction instead of x = x + 1
Shift instead of multiply by power of 2

Q52. Generate Code for R = (p+q) – ((r+s) – t)

Three-Address Code:
t1 = p + q
t2 = r + s
t3 = t2 - t
t4 = t1 - t3
R = t4

Assembly Code (Assuming registers R0, R1):

MOV R0, p // R0 = p
ADD R0, q // R0 = p + q = t1
MOV R1, r // R1 = r
ADD R1, s // R1 = r + s = t2
 SUB R1, t // R1 = t2 - t = t3
SUB R0, R1 // R0 = t1 - t3 = t4
MOV R, R0 // R = t4

Q53. Register Allocation and Assignment

Register Allocation:
Deciding WHICH values should reside in registers (rather than memory) at each point in the
program. Goal: maximize register usage to minimize slow memory accesses.

Register Assignment:
Deciding WHICH SPECIFIC register should hold a value.

Approaches:
1. Local Register Allocation (within basic block):
Use reference counts. Assign registers to variables with highest usage. When a register is needed
and all are full, spill the least useful value to memory.

2. Global Register Allocation:

Graph Coloring Method:
• Build an interference graph: nodes = live ranges, edges = two ranges that are
simultaneously alive
• Graph coloring: If k registers available, attempt to color graph with k colors
• Variables with same color cannot share a register
• If k-colorable: assign colors to registers. If not: spill some variable to memory

Example:
int a = 1, b = 2, c = a+b, d = a*c;
Live ranges: a:[1,4], b:[1,2], c:[3,4], d:[4]. Interference: a-b, a-c. Graph is 2-colorable → 2 registers
needed.
UNIT VII — Short Notes

Q54. Short Notes

(a) Peephole Optimization
(Refer to Q51 for complete answer.)
Peephole optimization is a local code improvement technique that examines a small window of
target instructions and replaces them with equivalent but more efficient sequences. Key techniques:
redundant instruction elimination, unreachable code removal, jump-to-jump optimization, algebraic
simplification, and use of hardware-specific idioms.

(b) Global Data Flow Equations

Data flow analysis propagates information about programs to all points in the flow graph. Standard
equations:
Reaching Definitions:
IN[B] = ∪ OUT[P] for all predecessors P of B
OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])
Available Expressions:
IN[B] = ∩ OUT[P] for all predecessors P
OUT[B] = EXPGEN[B] ∪ (IN[B] - EXPKILL[B])
Live Variables:
OUT[B] = ∪ IN[S] for all successors S of B
IN[B] = USE[B] ∪ (OUT[B] - DEF[B])
These equations are solved iteratively until a fixed point (no change) is reached.

(c) Dynamic Storage Allocation

Dynamic storage allocation manages the heap — a region of memory used for objects whose size
or lifetime cannot be determined at compile time.
Strategies:
• First Fit: Allocate first hole large enough
• Best Fit: Allocate smallest hole that fits (less waste)
• Worst Fit: Allocate largest hole (leaves larger residual)
Issues:
• External fragmentation: holes too small to use
• Internal fragmentation: allocated more than needed
• Garbage collection: automatic reclamation in Java, Python

(d) Error Detection and Recovery

A compiler detects and recovers from four types of errors:
• Lexical Errors: Invalid tokens (e.g., illegal characters). Recovery: skip invalid characters.
• Syntax Errors: Malformed statements. Recovery: Panic mode (discard tokens until
synchronizing token), Phrase-level (local correction), Error productions (add error rules to
grammar), Global correction (find closest valid program).
 • Semantic Errors: Type mismatches, undeclared identifiers. Recovery: Use a default type.
• Logical Errors: Program produces wrong result — compiler usually cannot detect.

Q55. Short Notes (May 2023)

(a) Common Sub-expression Elimination
(Refer to Q48 for detailed answer.)
CSE identifies expressions computed more than once with unchanged operands, and replaces
subsequent computations with the first result. Local CSE uses DAG of basic block. Global CSE
uses available expression data flow analysis.
t1 = a + b; t2 = a + b → t1 = a+b; t2 = t1

(b) Register Allocation

(Refer to Q53 for detailed answer.)
Register allocation determines which program variables are placed in registers. Uses graph
coloring: build interference graph (nodes = variables, edges = simultaneous liveness), color with k
colors for k registers. Uncolorable variables are spilled to memory.

(c) Three Address Code

Three-address code is an intermediate representation where each instruction has at most one
operator and three operands (x = y op z). It is close to assembly but machine-independent.
Forms:
• Binary: x = y op z
• Unary: x = op y
• Copy: x = y
• Unconditional jump: goto L
• Conditional jump: if x relop y goto L
• Parameter: param x; call p, n
• Indexed assignment: x = y[i]; x[i] = y
Representations:
• Quadruples: (op, arg1, arg2, result)
• Triples: (op, arg1, arg2) — no result field, referenced by index
• Indirect triples: array of pointers to triples

Q56. Short Notes (Jun 2025)

(a) Specification and Recognition of Tokens
Specification:
Tokens are specified using regular expressions. Each token class has a pattern:
• Keywords: 'if' | 'else' | 'while' | 'for' | ...
• Identifiers: letter(letter|digit)* where letter=[a-zA-Z_]
• Numbers: digit+ or digit+.digit+ (floats)
• Operators: '+' | '-' | '*' | '/' | '=' | '==' | ...
• Whitespace: (space|tab|newline)+ — usually skipped
Recognition:
Regular expressions are converted to NFA (Thompson's construction), then to DFA (subset
construction), then the DFA is minimized. The resulting DFA drives the scanner:
• Start in initial state
• For each character, follow DFA transitions
• When no transition exists: if in accepting state, return token; else, error
• Longest match (maximal munch) rule — take the longest valid token

(b) L-Attributed Definition

An SDT is L-attributed if each inherited attribute of each symbol Xj on the RHS of A→X1X2...Xn
depends only on: (1) Inherited attributes of A (the head), (2) Attributes of X1, X2, ..., X(j-1) —
symbols to the left of Xj.
Properties:
• Every S-attributed grammar is also L-attributed
• Can be evaluated in one left-to-right pass of the parse tree
• Suitable for LL parsing (top-down)
• Attributes flow left-to-right and top-to-bottom
Example:
A → B C D
Allowed: D.i = f(A.i, B.s, C.s) // from left siblings and parent
Not allowed: D.i = f(C.i) // if C.i is inherited from right sibling

(c) Dynamic Storage Allocation

(Same as Q54(c) — see above for complete answer.)

(d) Back Patching

Back patching is a technique for generating code for Boolean expressions and control flow
statements in a single pass over the intermediate representation.
Problem:
When generating code for 'if (condition) then S', the target of the jump for the condition is not yet
known (S hasn't been translated yet).
Solution:
Leave the jump target blank (use a placeholder), and maintain lists of incomplete jumps:
• truelist: list of jump instructions that jump when condition is TRUE
• falselist: list of jump instructions that jump when condition is FALSE
Operations:
makelist(i): creates a new list containing instruction i
merge(p1, p2): concatenates lists p1 and p2
backpatch(list, target): fills in target address for all jumps in list
Example:
if (a > b) { S1 } else { S2 }
100: if a > b goto _ // added to truelist
101: goto _ // added to falselist
... generate S1 ...
backpatch(truelist, 102) // fill in jump to S1
backpatch(falselist, S2_start) // fill in jump to S2

— End of Compiler Design Question Bank — Best of luck for your RGPV Exam! —