Skip to content
Tutorials Center
My learning

Topics

Lesson 60 of 61 ยท Practice and Review

Compiler Design Interview Questions

Prepare for compiler design interviews and exams: core concept questions, trick questions and GATE-style problems with answers, plus runnable checks in Python.

Compiler design questions show up in university exams, in GATE-style entrance tests, and in interviews for roles on language, tooling, database and infrastructure teams. They tend to fall into three families: concept questions ("what is the difference between...?"), trick questions that test whether you really understand a rule, and numeric problems with a single right answer. This lesson has all three, with short answers you can say out loud, and several problems whose answers you can verify by running code in this page.

Use it actively. Cover the answer, say your own answer aloud in two or three sentences, then compare. A good interview answer has a definition, one example, and one consequence ("...which is why LR parsers can handle left recursion").

Core concept questions

1. Compiler, interpreter, transpiler: what is the difference? A compiler translates a whole program to another form (usually machine code) before it runs. An interpreter executes the program directly, step by step. A transpiler translates between two high-level languages. Real systems blend these: Java compiles to bytecode, which a JVM interprets and JIT-compiles. See What Is a Compiler?.

2. Name the phases and what each one produces. Lexical analysis produces tokens; syntax analysis a parse tree or AST; semantic analysis an annotated tree with types and resolved names; intermediate code generation an IR such as three-address code; optimization a better IR; code generation target code. The symbol table and error handler serve every phase. See The Phases of a Compiler.

3. Token, lexeme, pattern? A lexeme is the actual text (count), a pattern is the rule that describes a class of lexemes (a letter followed by letters and digits), and a token is the pair (kind, attribute) handed to the parser, such as (ID, "count").

4. Why are lexers built on finite automata, and not on grammars? Token patterns are regular, and a DFA recognizes them in one table lookup per character. Regular expressions are converted to an NFA (Thompson), then to a DFA (subset construction), then minimized. See From Regex to NFA to DFA.

5. How does a lexer choose between two matching rules? First the longest match wins (maximal munch). If two rules match the same length, the one listed first wins; that is how keywords beat identifiers.

6. Why can't a regular expression check balanced parentheses? A finite automaton has finitely many states and so cannot count unbounded nesting. The pumping lemma proves it. A context-free grammar (S -> ( S ) S | ฮต) or a stack can do it, which is why parsing needs more than a lexer.

7. What is an ambiguous grammar, and how do you fix one? A grammar is ambiguous when some string has two parse trees. Fix it by rewriting the grammar in layers, one per precedence level and with left or right recursion for associativity, or by giving a parser generator precedence declarations. The classic example is the dangling else. See Ambiguity, Precedence and Associativity.

8. LL(1) versus LR(1)? LL parsers are top-down: they build the tree from the root using a leftmost derivation and predict a production from one token of lookahead. LR parsers are bottom-up: they build a rightmost derivation in reverse by shifting tokens and reducing handles. Every LL(1) grammar is LR(1), but not the other way around, so LR handles more grammars, including left-recursive ones. LL is easier to write by hand and to give good error messages with.

9. SLR, LALR and canonical LR? All three are shift-reduce parsers built from item sets; they differ in how lookahead is computed. SLR uses FOLLOW sets (weakest), canonical LR(1) tracks exact lookahead per item (strongest, many states), and LALR merges LR(1) states with the same core, so it has as few states as SLR (the LR(0) automaton) and is almost as strong as LR(1). Yacc and Bison generate LALR(1) parsers. See LR(0), SLR and LALR Parsers.

10. What are shift/reduce and reduce/reduce conflicts? A shift/reduce conflict means that in one state the parser could either shift the next token or reduce; a reduce/reduce conflict means two different reductions apply. Both are signs of ambiguity or of insufficient lookahead. Yacc resolves shift/reduce by shifting (which attaches a dangling else to the nearest if) and reduce/reduce by choosing the earlier rule.

11. Synthesized versus inherited attributes? A synthesized attribute is computed from a node's children (the value of an expression). An inherited attribute is passed down or sideways from the parent or siblings (the declared type propagating to a list of variables). A grammar with only synthesized attributes is S-attributed and fits bottom-up parsing perfectly.

12. What is three-address code, and why SSA? Three-address code has at most one operator per instruction (t1 = a + b), which makes optimization and code generation simple. In SSA form every variable is assigned exactly once and joins use phi functions; this makes many analyses (constant propagation, dead code, value numbering) simpler and faster. See Static Single Assignment.

