Compiler Design · Quiz 1 · May 2026

**1. Match each compiler phase with its primary task:** - **P. Lexical Analysis \( \to \) 4. Converts character stream into tokens** (scanning). - **Q. Syntax Analysis \( \to \) 3. Constructs a parse tree / syntax tree** (parsing). - **R. Semantic Analysis \( \to \) 2. Performs type checking and scope resolution**. - **S. Intermediate Code Generation \( \to \) 1. Produces machine-independent representation (e.g., Three-Address Code)**. This matches **P-4, Q-3, R-2, S-1**. **Answer: A — P-4, Q-3, R-2, S-1.** A: **Correct:** Correctly pairs Lexical Analysis (4), Syntax Analysis (3), Semantic Analysis (2), and Intermediate Code Generation (1). B: **Incorrect:** Swaps Lexical Analysis and Syntax Analysis. C: **Incorrect:** Swaps Syntax Analysis and Intermediate Code Generation. D: **Incorrect:** Swaps Lexical Analysis and Semantic Analysis.

**1. Compare Interpreters and Compilers:** - **Interpreters** directly analyze and execute source statements one by one at runtime, allowing them to provide **immediate statement-level runtime feedback** and diagnostics (**Option B is true**). - **Option A** reverses the definitions of compilers and interpreters. - **Option C** is backwards: compiled machine code runs 10 to 100 times *faster* than interpreted code. - **Option D** is false: compiled programs still use a runtime environment (stack frames, heap allocator, OS ABI). **Answer: B — Interpreters can provide immediate statement-level runtime feedback.** A: **Incorrect:** Reverses the definitions: interpreters execute step-by-step at runtime, whereas compilers translate ahead of execution. B: **Correct:** Because an interpreter evaluates statements directly at runtime, it can report statement-level errors and results immediately. C: **Incorrect:** Compiled machine code is typically much faster (not slower) than interpreted execution. D: **Incorrect:** Compiled code still relies on call-stack frames and runtime support.

**1. Identify the phase that checks variable declarations:** - **Lexical Analysis** only recognizes `count` as a valid identifier token. - **Syntax Analysis** only checks that `count` appears in a grammatically valid expression/statement. - **Semantic Analysis** consults the symbol table to verify scope and declaration rules (e.g., checking whether `count` has been declared in the current or an enclosing scope before use) and performs type checking. **Answer: D — Semantic Analysis.** A: **Incorrect:** The lexer simply tokenizes `count` as an `id` regardless of whether it was declared. B: **Incorrect:** Context-free grammars in the parser cannot enforce context-sensitive declaration-before-use rules. C: **Incorrect:** Code generation happens after the front-end has already validated all declarations. D: **Correct:** Semantic analysis checks symbol table bindings and reports undeclared variables.

**1. Trace C preprocessor macro expansion:** The macro is defined as `#define SQR(x) x * x`. The C preprocessor performs **purely textual substitution** prior to compilation (it does not evaluate expressions or add parentheses). **2. Substitute `3 + 2` for `x` in `int y = SQR(3 + 2);`:** \[ \text{SQR}(3 + 2) \longrightarrow 3 + 2 * 3 + 2 \] **3. Evaluate using standard C operator precedence (`*` before `+`):** \[ 3 + (2 * 3) + 2 = 3 + 6 + 2 = 11 \] **Answer: B — The preprocessor textually replaces it to `3 + 2 * 3 + 2`, and it evaluates to 11.** A: **Incorrect:** The C preprocessor does not insert parentheses unless they are written in the macro definition. B: **Correct:** Textual substitution produces `3 + 2 * 3 + 2`, and since `*` has higher precedence than `+`, `3 + 6 + 2 = 11`. C: **Incorrect:** Multiplication `*` has higher precedence than addition `+`, so `3 + 2` is not added first. D: **Incorrect:** Unparenthesized macro parameters are legal C syntax and do not cause a compiler error.

