Lab 1: The Lexer (Milestone 1)

Background

You will build src/token.rs, src/lexer.rs, and enough of src/error.rs and src/span.rs to report a lexical error with a caret under the offending characters. At the end, ember tokens prints the token stream for any file.

This is the only component in the entire runtime that sees raw bytes. Everything downstream trusts its classification and inherits its spans.

Why This Lab Matters

Spans start here or they never start. Every diagnostic in Section 6 and every stack trace in Section 5 traces back to the Span field you add in Step 1. Skipping it is the single most expensive shortcut available in this curriculum.
It is the first place the runtime meets hostile input. By Section 5, this code runs on scripts you did not write. unwrap() here is a denial-of-service bug there.
It is small enough to get completely right, which makes it the right place to establish the standards — Result everywhere, error messages that name the construct, a test per rule — that the rest of the project inherits.

Prerequisites

Lexical Analysis read.
Spans and Source Maps read, at least Concept 1.
The crate scaffolded per The Rust Crate Design, with src/span.rs and src/error.rs already compiling.

Predict First

Write these down with a confidence level before you start.

size_of::<Token>() with TokenKind::Ident(String) — what do you expect, and why is it not 16?
Feed the lexer 10..20. How many tokens, and what are they? (This one catches most people.)
Feed it --[[ comment with no closing bracket. What should happen?
Feed it 9223372036854775808 (that is i64::MAX + 1). Integer or float?
Feed it 0xFFFFFFFFFFFFFFFF. Integer or float, and what value?
"hello with no closing quote — what is the span of the error?

Step 1: Tokens Carry Spans

Concept. Classification and position, together, from the first line of code.

Goal. Define TokenKind and Token, and nothing else.

Observable behavior. cargo test compiles. Nothing runs yet.

#![allow(unused)]
fn main() {
// src/token.rs
use crate::span::Span;

#[derive(Clone, Debug, PartialEq)]
pub enum TokenKind {
    Int(i64), Float(f64), Str(String), Ident(String),

    And, Break, Do, Else, Elseif, End, False, For, Function, If, In,
    Local, Nil, Not, Or, Repeat, Return, Then, True, Until, While,

    Plus, Minus, Star, Slash, DoubleSlash, Percent, Caret, Hash,
    Eq, NotEq, LessEq, GreaterEq, Less, Greater, Assign,
    LParen, RParen, LBrace, RBrace, LBracket, RBracket,
    DoubleColon, Semi, Colon, Comma, Dot, DotDot, Ellipsis,

    Eof,
}

#[derive(Clone, Debug, PartialEq)]
pub struct Token { pub kind: TokenKind, pub span: Span }

/// Human-readable name for error messages. `expected ',', found 'end'` is
/// readable; `expected Comma, found End` is a compiler talking to itself.
pub fn describe(k: &TokenKind) -> String {
    use TokenKind::*;
    match k {
        Int(_) => "a number".into(), Float(_) => "a number".into(),
        Str(_) => "a string".into(), Ident(n) => format!("'{n}'"),
        Eof => "end of file".into(),
        Plus => "'+'".into(), DotDot => "'..'".into(),
        // ... one arm each. Yes, it is tedious. It is also every error message
        // your language will ever print, so write them once and well.
        _ => format!("{k:?}"),
    }
}
}

Line-by-line, the parts that matter. Token derives PartialEq so tests can compare token streams directly. It does not derive Copy — String payloads forbid it — which is a cost the concept chapter accepted deliberately. describe exists now, not later, because a describe added in Lab 24 will be inconsistent with the messages already written by then.

Checkpoint question. Why is Eof a variant rather than the parser checking pos >= len?

Step 2: The Scanner Skeleton and Trivia

Concept. One pass, one character of lookahead, trivia removed in one place.

Goal. Lexer::next_token returns Eof for empty input and skips whitespace and comments.

#![allow(unused)]
fn main() {
// src/lexer.rs
use crate::{error::{EmberError, ErrorKind, Result}, span::Span, token::*};

pub struct Lexer<'a> { src: &'a str, bytes: &'a [u8], pos: usize }

impl<'a> Lexer<'a> {
    pub fn new(src: &'a str) -> Self {
        // Strip a UTF-8 BOM: it is not whitespace and it is not an identifier.
        let src = src.strip_prefix('\u{feff}').unwrap_or(src);
        Lexer { src, bytes: src.as_bytes(), pos: 0 }
    }

    fn peek(&self) -> u8 { *self.bytes.get(self.pos).unwrap_or(&0) }
    fn peek2(&self) -> u8 { *self.bytes.get(self.pos + 1).unwrap_or(&0) }
    fn bump(&mut self) -> u8 { let b = self.peek(); self.pos += 1; b }
    fn eat(&mut self, c: u8) -> bool {
        if self.peek() == c { self.pos += 1; true } else { false }
    }
    fn at_end(&self) -> bool { self.pos >= self.bytes.len() }

    fn tok(&self, kind: TokenKind, start: u32) -> Token {
        Token { kind, span: Span::new(start, self.pos as u32) }
    }
    fn err_at(&self, start: u32, msg: impl Into<String>) -> EmberError {
        EmberError { kind: ErrorKind::Lex, message: msg.into(),
                     span: Some(Span::new(start, (self.pos as u32).max(start + 1))),
                     traceback: Vec::new() }
    }

    /// Whitespace and comments. The ONLY place either is handled.
    fn skip_trivia(&mut self) -> Result<()> {
        loop {
            match self.peek() {
                b' ' | b'\t' | b'\r' | b'\n' => { self.pos += 1; }
                b'-' if self.peek2() == b'-' => {
                    let start = self.pos as u32;
                    self.pos += 2;
                    if self.peek() == b'[' && self.peek2() == b'[' {
                        self.pos += 2;
                        loop {
                            if self.at_end() {
                                return Err(self.err_at(start, "unterminated block comment"));
                            }
                            if self.bump() == b']' && self.eat(b']') { break; }
                        }
                    } else {
                        while !self.at_end() && self.peek() != b'\n' { self.pos += 1; }
                    }
                }
                _ => return Ok(()),
            }
        }
    }
}
}

The parts that matter.

skip_trivia returns Result because an unterminated block comment is a lexical error with a span — pointing at the --[[ that opened it, not at EOF. That is why start is captured before the += 2.
The block-comment loop checks at_end() before bump(). Reverse them and an unterminated comment loops until pos overflows. Every scanner loop in this file needs an EOF exit; this is the first of four.
The BOM strip in new shifts nothing: strip_prefix returns a subslice, and all offsets are relative to the stripped string. Document that the reported offsets exclude the BOM, or a caret in a BOM'd file is off by three.

Checkpoint question. Why is comment handling here rather than in the b'-' arm of the operator match?

Step 3: Operators and Maximal Munch

Concept. Longest match wins.

Goal. Every operator and delimiter lexes, with the overlapping ones taking their longest form.

Write next_token's operator match exactly as in the concept chapter. Then write this test first — it is the specification:

#![allow(unused)]
fn main() {
#[test]
fn maximal_munch_on_every_overlapping_operator() {
    // Each pair is (source, expected token count). The SHORT form must not be
    // produced when the LONG form matches.
    let cases: &[(&str, &[TokenKind])] = &[
        ("..",  &[TokenKind::DotDot]),
        ("...", &[TokenKind::Ellipsis]),
        (". .", &[TokenKind::Dot, TokenKind::Dot]),
        ("==",  &[TokenKind::Eq]),
        ("= =", &[TokenKind::Assign, TokenKind::Assign]),
        ("~=",  &[TokenKind::NotEq]),
        ("<=",  &[TokenKind::LessEq]),
        (">=",  &[TokenKind::GreaterEq]),
        ("//",  &[TokenKind::DoubleSlash]),
        ("/ /", &[TokenKind::Slash, TokenKind::Slash]),
        ("::",  &[TokenKind::DoubleColon]),
    ];
    for (src, expect) in cases {
        let toks = tokenize(src).expect(src);
        let kinds: Vec<_> = toks[..toks.len() - 1].iter().map(|t| t.kind.clone()).collect();
        assert_eq!(&kinds[..], *expect, "maximal munch failed on {src:?}");
    }
}
}

Warning: ~ alone is a lexer error in Ember, because Ember has no bitwise operators — see the grammar. If you later add them, ~ becomes bitwise-xor/not and this arm changes. Leave the error message specific ("expected '=' after '~'") so the future you knows what it meant.

Step 4: Numbers, and Lua's Integer/Float Rule

Concept. The lexer decodes literals, and the decoding rule is a language rule.

Goal. 10, 10.5, 1e3, .5, 0x1F all lex, with the right TokenKind.

Write number() from the concept chapter. Then verify against the reference implementation rather than against your memory:

for n in 10 10.5 1e3 1E-3 .5 0x1F 0xff 9223372036854775807 9223372036854775808 \
         0xFFFFFFFFFFFFFFFF; do
  printf '%-22s lua: %-8s value: %s\n' "$n" \
    "$(lua -e "print(math.type($n))")" "$(lua -e "print($n)")"
done

10                     lua: integer  value: 10
10.5                   lua: float    value: 10.5
1e3                    lua: float    value: 1000.0
1E-3                   lua: float    value: 0.001
.5                     lua: float    value: 0.5
0x1F                   lua: integer  value: 31
0xff                   lua: integer  value: 255
9223372036854775807    lua: integer  value: 9223372036854775807
9223372036854775808    lua: float    value: 9.2233720368548e+18
0xFFFFFFFFFFFFFFFF     lua: integer  value: -1

Rows 9 and 10 are the interesting ones and they are the two most people get wrong:

A decimal integer literal too large for i64 becomes a float.
A hexadecimal literal too large wraps and stays an integer.

Both are Lua 5.4 §3.1. Write one test per row of that table, with the manual reference in a comment.

Checkpoint question. Why does the hex path use u64::from_str_radix and then cast to i64 rather than parsing directly as i64?

Step 5: Strings and Escapes

Concept. A multi-character literal with an internal error surface.

Goal. "hi", 'hi', "a\nb", "\65", "\x41" lex. Unterminated and invalid-escape produce errors with useful spans.

#![allow(unused)]
fn main() {
fn string(&mut self, start: u32) -> Result<Token> {
    let quote = self.bump();                      // ' or "
    let mut out = String::new();
    loop {
        if self.at_end() {
            return Err(self.err_at(start, "unterminated string literal"));
        }
        match self.bump() {
            b if b == quote => break,
            b'\n' => return Err(self.err_at(start,
                        "unterminated string literal (newline in string)")),
            b'\\' => {
                let esc_start = self.pos as u32 - 1;
                match self.bump() {
                    b'n' => out.push('\n'),  b't'  => out.push('\t'),
                    b'r' => out.push('\r'),  b'\\' => out.push('\\'),
                    b'"' => out.push('"'),   b'\'' => out.push('\''),
                    b'a' => out.push('\x07'),b'b'  => out.push('\x08'),
                    b'f' => out.push('\x0c'),b'v'  => out.push('\x0b'),
                    b'\n' => out.push('\n'),              // line continuation
                    b'x' => {                              // \xXX
                        let mut v = 0u32;
                        for _ in 0..2 {
                            let d = (self.peek() as char).to_digit(16).ok_or_else(||
                                self.err_at(esc_start, "hexadecimal digit expected"))?;
                            v = v * 16 + d; self.pos += 1;
                        }
                        out.push(v as u8 as char);
                    }
                    d if d.is_ascii_digit() => {           // \ddd, up to 3 digits
                        let mut v = (d - b'0') as u32;
                        for _ in 0..2 {
                            if !self.peek().is_ascii_digit() { break; }
                            v = v * 10 + (self.bump() - b'0') as u32;
                        }
                        if v > 255 {
                            return Err(self.err_at(esc_start, "decimal escape too large"));
                        }
                        out.push(v as u8 as char);
                    }
                    c => return Err(self.err_at(esc_start,
                             format!("invalid escape sequence '\\{}'", c as char))),
                }
            }
            b => {
                // Non-ASCII bytes pass through. Re-slice from the source so a
                // multi-byte character survives intact rather than becoming
                // one char per byte.
                if b < 0x80 { out.push(b as char); }
                else {
                    let s = self.pos - 1;
                    let ch = self.src[s..].chars().next().unwrap();
                    self.pos = s + ch.len_utf8();
                    out.push(ch);
                }
            }
        }
    }
    Ok(self.tok(TokenKind::Str(out), start))
}
}

The parts that matter.

The error span for an unterminated string points at the opening quote (start), not at EOF. That is what a reader needs. The error for a bad escape points at the backslash (esc_start). Two different spans, two different questions, one function.
The non-ASCII arm is the one place a UTF-8 character crosses the byte-oriented scanner. Getting it wrong produces mojibake in string literals and, worse, a panic when self.src[s..] lands mid-character. It cannot here, because every other arm consumed only ASCII. State that invariant in a comment — it is the kind of thing a later refactor breaks silently.
v as u8 as char for \ddd and \xXX matches Lua: those escapes produce a byte, not a Unicode code point. Ember's strings are String (UTF-8) rather than byte strings, so bytes above 0x7F become the corresponding U+0080..U+00FF character. That is a divergence from Lua, whose strings are byte strings. Write it in appendix/lua-differences.md now; it will matter in Lab 16.

Step 6: Identifiers, Keywords, and `tokenize`

#![allow(unused)]
fn main() {
fn name(&mut self, start: u32) -> Result<Token> {
    while matches!(self.peek(), b'a'..=b'z' | b'A'..=b'Z' | b'0'..=b'9' | b'_') {
        self.pos += 1;
    }
    let text = &self.src[start as usize..self.pos];
    Ok(self.tok(keyword_or_ident(text), start))
}

pub fn tokenize(src: &str) -> Result<Vec<Token>> {
    let mut lx = Lexer::new(src);
    let mut out = Vec::new();
    loop {
        let t = lx.next_token()?;
        let done = t.kind == TokenKind::Eof;
        out.push(t);
        if done { return Ok(out); }
    }
}
}

Checkpoint question. keyword_or_ident runs a match on a &str for every identifier. Is that a hash lookup, a chain of comparisons, or something else? Check what rustc generates — cargo asm or just reason about it — and write the answer in docs/learning/01-lexer.md.

Step 7: `ember tokens`

#![allow(unused)]
fn main() {
// src/bin/ember.rs
fn cmd_tokens(src: &str, name: &str) -> ExitCode {
    let map = SourceMap::with(name, src);
    match ember::lexer::tokenize(src) {
        Ok(toks) => {
            println!("{:>4}  {:<10}  {:<22}  {}", "#", "span", "kind", "text");
            for (i, t) in toks.iter().enumerate() {
                let text = &src[t.span.start as usize..t.span.end as usize];
                println!("{:>4}  {:<10}  {:<22}  {:?}",
                         i, format!("{}..{}", t.span.start, t.span.end),
                         format!("{:?}", t.kind), text);
            }
            ExitCode::SUCCESS
        }
        Err(e) => { eprint!("{}", ember::error::render(&e, &map, SourceId(0))); ExitCode::FAILURE }
    }
}
}

The Trace

$ printf 'local x = 10 + 20  -- a comment\n' > /tmp/t.ember
$ ember tokens /tmp/t.ember

   #  span        kind                    text
   0  0..5        Local                   "local"
   1  6..7        Ident("x")              "x"
   2  8..9        Assign                  "="
   3  10..12      Int(10)                 "10"
   4  13..14      Plus                    "+"
   5  15..17      Int(20)                 "20"
   6  32..32      Eof                     ""

Three things to verify on every token dump, forever:

Spans are non-overlapping and non-decreasing. end of token n ≤ start of token n+1.
The gaps are exactly the trivia. Between token 5 (..17) and Eof (32..) lies " -- a comment\n" — 15 characters. Count them. If the arithmetic does not work, a scanner arm is consuming or leaving the wrong number of bytes, and that error will surface as a misplaced caret three labs from now.
Eof has a zero-width span at the end of input, not at 0 and not past the end.

Expected Output

$ ember tokens /dev/stdin <<< 'x = "a\qb"'
<stdin>:1:8: error: invalid escape sequence '\q'

   1 │ x = "a\qb"
     │       ^^

$ ember tokens /dev/stdin <<< 'return 0x'
<stdin>:1:8: error: malformed hexadecimal number

   1 │ return 0x
     │        ^^

Debugging Steps

Spans are off by one

You captured start after a bump(), or read self.pos before the last one. The rule: start is read at the top of next_token before any consumption; end is self.pos at the moment the token is constructed. Never compute a span from a length.

`"a" .. "b"` produces three `Dot`s or a parse error later

eat is not being used in the . arm, or the arm's order tries Dot before DotDot.

A comment at end of file loops forever

while self.peek() != b'\n' with no at_end() check, and peek() returns 0 forever past the end. Add !self.at_end() &&.

Panic: byte index is not a char boundary

Something advanced pos past a non-ASCII lead byte without consuming its continuation bytes. Only the string scanner's non-ASCII arm and name() touch this; name() cannot, because its match arms are all ASCII. Check the string scanner.

`9223372036854775808` errors instead of becoming a float

Your parse::<i64>() failure path returns an error instead of falling through to parse::<f64>(). Re-read Lua 5.4 §3.1.

Experiment

CLAIM. A lexer that decodes literals eagerly cannot represent a program it cannot decode — so the error surface of the lexer is larger than the error surface of a "dumb" tokenizer, and that is a good trade.

METHOD. Write a second tokenize_dumb that emits TokenKind::NumberText(String) without parsing. Run both over tests/golden/ and over 1 MB of /dev/urandom. Count: how many inputs does the dumb one accept that the real one rejects? For each, where would the error have surfaced instead?

PREDICTION. Write down, before running: does the dumb lexer accept 9e99999999? Where does that program fail, and is the resulting message better or worse?

RESULT. Record it in docs/learning/01-lexer.md. Then delete tokenize_dumb; you have made the point.

Test

#![allow(unused)]
fn main() {
#[test]
fn every_token_has_a_nonempty_span_covering_its_text() {
    let src = "local x = 10 + 20.5 .. \"s\" -- c\n";
    let toks = tokenize(src).unwrap();
    let mut prev_end = 0u32;
    for t in &toks {
        assert!(t.span.start >= prev_end,
                "spans must be non-decreasing: {t:?} after end {prev_end}");
        assert!(t.span.end as usize <= src.len());
        if t.kind != TokenKind::Eof {
            assert!(t.span.len() > 0, "non-EOF token with empty span: {t:?}");
        }
        prev_end = t.span.end;
    }
}

#[test]
fn integer_float_rule_matches_lua_5_4() {
    // Lua 5.4 §3.1. Verified with: lua -e 'print(math.type(X))'
    use TokenKind::*;
    let cases: &[(&str, TokenKind)] = &[
        ("10",                   Int(10)),
        ("10.5",                 Float(10.5)),
        ("1e3",                  Float(1000.0)),
        (".5",                   Float(0.5)),
        ("0x1F",                 Int(31)),
        ("9223372036854775807",  Int(i64::MAX)),
        ("9223372036854775808",  Float(9223372036854775808.0)),  // decimal overflow → float
        ("0xFFFFFFFFFFFFFFFF",   Int(-1)),                        // hex wraps, stays integer
    ];
    for (src, want) in cases {
        assert_eq!(tokenize(src).unwrap()[0].kind, *want, "for source {src:?}");
    }
}

#[test]
fn lexer_never_panics_on_arbitrary_bytes() {
    // A cheap stand-in for the fuzzer that arrives in §6. Deterministic seed.
    let mut x: u64 = 0x243F6A8885A308D3;
    for _ in 0..2000 {
        let mut s = String::new();
        for _ in 0..64 {
            x = x.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            s.push((32 + (x >> 33) as u8 % 95) as char);
        }
        let _ = tokenize(&s);          // Err is fine. Panic is not.
    }
}

#[test]
fn unterminated_constructs_error_at_the_opener() {
    for (src, at) in [("\"abc", 0u32), ("--[[ x", 0), ("'x", 0)] {
        let e = tokenize(src).unwrap_err();
        assert_eq!(e.kind, ErrorKind::Lex);
        assert_eq!(e.span.unwrap().start, at, "error should point at the opener in {src:?}");
    }
}
}

cargo test --lib lexer

Challenge Extensions

Long brackets. Implement [==[ ... ]==] for both strings and comments, with matching level counts. Read Lua's read_long_string first, then close the book and write it.
Error recovery. Change tokenize to collect a Vec<EmberError> and emit TokenKind::Error(Span) instead of stopping. Report all lexical errors in one run. Keep both behaviors behind a flag and compare the experience.
Zero-allocation identifiers. Change Ident(String) to a (u32, u32) span and have the parser slice the source. Benchmark tokenize on a 1 MB file before and after with criterion. Report the delta and the diff size, then decide whether it was worth it — and record the decision either way.
Benchmark against logos. Write the same token set with #[derive(Logos)] in a scratch crate. Compare throughput and, more importantly, compare the error messages each produces for "a\qb".
no_std. Make lexer.rs and token.rs build with #![no_std] + alloc. This is the first step toward the WASM capstone project, and it proves the front end has no OS dependency.

Deliverables

src/token.rs, src/lexer.rs complete; describe() written for every variant.
ember tokens FILE prints the table shown in The Trace.
Maximal munch tested for all eleven overlapping operator pairs.
The Lua 5.4 integer/float table tested row by row, each with a manual reference in a comment.
Unterminated string, unterminated block comment, invalid escape, and malformed number each produce an error whose span points at the opener or the escape, tested.
render() produces the caret output shown in Expected Output, with --no-color honored.
The no-panic test passes.
cargo clippy -- -D warnings clean; ./scripts/boundary-audit.sh passes.
docs/learning/01-lexer.md written, including the tokenize_dumb experiment result and your answer to the keyword_or_ident checkpoint question.

Validation / Self-check

Name every scanner loop in your lexer and the EOF exit condition of each.
Why does the unterminated-string error point at the opening quote instead of at EOF?
Give Lua 5.4's four-branch rule for integer vs float literals and the test row that covers each.
Where is the only place a non-ASCII byte can reach, and what invariant prevents a char-boundary panic elsewhere?
What is the divergence between Ember's \xNN and Lua's, and where is it documented?
What three properties must hold of every token dump, and what bug does each catch?
Your caret is two columns to the left of the offending text in a file that uses tabs. What is wrong, and in which module?
Why is Result on skip_trivia — what error can trivia possibly produce?

Next: Lab 2 — The Pratt Parser.

Open-Source Engineer & Contributor