Top 50 Compiler Design Interview Questions (2026)

A compiler is a program that translates source code written in one language into an equivalent program in another, usually lower-level, language such as machine code or bytecode. It reads the whole input, checks it, and produces output you run separately.

It works in phases: it turns characters into tokens, builds a tree from those tokens, checks the meaning against rules like types and scope, then generates and optimizes target code. A good compiler also reports useful errors instead of just failing, since catching mistakes early is half its value.

A compiler translates the entire program to target code ahead of time, then you run that separate output. An interpreter reads and executes the source directly, one statement at a time, without ever producing a standalone machine-code file first, so it runs the program itself rather than handing you a binary.

The practical trade-off: compiled programs run faster and catch many errors before running, but you rebuild on every change. Interpreted programs start fast and are easy to debug and port, but run slower because the source is analyzed each time. Many languages combine both, compiling to bytecode that an interpreter or JIT then runs.

The classic six are lexical analysis, syntax analysis, semantic analysis, intermediate code generation, code optimization, and target code generation. The first three form the front end, which understands the program; the last three form the back end, which produces output.

Two things thread through every phase: the symbol table, which records identifiers and their attributes, and the error handler, which reports and recovers from problems. Splitting front end from back end is what lets one front end target many machines and one back end serve many languages.

A lexeme is the actual sequence of characters in the source, like the text count or the digits 42. A pattern is the rule that describes a set of lexemes, usually a regular expression, such as 'a letter followed by letters or digits' for an identifier. A token is the category the lexer produces, like IDENTIFIER or NUMBER, often paired with the lexeme and a source position.

So the lexer matches lexemes against patterns and emits tokens. The word count is a lexeme, the identifier regex is its pattern, and the token might be (IDENTIFIER, "count"). Keeping these three straight is a common early check.

The lexical analyzer, or scanner, reads the source character by character and groups characters into tokens according to patterns. It also throws away whitespace and comments, tracks line and column numbers for error messages, and hands a clean token stream to the parser.

It's built on regular expressions and finite automata: each token type has a pattern, and the scanner effectively runs a DFA to match the longest valid lexeme. If it hits characters that match no pattern, it reports a lexical error, like an illegal symbol.

Syntax analysis takes the token stream from the lexer and checks it against the language's grammar, building a parse tree or abstract syntax tree that shows how the tokens fit together. If the tokens don't form a valid structure, it reports a syntax error.

The grammar is context-free, so the parser handles nesting that the lexer can't, like matched parentheses or nested blocks. The output tree is what later phases walk to check types and generate code, so parsing is where the flat token stream becomes structure.

A parse tree, also called a concrete syntax tree, shows every grammar rule applied to derive the input, including every intermediate nonterminal and every piece of punctuation like parentheses and semicolons. It mirrors the grammar exactly, so it's large and verbose even for a small expression.

An abstract syntax tree keeps only the meaningful structure and drops the syntactic noise: a plus node with two children instead of the full expression-term-factor chain. Most compilers build or reduce to an AST because later phases care about meaning, not about every grammar detail.

A context-free grammar is a set of production rules that describe a language's syntax. It has terminals (the tokens), nonterminals (syntactic categories like Expr or Stmt), a start symbol, and productions that say how each nonterminal expands. 'Context-free' means a nonterminal expands the same way regardless of what surrounds it.

Programming-language syntax is context-free because it needs nesting that regular expressions can't express, like arbitrarily deep parentheses. The parser's whole job is deciding whether the token stream can be derived from the grammar's start symbol.

Top-down parsing starts at the grammar's start symbol and tries to derive the input by expanding rules toward the tokens. Recursive descent and LL parsers are top-down. Bottom-up parsing starts from the input tokens and reduces them back up toward the start symbol. LR-family parsers (SLR, LALR, canonical LR) are bottom-up.

