GTU 2170701 Compiler Design (CD) Winter 2025 Solved Paper & Solutions

Definitions:

1. Compiler:

• A language translator that converts the entire High-Level Language (HLL) source program (e.g., C, C++) into equivalent machine/target code in a single comprehensive process before execution.
• Produces an independent executable object file (faster execution, errors reported after full scan).

2. Interpreter:

• A language translator that takes HLL source code (e.g., Python, JavaScript) and translates and executes it line-by-line in real time.
• Does not generate an object code file; execution stops immediately on the first encountered error (easier debugging, slower execution).

3. Assembler:

• A specialized system program that converts low-level Assembly Language mnemonics (e.g., MOV, ADD, JMP) into native binary machine code instructions ($0\text{s}$ and $1\text{s}$).

Error Recovery Strategies in Compilers

When a syntax or semantic error is detected during parsing, the compiler employs one of the following recovery strategies to continue scanning without abruptly halting:

1. Panic Mode Recovery:

• The simplest and most widely used strategy. Upon discovering an error, the parser discards incoming tokens one by one until a designated synchronizing token (such as a semicolon ;, closing brace }, or end) is found.
• Advantage: Guarantees no infinite loops; simple to implement.

2. Phrase-Level Recovery:

• The parser replaces an erroneous prefix of the remaining input with a valid string that allows parsing to proceed (e.g., inserting a missing comma or semicolon, or replacing a comma with a semicolon).
• Drawback: May lead to infinite loops if repair choices are cyclic.

3. Error Productions:

• The grammar is augmented with anticipated common syntactic mistakes (e.g., writing then after else).
• When an error production matches, the parser emits an exact error message and continues normal parsing.

4. Global Correction:

• Algorithms (like the Cocke-Younger-Kasami algorithm) that find the minimum number of insertions/deletions needed to transform the incorrect program into a valid program.
• Drawback: Extremely expensive in time and space; primarily of theoretical interest.

Phases of a Compiler

A compiler translates source code into machine code across two main logical structures: the Analysis (Front-End) and the Synthesis (Back-End) phases, supported universally by the Symbol Table and Error Handler.

Detailed Description of Each Phase:

1. Lexical Analysis (Scanner):

• Reads the raw input character stream and groups characters into meaningful sequences called lexemes, producing a stream of tokens: $\langle\text{token-name}, \text{attribute-value}\rangle$.
• Strips out comments and redundant whitespace.
• Example: position = initial + rate * 60 produces:

2. Syntax Analysis (Hierarchical Parsing):

• Uses Context-Free Grammars (CFG) to verify whether the token stream conforms to language syntax rules.
• Constructs a hierarchical Parse Tree or abstract Syntax Tree showing operator precedence and associativity.

3. Semantic Analysis (Type & Consistency Checking):

• Checks the parse tree for semantic validity, enforcing type compatibility, array bounds, and declaration rules.
• Performs Type Checking and automatic Type Coercion (e.g., converting integer 60 to floating-point 60.0 if rate is float).

4. Intermediate Code Generation (ICG):

• Produces an explicit, machine-independent low-level intermediate representation, commonly Three-Address Code (TAC):

5. Code Optimization:

• Transforms intermediate code to make target code run faster and consume less memory without changing program semantics.
• Employs dead-code elimination, common sub-expression elimination, loop unrolling, and constant folding.

6. Code Generation:

• Maps optimized intermediate representations into the target machine architecture (registers, memory offsets, assembly instructions):

LDF   R2, id3
     MULF  R2, #60.0
     LDF   R1, id2
     ADDF  R1, R2
     STF   id1, R1

7. Symbol Table Management & Error Handling:

• Symbol Table: Stores identifier names, types, scopes, sizes, and memory locations used across all phases.
• Error Handler: Identifies, reports, and recovers from errors at each phase without aborting compilation.

Regular Expression for Date (DD/MM/YYYY):

Breakdown of Components:

