Compilers & Languages Interview Questions and Answers

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.