2026 question paper

Compiler Design

25 questions

1. Q1a. Consider the statement: int total = 25; Which of the following represents a lexeme? (i) int (ii) 25 (iii) total (iv) All of the Above20262m

   Module 1: Introduction, Lexical Analysis

   Consider the statement: int total = 25; Which of the following represents a lexeme?
   (i) int
   (ii) 25
   (iii) total
   (iv) All of the Above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) All of the Above

   Explanation

   A lexeme is the actual sequence of characters in the source program that matches the pattern of a token. The scanner groups the characters of int total = 25; into these lexemes:

   Lexeme	Token class
   int	keyword
   total	identifier
   =	assignment operator
   25	integer constant
   ;	separator

   So int, total and 25 are all lexemes.

   $$\boxed{\text{(iv) All of the Above}}$$

2. Q1b. The regular expression (a \mid b)^* represents: (i) Strings containing only a (ii) Strings containing only b (iii) All strings over \{a, b\}, including \varepsilon (iv) Strings beginning with ab20262m

   Module 1: Introduction, Lexical Analysis

   The regular expression $(a \mid b)^*$ represents:
   (i) Strings containing only $a$
   (ii) Strings containing only $b$
   (iii) All strings over $\{a, b\}$, including $\varepsilon$
   (iv) Strings beginning with $ab$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) All strings over $\{a, b\}$, including $\varepsilon$

   Explanation

   • $(a \mid b)$ matches exactly one symbol: either $a$ or $b$.
   • The Kleene star $^*$ allows zero or more repetitions of that choice.

   So the language is $\{\varepsilon, a, b, aa, ab, ba, bb, aaa, \dots\}$, i.e. every string over the alphabet $\{a,b\}$, with $\varepsilon$ (zero repetitions) included.

   Why the other options fail:

   • (i), (ii): they allow only one of the two symbols.
   • (iv): it forces the string to start with $ab$, but $(a\mid b)^*$ also accepts $b$, $\varepsilon$, etc.

   $$\boxed{\text{(iii)}}$$

3. Q1c. Which of the following is a problem for a top-down parser? (i) Left recursion (ii) Right recursion (iii) Ambiguity only (iv) Bottom-up derivation20262m

   Module 2: Syntax Analysis (Parser)

   Which of the following is a problem for a top-down parser?
   (i) Left recursion
   (ii) Right recursion
   (iii) Ambiguity only
   (iv) Bottom-up derivation

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) Left recursion

   Explanation

   A grammar is left recursive if it has a rule of the form $A \to A\alpha \mid \beta$.

   A top-down (recursive-descent / LL) parser expands the leftmost non-terminal first. For $A \to A\alpha$ it would call A() which immediately calls A() again without consuming any input, so it falls into an infinite loop.

   Fix: eliminate left recursion

   $$A \to A\alpha \mid \beta \;\;\Longrightarrow\;\; A \to \beta A',\quad A' \to \alpha A' \mid \varepsilon$$

   • Right recursion ($A \to \alpha A$) is harmless for top-down parsers.
   • Ambiguity affects all parsers, but it is not the characteristic problem of top-down parsing, and option (iii) says "only".

   $$\boxed{\text{(i) Left recursion}}$$

4. Q1d. In bottom-up parsing, the parser constructs: (i) Leftmost derivation (ii) Rightmost derivation (iii) Reverse of a rightmost derivation (iv) Leftmost derivation in reverse20262m

   Module 2: Syntax Analysis (Parser)

   In bottom-up parsing, the parser constructs:
   (i) Leftmost derivation
   (ii) Rightmost derivation
   (iii) Reverse of a rightmost derivation
   (iv) Leftmost derivation in reverse

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Reverse of a rightmost derivation

   Explanation

   A bottom-up (shift-reduce) parser starts from the input string and repeatedly reduces a handle to a non-terminal until the start symbol is reached.

   Each reduction undoes one step of a rightmost derivation, so the sequence of reductions is a rightmost derivation traced backwards.

   Example for $E \to E+E \mid id$ on $id + id$:

   • Rightmost derivation: $E \Rightarrow E+E \Rightarrow E+id \Rightarrow id+id$
   • Reductions performed by the parser: $id+id \to E+id \to E+E \to E$ (exactly the reverse).

   (Top-down parsers build a leftmost derivation; options (i), (ii), (iv) are wrong.)

   $$\boxed{\text{(iii) Reverse of a rightmost derivation}}$$

5. Q1e. Consider a symbol table implemented using hashing with table size 10. For key 27, using h(k) = k \bmod 10, the initial position is: (i) 5 (ii) 7 (iii) 6 (iv) 820262m

   Module 3: Semantic Analysis, Symbol Table, Run-time environment

   Consider a symbol table implemented using hashing with table size $10$. For key $27$, using $h(k) = k \bmod 10$, the initial position is:
   (i) $5$
   (ii) $7$
   (iii) $6$
   (iv) $8$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) 7

   Calculation

   $$h(27) = 27 \bmod 10 = 7$$

   because $27 = 2 \times 10 + 7$. The key $27$ is initially placed at index $7$ of the hash table.

   Note: if slot $7$ is already occupied (a collision, e.g. key $17$), it is resolved by chaining (linked list at slot 7) or open addressing (linear probing to slot 8, 9, ...).

   $$\boxed{\text{(ii) } 7}$$

6. Q1f. Under static scoping, the meaning of a variable reference is determined primarily by: (i) Runtime call sequence (ii) CPU register contents (iii) Heap location (iv) Lexical program structure20262m

   Module 3: Semantic Analysis, Symbol Table, Run-time environment

   Under static scoping, the meaning of a variable reference is determined primarily by:
   (i) Runtime call sequence
   (ii) CPU register contents
   (iii) Heap location
   (iv) Lexical program structure

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) Lexical program structure

   Explanation

   In static (lexical) scoping, a variable reference is bound to the declaration found by looking at the textual nesting of blocks/procedures in the source code: first the innermost enclosing block, then the next one outward, and so on.

   • The binding can be decided at compile time, without running the program.
   • The call sequence at run time (option i) decides the binding only in dynamic scoping.
   • Registers (ii) and heap location (iii) have nothing to do with name resolution.

   int x = 10;
   void f() { printf("%d", x); }   // x refers to the global x
   void g() { int x = 20; f(); }   // still prints 10 under static scoping
   

   $$\boxed{\text{(iv)}}$$