Bottom-up parsers handle a larger class of grammars, including left recursion, which is why parser generators use them. Top-down parsers, especially hand-written recursive descent, are simpler to write and give friendlier error messages, which is why many production compilers still use them.

A grammar is ambiguous if some string in the language has more than one distinct parse tree. The classic cases are an expression grammar with no precedence (so 1 + 2 * 3 could group two ways) and the dangling-else problem, where an else could attach to either if.

It's a problem because the parse tree drives meaning: two trees can mean two different computations. Parsers need one answer per input, so you remove ambiguity by rewriting the grammar to encode precedence and associativity, or by adding a disambiguation rule like 'else binds to the nearest if'.

A rule is left-recursive when a nonterminal appears as the first symbol on the right side of its own production, like Expr -> Expr + Term. A top-down parser trying to expand Expr would call Expr again before consuming any token, so it recurses forever.

You remove it by rewriting the rule to be right-recursive using a helper nonterminal, which keeps the same language but lets a top-down parser make progress. Bottom-up parsers don't need this because they reduce from the tokens up.

A syntax error breaks the grammar's structure: a missing semicolon, an unbalanced parenthesis, a keyword in the wrong place. The parser catches these during syntax analysis because the tokens simply can't be arranged into a valid parse tree, so the derivation fails before meaning is ever considered.

A semantic error is grammatically valid but meaningless: adding a string to an integer, calling an undeclared function, assigning to a constant. Semantic analysis catches these using the symbol table and type rules, after the parse succeeds. The code parses fine; it just doesn't make sense.

Tokens are simple, flat patterns like identifiers, numbers, and operators, and regular expressions describe them precisely while a fast finite automaton recognizes them. That combination is ideal for scanning millions of characters quickly, which is exactly what the lexer has to do on every source file.

Syntax needs nesting: matched parentheses, nested blocks, expressions inside expressions. Regular expressions provably can't count arbitrary nesting, so you need the extra power of a context-free grammar and a parser. Splitting the job this way keeps the lexer fast and the parser focused on structure.

The front end understands the source: lexical analysis, syntax analysis, and semantic analysis, ending in an intermediate representation. It depends on the source language but not on the target machine, so the same front end can serve many different processors as long as they share the back end.

