GATE Compiler Design Questions

Introduction to GATE Compiler Design

Compiler Design is a significant topic in the GATE Computer Science exam, typically contributing 5-8 marks. Questions test your understanding of formal languages, parsing algorithms, optimization techniques, and runtime environments. The key to scoring well is not just knowing definitions but being able to trace through algorithms step-by-step and identify subtle distinctions between similar concepts.

This collection presents representative questions with detailed explanations — not just the correct answer, but why each wrong answer is wrong and the reasoning process you should follow.

Lexical Analysis and Formal Languages

**Q1: The language L = {wcw^R | w ∈ {a,b}*, w^R is the reverse of w} is:**

• (A) Regular language
• (B) Context-free language
• (C) Context-sensitive language
• (D) Recursive language

Answer: (B) Context-free language

Explanation: This language requires matching the first half against the reverse of the second half, separated by 'c'. A pushdown automaton (PDA) can handle this: push symbols until 'c' is seen, then pop and match. Since PDAs recognize exactly the context-free languages, L is context-free. It is NOT regular because regular languages cannot "remember" arbitrary-length strings for matching. It is not merely context-sensitive because a PDA suffices (context-free ⊂ context-sensitive).

Q2: Which of the following is NOT a valid token in C?

• (A) main
• (B) 123abc
• (C) _var
• (D) a+b

Answer: (B) 123abc

Explanation: In C, identifiers must start with a letter or underscore. 123abc starts with a digit, making it invalid as a single token (the lexer would tokenize it as integer 123 followed by identifier abc). Option (A) main is a valid identifier (not a reserved keyword in C, just a conventional function name). Option (C) _var starts with underscore — valid. Option (D) a+b is three separate tokens, not one, but each is individually valid.

Q3: A lexical analyzer uses which of the following to recognize tokens?

• (A) Pushdown automata
• (B) Turing machines
• (C) Finite automata
• (D) Linear bounded automata

Answer: (C) Finite automata

Explanation: Tokens are defined by regular expressions, which are equivalent in power to finite automata (both DFA and NFA). The lexer generator converts regex patterns to a DFA for efficient O(n) scanning. Pushdown automata are used for parsing (context-free languages), and Turing machines are unnecessarily powerful for token recognition.

Parsing

Q4: Consider the grammar: S → aS | b. Which is true?

• (A) LL(1) parsable
• (B) Ambiguous
• (C) Left-recursive
• (D) Not context-free

Answer: (A) LL(1) parsable

Explanation: This grammar has no left recursion (S does not appear as the leftmost symbol on any right-hand side). FIRST(aS) = {a} and FIRST(b) = {b}. Since {a} ∩ {b} = ∅, there is no ambiguity in choosing which production to apply — if the current token is 'a', use S → aS; if 'b', use S → b. This satisfies the LL(1) condition perfectly. The grammar is not ambiguous (each string has exactly one leftmost derivation).

Q5: For the grammar S → A | B, A → a, B → a, how many reduce-reduce conflicts exist?

• (A) 0
• (B) 1
• (C) 2
• (D) 3

Answer: (B) 1

Explanation: When the parser has 'a' on the stack and sees the end-of-input marker, it can reduce 'a' to either A (using A → a) or B (using B → a). Both are valid reductions in this state. This is a classic reduce-reduce conflict — the parser cannot determine which nonterminal to derive. This indicates the grammar is ambiguous (both A and B generate the same string 'a', and S accepts both).

**Q6: The number of states in the minimal DFA for the language (a|b)*abb is:**

• (A) 3
• (B) 4
• (C) 5
• (D) 6

Answer: (C) 5

Explanation: The DFA recognizes strings ending in "abb" over alphabet {a,b}. States represent: (q0) haven't seen any suffix yet, (q1) just saw 'a', (q2) saw 'ab', (q3) saw 'abb' — accepting state, plus transitions back on mismatch. The minimal DFA has exactly 5 states: the start state, three states tracking progress toward "abb", and one state handling the 'a' character that could start a new "abb" pattern after a mismatch. This can be verified by the Myhill-Nerode theorem.

Type Systems and Semantic Analysis

Q7: Consider: int x = 5.5; in C. What happens?

• (A) Compile error
• (B) Runtime error
• (C) Implicit conversion, x = 5
• (D) Implicit conversion, x = 5.5

Answer: (C) Implicit conversion to int, x = 5

Explanation: C performs implicit narrowing conversion from double to int. The fractional part is truncated (not rounded), so 5.5 becomes 5. This is legal C code that compiles without error (though many modern compilers issue a warning). It is NOT a runtime error — the conversion happens at the assignment statement during normal execution. Option (D) is wrong because an int variable cannot store a fractional value.

Q8: Which error is detected during semantic analysis?

• (A) int x = ; (missing expression)
• (B) int x y ; (missing operator/delimiter)
• (C) int x = "hello"; (type mismatch)
• (D) int x = 1/0; (division by zero)