7. Q1g. Which optimization eliminates repeated computation of the same expression? (i) Loop interchange (ii) Dead-code elimination only (iii) Common subexpression elimination (iv) Register allocation20262m

   Module 4: Intermediate Code Generation, Code Improvement (optimization)

   Which optimization eliminates repeated computation of the same expression?
   (i) Loop interchange
   (ii) Dead-code elimination only
   (iii) Common subexpression elimination
   (iv) Register allocation

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Common subexpression elimination

   Explanation

   Common subexpression elimination (CSE) detects an expression that was already computed and whose operands have not changed since, and reuses the earlier result instead of recomputing it.

   Before:

   x = a * b + c
   y = a * b + d
   

   After CSE:

   t = a * b
   x = t + c
   y = t + d
   

   The other options: loop interchange changes loop order (cache behaviour); dead-code elimination removes useless code; register allocation maps variables to registers.

   $$\boxed{\text{(iii) Common subexpression elimination}}$$

8. Q1h. Which pipeline hazard occurs when an instruction depends on the result of a previous instruction? (i) Structural hazard (ii) Data hazard (iii) Syntax hazard (iv) Memory hazard20262m

   Module 5: Architecture Dependent Code Improvement

   Which pipeline hazard occurs when an instruction depends on the result of a previous instruction?
   (i) Structural hazard
   (ii) Data hazard
   (iii) Syntax hazard
   (iv) Memory hazard

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Data hazard

   Explanation

   A data hazard occurs when an instruction needs a value that a previous, still-in-flight instruction has not yet written back. The most common form is RAW (read-after-write):

   ADD R1, R2, R3     ; writes R1
   SUB R4, R1, R5     ; reads R1 -> must wait for the ADD result
   

   Remedies: pipeline stalls, forwarding (bypassing), and compiler instruction scheduling (placing independent instructions in between).

   • Structural hazard: two instructions need the same hardware resource at the same time.
   • Control hazard: caused by branches.
   • "Syntax hazard" and "memory hazard" are not standard pipeline hazard classes.

   $$\boxed{\text{(ii) Data hazard}}$$

9. Q1i. Dynamic method dispatch is primarily used to implement: (i) Lexical analysis (ii) Constant folding (iii) Runtime polymorphism (iv) Register allocation20262m

   Module 6: Advanced Topics

   Dynamic method dispatch is primarily used to implement:
   (i) Lexical analysis
   (ii) Constant folding
   (iii) Runtime polymorphism
   (iv) Register allocation

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Runtime polymorphism

   Explanation

   Dynamic method dispatch selects which overridden method to call based on the actual (run-time) type of the object, not the declared type of the reference.

   Compilers implement it with a virtual method table (vtable): each object carries a hidden pointer to its class's vtable, and a virtual call becomes an indirect call through a fixed slot index.

   Animal a = new Dog();
   a.speak();   // Dog.speak() is chosen at run time
   

   This is exactly runtime (dynamic) polymorphism. It has nothing to do with lexical analysis, constant folding or register allocation.

   $$\boxed{\text{(iii) Runtime polymorphism}}$$

10. Q1j. Which statement is true regarding DFA and NFA? (i) NFA is strictly more powerful than DFA (ii) DFA and NFA recognize the same class of languages (iii) DFA is strictly more powerful than NFA (iv) Every NFA requires more states than every equivalent DFA20262m

    Module 1: Introduction, Lexical Analysis

    Which statement is true regarding DFA and NFA?
    (i) NFA is strictly more powerful than DFA
    (ii) DFA and NFA recognize the same class of languages
    (iii) DFA is strictly more powerful than NFA
    (iv) Every NFA requires more states than every equivalent DFA

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (ii) DFA and NFA recognize the same class of languages

    Explanation

    Both DFAs and NFAs recognize exactly the regular languages.

    • Every DFA is already an NFA (a special case).
    • Every NFA can be converted to an equivalent DFA by the subset construction.

    So neither is more powerful, which rules out (i) and (iii). An NFA is often smaller than the equivalent DFA: an NFA with $n$ states may need up to $2^n$ DFA states. That is a size difference only, and option (iv) is false because many NFAs need no more states than their DFAs (a DFA is itself an NFA).

    $$\boxed{\text{(ii)}}$$

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. Explain the different phases of compilation with a suitable example. Show the input and output produced at each phase.20267m

    Module 1: Introduction, Lexical Analysis

    Explain the different phases of compilation with a suitable example. Show the input and output produced at each phase.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Phases of a compiler

    A compiler translates a source program into target code in a sequence of phases. Two components work with every phase: the symbol table (stores names and attributes) and the error handler (reports errors with line numbers).

    MermaidDiagram

    Code

    Rendering diagram…

    Running example: position = initial + rate * 60 where position, initial, rate are float.

    Phase	Task	Output for the example
    1. Lexical analysis	Scans characters, groups them into lexemes and produces tokens; enters identifiers into the symbol table; removes whitespace and comments	<id,1> <=> <id,2> <+> <id,3> <*> <num,60>
    2. Syntax analysis	Checks token order against the grammar and builds a parse/syntax tree	Syntax tree (diagram below)
    3. Semantic analysis	Type checking, declaration checks, type conversions (coercion)	60 is int, rate is float, so insert inttofloat(60)
    4. Intermediate code generation	Produces machine-independent code, usually three-address code	t1 = inttofloat(60)
    t2 = id3 * t1
    t3 = id2 + t2
    id1 = t3
    5. Code optimization	Improves speed/size: constant folding, copy propagation, dead-code removal	t1 = id3 * 60.0
    id1 = id2 + t1
    6. Code generation	Selects instructions, allocates registers, emits target code	LDF R2, id3
    MULF R2, R2, #60.0
    LDF R1, id2
    ADDF R1, R1, R2
    STF id1, R1

    Input and output summary

    • Lexical analyzer: character stream to token stream.
    • Syntax analyzer: tokens to syntax tree.
    • Semantic analyzer: syntax tree to type-checked (annotated) tree.
    • Intermediate code generator: annotated tree to three-address code.
    • Optimizer: intermediate code to better intermediate code.
    • Code generator: optimized intermediate code to target code.

    The first three phases form the analysis (front end); the last three form the synthesis (back end).

    Syntax tree (phase 2)

    MermaidDiagram

    Code

    Rendering diagram…

    Tree after semantic analysis (phase 3): the integer constant is converted to float.

    MermaidDiagram

    Code

    Rendering diagram…