The back end produces output from that intermediate representation: optimization and target code generation. It depends on the target machine but not on the source language. This split is what lets one front end target many CPUs, and one back end (like LLVM's) serve many source languages, which is the whole reason the design is popular.

An intermediate representation (IR) is a form of the program that sits between the source and the target: it's not the original syntax anymore, and it's not final machine code yet. Common forms are three-address code, abstract syntax trees, and control-flow graphs, each chosen for how easy it makes analysis.

You use one for two reasons. It decouples the front end from the back end, so many languages and many targets can share optimizers. And it's a convenient level to optimize at, simpler than the source but not yet tied to a specific machine's registers and instructions.

A symbol table maps each identifier to its attributes: its type, its scope, its memory location, and whether it's a variable, function, or constant. It's usually built incrementally as the parser and semantic analyzer walk the tree, adding an entry when a name is declared and looking it up wherever the name is used.

Almost every phase touches it. Semantic analysis reads it to check types and catch undeclared names, code generation reads it to know where variables live, and scope handling adds and removes entries as blocks open and close. A good symbol table supports nested scopes so an inner declaration can shadow an outer one.

A cross-compiler runs on one platform but produces code for a different target platform. You might build it on your x86 laptop and have it emit ARM binaries for a phone or a microcontroller that can't compile code itself.

It's the normal tool for embedded work, where the target device is too small to host a compiler, and for building an operating system for a machine before that machine can run anything. The key idea is that the host (where the compiler runs) and the target (what it produces code for) are different.

The assembler translates assembly code into machine code (object files). The linker combines multiple object files and libraries into a single executable, resolving references so a call to a function defined elsewhere points at the right address. The loader brings that executable into memory and sets it up to run.

They sit after the compiler in the classic toolchain. The compiler often emits assembly, the assembler makes object files, the linker stitches them together, and the loader (part of the OS) starts the program. Knowing this pipeline shows you see where the compiler fits in the bigger picture.

LL(1) means the parser reads input Left to right, produces a Leftmost derivation, and uses 1 token of lookahead. It's a top-down predictive parser: at each step it decides which production to use by looking at the next single token, with no backtracking.

For a grammar to be LL(1) it must have no left recursion and no ambiguity, and its rules must not conflict under one token of lookahead, which you check with FIRST and FOLLOW sets. When those hold, you can build a predictive parsing table and parse in linear time.

FIRST(X) is the set of terminals that can begin a string derived from X. FOLLOW(X) is the set of terminals that can appear immediately after X in some derivation. Together they tell a predictive parser which production to pick for a nonterminal given the next token.

You need FOLLOW because a rule can derive the empty string; then the parser looks at what can follow the nonterminal to decide whether to apply the empty production. Building these sets is the step that lets you construct an LL(1) table and prove a grammar is LL(1).

A recursive descent parser is a top-down parser written as a set of functions, one per nonterminal, that call each other to match the grammar. Parsing an Expr calls parseExpr, which calls parseTerm, and so on, mirroring the grammar's structure directly in code.

It's popular because it's easy to write by hand, easy to debug, and gives you full control over error messages, which is why many production compilers use it. The catch is it can't handle left recursion, so you rewrite left-recursive rules first, often adding operator-precedence handling (like Pratt parsing) for expressions.

LR parsing is bottom-up. It reads input left to right, keeps a stack, and repeatedly does one of two actions: shift (push the next token onto the stack) or reduce (replace symbols on top of the stack that match a rule's right side with its left-side nonterminal). It's driven by a parsing table built from the grammar.

It handles a much larger class of grammars than LL, including left recursion, which is why parser generators like yacc and bison use LALR, a compact LR variant. The trade-offs are that the tables are complex to build by hand and the error messages are harder to make friendly.

A shift-reduce conflict happens when an LR parser's table says it could either shift the next token or reduce by a rule at the same point, and the grammar doesn't tell it which. The dangling-else problem is the classic source: after parsing an if-then, seeing else, the parser can't tell whether to attach the else or reduce the inner statement.

You resolve it by disambiguating the grammar, or by giving the generator a precedence rule. Most tools default to shift on a conflict, which happens to attach else to the nearest if, the usual desired behavior. A reduce-reduce conflict, where two rules could both reduce, usually signals a deeper grammar problem.

A derivation is the sequence of rule expansions that produces a string from the grammar's start symbol. In a leftmost derivation you always expand the leftmost nonterminal first at each step. In a rightmost derivation you always expand the rightmost nonterminal first. Both can produce the same string and the same parse tree.

The distinction matters because parsing techniques align with them. Top-down LL parsers trace a leftmost derivation as they go, while bottom-up LR parsers construct a rightmost derivation in reverse, reducing from the tokens back toward the start symbol. So when someone says LR does a rightmost derivation, that reverse order is what they mean.

Type checking is the headline, but semantic analysis does more. It checks that names are declared before use and resolves each to the right declaration through scope, catches duplicate declarations, verifies that function calls match their signatures, and checks that break or return appears only where it's legal.

It also enforces language-specific rules: that a constant isn't assigned to, that array indices and access modifiers are valid, that control flow reaches a required return. All of this uses the symbol table and often decorates the AST with type and scope information for the code generator to use.

The type checker walks the AST and assigns a type to each expression from the bottom up. A literal has a known type, a variable's type comes from the symbol table, and an operation's type follows a rule: adding two ints gives an int, comparing gives a bool. If the operands don't fit the operator's rule, it reports a type error.

It also handles coercion and conversion where the language allows it (int to float in mixed arithmetic) and verifies assignments and function arguments are compatible. Static type checking does this at compile time; dynamically typed languages defer most of it to runtime instead.

Three-address code is a linear intermediate representation where each instruction has at most one operator and up to three operands (typically two sources and one destination), like t1 = a + b. Complex expressions are broken into a sequence using temporary variables.

It's useful because it's close to machine code but still machine-independent, which makes it a good level to optimize at. Its simple, uniform shape makes analyses like reaching definitions and live-variable analysis straightforward, and it translates cleanly to real instructions in the back end.

Syntax-directed translation attaches semantic rules or actions to grammar productions, so as the parser recognizes structure, it also computes something: a type, a value, or a piece of intermediate code. You annotate nonterminals with attributes and give each rule a rule for computing them.

Attributes come in two flavors. Synthesized attributes flow up from children to parent (an expression's type computed from its operands). Inherited attributes flow down or across (a declared type passed to the identifiers it applies to). It's the standard framework for turning a parse into meaning and code as you go.

An activation record is the block of memory a function call uses on the stack. It holds the function's parameters, local variables, the return address, saved registers, and a link to the caller's frame. Each call pushes a new record; each return pops one.

The compiler decides the layout and generates code to set up and tear down each frame. Understanding this matters for code generation and for reasoning about recursion, variable lifetimes, and why local variables vanish when a function returns. The stack of these records is the call stack.

Constant folding evaluates constant expressions at compile time, so 3 * 4 becomes 12 and the multiply never runs. Constant propagation replaces a variable with its known constant value where the compiler can prove it's constant, so after x = 5 a later use of x becomes 5.

They work together and cascade: propagation turns a variable into a constant, folding then simplifies the expression around it, which can expose more constants and more dead code. Both are safe because they don't change the program's meaning, only when the work happens.

Dead code elimination removes code whose result is never used or that can never run. That includes assignments to a variable that's never read again, and unreachable code after an unconditional return or behind a condition that's always false.

The compiler proves code is dead using data-flow analysis, like live-variable analysis to find values that are never used, and reachability analysis on the control-flow graph. Removing dead code shrinks the program and speeds it up, and it's safe precisely because, by definition, the removed code couldn't affect the output.

A basic block is a straight-line sequence of instructions with one entry at the top and one exit at the bottom: no jumps in except to the first instruction, no jumps out except from the last. Once you enter, every instruction runs in order.

A control-flow graph (CFG) has basic blocks as nodes and edges for the possible jumps between them. It's the structure most optimizations and analyses run on, because reasoning about straight-line blocks and the edges connecting them is far easier than reasoning about raw instructions with arbitrary jumps.

Peephole optimization scans a small sliding window of adjacent instructions and replaces inefficient patterns with better ones. Examples: deleting a load immediately followed by a store of the same value, removing a jump to the very next instruction, or replacing a multiply by a power of two with a shift.

It's local and cheap because it only looks at a few instructions at a time, usually late in the back end after code generation. It won't restructure the program, but it cleans up the small inefficiencies that earlier phases and naive code generation leave behind.

Lex (or flex) is a scanner generator: you give it token patterns as regular expressions with actions, and it produces the C code for a lexer. Yacc (or bison) is a parser generator: you give it a grammar with actions, and it produces a bottom-up LALR parser.

Together they let you build a front end from declarative specs instead of hand-writing every scanner state and parser table. The lexer feeds tokens to the parser, and the parser's actions build the tree or emit code. They're the classic teaching and prototyping toolchain for compilers.

You encode precedence by layering the grammar: lower-precedence operators appear in rules higher up, higher-precedence ones in rules further down, so multiplication binds tighter than addition because it sits closer to the operands. The grammar's structure forces the right grouping.

Associativity comes from how you recurse. Left recursion (Expr -> Expr + Term) gives left associativity, so a - b - c parses as (a - b) - c. Right recursion gives right associativity, which you want for things like exponentiation or assignment. Parser generators also let you declare precedence and associativity directly to resolve conflicts.

Data-flow analysis computes facts about how values move through a program by propagating information around the control-flow graph until it stabilizes. Each block has transfer functions describing how it changes the facts, and you iterate, merging facts at join points, until nothing changes (a fixed point).

Classic instances are reaching definitions, live-variable analysis, and available expressions. The framework is a lattice of facts plus monotone transfer functions, which guarantees the iteration terminates. Forward analyses flow with control (reaching definitions); backward ones flow against it (liveness). It's the theory almost every global optimization stands on.

Static single assignment form rewrites the IR so every variable is assigned exactly once. Where a variable is reassigned, you rename each assignment (x1, x2, x3), and where control paths merge, you insert a phi function that picks the right version based on which path reached the block.

The single-assignment property makes many analyses and optimizations far simpler and faster, because each use has exactly one definition, so def-use chains are trivial. Constant propagation, dead code elimination, and value numbering all get cleaner in SSA. Modern back ends like LLVM use it as their main IR for exactly this reason.

Register allocation assigns the program's many variables to a small fixed set of physical registers, spilling to memory when there aren't enough. The standard model is graph coloring: build an interference graph where two variables that are live at the same time share an edge, then color it with as many colors as there are registers so no two adjacent nodes share one.

It's hard because optimal graph coloring is NP-complete, so real allocators use heuristics like Chaitin-Briggs, and because spilling has a real runtime cost you're trying to minimize. Choices about which variable to spill, and where, directly affect performance, which is why register allocation is one of the most studied back-end problems.

Instruction scheduling reorders instructions to run faster on the target processor without changing the program's meaning. It hides latency by moving independent work in front of a slow instruction (like a memory load), keeps the CPU's pipeline and functional units busy, and avoids stalls from data hazards.

It has to respect dependencies: a true data dependency (one instruction needs another's result) can't be reordered, and it interacts with register allocation, since aggressive scheduling can increase register pressure. On modern out-of-order CPUs the hardware reschedules too, so the compiler's scheduling matters most on in-order and specialized processors.

Loops are where programs spend most of their time, so they get special attention. Common transforms: loop-invariant code motion hoists computations that don't change out of the loop, strength reduction replaces expensive operations with cheaper ones (a multiply by the induction variable becomes an add), and induction-variable elimination removes redundant counters.

Others include loop unrolling (fewer iterations, more work per iteration, better scheduling), loop fusion and fission (merging or splitting loops for locality), and vectorization (using SIMD instructions to process several elements at once). Each is legal only when the compiler can prove it preserves the program's semantics, especially around aliasing and side effects.

An optimization is legal only if it preserves the program's observable behavior for every valid input. The compiler proves this with analysis: data-flow facts, alias analysis to know whether two pointers can touch the same memory, and dependency analysis to know what must happen before what. If it can't prove safety, it must not apply the transform.

The tricky cases are side effects, aliasing, and things the language leaves undefined or observable. Reordering across a memory operation that might alias, or across a call that might have side effects, can change results. Floating-point is a common trap: reassociating additions can change the rounded result, so it's illegal unless the language or a flag permits it.

Alias analysis determines whether two pointers or references can point to the same memory location. If the compiler can't rule out aliasing, it has to assume the worst: a write through one pointer might change what another reads, so it can't reorder or eliminate those memory operations.

That's why aliasing limits optimization. Precise alias analysis unlocks moving loads and stores, keeping values in registers, and vectorizing loops. Languages help it: C's restrict keyword and stronger type rules let the compiler assume two pointers don't alias, which is exactly why aliasing-heavy code often optimizes worse than value-heavy code.

A just-in-time compiler compiles code to native instructions at runtime instead of ahead of time. A typical engine starts by interpreting or running bytecode, profiles which methods run hot, then compiles those to optimized machine code, sometimes at several tiers of increasing optimization. Deoptimization lets it fall back if a speculative assumption breaks.

It's worth it when runtime information beats static knowledge: a JIT can inline based on which types actually show up, or specialize a hot loop for the values seen in practice, which an ahead-of-time compiler can't. The costs are warmup time and memory for the compiler itself, so JITs shine for long-running programs and less for short scripts.

A tracing garbage collector needs to find every live pointer, so the compiler emits metadata describing where pointers live at each safepoint: which registers and stack slots hold references. Without this, the collector couldn't distinguish a pointer from an integer that happens to look like one.

The compiler also inserts safepoints (places threads can pause for collection), may add write barriers so generational or concurrent collectors track pointer updates, and has to keep its optimizations honest so a value the collector needs isn't optimized into an untracked form. So GC isn't purely a runtime feature; the compiler and collector are co-designed.

Good compilers don't stop at the first error; they recover so they can report several problems in one run. The simplest strategy is panic-mode recovery: on an error, skip tokens until reaching a synchronizing token like a semicolon or closing brace, then resume parsing from there.

Other strategies include phrase-level recovery (locally inserting or deleting a token to repair the input) and error productions (grammar rules that match common mistakes so the parser can report them specifically). The goal is to report accurate, non-cascading errors: a bad recovery causes a flood of spurious errors after the real one, which is worse than stopping.

Bootstrapping is writing a compiler for a language in that same language. You face a chicken-and-egg problem: to compile the compiler, you first need a compiler. You solve it by writing an initial version in another language (or a subset), using it to compile the self-hosted compiler, then compiling the compiler with itself.

Once self-hosting, each new version is compiled by the previous one, which is a strong test: the compiler is its own large test program. The famous subtlety is the trusting-trust problem, a compromised compiler could inject a backdoor into every compiler it builds, including itself, without leaving a trace in the source.

An AST-walking interpreter runs the program by recursively traversing the abstract syntax tree and evaluating each node. It's simple to build and easy to understand, but slow: every execution re-walks the tree, chasing pointers and re-deciding node types each time.

A bytecode VM first compiles the AST to a flat sequence of compact instructions (bytecode), then runs a tight loop that dispatches on each opcode. It's faster because the instructions are linear and cache-friendly and the per-node overhead is gone. Most production dynamic languages compile to bytecode for this reason, then add a JIT on top for the hottest code.

Type inference lets the compiler figure out types you didn't write. The classic approach is Hindley-Milner, used in ML and Haskell: it assigns each expression a type variable, generates equations (constraints) from how expressions are used, then solves them with unification to find the most general type that fits.

Unification is the engine, it makes two type expressions equal by finding a substitution for their variables, or fails if they can't match, which is a type error. Local inference like var in Java or auto in C++ is a lighter version that infers a variable's type from its initializer without full constraint solving. Full inference saves typing but can produce confusing errors far from the actual mistake.

LLVM formalized the three-part split: language front ends lower source to a common intermediate representation (LLVM IR), a shared set of optimization passes transforms that IR, and target back ends turn it into machine code for each CPU. The IR is typed, in SSA form, and stable enough to be a real interface.

The payoff is reuse at scale. A new language only needs a front end that emits LLVM IR to inherit every optimization and every supported target; a new CPU only needs a back end to gain every language. That's why languages like Rust, Swift, and Clang's C and C++ all sit on LLVM instead of each building an optimizer and code generator from scratch.

Clarify first: what's the target (native, bytecode, transpile to another language), is it statically or dynamically typed, and how much optimization actually matters. Then lay out the front end: a hand-written lexer for tokens, a recursive descent parser producing an AST, and a semantic pass that builds a symbol table and type-checks, decorating the AST as it goes.

For the back end, lower the AST to a simple intermediate representation (three-address code or, if I want real optimization, an SSA IR), run a few well-chosen passes like constant folding and dead code elimination, then generate the target. If the target is native and I want the optimizer and multi-platform support for free, I'd emit LLVM IR rather than hand-roll code generation and register allocation. The structure that scores is clarify, front end, IR, optimize, target, each choice justified by the requirements I asked for.