Section 1: From Characters to Trees

The front end is the part of a language implementation that turns text into structure. It is the only part that ever sees your source code, and it is the only part that can produce a good error message — because it is the only part that still knows where things were written.

This section covers Milestones M1 and M2. By the end you have a working calculator language with real values, real type errors, and error messages that point at the exact characters that were wrong.

$ echo '10 + 20 * 3' > t.ember && ember run t.ember
70

That looks small. Getting there requires a scanner, a grammar, a precedence-correct parser, a typed tree, a span discipline, and a value representation you can live with for the next fifteen weeks. Three of those five decisions are hard to change later.

What You Build

The Layer You Are Building

   "10 + 20 * 3"                                          ← you never see this again
        │
        ▼
  ┌─────────────────────────────────────────────────────────────┐
  │  LEXER                                       lexer.rs       │
  │  a loop over bytes with one character of lookahead          │
  │  decides: is this a number, a name, an operator, a comment? │
  │  ATTACHES A SPAN TO EVERYTHING                              │
  └─────────────────────────────────────────────────────────────┘
        │  [Int(10)@0..2, Plus@3..4, Int(20)@5..7, Star@8..9, Int(3)@10..11, Eof]
        ▼
  ┌─────────────────────────────────────────────────────────────┐
  │  PARSER                                     parser.rs       │
  │  statements: recursive descent (one fn per production)      │
  │  expressions: Pratt / precedence climbing (one loop,        │
  │               a binding-power table, and recursion)         │
  │  PRECEDENCE BECOMES TREE SHAPE — this is the whole job      │
  └─────────────────────────────────────────────────────────────┘
        │  Binary(Add, Int(10), Binary(Mul, Int(20), Int(3)))
        ▼
  ┌─────────────────────────────────────────────────────────────┐
  │  EVALUATOR                              interp/eval.rs      │
  │  a recursive match over the tree. Post-order: children      │
  │  first, then the node. That IS the evaluation order.        │
  └─────────────────────────────────────────────────────────────┘
        │
        ▼
     Value::Integer(70)

Note: Notice what the parser does to precedence. 10 + 20 * 3 and (10 + 20) * 3 produce different trees, and once the tree exists there is no precedence left to get wrong — the evaluator just walks it. Precedence is a parsing problem that stops existing after parsing. That is the single most useful thing to understand about front ends.

The Concepts, and Where Each Is Treated

The Labs

Crates: What You Are Allowed to Use, and When

The rule is not asceticism. It is that you cannot evaluate a library for a job you have never done. After Lab 2 you will have opinions about parser libraries. Before it you would only have preferences.

Deliverables

• ember tokens, ember ast, and ember run all work on 10 + 20 * 3.
• 2 ^ 3 ^ 2 evaluates to 512 and -2 ^ 2 to -4, each with a test naming the rule.
• Every Token and every Expr/Stmt node carries a Span, checked by a test that walks the tree and asserts no node has Span::EMPTY.
• A lexer error, a parser error, and a type error each render as: message, source line, caret under the exact span.
• Value is defined, Copy, and size_of::<Value>() is asserted in a test.
• The integer/float coercion table is implemented and tested for every operator/type pair.
• tests/golden/ exists with at least 12 programs and expected outputs.
• docs/learning/01-lexer.md, 02-parser.md, 03-ast.md written.
• docs/adr/ADR-004-value-representation.md and ADR-005-integer-float-split.md written.

Common Mistakes in This Section

How to Verify Success

# 1. The pipeline, one representation at a time.
echo '10 + 20 * 3' > /tmp/t.ember
ember tokens /tmp/t.ember     # 6 tokens, spans contiguous and covering the input
ember ast    /tmp/t.ember     # Add at the root, Mul as its RIGHT child
ember run    /tmp/t.ember     # 70

# 2. Precedence, against the reference implementation.
for e in '10 + 20 * 3' '(10 + 20) * 3' '2 ^ 3 ^ 2' '-2 ^ 2' '1 - 2 - 3' '7 // 2' '7 % -3'; do
  printf '%-16s ember=%-8s lua=%s\n' "$e" \
    "$(ember run -e "return $e")" "$(lua -e "print($e)")"
done
# Every row must match. If one does not, YOU decide which is right and write it
# down in appendix/lua-differences.md — but you must notice first.

# 3. Diagnostics point at the right characters.
ember run -e 'return 1 + * 2'     # caret under the '*'
ember run -e 'return "x" * 2'     # caret under the '"x"', not the whole expression
ember run -e 'return 0x'          # lexer error, caret under '0x'

# 4. No panics.
ember tokens /dev/urandom 2>/dev/null | head -1   # an error, not a crash

Section Profile: What a Section 1 Graduate Can Do

• Write a hand-rolled lexer for any small language in an afternoon, with correct maximal munch and spans on every token.
• Explain precedence and associativity in terms of tree shape, and implement either with a one-line change in a Pratt loop.
• Read the grammar section of a language reference manual and predict what its parser looks like.
• Design an AST that a later compiler pass can consume without re-deriving information.
• Produce a diagnostic with a source line and a caret, and explain why it required a decision made in the first hour of the project.
• State the four common value representations and defend the choice of one.

Next: Lexical Analysis.