Compilers & Languages Interview Questions and Answers

A compiler translates the whole program from source into machine code or an intermediate form before it runs, producing an executable. Errors are reported after the whole translation, and the resulting program runs without the compiler present and typically fast, because optimisation happens ahead of time.

An interpreter executes the source directly, reading and evaluating one statement or expression at a time. It starts instantly and gives immediate feedback, which is great for scripting and REPLs, but execution is slower because it re-analyses code as it goes.

compiler:    source -> compiler -> machine code -> run
interpreter: source -> interpreter -> output

The line is blurry. Java compiles to bytecode and a JVM interprets or just-in-time compiles it. JavaScript engines parse to bytecode and optimise hot paths at runtime. Python compiles to bytecode then interprets it. Most modern languages mix both strategies for startup speed plus peak performance.

A typical compiler pipeline has a front end, a middle end and a back end.

• Lexical analysis: turn characters into tokens.
• Syntax analysis: build a parse tree from the token stream using the grammar.
• Semantic analysis: check types, scopes and declarations, and build a symbol table.
• Intermediate representation: lower the tree to a form such as three-address code or SSA.
• Optimisation: improve the IR without changing meaning, for example constant folding and dead code elimination.
• Code generation: emit target machine code or bytecode, including register allocation and instruction selection.

chars -> lexer -> tokens -> parser -> AST -> semantics
      -> IR -> optimiser -> codegen -> machine code

Front ends are language-specific, back ends are target-specific, and the shared IR is what lets a compiler support many languages and many CPUs without an explosion of combinations.

An abstract syntax tree, AST, is a tree representation of a program's structure. The parser produces it after checking that the token stream matches the grammar. It is called abstract because it omits details that do not matter for later processing, such as parentheses and separators.

For the expression 1 + 2 * 3, the AST captures precedence directly, with + at the root and * below it:

      +
     / \
    1   *
       / \
      2   3

Nodes represent constructs such as literals, binary operators, function declarations and statements. ASTs are used by compilers for semantic analysis, optimisation and code generation, and by linters, formatters, transpilers and refactoring tools. The concrete parse tree usually keeps more detail and is closer to the grammar, while the AST is the practical working form. Traversal is commonly done with the visitor pattern.

Parsing turns tokens into a parse tree. Two broad families exist.

Top-down parsers start at the root and predict productions. Recursive descent, and its table-driven form LL(1), is easy to write by hand and gives good errors. Left recursion must be eliminated, and the grammar must be factored to avoid backtracking. Many production compilers use hand-written recursive descent.

Bottom-up parsers start at the leaves and reduce to the start symbol. LR variants, SLR, LALR and canonical LR, are driven by tables and handle a larger class of grammars, including left recursion, without backtracking. LALR is what tools like yacc and Bison generate.

LL: root -> leaves, predictive
LR: leaves -> root, shift/reduce

LL is simpler to understand and debug; LR is more powerful and efficient for complex grammars but its errors are harder to explain. Parser generators trade control for speed of development.

Static typing checks types at compile time. Every variable and expression has a type known before the program runs, so many errors are caught early, tooling can autocomplete and refactor safely, and the compiler can generate efficient code. Java, C++, Go, Rust and TypeScript are statically typed. Inference reduces the annotation burden, as in var x = 42.

Dynamic typing checks types at runtime. A variable can hold any value, and an operation's validity depends on the actual object. Python, Ruby and JavaScript are dynamically typed. This enables fast prototyping, duck typing and metaprogramming, but type errors surface as runtime exceptions and require thorough tests.

def add(a, b): return a + b   # resolves at runtime

The distinction is orthogonal to strong versus weak typing: JavaScript is dynamically and weakly typed, coercing values, while Python is dynamically and strongly typed. Gradual typing, such as Python type hints or TypeScript, lets teams add static checks where they pay off.

After parsing, semantic analysis checks that the program is meaningful, not merely grammatically valid. It enforces rules the grammar cannot express.

Typical jobs:

• Build a symbol table mapping names to declarations, scopes and types.
• Resolve identifiers, so each use points to the right declaration.
• Type check expressions and assignments, applying implicit conversions where defined, and report mismatches.
• Check arity of calls, return types and control flow such as break outside a loop.
• Enforce access rules, for example private members.
• Detect unreachable code and uninitialised variables.

scope stack: function -> block -> for
symbol: { name: "x", type: int, scope: 2 }

The symbol table is usually a stack of hash maps, pushed on entering a scope and popped on leaving, which naturally implements shadowing. Semantic analysis produces a typed, annotated tree that later phases trust, and it is where most friendly compiler error messages originate.

Optimisation improves the intermediate representation while preserving observable behaviour. Common examples:

• Constant folding and propagation: compute 2 * 3 at compile time and substitute known constants.
• Dead code elimination: remove computations whose results are never used.
• Common subexpression elimination: reuse a repeated computation.
• Inlining: replace a call with the callee's body to remove call overhead and expose more optimisation.
• Loop-invariant code motion: hoist computations that do not change across iterations.
• Strength reduction: replace expensive operations, such as multiplying by a power of two with a shift.
• Register allocation: keep hot values in registers.

x = 4 * 8           ->  x = 32
if (false) { ... }  ->  removed

Optimisations rely on analyses such as use-def chains, dominance and alias analysis. Correctness is paramount: an optimisation must never change output, which is why alias analysis for pointers is hard and some transformations are conservative.

A lexer converts a character stream into tokens. A hand-written tokenizer scans one character at a time and skips whitespace.

def tokenize(src):
    tokens, i = [], 0
    while i < len(src):
        c = src[i]
        if c.isspace():
            i += 1
        elif c.isdigit():
            j = i
            while j < len(src) and src[j].isdigit():
                j += 1
            tokens.append(("NUM", int(src[i:j])))
            i = j
        elif c.isalpha():
            j = i
            while j < len(src) and src[j].isalnum():
                j += 1
            tokens.append(("IDENT", src[i:j]))
            i = j
        elif c in "+-*/()":
            tokens.append((c, c))
            i += 1
        else:
            raise SyntaxError(f"unexpected {c!r} at {i}")
    tokens.append(("EOF", None))
    return tokens

Real lexers use maximal munch, precedence for multi-character operators such as == over =, and a DFA or a generator like flex. Track line and column numbers so later phases can report precise errors.

Register allocation assigns the many virtual registers produced by the compiler to the small, fixed set of physical CPU registers. It happens late, after instruction selection, and is critical because memory accesses dominate runtime.

The classic formulation builds an interference graph: two virtual registers interfere if their live ranges overlap, and they cannot share a physical register. The problem reduces to graph colouring, with the number of colours equal to the number of available registers.

a: def ... use
b:      def ... use   (overlap with a -> edge a-b)

Since graph colouring is NP-hard, compilers use heuristics. Chaitin-style allocation iteratively removes nodes with fewer than k neighbours; if none remain, a node is spilled. Spilling stores a value to memory and reloads it, adding code but making the graph colourable. Linear scan allocation is faster and used in JITs and debug builds. Other considerations include calling conventions, callee-saved registers and coalescing to remove copies.

Ahead-of-time, AOT, compilation translates the program to machine code before it runs, producing a native binary. Startup is fast, memory overhead is predictable and there is no runtime compiler. It cannot adapt to runtime data, and cross-compilation and dynamic loading are more awkward. C, C++, Rust, Go and Swift are typically AOT.

Just-in-time, JIT, compilation waits until the program runs, then compiles hot methods to machine code inside the process. The compiler can use real profiling data: inlining monomorphic call sites, speculating on types and deoptimising if assumptions break. Peak throughput can exceed AOT, at the cost of warmup time, memory and complexity. Java's HotSpot, the .NET CLR and JavaScript V8 use JIT, often tiered with a fast baseline compiler plus an optimising tier.

AOT: source -> native at build time
JIT: bytecode -> profile -> compile at runtime

Hybrids such as GraalVM native image and Android's ART combine AOT startup with JIT or profile-guided speed.