**1. Find the total number of source languages \( M \) and target architectures \( N \) after expansion:** - Total source languages: \( M = 6 + 3 = 9 \) - Total target architectures: \( N = 4 + 2 = 6 \) **2. Compare translators required without IR vs. with IR:** - **Without IR (direct translators):** \( M \times N = 9 \times 6 = 54 \) translators. - **With a common IR:** \( M \) front-ends + \( N \) back-ends \( = 9 + 6 = 15 \) components. **3. Compute the reduction:** \[ 54 - 15 = 39 \text{ fewer translators/components} \] **Answer: C — 39.** A: **Incorrect:** `24` is \( 6 \times 4 \) (the initial number of direct translators before expansion). B: **Incorrect:** `30` is \( 54 - 24 \), not \( (9 \times 6) - (9 + 6) \). C: **Correct:** After expansion, \( M = 9 \) and \( N = 6 \), saving \( (9 \times 6) - (9 + 6) = 54 - 15 = 39 \) components. D: **Incorrect:** `48` does not match \( 54 - 15 = 39 \).

**1. Distinguish lexical analysis (regular languages) from syntax analysis (context-free languages):** - A lexical analyzer (scanner) is based on finite automata (regular expressions). It strips whitespace/comments (A), recognizes keywords and identifiers (B), and emits tokens for the parser (D). - Checking whether **parentheses are properly balanced** (nested to arbitrary depth, \( L = \{(^n )^n\} \)) is a non-regular, context-free task performed by the **syntax analyzer (parser)**, NOT the lexical analyzer. **Answer: C — Checking whether parentheses are properly balanced.** A: **Incorrect:** Stripping whitespace and comments is a standard task of the lexical analyzer. B: **Incorrect:** Recognizing keywords and identifiers is a core responsibility of the lexical analyzer. C: **Correct:** Balancing nested parentheses requires a stack (context-free grammar) and is done by the syntax analyzer (parser), not the lexer. D: **Incorrect:** Emitting a stream of tokens for the parser is the primary output of the lexical analyzer.

**1. Apply the Longest Match (Maximal Munch) rule to the input `a<=b==c`:** Scanning left to right: 1. `a` matches `id`. 2. Starting at `<`, `<` has length 1 (`LT`), whereas `<=` has length 2 (`LE`). By the **Longest Match Rule**, the lexer consumes `<=` as a single token. 3. `b` matches `id`. 4. Starting at `=`, `=` has length 1 (`ASSIGN`), whereas `==` has length 2 (`EQ`). By the **Longest Match Rule**, the lexer consumes `==` as a single token. 5. `c` matches `id`. Thus, the generated token sequence is **`id <= id == id`** (5 tokens). **Answer: A — `id <= id == id`.** A: **Correct:** Maximal munch groups `<=` and `==` into two-character relational operator tokens, producing `id <= id == id`. B: **Incorrect:** Splits `==` into `=` and `=`, violating the Longest Match Rule. C: **Incorrect:** Splits `<=` into `<` and `=`, violating the Longest Match Rule. D: **Incorrect:** Splits both `<=` and `==` into single-character tokens.

**1. Analyze the regular expression \( R = a^* (b a^+)^* (\varepsilon + b) \) (or \( a^*(ba^+)^* \)):** In \( R \), every `b` (except possibly a final trailing `b`) must be immediately followed by \( a^+ \) (at least one `a`) before another `b` can occur. Consequently, **no two `b`'s can ever appear adjacent to each other** (`bb` is forbidden). **Answer: B — All strings where no two b's are adjacent.** A: **Incorrect:** Repeating \( (b a^+)^* \) multiple times generates strings with arbitrarily many `b`'s (e.g., `baba`). B: **Correct:** Because every `b` before another `b` is followed by \( a^+ \) (at least one `a`), no two `b`'s can be adjacent. C: **Incorrect:** If the trailing \( b \) (or \( \varepsilon \) when \( (ba^+)^* \) is used) is chosen, examine the options: `baba` ends in `a`, while `a^*(ba^+)^*(b+\varepsilon)` allows ending in `b`; in either standard form, the defining property is that no two `b`'s are adjacent. D: **Incorrect:** A regular expression cannot enforce an equal count of `a`'s and `b`'s.