• Day (DD) $\to$ (0[1-9]|[12][0-9]|3[01]):
• 0[1-9]: Matches days 01 through 09.
• [12][0-9]: Matches days 10 through 29.
• 3[01]: Matches days 30 and 31.
• Separator $\to$ /: Exact forward slash delimiter.
• Month (MM) $\to$ (0[1-9]|1[0-2]):
• 0[1-9]: Matches months 01 through 09 (Jan–Sep).
• 1[0-2]: Matches months 10, 11, and 12 (Oct–Dec).
• Year (YYYY) $\to$ [0-9]{4} (or \d{4}): Matches any four-digit year.

Difference Between NFA and DFA

Example (Language ending with ab over $\Sigma = \{a, b\}$):

• NFA: State $q_0$ has two transitions on input a: self-loop on a ($q_0 \to q_0$) and move to $q_1$ ($q_0 \to q_1$).
• DFA: From state $q_0$, input a leads strictly to single state $q_1$, and input b leads to $q_0$.

Subset Construction Method (NFA to DFA)

The Subset Construction (or powerset construction) algorithm converts an NFA $N = (Q_N, \Sigma, \delta_N, q_0, F_N)$ into an equivalent DFA $D = (Q_D, \Sigma, \delta_D, q_D0, F_D)$ where each DFA state corresponds to a subset of NFA states.

Core Operations:

1. $\epsilon\text{-closure}(s)$: Set of all NFA states reachable from state $s$ on $\epsilon$-transitions alone.
2. $\text{move}(T, a)$: Set of all NFA states reachable from any state in subset $T$ on input symbol $a$.
3. Transition Function for DFA:

Step-by-Step Example

Consider an NFA recognizing strings over $\Sigma = \{0, 1\}$ ending with 01:

• States: $\{q_0, q_1, q_2\}$, Start state: $q_0$, Final state: $q_2$
• Transitions:
• $\delta(q_0, 0) = \{q_0, q_1\}$, $\delta(q_0, 1) = \{q_0\}$
• $\delta(q_1, 1) = \{q_2\}$

Step 1: Initial DFA State

Step 2: Transitions from State A

• On 0: $\delta_D(A, 0) = \epsilon\text{-closure}(\text{move}(\{q_0\}, 0)) = \{q_0, q_1\} = \mathbf{B}$
• On 1: $\delta_D(A, 1) = \epsilon\text{-closure}(\text{move}(\{q_0\}, 1)) = \{q_0\} = \mathbf{A}$

Step 3: Transitions from State B ($\{q_0, q_1\}$)

• On 0: $\delta_D(B, 0) = \{q_0, q_1\} = \mathbf{B}$
• On 1: $\delta_D(B, 1) = \{q_0, q_2\} = \mathbf{C}$ (New state!)

Step 4: Transitions from State C ($\{q_0, q_2\}$)

• On 0: $\delta_D(C, 0) = \{q_0, q_1\} = \mathbf{B}$
• On 1: $\delta_D(C, 1) = \{q_0\} = \mathbf{A}$

Resulting DFA Transition Table:

The resulting DFA has 3 states, with $\mathbf{C}$ as the accepting state.

S-Attributed vs L-Attributed Definitions (SDDs)

Given Grammar:

1. $S \to 1AB \mid \epsilon$
2. $A \to 1AC \mid 0C$
3. $B \to 0S$
4. $C \to 1$

Step 1: Compute FIRST Sets

• $\text{FIRST}(C)$: From $C \to 1 \implies \mathbf{\{1\}}$
• $\text{FIRST}(B)$: From $B \to 0S \implies \mathbf{\{0\}}$
• $\text{FIRST}(A)$:
• $A \to 1AC \implies \text{adds } 1$
• $A \to 0C \implies \text{adds } 0$
• Hence, $\text{FIRST}(A) = \mathbf{\{0, 1\}}$
• $\text{FIRST}(S)$:
• $S \to 1AB \implies \text{adds } 1$
• $S \to \epsilon \implies \text{adds } \epsilon$
• Hence, $\text{FIRST}(S) = \mathbf{\{1, \epsilon\}}$

Step 2: Compute FOLLOW Sets