13. Q2b. Construct a DFA over \{0, 1\} that accepts all strings containing an even number of 0s and an odd number of 1s. Verify the constructed DFA using suitable accepted and rejected input strings.20267m

    Module 1: Introduction, Lexical Analysis

    Construct a DFA over $\{0, 1\}$ that accepts all strings containing an even number of $0$s and an odd number of $1$s. Verify the constructed DFA using suitable accepted and rejected input strings.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    DFA for: even number of 0s and odd number of 1s over $\{0,1\}$

    Idea: track two parities, the parity of the number of 0s and the parity of the number of 1s seen so far. That gives $2 \times 2 = 4$ states.

    State	#0s	#1s
    $A$ (start)	even	even
    $B$	odd	even
    $C$ (final)	even	odd
    $D$	odd	odd

    Reading a 0 flips the parity of 0s; reading a 1 flips the parity of 1s. Accepting state: $C$ (even 0s, odd 1s).

    Transition table

    State	on 0	on 1
    $\to A$	$B$	$C$
    $B$	$A$	$D$
    $*C$	$D$	$A$
    $D$	$C$	$B$

    Transition diagram

    MermaidDiagram

    Code

    Rendering diagram…

    Formally $M = (\{A,B,C,D\}, \{0,1\}, \delta, A, \{C\})$.

    Verification

    Input	Path	Final state	0s / 1s	Result
    1	$A \to C$	$C$	0 / 1	Accepted
    001	$A \to B \to A \to C$	$C$	2 / 1	Accepted
    10011	$A \to C \to D \to C \to A \to C$	$C$	2 / 3	Accepted
    01	$A \to B \to D$	$D$	1 / 1	Rejected
    0110	$A \to B \to D \to B \to A$	$A$	2 / 2	Rejected
    11	$A \to C \to A$	$A$	0 / 2	Rejected
    $\varepsilon$	$A$	$A$	0 / 0	Rejected

    Every accepted string has an even count of 0s and an odd count of 1s, and every rejected one violates at least one condition, so the DFA is correct.

14. Q3a. For a lexical analyzer, design regular expressions to recognize the following token classes: (i) Identifiers beginning with a letter and containing letters and digits thereafter. (ii) Unsigned integer constants. (iii) Relational operators <, <=, >, >=, ==, and !=.20267m

    Module 1: Introduction, Lexical Analysis

    For a lexical analyzer, design regular expressions to recognize the following token classes:
    (i) Identifiers beginning with a letter and containing letters and digits thereafter.
    (ii) Unsigned integer constants.
    (iii) Relational operators $<, <=, >, >=, ==,$ and $!=$.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Regular expressions for the token classes

    Let

    $$\text{letter} = [A\text{-}Za\text{-}z] \quad (\text{often also } \_), \qquad \text{digit} = [0\text{-}9]$$

    (i) Identifiers (start with a letter, then letters or digits)

    $$\text{id} = \text{letter}\,(\text{letter} \mid \text{digit})^*$$

    Accepted: total, x1, rate2023. Rejected: 2abc (starts with a digit).

    (ii) Unsigned integer constants

    $$\text{num} = \text{digit}\,\text{digit}^* \;=\; \text{digit}^+$$

    Accepted: 0, 25, 1000. Rejected: -5 (sign), 3.5 (not an integer).

    (iii) Relational operators

    $$\text{relop} = \; < \;\mid\; <= \;\mid\; > \;\mid\; >= \;\mid\; == \;\mid\; !=$$

    Factored form: $\text{relop} = (< \mid >)\,(=)? \;\mid\; (= \mid !)\,=$

    The scanner always takes the longest match, so <= is read as one token, not < followed by =. A single = is the assignment operator, not a relational operator.

    Recognizer for relop (transition diagram)

    MermaidDiagram

    Code

    Rendering diagram…

    Final states: LT (<), GT (>), LE (<=), GE (>=), EQEQ (==), NE (!=). The states EQ1 and NOT are not final because = alone (assignment) and ! alone are not relational operators here.

