Compiler Design Interview Questions

Introduction

This collection covers the most commonly asked compiler design interview questions, from fundamentals that every CS graduate should know to advanced topics for specialized roles. Each answer is written to demonstrate understanding depth — not just stating facts but explaining the reasoning, trade-offs, and practical implications that interviewers look for.

Compilation Fundamentals

Q1: What are the main phases of compilation and what does each produce?

A compiler transforms source code through six major phases, each producing a distinct output. Lexical analysis reads characters and produces tokens. Syntax analysis reads tokens and produces a parse tree (or AST). Semantic analysis reads the tree and produces an annotated tree with type information and symbol bindings. Intermediate code generation produces a language-independent representation (like three-address code). Optimization transforms the IR into a more efficient version. Code generation produces target machine instructions. Each phase builds on the previous phase's output, creating a clean pipeline where responsibilities are clearly separated.

Q2: What is the fundamental difference between a compiler and an interpreter?

A compiler translates the entire source program into target code before any execution happens — you get an executable that runs independently of the compiler. An interpreter reads and executes the source program statement by statement, with no separate executable produced. The key trade-offs: compilers produce faster-running programs (no interpretation overhead) but have a slower development cycle (edit-compile-run). Interpreters give instant feedback (great for development) but slower execution. Modern systems often blend both: Java compiles to bytecode (compiled), which runs on the JVM (interpreted/JIT-compiled).

Q3: Explain the role of a symbol table throughout compilation.

The symbol table is a persistent data structure maintained across all compilation phases. It maps each identifier (variable, function, type name) to its attributes — declared type, scope level, memory address, parameter list (for functions), array dimensions, etc. The lexer creates entries when identifiers are first seen. The parser associates them with declarations. Semantic analysis fills in type information and checks for undeclared/duplicate symbols. Code generation reads memory offsets for generating load/store instructions. Without the symbol table, the compiler would have no "memory" of previous declarations and could not validate anything beyond syntax.

Q4: What is the difference between a parse tree and an abstract syntax tree?

A parse tree (concrete syntax tree) faithfully represents every step of the grammar derivation — every nonterminal appears as an internal node, every terminal as a leaf. An AST is a simplified version that retains only semantically meaningful information. For example, parsing 3 + 4 with grammar E → E + T, T → 3 | 4 produces a parse tree with nodes for E, T, +, 3, and 4. The AST has just: a + node with children 3 and 4. The AST removes grammar artifacts (intermediate nonterminals, parentheses as grouping), keeping only what matters for code generation.

Parsing Deep Dive

Q5: Explain LL(1) parsing — what does each letter mean?

The first L means "left-to-right scan" of input. The second L means "leftmost derivation" (always expand the leftmost nonterminal). The (1) means "one token of lookahead." An LL(1) parser is predictive — given the current nonterminal on top of its stack and the next input token, it can determine exactly which production to apply without backtracking. This requires the grammar to have no left recursion and no ambiguity (no overlapping FIRST sets). The parsing table maps (nonterminal, token) pairs to productions.

Q6: Why is LALR(1) the practical choice for parser generators?

LALR(1) hits the sweet spot between power and table size. LR(1) (CLR) can parse the most grammars but produces very large tables (thousands of states for real languages). SLR(1) produces small tables but fails on many practical grammars. LALR(1) achieves nearly the power of CLR with table sizes comparable to SLR — it merges CLR states that have identical core items, keeping only 200-400 states for typical programming language grammars. Bison uses LALR(1), and almost all real programming languages can be parsed with it.

Q7: How do FIRST and FOLLOW sets enable predictive parsing?

FIRST(α) tells the parser which tokens can begin a derivation of α. If the parser needs to decide between A → α and A → β, it looks at the current token: if it is in FIRST(α), choose that production. FOLLOW(A) handles the case where α can derive ε (empty): if the current token is in FOLLOW(A), it means A should derive ε because what follows matches what can come after A. Together, FIRST and FOLLOW provide exactly the information needed to populate the LL(1) parsing table.

Q8: What are shift-reduce conflicts and how do you resolve them?

