cp-02 — Arithmetic Evaluator

The first real compiler. Read source text. Produce a number. Use every classical frontend technique compressed into ~400 lines of C++17.

Why This Lab

This is the foundational lab of the entire curriculum. Almost every concept in the rest of the course is a generalization of something built here:

Built here	Generalizes to (later)
Hand-written DFA lexer	Clang's lexer; Phase 3 bytecode-compiler lexer
Recursive-descent parser	Pratt parser (cp-03); Clang's parser
AST + Visitor pattern	Every IR in every later lab
Post-order tree-walk eval	Bytecode VM (cp-06); LLVM IRBuilder traversal
EBNF grammar	All MiniLang grammar throughout the curriculum
Operator precedence via grammar nesting	Pratt's "binding powers" (cp-03); MLIR op verifiers

Read First

CONCEPTS.md — the 8-part deep dive: lexers, parsers, AST, EBNF, precedence, associativity, the Visitor pattern.
references.md — Crafting Interpreters chapters, Clang lexer source, V8 parser source.
docs/analysis.md — design tradeoffs (DFA vs regex, recursive descent vs Pratt vs LR, Visitor vs std::variant).

Walk The Steps

steps/01-the-lexer.md — tokens, DFA, single-char lookahead.
steps/02-the-ast.md — node hierarchy, ownership, the Visitor pattern.
steps/03-recursive-descent-parser.md — grammar, precedence-via-nesting, associativity-via-recursion-direction.
steps/04-the-evaluator.md — post-order tree walk implemented as a Visitor returning double.
steps/05-repl-tests-and-cli.md — wire it into a usable tool with a test suite.
steps/06-extensions.md — extension exercises (right-associative ^, AST printer, source-location errors, constant folding).

Lab Docs

docs/execution.md — exact build/run/test commands.
docs/verification.md — the 19 unit tests + 4 manual REPL checks.
docs/observation.md — how to inspect the AST, debug parser failures, trace evaluation.
docs/broader-ideas.md — Pratt parsing preview, LR parsing, parser combinators, error recovery.

Code

src/cpp/ — full reference implementation (CMake project, ~450 lines of C++).

Build & Run (TL;DR)

cd src/cpp
cmake -B build && cmake --build build
./build/eval "1 + 2 * 3"      # 7
./build/eval                  # REPL
ctest --test-dir build        # 19 tests

Outcomes

You leave this lab able to:

Hand-write a lexer for an arbitrary regular language (no lex / flex).
Write a recursive-descent parser for any LL(1) grammar.
Design an AST with the Visitor pattern.
Explain why the grammar shape determines operator precedence and associativity.
Recognize what changes (and what doesn't) when you swap a tree-walker for a bytecode VM or LLVM backend in later labs.

Compilers & Parser Engineer