15. Q3b. Consider the grammar: S \to ABC A \to aA \mid \varepsilon B \to bB \mid \varepsilon C \to cC \mid d Compute the \text{FIRST} and \text{FOLLOW} sets for all non-terminals. Using these, construct the \text{LL}(1) parsing table. Use the parsing table to show the parsing steps for the input string "aabd".20267m

    Module 2: Syntax Analysis (Parser)

    Consider the grammar:
    $S \to ABC$
    $A \to aA \mid \varepsilon$
    $B \to bB \mid \varepsilon$
    $C \to cC \mid d$
    Compute the $\text{FIRST}$ and $\text{FOLLOW}$ sets for all non-terminals. Using these, construct the $\text{LL}(1)$ parsing table. Use the parsing table to show the parsing steps for the input string "aabd".

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Grammar

    $S \to ABC$, $A \to aA \mid \varepsilon$, $B \to bB \mid \varepsilon$, $C \to cC \mid d$

    FIRST sets

    • $\mathrm{FIRST}(A) = \{a, \varepsilon\}$
    • $\mathrm{FIRST}(B) = \{b, \varepsilon\}$
    • $\mathrm{FIRST}(C) = \{c, d\}$
    • $\mathrm{FIRST}(S) = (\mathrm{FIRST}(A)\setminus\varepsilon) \cup (\mathrm{FIRST}(B)\setminus\varepsilon) \cup \mathrm{FIRST}(C) = \{a, b, c, d\}$ (since $A$ and $B$ can both vanish, $C$ is reached)

    FOLLOW sets

    • $\mathrm{FOLLOW}(S) = {$}$
    • $\mathrm{FOLLOW}(A) = (\mathrm{FIRST}(B)\setminus\varepsilon) \cup \mathrm{FIRST}(C) = \{b, c, d\}$ (from $S \to ABC$, as $B$ is nullable)
    • $\mathrm{FOLLOW}(B) = \mathrm{FIRST}(C) = \{c, d\}$
    • $\mathrm{FOLLOW}(C) = \mathrm{FOLLOW}(S) = {$}$

    Non-terminal	FIRST	FOLLOW
    $S$	$\{a,b,c,d\}$	${$}$
    $A$	$\{a,\varepsilon\}$	$\{b,c,d\}$
    $B$	$\{b,\varepsilon\}$	$\{c,d\}$
    $C$	$\{c,d\}$	${$}$

    LL(1) parsing table

    • $S \to ABC$: $\mathrm{FIRST}(ABC) = \{a,b,c,d\}$, so fill $a,b,c,d$.
    • $A \to aA$ on $a$; $A \to \varepsilon$ on $\mathrm{FOLLOW}(A) = b,c,d$.
    • $B \to bB$ on $b$; $B \to \varepsilon$ on $\mathrm{FOLLOW}(B) = c,d$.
    • $C \to cC$ on $c$; $C \to d$ on $d$.

    | | $a$ | $b$ | $c$ | $d$ | \0 | `aabd | $S \to ABC$ | | 2 | ABC\1 | `aabd | match a |
    | 4 | ABC\2 | `abd| matcha | | 6 | ABC\3 | `bd | $B \to bB$ |
    | 8 | bBC\4 | `d | $B \to \varepsilon$ | | 10 | C\5 | `d | match d |
    | 12 | $$$| `$` | accept |

    The string aabd is accepted.

16. Q4a. Explain ambiguity in context-free grammars. Illustrate how ambiguity can lead to shift-reduce or reduce-reduce conflicts during LR parsing.20267m

    Module 2: Syntax Analysis (Parser)

    Explain ambiguity in context-free grammars. Illustrate how ambiguity can lead to shift-reduce or reduce-reduce conflicts during LR parsing.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Ambiguity in a context-free grammar

    A CFG is ambiguous if some string in its language has more than one parse tree (equivalently, more than one leftmost derivation or more than one rightmost derivation).

    Example: $E \to E + E \mid E * E \mid id$ on the string $id + id * id$ has two parse trees.

    MermaidDiagram

    Code

    Rendering diagram…

    The two trees give different meanings (different evaluation order), so the compiler cannot decide which one is intended.

    How ambiguity causes conflicts in LR parsing

    An LR parser must decide in every state whether to shift or reduce. An ambiguous grammar can never be LR(k) for any $k$, so its LR table always has at least one multiply-defined entry.

    1. Shift-reduce conflict. For the grammar above, after reading E + E the parser reaches a state containing both items

    $$E \to E + E \cdot \qquad\text{and}\qquad E \to E \cdot * E$$

    On the next input symbol * it could reduce by $E \to E+E$ (giving tree 2) or shift * (giving tree 1). The table entry for (state, *) holds both s and r.

    2. Reduce-reduce conflict. Take $S \to A \mid B$, $A \to a$, $B \to a$. The string a has two parse trees. After shifting a the state contains

    $$A \to a \cdot \qquad\text{and}\qquad B \to a \cdot$$

    On lookahead `$` the parser can reduce by$A \to a$**or** by$B \to a$: two reduce actions in one cell.

    Removing the conflicts

    • Rewrite the grammar to enforce precedence and associativity: $E \to E+T \mid T$, $T \to T*F \mid F$, $F \to id$.
    • Or keep the grammar and resolve conflicts with rules (precedence: * binds tighter than +; left associativity), as Yacc/Bison do.
    • Shift is the default choice in a shift-reduce conflict; the earlier rule is chosen in a reduce-reduce conflict.
17. Q4b. Construct a transition diagram for the Pushdown Automaton for the language: L = \{ wcw^R \mid w \in \{a, b\}^* \}20267m

    Module 2: Syntax Analysis (Parser)

    Construct a transition diagram for the Pushdown Automaton for the language:
    $L = \{ wcw^R \mid w \in \{a, b\}^* \}$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    PDA for $L = \{ w c w^R \mid w \in \{a,b\}^* \}$

    Idea

    1. In state $q_0$, push every symbol of $w$ on the stack.
    2. On reading the middle marker c, move to $q_1$ without touching the stack.
    3. In $q_1$, each input symbol must match the stack top; pop it. This checks the second half is $w^R$ (the stack reverses $w$).
    4. When the input is finished and only $Z_0$ remains, move to the accepting state $q_2$.

    Formal definition: $M = (\{q_0,q_1,q_2\}, \{a,b,c\}, \{a,b,Z_0\}, \delta, q_0, Z_0, \{q_2\})$ (acceptance by final state).

    Transition function $\delta$ (notation: input, stack top / new stack top)

    #	Move
    1	$\delta(q_0, a, Z_0) = (q_0, aZ_0)$
    2	$\delta(q_0, b, Z_0) = (q_0, bZ_0)$
    3	$\delta(q_0, a, a) = (q_0, aa)$
    4	$\delta(q_0, a, b) = (q_0, ab)$
    5	$\delta(q_0, b, a) = (q_0, ba)$
    6	$\delta(q_0, b, b) = (q_0, bb)$
    7	$\delta(q_0, c, X) = (q_1, X)$ for $X \in \{Z_0, a, b\}$
    8	$\delta(q_1, a, a) = (q_1, \varepsilon)$
    9	$\delta(q_1, b, b) = (q_1, \varepsilon)$
    10	$\delta(q_1, \varepsilon, Z_0) = (q_2, Z_0)$

    Transition diagram

    MermaidDiagram

    Code

    Rendering diagram…

    Trace for abcba

    State	Remaining input	Stack (top left)	Move
    $q_0$	abcba	$Z_0$	push a
    $q_0$	bcba	$aZ_0$	push b
    $q_0$	cba	$baZ_0$	read c, go to $q_1$
    $q_1$	ba	$baZ_0$	b matches, pop
    $q_1$	a	$aZ_0$	a matches, pop
    $q_1$	$\varepsilon$	$Z_0$	$\varepsilon$-move to $q_2$
    $q_2$	$\varepsilon$	$Z_0$	accept

    A string such as abcab is rejected: after c the stack top is b but the input is a, so no move exists. The PDA is deterministic because c marks the middle.