Answer: (C) int x = "hello";

Explanation: (A) and (B) are syntax errors — they violate grammar rules and are caught by the parser. (C) is syntactically valid (it follows the pattern type id = expression ;) but semantically invalid because you cannot assign a string literal to an integer variable — this is a type mismatch caught by semantic analysis. (D) is a runtime error because the compiler generally cannot detect division by zero when the divisor is a computed value (though constant 1/0 might trigger a warning).

Code Generation and Optimization

Q9: The three-address code for array access a[i] = b is:

• (A) t1 = a + i; *t1 = b
• (B) a[i] = b
• (C) t1 = i * width; t2 = a + t1; *t2 = b
• (D) load a[i]; store b

**Answer: (C) t1 = i * width; t2 = a + t1; *t2 = b**

Explanation: Array element address computation requires multiplying the index by the element size (width) and adding to the base address. t1 = i * width computes the byte offset. t2 = a + t1 computes the actual memory address of a[i]. *t2 = b stores value b at that address. Option (A) is wrong because it doesn't account for element width. Option (B) is not three-address code (it's high-level). Option (D) is assembly-style, not three-address code format.

Q10: Which optimization is demonstrated by: x = 2 + 3 → x = 5?

• (A) Constant propagation
• (B) Constant folding
• (C) Dead code elimination
• (D) Strength reduction

Answer: (B) Constant folding

Explanation: Constant folding evaluates expressions involving only constants at compile time rather than generating code to compute them at runtime. 2 + 3 involves two constants, so the compiler computes 5 and generates x = 5 directly. Constant propagation is different — it replaces variables with their known constant values (if y = 5, then x = y + 1 becomes x = 5 + 1). Dead code elimination removes unused code. Strength reduction replaces expensive operations with cheaper equivalents (like x * 2 → x << 1).

Q11: In a graph coloring approach to register allocation, what do colors represent?

• (A) Variables
• (B) Registers
• (C) Instructions
• (D) Basic blocks

Answer: (B) Registers

Explanation: In the interference graph, each node represents a variable (or temporary), and an edge connects two variables that are simultaneously live (both needed at the same time). Graph coloring assigns colors (registers) to nodes such that no two adjacent nodes share the same color — meaning no two simultaneously live variables are assigned the same register. If the graph can be colored with k colors, k registers suffice.

Parsing Table Construction

Q12: For an LL(1) grammar, if FIRST(α) and FIRST(β) overlap for productions A → α | β, then:

• (A) The grammar is LL(1)
• (B) The grammar is ambiguous
• (C) The grammar is not LL(1)
• (D) Left factorization is needed

Answer: (C) The grammar is not LL(1)

Explanation: LL(1) requires that for any nonterminal with multiple productions, the parser can determine which production to use based on a single lookahead token. If FIRST(α) ∩ FIRST(β) ≠ ∅, then there exists a token that could begin either α or β, making the choice ambiguous with one lookahead. The grammar might be fixable through left factoring (extracting the common prefix), but as stated it fails the LL(1) condition. Note: overlapping FIRST sets do not necessarily mean the grammar is ambiguous — it might simply need more lookahead.

Q13: LALR parsing reduces the number of states compared to CLR by:

• (A) Removing unreachable states
• (B) Merging states with the same core items
• (C) Eliminating left-recursive rules
• (D) Using shorter lookahead strings

Answer: (B) Merging states with the same core items

Explanation: CLR (canonical LR(1)) constructs states where each item includes a specific lookahead set. Two states might have identical core items (same productions with same dot positions) but different lookaheads. LALR merges such states by unioning their lookahead sets. This dramatically reduces table size (LALR tables are typically 10x smaller than CLR) with minimal loss of parsing power — most practical grammars parse identically under LALR and CLR.

Runtime Environment

Q14: In a language with nested functions, access to non-local variables is provided by:

• (A) Static link (access link)
• (B) Dynamic link (control link)
• (C) Return address
• (D) Program counter

Answer: (A) Static link (access link)

Explanation: The static link points to the activation record of the lexically enclosing function, allowing access to non-local variables defined in outer scopes. The dynamic link (saved frame pointer) points to the caller's activation record — useful for return but not for accessing variables in enclosing scopes (the caller might not be the enclosing function). The distinction: static link follows the program's nesting structure, while dynamic link follows the call chain.

Q15: The output of a lexical analyzer is:

• (A) Parse tree
• (B) Stream of tokens
• (C) Object code
• (D) Intermediate code

Answer: (B) Stream of tokens

Explanation: The lexer reads characters and groups them into tokens — each token has a type (keyword, identifier, number, operator) and attributes (the actual text, numeric value, etc.). This token stream is the input to the parser. Parse trees are produced by the parser, intermediate code by the IR generator, and object code by the assembler.