13. What is a basic block? A maximal straight-line sequence of instructions with one entry (the first instruction, a leader) and one exit (the last). Leaders are the first instruction, every jump target, and every instruction after a jump. Basic blocks are the nodes of the control flow graph.

14. Name some optimizations. Constant folding and propagation, algebraic simplification, strength reduction, common subexpression elimination, dead code elimination, loop-invariant code motion, induction variable elimination, inlining, loop unrolling, tail-call elimination and peephole optimization. See Local Optimizations.

15. How is register allocation done? Build an interference graph (variables are nodes, an edge joins two variables that are live at the same time) and color it with as many colors as there are registers. When it cannot be colored, spill a variable to memory. Graph coloring is NP-complete, so compilers use heuristics (Chaitin-Briggs) or fast linear scan for JITs.

16. What does an activation record contain? Return address, parameters, local variables, saved registers, a control (dynamic) link to the caller's frame, and for nested functions an access (static) link to the enclosing scope's frame. See Runtime Environments.

17. Compare garbage collection strategies. Reference counting is simple and immediate but cannot free cycles. Mark-and-sweep handles cycles but pauses the program and leaves fragmentation. Copying collection compacts memory and allocates cheaply but needs twice the space. Generational collectors exploit the observation that most objects die young.

18. JIT versus ahead-of-time compilation? AOT produces a fast-starting, predictable binary but optimizes without runtime knowledge. A JIT compiles hot code while the program runs and can use real type and branch statistics, at the price of warm-up time and memory. See Interpreters, JIT and AOT.

flowchart TD
    L0["LR(0)"] --> S1["SLR(1)"]
    S1 --> LA["LALR(1)"]
    LA --> L1["LR(1)"]
    LL["LL(1)"] --> L1
    L1 --> CF["Deterministic context-free<br/>languages"]
    AMB["Ambiguous grammars"] -. "never in any of these" .-> L1

An arrow means "every grammar in this class is also in the next one". Ambiguous grammars are in none of the deterministic classes.

Trick questions

These are the ones that separate memorized answers from understanding.

Does the lexer detect int x = ;? No. Every token is valid; the error is in the arrangement, which is the parser's job. The lexer only catches illegal characters, unterminated strings and similar.

Is a regex alternation a maximal-munch matcher? Not in most engines: +|++|+= tries alternatives in order, so it matches a single + in the text ++. Lexer generators implement the longest-match rule explicitly, and in a hand-written regex lexer you sort the alternatives by length. The program below demonstrates this and a few famous lexing puzzles from C.

Python Maximal munch puzzles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

a+++++b becomes a ++ ++ + b, which is a valid token sequence but not a valid C expression, because ++ cannot be applied to the result of a++. i+++j is i ++ + j. The printf call has 10 tokens: the string literal is a single token, whatever it contains.

Is every unambiguous grammar LR(1)? No. Unambiguity is about the grammar; LR(1) is about a deterministic parser with one token of lookahead. A grammar like S -> a S a | b S b | a | b | ฮต (palindromes) is unambiguous but not LR(k) for any k, because the parser cannot know where the middle is.

Is every LL(1) grammar unambiguous? Yes. At every step one lookahead token selects exactly one production, so each string has one leftmost derivation.

Does an LR parser need left recursion removed? No, it prefers left recursion: E -> E + T keeps the parse stack small. Removing it is a requirement for top-down (LL and recursive descent) parsers.

Is x * 2 always the same as x << 1? For two's-complement integers yes, but not for floating point, and the optimizer must respect the language's rules about signed overflow. Strength reduction is only valid when the semantics match.

Does optimization always make a program faster? No. Inlining can bloat code and hurt the instruction cache, aggressive unrolling can overflow it, and some transformations help only in particular situations. Compilers use heuristics and profile data.

Why can't a compiler find all dead code or all bugs? Questions about what a program does at runtime are undecidable in general (Rice's theorem), so analyses are conservative: they may miss opportunities but must never change behavior.

What does a = a++ + ++a; mean in C? Undefined behavior. The language does not specify the order of the side effects, and the compiler may produce any result. The right answer in an interview is to say so and not to guess a number.

GATE-style problems

Each problem is followed by its answer. Some are checked by the code in this lesson.