18. Q5a. Explain the structure of an activation record and its role during procedure execution.20267m

    Module 3: Semantic Analysis, Symbol Table, Run-time environment

    Explain the structure of an activation record and its role during procedure execution.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Activation record (stack frame)

    An activation record is the block of memory pushed on the run-time stack each time a procedure is called. It holds everything one activation of the procedure needs. Records are pushed on a call and popped on return, so the stack mirrors the chain of active calls.

    Structure of an activation record

    SVGVector Architecture Diagram (SVG)

    SourceZoom

    Field	Purpose
    Returned value	Space where the callee stores its result for the caller
    Actual parameters	Arguments supplied by the caller
    Control (dynamic) link	Points to the caller's activation record, so the stack can be unwound on return
    Access (static) link	Points to the record of the lexically enclosing procedure, used to reach non-local variables
    Saved machine status	Return address and the register contents of the caller, restored on return
    Local variables	Data declared inside the procedure
    Temporaries	Intermediate values of expression evaluation

    Role during procedure execution

    1. Call sequence. The caller evaluates and stores the actual parameters and the return address; the callee saves registers, sets the frame pointer fp, and allocates space for locals and temporaries.
    2. Execution. Local variables are accessed at a fixed offset from fp. Non-local variables are reached by following access links (static scope) the required number of levels, then adding the offset. Global variables live in static memory with a fixed address.
    3. Return sequence. The callee stores the return value, restores the saved registers and fp, pops its record, and jumps to the return address.
    4. Recursion. Every call gets its own record, so each recursive activation has its own copy of locals and parameters.

    Accessing variables: for a local x use [fp + offset_x]. For a non-local y declared $k$ nesting levels up, follow the access link $k$ times to that procedure's record, then use [record + offset_y].

19. Q5b. Discuss the structure of a symbol table and the information stored for each identifier.20267m

    Module 3: Semantic Analysis, Symbol Table, Run-time environment

    Discuss the structure of a symbol table and the information stored for each identifier.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Symbol table

    A symbol table is a data structure used by the compiler to store information about every identifier (variables, constants, functions, labels, types, parameters) found in the source program. It is created during lexical/syntax analysis and used by every later phase.

    Structure

    Each entry is a record, and the table is organized for fast lookup and insertion.

    MermaidDiagram

    Code

    Rendering diagram…

    Common organizations:

    Implementation	Lookup	Remarks
    Unordered linear list	$O(n)$	Simple, only for tiny programs
    Ordered list / binary search tree	$O(\log n)$	Slower insertion
    Hash table	$O(1)$ average	Most common; collisions resolved by chaining

    Handling scope: one table per scope, chained to its enclosing scope (or a single stack-like table). Entering a block creates a new table; leaving it discards that table. Lookup searches the innermost scope first, then outwards.

    Operations: insert(name, attributes), lookup(name), delete / exit scope, modify attributes.

    Information stored for each identifier

    Attribute	Meaning
    Name	The lexeme (or an index into a string table)
    Kind / category	Variable, constant, function, procedure, parameter, label, type name
    Data type	int, float, char, array, struct, pointer, ...
    Size	Bytes needed (for arrays: element type and dimensions/bounds)
    Scope / nesting level	Block or procedure where the name is visible
    Storage location	Address or offset in the activation record (or static address)
    For functions	Number, order and types of parameters, return type, parameter-passing mode
    For records/classes	Fields, their types and offsets
    Line numbers	Declaration and usage lines, for error messages and cross-reference
    Other flags	Initialized or not, constant value, access mode

    Example: for float rate; declared in main, the entry is
    <rate, variable, float, 4 bytes, level 1, offset 8>.

    Use by the phases: the scanner inserts names, the parser and semantic analyzer add type and scope information and check for undeclared or redeclared names, type checking reads types, and the code generator reads sizes and offsets.