• $\text{FOLLOW}(S)$:
• $S$ is start symbol \implies \text{adds } \$
• From $B \to 0S \implies \text{FOLLOW}(S) \supseteq \text{FOLLOW}(B)$
• From $S \to 1AB \implies \text{FOLLOW}(B) \supseteq \text{FOLLOW}(S)$
• Therefore, \text{FOLLOW}(S) = \text{FOLLOW}(B) = \mathbf{\{\\}}$
• $\text{FOLLOW}(A)$:
• From $S \to 1AB$: following $A$ is $B$, so $\text{FOLLOW}(A) \supseteq \text{FIRST}(B) = \{0\}$
• From $A \to 1AC$: following $A$ is $C$, so $\text{FOLLOW}(A) \supseteq \text{FIRST}(C) = \{1\}$
• Hence, $\text{FOLLOW}(A) = \mathbf{\{0, 1\}}$
• $\text{FOLLOW}(C)$:
• From $A \to 1AC$ and $A \to 0C$: $C$ appears at the end of $A$, so $\text{FOLLOW}(C) \supseteq \text{FOLLOW}(A) = \{0, 1\}$
• Hence, $\text{FOLLOW}(C) = \mathbf{\{0, 1\}}$

Summary of Results:

Construction of SLR(1) Parsing Table

Given Grammar:
(1) $S \to aAb$
(2) $S \to bB$
(3) $A \to Aa$
(4) $A \to \epsilon$
(5) $B \to Bb$
(6) $B \to \epsilon$

Step 1: Augmented Grammar

(0) $S' \to S$
(1) $S \to aAb$
(2) $S \to bB$
(3) $A \to Aa$
(4) $A \to \epsilon$
(5) $B \to Bb$
(6) $B \to \epsilon$

Step 2: Compute FOLLOW Sets

• \text{FOLLOW}(S') = \{\\}$
• \text{FOLLOW}(S) = \{\\}$
• In $S \to aAb$, following $A$ is $b$, and in $A \to Aa$, following $A$ is $a$:

• In $S \to bB$, $B$ is at end \implies \text{adds } \text{FOLLOW}(S) = \{\\}$, and in$B \to Bb$, following$B$is$b$:

Step 3: Canonical Collection of LR(0) Items

• $I_0$:

• $\text{GOTO}(I_0, S) = I_1$
• $\text{GOTO}(I_0, a) = I_2$
• $\text{GOTO}(I_0, b) = I_3$

• $I_1$:

(Accept state on \$)

• $I_2$ (on $a$ from $I_0$):

(Reduce by $A \to \epsilon$)

• $\text{GOTO}(I_2, A) = I_4$

• $I_3$ (on $b$ from $I_0$):

(Reduce by $B \to \epsilon$)

• $\text{GOTO}(I_3, B) = I_5$

• $I_4$ (on $A$ from $I_2$):

• $\text{GOTO}(I_4, b) = I_6$ (shift $b$)
• $\text{GOTO}(I_4, a) = I_7$ (shift $a$)

• $I_5$ (on $B$ from $I_3$):

(Reduce by $S \to bB$)

• $\text{GOTO}(I_5, b) = I_8$ (shift $b$)

• $I_6$ (on $b$ from $I_4$):

(Reduce by $S \to aAb$)

• $I_7$ (on $a$ from $I_4$):

(Reduce by $A \to Aa$)

• $I_8$ (on $b$ from $I_5$):

(Reduce by $B \to Bb$)

Step 4: SLR(1) Parsing Table

• Reduction $A \to \epsilon$ (rule 4) in $I_2$ placed under $\text{FOLLOW}(A) = \{a, b\}$.
• Reduction $B \to \epsilon$ (rule 6) in $I_3$ placed under \text{FOLLOW}(B) = \{b, \\}$.
• In $I_5$, reduction $S \to bB$ (rule 2) placed under \text{FOLLOW}(S) = \{\\}$, while shift$b$to$I_8$is placed under column$b$. There is no clash!

• Conclusion: Since there are no multiply-defined entries (no shift-reduce or reduce-reduce conflicts), the grammar is SLR(1).