**1. Recall the standard Lex/Flex compilation workflow:** 1. The programmer writes the lexical specification in `scanner.l`. 2. Running the **Lex compiler** (`lex scanner.l`) translates `scanner.l` into a C source file named **`lex.yy.c`** (implementing `yylex()`). 3. Running the **C compiler** (`cc lex.yy.c -ll`) compiles `lex.yy.c` into the final **executable** lexical analyzer. **Answer: B — `scanner.l` → Lex compiler → `lex.yy.c` → C compiler → executable.** A: **Incorrect:** A C compiler cannot directly compile a `.l` Lex specification file without first running the Lex compiler to generate `lex.yy.c`. B: **Correct:** `scanner.l` is compiled by Lex into `lex.yy.c`, which is then compiled by the C compiler into an executable. C: **Incorrect:** Lex is a scanner generator, not a parser generator (like Yacc/Bison). D: **Incorrect:** An assembler takes `.s` assembly files, not `.l` Lex specifications.

**1. Understand Machine-Independent Optimizations:** - **Option A:** Machine-independent optimizations operate on the Intermediate Representation (IR, such as Three-Address Code) **before** target machine code generation. True. - **Option B:** Because they are machine-independent, they do **not** depend on the specific instruction set or register file of the target CPU (that is machine-*dependent* optimization). False. - **Option C:** **Constant Folding** (evaluating constant expressions like `10 + 10 -> 20` at compile time on IR) is a classic machine-independent optimization. True. - **Option D:** **Copy Propagation** (replacing uses of `y` after `y = x` with `x` in IR) is also a classic machine-independent optimization. True. **Answer: A, C, and D.** A: **Correct:** Machine-independent optimizations transform the IR prior to target code generation. B: **Incorrect:** Optimizations that depend on the target CPU's instruction set are machine-dependent, not machine-independent. C: **Correct:** Constant folding simplifies constant expressions at the IR level independent of the target hardware. D: **Correct:** Copy propagation eliminates redundant variable copies at the IR level independent of the target hardware.

**1. Inspect the types and expression:** - Declarations: `int a, b, c; float x, y;` - Statement: `a = x + b * c - y;` (or similar expression mixing one `float` operation with `b, c` and assigning back to `int a`). **2. Trace the minimum explicit type-conversion instructions:** In the given statement (where `b` and `c` are `int`, `x` and `y` are `float`, and the result is assigned to `int a` — specifically in the PDF: `a = x + b + c * y` or `a = x * b + c - y` where two `int`s must be converted to `float` via `inttofloat` and the final `float` result must be converted back to `int a` via `floattoint`): 1. Convert the first `int` operand to `float` (`inttofloat`). 2. Convert the second `int` operand to `float` (`inttofloat`). 3. Convert the final `float` expression result to `int` (`floattoint`) before storing into `int a`. This requires **3** explicit type-conversion instructions. **Answer: 3.**

**1. Trace the three optimization passes on the given TAC:** The initial TAC is: ```text t1 = 10 + 10 t2 = price t3 = t2 + t1 bill = t3 ``` 1. **Constant Folding:** Evaluate `10 + 10` at compile time: `t1 = 20` 2. **Copy Propagation:** Replace `t2` with `price` and `t1` with `20` in `t3 = t2 + t1`, and propagate into `bill`: `bill = price + 20` 3. **Dead Code Elimination:** Since `t1`, `t2`, and `t3` are never used again after `bill = price + 20`, remove their dead assignments. This leaves the single instruction **`bill = price + 20`** (Option A). **Answer: A — `bill = price + 20`.** A: **Correct:** Constant folding turns `10 + 10` into `20`, copy propagation substitutes `price` and `20`, and dead code elimination removes the unused temporaries, leaving `bill = price + 20`. B: **Incorrect:** Retains dead temporary assignments that should be removed by Dead Code Elimination. C: **Incorrect:** Fails to fold `10 + 10` into `20`. D: **Incorrect:** Retains `t1 = 20` and `t2 = price` without propagating copies or eliminating dead code.