20. Q6a. Generate the three-address code for the following expression. Then represent the generated code using quadruple, triple, and indirect-triple representations. x = a * (b + c) - d / e20267m

    Module 4: Intermediate Code Generation, Code Improvement (optimization)

    Generate the three-address code for the following expression. Then represent the generated code using quadruple, triple, and indirect-triple representations.
    $x = a * (b + c) - d / e$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Expression: $x = a * (b + c) - d / e$

    Operator precedence and parentheses give the evaluation order: $(b+c)$ first, then $a * (\dots)$, then $d/e$, then the subtraction, then the assignment.

    Three-address code

    Code

    Copy

    t1 = b + c
    t2 = a * t1
    t3 = d / e
    t4 = t2 - t3
    x  = t4
    

    Syntax tree of the expression (each internal node becomes one three-address instruction, bottom-up)

    MermaidDiagram

    Code

    Rendering diagram…

    (i) Quadruples (op, arg1, arg2, result)

    #	op	arg1	arg2	result
    0	+	b	c	t1
    1	*	a	t1	t2
    2	/	d	e	t3
    3	-	t2	t3	t4
    4	=	t4		x

    (ii) Triples (op, arg1, arg2): there is no result field; a result is referred to by the number of the triple that computed it.

    #	op	arg1	arg2
    (0)	+	b	c
    (1)	*	a	(0)
    (2)	/	d	e
    (3)	-	(1)	(2)
    (4)	=	x	(3)

    (iii) Indirect triples: the triples are the same as above, but a separate instruction list holds pointers to them. The order of execution can then be changed by reordering the pointers without touching the triples.

    Instruction list	Points to
    100	(0)
    101	(1)
    102	(2)
    103	(3)
    104	(4)

    Triple #	op	arg1	arg2
    (0)	+	b	c
    (1)	*	a	(0)
    (2)	/	d	e
    (3)	-	(1)	(2)
    (4)	=	x	(3)

    Comparison

    Form	Temporaries in symbol table	Easy to reorder for optimization
    Quadruples	Yes (explicit result names)	Yes
    Triples	No	No (numbers refer to positions)
    Indirect triples	No	Yes (reorder the pointer list)

21. Q6b. Explain the construction of basic blocks and control-flow graphs (CFGs) in compiler design using a suitable three-address code example.20267m

    Module 4: Intermediate Code Generation, Code Improvement (optimization)

    Explain the construction of basic blocks and control-flow graphs (CFGs) in compiler design using a suitable three-address code example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Basic block

    A basic block is a maximal sequence of consecutive three-address instructions with one entry point (only the first instruction can be reached from outside) and one exit point (control leaves only at the last instruction, with no jumps into or out of the middle).

    Algorithm to find basic blocks

    1. Find the leaders (first instructions of blocks):
       • the first instruction of the program;
       • the target of any conditional or unconditional jump;
       • the instruction immediately after a jump (conditional or unconditional).
    2. For each leader, the basic block consists of the leader and all instructions up to (but not including) the next leader or the end of the program.

    Example three-address code

    Code

    Copy

    1  sum = 0
    2  i = 1
    3  if i > 10 goto 8
    4  t1 = i * 2
    5  sum = sum + t1
    6  i = i + 1
    7  goto 3
    8  print sum
    

    Leaders: instruction 1 (first), 3 (target of the jump at 7), 4 (follows the conditional jump at 3), 8 (target of the jump at 3 and follows the jump at 7). So the leaders are $\{1, 3, 4, 8\}$.

    Block	Instructions
    $B_1$	1-2
    $B_2$	3
    $B_3$	4-7
    $B_4$	8

    Control-flow graph (CFG)

    A CFG has the basic blocks as nodes. There is an edge $B_i \to B_j$ if control can pass from the end of $B_i$ to the start of $B_j$: either by a jump from the last instruction of $B_i$ to the leader of $B_j$, or because $B_j$ follows $B_i$ in program order and $B_i$ does not end in an unconditional jump.

    MermaidDiagram

    Code

    Rendering diagram…

    Uses: the CFG exposes loops (here $B_2 \to B_3 \to B_2$), and is the basis for data-flow analysis, local optimizations inside a block, and global optimizations such as code motion and dead-code elimination.

22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. Explain cache locality and its importance in loop optimization.20267m

    Module 5: Architecture Dependent Code Improvement

    Explain cache locality and its importance in loop optimization.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Cache locality

    A cache is a small, fast memory between the CPU and main memory. Data moves in blocks called cache lines (typically 64 bytes). A program runs faster when most of its memory accesses are hits. Cache locality is the tendency of a program to access data that is already in, or close to, the data in the cache.

    Two kinds of locality

    Type	Meaning	Example
    Temporal locality	A location that was just used is likely to be used again soon	A loop variable or a running sum accessed in every iteration
    Spatial locality	Locations near a recently used one are likely to be used soon	Walking through consecutive array elements

    When one element is fetched, the whole line comes with it (for example 16 consecutive 4-byte ints), so sequential access gives about 1 miss per 16 accesses, while a large stride can give a miss on every access.

    Why it matters in loop optimization

    Loops execute most of a program's instructions and memory accesses. A cache miss costs on the order of 100 cycles against 1-4 for a hit, so the order in which a loop nest touches memory often matters more than the arithmetic it does.

    Example (C arrays are stored row by row)

    C

    Copy

    // Poor spatial locality: column-wise walk, stride = N elements
    for (j = 0; j < N; j++)
        for (i = 0; i < N; i++)
            sum += a[i][j];
    
    // After loop interchange: row-wise walk, stride = 1
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    

    Both loops compute the same result, but the second uses every element of each fetched cache line before it is evicted.

    SVGVector Architecture Diagram (SVG)

    SourceZoom

    Loop transformations that improve locality

    Transformation	Effect
    Loop interchange	Reorders nested loops so the innermost loop has stride 1
    Loop tiling (blocking)	Splits the iteration space into small blocks that fit in the cache so data is reused (key for matrix multiplication)
    Loop fusion (jamming)	Merges loops that use the same data so it is used while still in cache
    Loop fission (distribution)	Splits a loop whose body touches too much data for the cache
    Array padding / data layout change	Avoids conflict misses; structure-of-arrays vs array-of-structures

    The compiler applies these only after a dependence analysis shows that the new order gives the same results.