A shift-reduce conflict occurs when the LR parser, in a particular state with a particular lookahead token, has two valid actions: shift the token (add it to the stack) or reduce the current stack top by some production. This usually arises from ambiguous grammar constructs. Resolution strategies: (1) Rewrite the grammar to eliminate ambiguity. (2) Use precedence declarations (%left, %right in Bison) to tell the parser which action to prefer. (3) Default to shift (Bison's behavior), which correctly resolves the dangling-else problem. The important thing is to understand *why* the conflict exists, not just to suppress it.

Code Generation and Optimization

Q9: What is intermediate representation and why is it useful?

An IR is a representation between high-level source code and low-level machine code. Common forms include three-address code, SSA (Static Single Assignment), and control flow graphs. IR serves three purposes: (1) It enables machine-independent optimizations that apply regardless of target architecture. (2) It separates the frontend (language-specific) from the backend (machine-specific), allowing M languages × N targets with only M+N implementations instead of M×N. (3) It provides a uniform representation that simplifies analysis algorithms.

Q10: Explain register allocation using graph coloring.

Variables compete for a limited number of CPU registers. Two variables that are "live" simultaneously (both needed at the same point in execution) cannot share a register — they "interfere." We build an interference graph: nodes are variables, edges connect simultaneously-live variables. Then we k-color this graph (where k is the number of available registers) — assigning colors (registers) so no adjacent nodes share a color. If the graph cannot be k-colored, some variables must be "spilled" to memory. Graph coloring NP-complete in general, but heuristics work well in practice.

Q11: What are the most impactful code optimizations?

From most to least impactful in typical programs: (1) Inlining — eliminates function call overhead for small functions, enables further optimizations on the inlined code. (2) Loop optimizations — loop invariant motion, unrolling, and vectorization affect the hottest code paths. (3) Register allocation — keeping variables in registers vs memory can be 100x faster for accessed values. (4) Dead code elimination — reduces code size and improves cache behavior. (5) Constant propagation/folding — eliminates runtime computation entirely. The key principle: optimize what executes most frequently (loops and hot functions).

Type Systems

Q12: What is the difference between static and dynamic type checking?

Static type checking happens at compile time — the compiler verifies type correctness before the program runs. Languages like C, Java, and Rust use static typing. Dynamic type checking happens at runtime — type errors are detected during execution. Languages like Python, Ruby, and JavaScript use dynamic typing. Static typing catches errors earlier and enables compiler optimizations (knowing a variable is always an int lets the compiler use integer registers). Dynamic typing offers flexibility and shorter code but risks runtime type errors.

Q13: Explain type inference — how can a compiler deduce types without annotations?

Type inference algorithms (like Hindley-Milner, used in ML, Haskell, and Rust) analyze how values are used to determine their types. If you write let x = 3 + y, the compiler infers: 3 is int, + requires two ints and returns int, therefore y must be int and x is int. The algorithm uses unification — treating unknown types as type variables and solving constraints generated from expressions. Modern languages like Kotlin, Swift, and Rust use type inference extensively, reducing annotation burden while maintaining full static type safety.

Advanced Topics

Q14: What is Just-In-Time (JIT) compilation?

JIT compilation translates code to native machine code at runtime, just before execution. The JVM's HotSpot compiler profiles running code, identifies "hot" methods (frequently executed), and compiles them from bytecode to optimized native code. This combines the portability of interpretation (distribute bytecode, not machine code) with the performance of compilation. JIT compilers can even perform optimizations impossible for static compilers — like inlining virtual method calls based on observed runtime types, or de-optimizing when assumptions are violated.

Q15: How does garbage collection interact with the compiler?

The compiler must cooperate with the GC in several ways. It generates write barriers — small code snippets executed on every reference store that notify the GC about pointer changes (essential for generational collectors). It produces stack maps that tell the GC which stack slots contain object references at each program point (so the GC can find all roots). For moving collectors, the compiler must ensure all references are updated when objects relocate. Some compilers perform escape analysis — proving that an object never escapes its creating function, allowing stack allocation instead of heap allocation.

Q16: Describe how you would design an extensible compiler architecture.

A well-designed compiler has clear phase separation with well-defined interfaces between phases. Use a common IR that multiple frontends can target and multiple backends can consume. Make the optimizer a sequence of independent passes, each transforming IR to IR, so new optimizations can be added without disturbing existing ones. Support plugins for custom passes. Use a visitor pattern for tree traversals so new node types don't require modifying existing code. LLVM is the gold standard of this approach — hundreds of frontends and backends share a common IR and optimization pipeline.

Q17: What testing strategies ensure compiler correctness?

Compiler testing requires multiple layers. Unit tests verify individual functions (does this function correctly compute FIRST sets?). Phase tests verify each compilation phase in isolation (does the parser produce the expected AST for this input?). End-to-end tests compile programs and verify their output matches expected results. Fuzzing generates random programs to find crashes and miscompilations. Bootstrapping compiles the compiler with itself — a powerful consistency check. Conformance test suites verify language specification compliance. The gold standard is translation validation — proving that the compiled code is semantically equivalent to the source for each compilation.