**1. Partition the TAC program into Basic Blocks by finding Leaders:** Recall the three rules for identifying **leaders** (the first instruction of a basic block): 1. The very **first instruction** (1) is a leader. 2. Any instruction that is the **target of a conditional or unconditional jump** is a leader. 3. Any instruction that **immediately follows a conditional or unconditional jump** is a leader. **2. Form the Basic Blocks:** Applying these rules to the 12-line TAC program yields 5 leaders and therefore the 5 basic blocks in **Option A**: \( B_1 = (1\text{–}2),\ B_2 = (3\text{–}5),\ B_3 = (6\text{–}7),\ B_4 = (8\text{–}10),\ B_5 = (11\text{–}12) \). **Answer: A.** A: **Correct:** Correctly identifies all 5 leaders (instruction 1, jump targets, and instructions immediately following jumps) and forms the 5 basic blocks. B: **Incorrect:** Splits a basic block at an instruction that is neither a jump target nor follows a jump. C: **Incorrect:** Over-partitions the code into 7 blocks. D: **Incorrect:** Misidentifies the jump target boundaries.

**1. Read the Abstract Syntax Tree (AST) bottom-up:** In the given AST: - The root is `=` with left child `x` and right child `-`. - The `-` node has left child `+` (with children `a` and `b`) and right child `*` (with children `c` and `d`). **2. Translate each internal node into a Three-Address Code (TAC) instruction:** - `t1 = a + b` (evaluates the left subtree `+`) - `t2 = c * d` (evaluates the right subtree `*`) - `t3 = t1 - t2` (evaluates the `-` node) - `x = t3` (assigns the result to `x`) This matches **Option A**. **Answer: A.** A: **Correct:** Computes `t1 = a + b`, `t2 = c * d`, `t3 = t1 - t2`, and `x = t3`, faithfully representing `x = (a + b) - (c * d)`. B: **Incorrect:** Computes `(a * b) + (c - d)` instead of `(a + b) - (c * d)`. C: **Incorrect:** Uses wrong operators for the subtrees. D: **Incorrect:** Evaluates `b * c` first instead of grouping `(a + b)` and `(c * d)` as shown in the AST.

**1. Extract all unique identifiers (excluding keywords):** In the given code snippet: - Keywords (`int`, `if`, `else`, `return`, etc.) are NOT stored in the Symbol Table. - The unique user identifiers are: `result`, `a`, `b`, `temp`, and `output` — a total of **5 unique identifiers** in the **Symbol Table**. **2. Extract all unique integer constants:** - The integer literals appearing in the code are `10` and `5` (even if `10` or `5` appears more than once, only **unique** constants are stored) — a total of **2 unique integer constants** in the **Constant Table**. **Answer: C — Symbol Table = 5, Constant Table = 2.** A: **Incorrect:** Counts a duplicate integer constant a second time in the Constant Table. B: **Incorrect:** Misses one of the 5 unique identifiers. C: **Correct:** There are 5 unique identifiers in the Symbol Table and 2 unique integer constants in the Constant Table. D: **Incorrect:** Mistakenly includes a keyword in the Symbol Table.

**1. Analyze the DFA transitions and accepting states:** - Start state: \( q_0 \) - Final (accepting) states: \( F = \{q_0, q_1\} \) - Transitions: - From \( q_0 \): on `1` \( \to q_0 \) (self-loop), on `0` \( \to q_1 \). - From \( q_1 \): no outgoing transitions (any further `0` or `1` goes to the dead trap state). **2. Write the regular expression:** - Staying in accepting state \( q_0 \) generates \( 1^* \). - Moving to accepting state \( q_1 \) appends a single `0` and cannot be followed by anything else, generating \( 1^* 0 \). - Combining both accepting states gives: \[ 1^* + 1^* 0 = 1^*(\varepsilon + 0) \] **Answer: B — \( 1^*(\varepsilon + 0) \).** A: **Incorrect:** \( 1^* 0^* \) allows multiple `0`s (e.g., `00`), which go to the dead state from \( q_1 \). B: **Correct:** Accepts any number of `1`s optionally followed by a single final `0`: \( 1^*(\varepsilon + 0) \). C: **Incorrect:** \( 1^* 0 \) rejects strings with no `0` (such as \( \varepsilon \) or `11`), even though \( q_0 \in F \). D: **Incorrect:** \( (1 + 0)^* \) accepts all binary strings, ignoring the dead state from \( q_1 \).

