Follow one expression to its result
An expression calculator provides a small enough system to understand from beginning to end. Enter 12 + 3 * (4 - 1) and first determine the intended result: 21. A correct implementation must recognize complete numbers, group operators according to the language rules, and compute from that grouping. These are three different responsibilities. Scanning turns characters into tokens. Parsing turns tokens into a structural representation. Evaluation turns that representation into a value. Keeping the expected result beside the intermediate forms helps locate a mistake instead of treating every wrong answer as an arithmetic problem. Our teaching language contains integers, identifiers, four arithmetic operators and parentheses. It deliberately leaves functions, strings and declarations outside this first pipeline. The aim is an inspectable implementation, rather than a miniature copy of every feature in a production language.
Preserve positions while scanning
The first number occupies two characters but represents one integer literal. A scanner advances across the complete digit sequence and creates a token containing a kind, its original spelling and its starting position. In our example that is NUM, 12 and position zero. Whitespace is ignored as a separator, but positions still refer to the original source. Renumbering after removing spaces would make diagnostics point to the wrong character. Decide identifier rules explicitly as well: a12 can be one name, while 12a becomes a number followed by a name and is rejected later as an incomplete expression. The accompanying implementation accepts ASCII digits and identifier characters. Unicode identifiers and comments require additional rules; they are not accidental extensions supplied by whatever character predicate happens to be available in the implementation language.
| Stage | Relationship in this example |
|---|---|
| Input | 12 + 3 * (4 - 1) |
| Structure | Addition has multiplication on its right; subtraction is nested within it |
| Inner evaluation | 4 - 1 = 3 |
| Final result | 12 + 3 * 3 = 21 |
Encode precedence in grammar levels
A flat token sequence does not decide how 1 + 2 * 3 is grouped. Define an expression as a term followed by zero or more additions or subtractions. Define a term as an atom followed by zero or more multiplications or divisions. An atom is a number, a name or a parenthesized expression. Because a term completes its multiplication work before returning to the expression level, multiplication becomes a child inside the addition tree. Draw the trees for 1 + 2 * 3 and (1 + 2) * 3 before reading any parser code. The difference is a language contract, not an optimization chosen after evaluating the input. Adding an operator therefore requires deciding its grammar level as well as recognizing its spelling. Unary negation is intentionally absent from this small grammar, so a leading minus is rejected rather than silently interpreted using a host-language rule.
Make associativity observable
Subtraction exposes grouping mistakes that addition can hide. Grouping 8 - 3 - 1 from the left produces 4; grouping it from the right produces 6. The parser starts with the first term in a variable called left. Each following subtraction replaces left with a node whose children are the previous tree and the next term. That loop expresses left associativity directly. Recursively reading an entire expression on the right instead can accidentally create the other tree. Similarly, a directly left-recursive rule is unsuitable for this simple recursive-descent implementation: it can call itself before consuming any token. We use a repeated sequence at each precedence level instead. Verify both progress through the input and the returned tree. The presence of recursion alone establishes neither the intended grouping nor termination on a given grammar.
Keep the structure needed by later stages
An abstract syntax tree records operations and operands rather than every visible source character. Parentheses determine grouping, but do not need separate nodes once that grouping is represented. The root of our running expression is addition, with the literal 12 on the left and a multiplication on the right. The subtraction of 4 and 1 is a child of that multiplication. Constructing this tree does not establish that every name has a value. The expression x + 1 is syntactically valid even if evaluating it later fails because x is missing from the environment. Classes and tuples are both reasonable teaching representations if node kinds and child positions are consistent. A formatter that must preserve comments or original parentheses has a different representation requirement; this evaluator is allowed to discard those surface details.
Distinguish failure stages
Compare three failing inputs. In 12 + @, the scanner cannot recognize the final character. In 12 +, the parser reaches the end while expecting an operand. In 12 / 0, scanning and parsing can succeed, but evaluation rejects the zero divisor. Calling all three cases an input error loses the information needed to repair them. An explicit EOF token gives the end of the source a position just like any other token. Require the parser to consume that token after building one expression, otherwise it might accept the first number in 1 2 and silently ignore the rest. Production parsers may recover and report several errors, but this teaching parser stops at the first clear failure. Omitting recovery does not justify accepting an unconsumed suffix or inventing a missing operand.
Test contracts at each boundary
A scanner test should compare spelling and source positions as well as token kinds. A parser test should compare tree structure, and an evaluator test should compare values or expected exceptions. These tests answer different questions. If the running example does not produce 21, inspect the earliest boundary whose output differs from its contract. Correct tokens with a wrong tree suggest a grouping problem; a correct tree with a wrong result suggests an evaluation rule or environment problem. Include empty input, empty parentheses, unknown characters, missing closing parentheses and leftover tokens. Short examples are sufficient to expose these distinctions. The implementation has ordinary recursion and resource limits and is not presented as a hardened public parsing service. Save the Python version and the exact teaching code so that later changes to the grammar can be compared against a reproducible baseline.
Adding negation changes a defined boundary
Before extending the language with -12, decide whether the sign belongs to a numeric token or to a unary grammar rule. Binary subtraction in 1-2 and unary negation in -2 need distinct structural treatment. With a lexer that already emits MINUS, the parser can introduce a unary production. The current tiny language deliberately has no unary operation. Do not describe it as supporting negative literals merely because Python integers can be negative. Update the specification, token sequence, tree, and evaluation tests together.
Change a condition and explain it
For a final exercise, remove only the parentheses from 12 + 3 * (4 - 1). Predict the tokens, tree and value before running anything. The parentheses disappear from the token sequence; multiplication groups 3 and 4; addition and subtraction then associate to the left, producing 23 rather than 21. Now change only the amount of whitespace in the original expression. Token positions change, but the tree and value do not. Together these cases distinguish a surface change from a semantic one. Finally draw the tree for 8 - 3 - 1 and identify the inner subtraction on its left branch. Explaining which rule produces 4 is more useful than memorizing that answer. Continue with the scanner experiment for implementation details, or return to the parser experiment whenever a grouping rule is unclear.
Distinguish character steps, token steps, and tree steps
The browser tokenizer demonstration makes the unit of a step explicit. Consuming one character, emitting one token, and appending one tree node are different events. While reading the start tag in <p>A</p>, the tag name may already be p even though no complete start-tag token exists yet. Keep the input position, partial token, and emitted tokens separately. The tree builder should consume only emitted tokens. Pause, resume, and rewind must restore those structures to one consistent point. That makes the resulting tree explainable and replayable rather than merely showing an animation over a final answer.
Do not transfer expression-language rules to HTML unchanged
Whitespace can be skipped in this expression language, but HTML text whitespace cannot simply be discarded: the space in Hello world is document content. Likewise, this parser rejects extra tokens, while standard HTML parsing includes recovery rules for omitted elements and malformed nesting. The reusable part is the engineering method: define input, state, output, and tests. The grammar and semantics are language-specific. When extending a parser to another language, list the reusable framework separately from the rules that must change. Report unsupported input explicitly instead of silently accepting it as if the language were fully implemented.