Problem 1. How many tokens does printf("i = %d, &i = %x", i, &i); contain? Answer: 10: printf, (, the string, ,, i, ,, &, i, ), ;. The string literal is one token. The program above counted exactly this.

Problem 2. For the grammar S -> A A, A -> a A | b, how many states does the LR(0) automaton have? The program below builds the canonical collection of LR(0) item sets for the augmented grammar and counts them.

Python Problem 2: the LR(0) automaton

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Answer: 7 states. The grammar is even LR(0): no state mixes a complete item with a shift item, and no state holds two complete items, so the parser needs no lookahead. (A canonical LR(1) parser for the same grammar needs 10 states, which shows the price of exact lookahead.)

Problem 3. How many three-address instructions does x = a*b + c*d - e need, and how many registers? The next program generates the code and computes the minimum number of registers with the Sethi-Ullman algorithm for two machine models: operations that may take one memory operand, and operations that need both operands in registers.

Python Problem 3: three-address code and Sethi-Ullman

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Answer: 5 instructions (four operations plus the final copy x = t4; a smarter generator writes the last result straight into x and uses 4). For (a+b) * (c+d) the answer is 2 registers with memory operands and 3 when both operands must be in registers. The rule: if both subtrees need the same number of registers, add one; otherwise take the larger. Evaluate the harder subtree first.

Problem 4. How many reduce steps does a bottom-up parser take to parse id + id * id with E -> E + T | T, T -> T * F | F, F -> id? Answer: 8. Each reduction applies one production and corresponds to one interior node of the parse tree: three F -> id, then T -> F twice, T -> T * F, E -> T, and E -> E + T. There are 5 shifts as well, so 13 steps in total.

Problem 5. Is S -> i E t S | i E t S e S | a ambiguous? Answer: yes. The string i E t i E t a e a has two parse trees, depending on whether e a belongs to the inner or the outer if. Adding the rule "attach to the nearest if", or braces, resolves it.

Problem 6. For S -> A B, A -> a | ฮต, B -> b | ฮต, find FIRST(S) and FOLLOW(A). Answer: FIRST(S) = {a, b, ฮต}, because both parts can be empty; FOLLOW(A) = {b, $}: b is what B can start with, and since B can vanish, whatever follows S (the end marker) follows A too.

Problem 7. What is the minimum number of states in a DFA for (a|b)*abb? Answer: 4. The earlier lesson From Regex to NFA to DFA builds a 5-state DFA and minimizes it to 4.

How to answer well

  • State the definition, then an example, then why it matters. "A basic block is straight-line code with one entry and one exit, like the body of this loop; optimizers work on blocks because inside one they can reason without worrying about jumps."
  • Say what you would measure. For "is this optimization good?" the right answer starts with benchmarks.
  • Admit trade-offs. Nearly every answer in this field is a trade-off between speed, memory, simplicity and power.
  • Draw. A small tree, automaton or stack trace makes an answer clear in seconds.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A lexer has the rules + , ++ and += . For the input +++ , what does maximal munch produce?

    At each position the longest matching rule is taken: ++ first, and then the remaining + on its own.
  2. 2. Which statement about LL(1) and LR(1) grammars is true?

    LR(1) is strictly more powerful. An LL(1) grammar is always unambiguous.
  3. 3. In Problem 2, why does the grammar need no lookahead for its parser?

    The grammar is LR(0): in every state of the automaton the action (shift or a single reduction) is determined by the state alone.
  4. 4. Why can a regular expression not recognize balanced parentheses?

    Recognizing arbitrarily deep nesting needs unbounded memory such as a stack, which finite automata lack.
  5. 5. A bottom-up parser parses id + id * id with the standard expression grammar. How many reductions does it perform?

    Eight reductions, one per interior node of the parse tree. The 13 in the options is the total of 8 reductions and 5 shifts.

Summary

  • Interview questions fall into concepts, trick questions and numeric problems; answer with a definition, an example and a consequence.
  • Maximal munch with rule order as a tie-breaker defines lexing; regex alternation alone does not give it.
  • LL(1) is a subset of LR(1); LALR(1) sits between SLR(1) and canonical LR(1); ambiguous grammars are in none of them.
  • Quick numeric tools: count LR(0) item sets, count interior nodes for reductions, and use Sethi-Ullman for registers.
  • Optimizers are conservative because most program properties are undecidable.

Next: Compiler Design Cheat Sheet