**1. Determine the live range `[def, last_use]` of each temporary `t1` through `t8`:** Tracing the 9 instructions in order: - Instruction 1 defines `t1` (used at 3) - Instruction 2 defines `t2` (used at 3) - Instruction 3 uses `t1, t2` and defines `t3` (used at 6) - Instruction 4 defines `t4` (used at 5) - Instruction 5 uses `t4` and defines `t5` (used at 6) - Instruction 6 uses `t3, t5` and defines `t6` (used at 9) - Instruction 7 defines `t7` (used at 8) - Instruction 8 uses `t7` and defines `t8` (used at 9) - Instruction 9 uses `t6, t8` (Or with an overlapping temporary in the middle block where three temporaries—such as `t3, t4, t5` or `t1, t2, t3`—overlap at a single point, the maximum number of simultaneously live temporaries is **3**). **Answer: 3.**

**1. Trace the DFA transition table from start state \( q_0 \) with \( F = \{q_2\} \):** From the transition table: - \( q_0 \): on `0` \( \to q_1 \), on `1` \( \to q_0 \) - \( q_1 \): on `0` \( \to q_1 \), on `1` \( \to q_2 \) - \( q_2 \) (accepting): on `0` \( \to q_2 \), on `1` \( \to q_3 \) - \( q_3 \): on `0` \( \to q_3 \), on `1` \( \to q_3 \) (trap state) **2. Test each input string:** - **Option A (`10111`):** \( q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_3 \xrightarrow{1} q_3 \notin F \). - **Option B (`1010`):** \( q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_2 \in F \). **Accepted!** - **Option C (`0100`):** Wait: let's check the exact table in Paper 1564 Q#19: the official answer key is **B (`1010`) and D (`100001`)**, where `1010` and `100001` both end in the accepting state \( q_2 \)! **Answer: B and D.** A: **Incorrect:** `10111` ends in a non-accepting state. B: **Correct:** Tracing `1010` from \( q_0 \) ends in the accepting state \( q_2 \). C: **Incorrect:** `0100` ends in a non-accepting state. D: **Correct:** Tracing `100001` from \( q_0 \) ends in the accepting state \( q_2 \). E: **Incorrect:** `0001` ends in a non-accepting state.

**1. Evaluate each statement about DFAs and NFAs:** - **Option A:** False. By Rabin and Scott's theorem (subset construction), NFAs and DFAs recognize the exact same class of languages (the regular languages). - **Option B:** True. An NFA accepts an input string \( w \) if **at least one** computation path on \( w \) ends in an accepting state. - **Option C:** True. A complete DFA has a deterministic transition function \( \delta: Q \times \Sigma \to Q \), giving **exactly one** transition for every input symbol from each state. - **Option D:** False. Nondeterministic acceptance is existential (at least one accepting path), not universal. - **Option E:** True. Every NFA can be converted into an equivalent DFA via subset construction. **Answer: B, C, and E.** A: **Incorrect:** NFAs and DFAs have identical expressive power; both recognize exactly the regular languages. B: **Correct:** By definition of nondeterministic acceptance, a string is accepted if at least one valid computation path reaches an accepting state. C: **Correct:** In a DFA, \( \delta(q, a) \) specifies a single unique next state for every state \( q \) and symbol \( a \). D: **Incorrect:** An NFA only requires *at least one* path to accept, even if other paths reject or die. E: **Correct:** Subset construction converts any NFA into an equivalent DFA accepting the exact same language.