Compiler Foundations: language model, phases, and contract design

This course is built in intentionally small, composable stages. A compiler can only be reliable when each stage has a strict contract and deterministic outputs.

Why this module exists

Real compilers are not “one big function.” They are a sequence of constrained transforms:

• tokens constrain syntax shape,
• AST gives structure,
• semantics checks meaning,
• lowering changes representation,
• backend emits executable artifacts.

The more explicit the contracts between stages, the easier bugs become local.

Phase contracts and what each stage owns

1) Lexing

• owns source location and token classification
• does not build meaning or scope
• should not interpret identifier roles beyond keyword mapping

2) Parsing

• owns syntactic structure only
• creates AST node kinds, nesting, and operator topology
• should not enforce runtime or semantic correctness

3) Semantics

• owns symbol environment and compatibility checks
• resolves declarations and references
• validates control-flow constraints and type contracts

4) Lowering / IR

• owns representation changes (AST -> bytecode-friendly form)
• may be shape-preserving or aggressively normalizing

5) Codegen & runtime

• owns execution model
• executes semantics assumed valid by earlier phases

A recurring bug pattern is carrying a phase concern backwards (e.g., semantic restrictions in lexer).

Invariant mindset

Each interface should preserve at least:

• deterministic order,
• no silent shape mutation,
• clear source location data,
• explicit error surfaces.

That keeps testing easy:

• unit tests can assert tokens,
• parser tests can assert tree shape,
• semantic tests can assert error text,
• VM tests can assert runtime behavior.

Grammar, precedence, and associativity as phase boundary

Grammar is not just “documentation.” It is the compiler’s syntax contract.

• expr -> term (+/- term)*
• term -> factor (*// / factor)*

This naturally produces precedence without precedence-climbing hacks.

Associativity is also part of grammar shape:

• left-recursive chains in parser functions produce left-associative trees for infix operators.

Later stages rely on this tree shape.

AST boundaries

An AST is a semantic skeleton, not trivia:

• it keeps structure and intent,
• it drops incidental formatting,
• it still keeps enough metadata (source locations, names, literal values) for diagnostics.

The AST should make later phases simpler, not harder.

Error quality as pipeline architecture

Error quality is not style—it's engineering leverage.

A useful error has:

• location,
• expected vs actual,
• a narrow scope so the user can fix one thing at a time.

If upstream stages emit good errors, downstream stages fail less often and run cleaner.

Determinism and reproducibility

A stable compiler should be deterministic:

• same source input -> same token stream,
• same token stream -> same AST,
• same AST -> same diagnostics,
• same diagnostics -> same artifact.

If any stage includes hidden timing/symbol dependence, debugging becomes probabilistic.

Deep practice checkpoints (almost solved)

1) Define stage ownership

For expression let x = 1 + 2;, identify which stage owns each step:

• tokenization,
• precedence grouping,
• declaration introduction,
• final VM value.

2) Contract leakage detection

Which of these belongs to parsing, not lexing?

• interpreting if as control-flow
• validating matching braces after tokenization

Expected: parsing.

3) Determinism test

Run the same valid source twice through the full pipeline.

Expected: same token stream, AST hash, and compiled artifact.

4) Error ownership

Given a malformed source containing both syntax and semantic mistakes, explain why parser error should stop before semantic checks.

5) AST simplification

Why does parser usually keep AST, not raw token list, for semantic analysis?

6) Source span precision

Why must Line/Col be preserved through parse and semantics?

7) Grammar precedence check

Given 1 + 2 * 3, what AST root is expected and why?

Expected: + root, right child *.

8) Contracted transitions

What should phase 2 (parse) never do?

• type inference,
• symbol import/export resolution,
• runtime execution.

9) What changed by v6 parsing types?

Explain the shift from syntax-only parser concerns to parse-time type syntax validation.

10) End-to-end failure expectation

For source let x = ;, which stage is responsible for the first returned error? Expected: parsing.