24. Q7b. Explain the major stages involved in target code generation in a compiler. Discuss instruction selection, register allocation, and instruction scheduling, and explain how each stage contributes to generating efficient target machine code.20267m

    Module 5: Architecture Dependent Code Improvement

    Explain the major stages involved in target code generation in a compiler. Discuss instruction selection, register allocation, and instruction scheduling, and explain how each stage contributes to generating efficient target machine code.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Target code generation

    The code generator takes the (optimized) intermediate representation and the symbol-table information and produces target machine code that is correct and efficient.

    MermaidDiagram

    Code

    Rendering diagram…

    Major stages

    1. Instruction selection - choose target instructions for each IR operation.
    2. Register allocation and assignment - decide which values live in registers.
    3. Instruction scheduling (ordering) - choose the order of instructions.
    4. Final clean-up such as peephole optimization, then emit the code.

    1. Instruction selection

    Maps IR operations to machine instructions, choosing the cheapest sequence that implements them. The choice depends on the instruction set and addressing modes. Techniques: tree-pattern matching, dynamic programming over expression trees.

    For a = b + c a naive translation is

    Code

    Copy

    LD  R0, b
    LD  R1, c
    ADD R0, R0, R1
    ST  a, R0
    

    and for x = x + 1 a good selector uses a single INC x (or an add with an immediate) instead of load, add and store.

    Contribution: decides the number and cost of instructions, so the code is small and fast, and uses special instructions where available.

    2. Register allocation

    Registers are far faster than memory but very few. Allocation decides which variables/temporaries to keep in registers; assignment picks the specific register. Methods: usage counts, graph colouring (variables that are live at the same time interfere and get different registers). If there are not enough registers, a value is spilled to memory.

    Contribution: reduces loads and stores, which dominate execution time.

    3. Instruction scheduling

    Reorders independent instructions to avoid pipeline stalls and to use all functional units, without changing the program's result (data dependences must be respected).

    Assume a load takes one extra cycle before its result can be used:

    Unscheduled	Scheduled
    LD R1, a	LD R1, a
    ADD R2, R1, R3 (stall)	LD R4, b
    LD R4, b	ADD R2, R1, R3
    ADD R5, R4, R6 (stall)	ADD R5, R4, R6

    The scheduled version has no stalls.

    Contribution: hides latency and increases instruction-level parallelism, so the program runs faster on the pipeline.

    Interaction: the stages influence each other. Scheduling more instructions in parallel needs more registers, and heavy register reuse creates dependences that limit scheduling. Compilers therefore balance the two.

    Summary

    Stage	Goal	Result
    Instruction selection	Correct, low-cost instruction sequence	Fewer, cheaper instructions
    Register allocation	Keep hot values in registers	Fewer memory accesses
    Instruction scheduling	Avoid stalls, fill pipeline	Fewer cycles

25. Q8a. Discuss the major challenges involved in compiling object-oriented features such as classes, inheritance, and polymorphism.20267m

    Module 6: Advanced Topics

    Discuss the major challenges involved in compiling object-oriented features such as classes, inheritance, and polymorphism.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Compiling object-oriented features: main challenges

    Object-oriented languages add classes, objects, inheritance and polymorphism on top of ordinary procedural features. The compiler must map these to plain memory layouts and jumps.

    MermaidDiagram

    Code

    Rendering diagram…

    1. Object layout (classes)

    An object is stored as a record of its fields, plus a hidden pointer to its class's method table. The compiler must compute field offsets and the total size.

    SVGVector Architecture Diagram (SVG)

    SourceZoom

    2. Inheritance

    • A subclass object must be usable wherever a superclass object is expected, so the inherited fields keep the same offsets as in the parent (the subclass fields are appended).
    • Multiple inheritance breaks this: an object has several parent parts, so the compiler needs several vptrs and must adjust the this pointer when converting to a base type; shared (virtual) base classes need extra indirection.
    • Constructors and destructors must run in the right order (base first on construction, derived first on destruction).

    3. Polymorphism and dynamic dispatch

    The method that runs depends on the object's run-time type, not on the declared type. The compiler builds a virtual method table (vtable) for each class and compiles a virtual call as an indirect call through a fixed slot:

    Slot	Animal vtable	Dog vtable
    0	Animal::speak	Dog::speak (overrides)

    A call a.speak() is compiled to an indirect call through the vptr and the fixed slot of speak:

    MermaidDiagram

    Code

    Rendering diagram…

    This costs an extra memory load and an indirect jump, and prevents simple inlining; optimizers use devirtualization (when the exact type is known) to recover speed.

    4. Other challenges

    Challenge	Why it is hard
    Type checking with subtyping	Assignments are legal from subclass to superclass; overriding rules (parameter and return types) must be checked
    Overloading and name mangling	Several methods share a name; the compiler selects one by argument types and encodes the signature in the symbol name
    Access control	private, protected, public checks at compile time
    this pointer	Passed as a hidden first argument to every instance method
    Run-time type information	Needed for casts, instanceof, exceptions
    Interfaces and abstract classes	Dispatch through interface tables; abstract methods have no body
    Memory management	Allocation on heap, garbage collection or destructors
    Separate compilation	Changing a base class's layout forces recompilation of all subclasses

26. Q8b. Consider the following grammar: E \to E + T \mid T T \to T * F \mid F F \to \text{digit} Define suitable synthesized attributes to evaluate an arithmetic expression. Construct the annotated syntax tree and evaluate the following expression: 3 + 5 * 220267m

    Module 3: Semantic Analysis, Symbol Table, Run-time environment

    Consider the following grammar:
    $E \to E + T \mid T$
    $T \to T * F \mid F$
    $F \to \text{digit}$
    Define suitable synthesized attributes to evaluate an arithmetic expression. Construct the annotated syntax tree and evaluate the following expression:
    $3 + 5 * 2$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Grammar: $E \to E + T \mid T$, $\;T \to T * F \mid F$, $\;F \to \text{digit}$

    Synthesized attribute: give every non-terminal $E$, $T$, $F$ an attribute val (its numeric value). The terminal digit has the attribute lexval supplied by the lexical analyzer.

    Syntax-directed definition

    Production	Semantic rule
    $E \to E_1 + T$	$E.val = E_1.val + T.val$
    $E \to T$	$E.val = T.val$
    $T \to T_1 * F$	$T.val = T_1.val \times F.val$
    $T \to F$	$T.val = F.val$
    $F \to \text{digit}$	$F.val = \text{digit}.lexval$

    Every attribute is computed from the attributes of the children, so val is synthesized and the definition is S-attributed (it can be evaluated during bottom-up parsing).

    Annotated parse tree for $3 + 5 * 2$

    Because of the grammar's structure, * sits lower in the tree than +, so 5 * 2 is evaluated first.

    MermaidDiagram

    Code

    Rendering diagram…

    Evaluation (bottom-up, post-order)

    Step	Node	Rule used	Value
    1	$F$ (digit 3)	$F.val = \text{digit}.lexval$	3
    2	$T$ over that $F$	$T.val = F.val$	3
    3	$E$ over that $T$	$E.val = T.val$	3
    4	$F$ (digit 5)	$F.val = \text{digit}.lexval$	5
    5	$T$ over that $F$	$T.val = F.val$	5
    6	$F$ (digit 2)	$F.val = \text{digit}.lexval$	2
    7	$T \to T * F$	$T.val = 5 \times 2$	10
    8	$E \to E + T$	$E.val = 3 + 10$	13

    $$\boxed{3 + 5 * 2 = 13}$$
