Lexer & Parser

A lexer and parser turn source text into structure that later compiler stages can use. For 12 + 3 * 4, the lexer emits five tokens in source order. The parser groups them as 12 + (3 * 4), producing 24 instead of the 60 produced by a flat left-to-right loop.

Think of the lexer as a clerk cutting a sentence into labeled tiles. The parser stacks those tiles into a model. The clerk preserves order and labels; the stacker supplies hierarchy. Blaming the lexer for broken precedence is blaming the tile cutter for a crooked staircase.

How a lexer and parser work

The lexer scans left to right. A digit starts a numeric lexeme, and adjacent digits extend the same lexeme, so 12 becomes one NUMBER(12) token rather than NUMBER(1) followed by NUMBER(2). +, *, (, and ) each become one token. Whitespace advances the scanner but emits nothing. An unknown character such as @ stops the lexer because no token kind accepts it.

The parser sees token kinds, not spaces or raw character offsets. This lesson uses three recursive-descent rules. primary() accepts NUMBER or a parenthesized expression. term() owns the STAR loop. expr() owns the PLUS loop. That split creates precedence: a term() must finish every multiplication it owns before it can return to the waiting expr() call.

A number token creates an AST leaf. Consuming an operator does not create a parent immediately. The current rule holds its left subtree and operator while a child call parses the right side; only then can it reduce both sides into Mul or Add. Parentheses never become AST nodes. They redirect parser control flow, then disappear because the resulting tree already records their effect.

Lexer and parser step by step

The default source is 12 + 3 * 4.

1. The lexer starts on 1, extends the same span over 2, then emits NUMBER(12). The two digits are one token.
2. It skips the first space. No placeholder is added to the token tape.
3. It emits PLUS(+), skips another space, and emits NUMBER(3).
4. After the third space it emits STAR(*); after the fourth it emits NUMBER(4). Lexing ends with five tokens and a separate EOF marker.
5. Stop at the completed tape: PLUS still appears before STAR. That order has not decided precedence because the parser has not built hierarchy yet.
6. Parsing begins with expr(), which calls term(), which calls primary(). primary() consumes NUMBER(12) and creates the leaf 12.
7. term() sees PLUS, not STAR, so it returns 12. The outer expr() consumes PLUS and holds left = 12 while it asks another term() for the right side.
8. That right-hand term() consumes NUMBER(3), sees STAR, holds left = 3, and calls primary() again for NUMBER(4).
9. term() reduces 3 * 4 into Mul. Only after that subtree returns can the waiting expr() reduce 12 + Mul into an Add root.
10. Every token has been consumed. Evaluating the completed tree gives 12 + (3 * 4) = 24.

The token tape never changes order. The useful action is in the parser-call panel: expr waits while term finishes STAR. The AST parents arrive in the same order as the reductions, first Mul, then Add.

How parser control flow becomes AST hierarchy

The source writes + before *, and the token tape faithfully preserves that order. Neither fact chooses which operation groups first. The grammar does. expr() delegates each operand of PLUS to term(), and term() finishes its STAR work before returning. The parser therefore creates Add(12, Mul(3, 4)).

Put both operators in one left-to-right loop and the same tape creates Mul(Add(12, 3), 4). That tree evaluates to 60. The operators did not change; parser control flow did. The AST is the receipt, not the cashier: it records the grouping decision so code generation, optimization, and evaluation no longer need to consult token precedence.

Parentheses use the same parser, not a special precedence mode. For (12 + 3) * 4, primary() recursively calls expr() inside the parentheses. The inner Add completes before the outer term() builds Mul, so 60 is now the correct result rather than evidence of a broken flat loop.

Lexer and parser time and space complexity

Let c be the number of source characters, t the number of emitted tokens, and d the maximum parenthesis nesting depth.

Those bounds belong to this small deterministic grammar. They are not a promise that every parsing strategy or arbitrary grammar runs in linear time.

A note on simplification

This lesson accepts non-negative integers, +, *, and one level of parentheses. It omits identifiers, unary operators, subtraction, division, strings, comments, source locations, type checking, and error recovery. Production parsers usually report several useful diagnostics instead of stopping at the first bad token.

The same architecture appears in small query languages, config expressions, template engines, and domain-specific languages as well as full compilers and linters. Adding an operator at an existing precedence level usually extends one loop; adding a new precedence level usually adds another parser rule and another call boundary. That is the practical reason to keep rule ownership explicit.

Lexer and parser edge cases

• Empty or whitespace-only input lexes successfully to an empty tape, then the parser rejects EOF because a primary expression must begin.
• 12+3*4 produces the same tokens and AST as the spaced default. Whitespace belongs to lexing, not parsing.
• 12 + @ 4 stops in the lexer. No token is invented for @, and parsing never starts.
• 12 + * 4 is lexically valid but syntactically invalid. primary() rejects STAR where a number or ( must begin.
• (12 + 3 * 4 builds a valid inner subtree, then fails when take("RPAREN") reaches EOF.

Lexer and parser common mistakes

• Emitting one number token per digit. Splitting 12 into adjacent NUMBER(1) and NUMBER(2) leaves the parser with an unexplained second operand.
• Treating tokenization as proof of valid syntax. A complete tape can still violate the grammar, as 12 + * 4 does.
• Building an operator node as soon as the operator token is consumed. The right subtree does not exist yet; the rule must hold the operator and wait.
• Putting + and * in one parser loop. That changes the grammar to left-to-right evaluation and turns the default result from 24 into 60.
• Saying that the AST creates precedence. Parser control flow chooses the grouping; the AST records the choice.
• Keeping parentheses as AST nodes. Parentheses control parsing, and the resulting hierarchy already preserves their effect.