27. Q9. Write a short note on any two of the following: (a) \text{SLR}(1) parser (b) Syntax Directed Definition (c) Peephole optimization (d) Attribute grammar202614m

    Module 2: Syntax Analysis (Parser)

    Write a short note on any two of the following:
    (a) $\text{SLR}(1)$ parser
    (b) Syntax Directed Definition
    (c) Peephole optimization
    (d) Attribute grammar

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Only two notes are required; all four are given here (7 marks each).

    ---

    (a) SLR(1) parser

    SLR(1) (Simple LR with 1 lookahead symbol) is a bottom-up LR parser whose states are the sets of LR(0) items, and which uses the FOLLOW sets to decide when to reduce.

    Construction steps

    1. Augment the grammar with $S' \to S$.
    2. Build the canonical collection of LR(0) item sets using closure and goto.
    3. Fill the ACTION/GOTO table:
       • $A \to \alpha \cdot a\beta$ in $I_i$ and $\mathrm{goto}(I_i, a) = I_j$ gives shift $j$ on terminal $a$.
       • $A \to \alpha \cdot$ in $I_i$ gives reduce $A \to \alpha$ for every terminal in $\mathrm{FOLLOW}(A)$ (this is the SLR rule).
       • $S' \to S \cdot$ gives accept on $.
       • $\mathrm{goto}(I_i, A) = I_j$ gives GOTO entry $j$ for non-terminal $A$.

    The grammar is SLR(1) if the table has no conflicts.

    Power: SLR(1) is stronger than LR(0) but weaker than LALR(1) and canonical LR(1), because FOLLOW(A) is a coarse lookahead that ignores the context of the item and can cause spurious shift-reduce conflicts. It has the same small number of states as LR(0) and LALR(1).

    ---

    (b) Syntax Directed Definition (SDD)

    An SDD is a context-free grammar in which each grammar symbol has attributes and each production has semantic rules that compute the attributes. It specifies the translation (evaluation of expressions, type checking, code generation) tied to the syntax.

    Production	Semantic rule
    $E \to E_1 + T$	$E.val = E_1.val + T.val$
    $T \to F$	$T.val = F.val$
    $F \to \text{digit}$	$F.val = \text{digit}.lexval$

    • Synthesized attribute: computed from the attributes of the node's children (bottom-up).
    • Inherited attribute: computed from the parent and/or siblings (top-down or sideways).
    • S-attributed SDD: uses only synthesized attributes (suits bottom-up parsing). L-attributed SDD: each inherited attribute depends only on the parent and the siblings to its left (suits one left-to-right pass).
    • The rules are evaluated on the annotated parse tree; the order must respect the dependency graph. An SDD may contain rules with side effects (for example printing or updating the symbol table); an SDD whose rules have no side effects is an attribute grammar. Unlike a syntax-directed translation scheme, an SDD does not fix where actions run; it only states the rules.

    ---

    (c) Peephole optimization

    A peephole optimizer examines a small sliding window of target (or intermediate) instructions, the peephole (typically 2-5 instructions), and replaces patterns by shorter or faster equivalents. It may be applied repeatedly because one change can create new opportunities.

    Technique	Before	After
    Redundant load/store elimination	ST a, R1<br>LD R1, a	ST a, R1
    Constant folding	x = 3 + 4	x = 7
    Algebraic simplification	x = x + 0, x = x * 1	removed
    Strength reduction	x = x * 2	x = x << 1
    Use of machine idioms	ADD R1, R1, #1	INC R1
    Unreachable code removal	goto L2 followed by instructions with no label	instructions removed
    Control-flow optimization	goto L1 ... L1: goto L2	goto L2

    Advantages: simple, local, machine-specific gains; limitation: it cannot see beyond the window, so it complements global optimization.

    ---

    (d) Attribute grammar

    An attribute grammar is a context-free grammar extended with attributes attached to grammar symbols and semantic (attribute evaluation) rules attached to productions. Formally, it is a CFG together with a set of attributes (partitioned into synthesized and inherited) and rules that define each attribute purely as a function of other attributes, with no side effects. An attribute grammar is thus an SDD without side effects, used to define the static semantics of a language.

    Example (type declaration, uses an inherited attribute):

    Production	Semantic rule
    $D \to T\,L$	$L.in = T.type$
    $T \to \text{int}$	$T.type = integer$
    $T \to \text{float}$	$T.type = float$
    $L \to L_1 , \text{id}$	$L_1.in = L.in;\; \text{addtype}(\text{id}.entry, L.in)$
    $L \to \text{id}$	$\text{addtype}(\text{id}.entry, L.in)$

    Here $T.type$ is synthesized and $L.in$ is inherited: the type flows from $T$ to every identifier in the list.

    Evaluation: build the dependency graph of attribute instances on the parse tree; if it has no cycle, evaluate the attributes in a topological order. Attribute grammars are used for type checking, symbol-table construction and intermediate code generation.