Lexical Analysis: Bytes to Tokens

Every concept in this section is presented in nine parts: concept, problem, mental model, implementation, alternatives, decision, tradeoffs, production concerns, and references. This chapter covers three concepts: the token, the scanner loop, and lexical errors.

Concept 1: The Token

1. Concept

A token is the smallest unit of a program that carries meaning: a keyword, an identifier, a literal, an operator, a delimiter. The lexer's entire job is to convert a flat sequence of bytes into a flat sequence of tokens.

"local x = 10 + 20"

  Local   Ident("x")   Equal   Int(10)   Plus   Int(20)   Eof
  @0..5   @6..7        @8..9   @10..12   @13..14 @15..17  @17..17

2. Problem

A parser that worked directly on characters would have to answer "is this the start of a keyword or an identifier?" at every position, in every grammar rule. That question has one answer and it does not depend on context, so it should be answered once, in one place. Separating lexing from parsing is the oldest and cheapest modularity decision in compiler construction.

There is a second, less obvious reason: classification is where you attach position information. Once a token knows its span, every later layer inherits the ability to point at source.

3. Mental model

The lexer is a classifier with a ruler. It walks the source once, left to right, chopping it into pieces and labeling each one. It never looks backwards and it never looks far forwards. It does not know what a program is. It could not tell you whether end end end end is valid.

That last sentence is the important one. The lexer is deliberately stupid, and its stupidity is what makes it fast, testable, and reusable.

4. Implementation

#![allow(unused)]
fn main() {
// src/token.rs
#[derive(Clone, Debug, PartialEq)]
pub enum TokenKind {
    // literals — the lexer DECODES these, so nobody re-parses "10" later
    Int(i64),
    Float(f64),
    Str(String),
    Ident(String),

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

    // operators and delimiters
    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,
}
}

Three decisions are visible in that code and each one is worth naming.

The lexer decodes literals. Int(i64), not Int with the text left for later. Decoding happens exactly once, at the point where the bytes are already in hand, and any failure — an integer that does not fit, a malformed escape — is reported with a span while the span is still obvious.

Keywords are token kinds, not identifiers. The scanner reads an identifier-shaped run of characters and then checks it against a keyword table. This is the standard trick and it means the parser never asks "is this identifier actually the word end?".

#![allow(unused)]
fn main() {
fn keyword_or_ident(text: &str) -> TokenKind {
    match text {
        "and" => TokenKind::And,
        "break" => TokenKind::Break,
        // ... one arm per keyword; the compiler builds an efficient match for you
        _ => TokenKind::Ident(text.to_string()),
    }
}
}

There is an explicit Eof token with a zero-width span at the end of input. This costs one enum variant and removes an Option from every single lookahead in the parser. It also gives you somewhere to point when the error is "unexpected end of file", which is otherwise the one error message with no location.

5. Alternatives

6. Decision

We use option A: owned payloads.

The lifetime in option B looks free and is not. Token<'src> forces Expr<'src>, which forces Parser<'src>, and then in Section 3 the compiler wants to hold an AST while also holding a Chunk, and you spend an afternoon on a lifetime puzzle that has nothing to do with language implementation. The allocation cost is real and it is measurable — and it is measured, in Lab 27, before you decide whether to graduate to option C.

Option D is the most interesting one and worth studying: rustc_lexer emits tokens carrying only a kind and a length, so it can be compiled and fuzzed with no dependency on the compiler's symbol table. That decoupling is exactly the kind of boundary the dependency rules are about, and it is the direction Ember moves if the front end ever needs to compile to wasm32 independently.

7. Tradeoffs

8. Production concerns

• Identifier character set. Ember accepts ASCII [A-Za-z_][A-Za-z0-9_]*, like Lua. Accepting Unicode identifiers means confronting UAX #31, normalization, and confusable-character attacks — a real security issue for any system that displays code and executes it. Restricting it is a decision; write it in appendix/lua-differences.md.
• Token count is unbounded input. A 1 GB source file produces a 1 GB-ish Vec<Token>. Section 5 puts a limit on source size, and it belongs at the host boundary, not in the lexer.
• BOM and CRLF. A UTF-8 BOM at offset 0 is not whitespace and will produce "unexpected character". Strip it explicitly. \r\n must count as one line, or every error message in a file authored on Windows is off by the number of preceding lines.

9. References

git clone https://github.com/lua/lua && cd lua
rg -n 'llex|read_numeral|read_string|check_next' llex.c

• Lua's llex.c — 500 lines, the whole lexer, including long strings and long comments. Note how SemInfo carries the decoded value: that is option A in C.
• rust-lang/rust, compiler/rustc_lexer/src/lib.rs — option D, and the crate-level docs explain why it is separate.
• CPython, Parser/tokenizer.c — what a lexer looks like when the language has significant indentation, which is to say: much worse.

Concept 2: The Scanner Loop and Maximal Munch

1. Concept

The scanner is a loop that, at each step, looks at the current character, decides which kind of token starts there, consumes as many characters as that token can possibly take, and emits it. "As many as possible" is a rule with a name: maximal munch, or the longest-match rule.

2. Problem

Operators overlap. . is a token; .. is a different token; ... is a third. = and == and ~= share prefixes. / and // do. - starts both subtraction and a comment. Without a rule, a scanner that takes the first match it finds will read .. as two . tokens and turn "a" .. "b" into a syntax error you will stare at for twenty minutes.

3. Mental model

The scanner is a greedy reader. At each position it asks "what is the longest thing that can start here?" and takes it. Greedy is not always right in general parsing, but for tokens it is both right and universal — every mainstream language uses it.

The classic counterexample, worth knowing: in C++ before C++11, vector<vector<int>> failed to compile because >> munched maximally into a right-shift operator. The fix was a special case in the parser. Maximal munch is simple, not free.

4. Implementation

#![allow(unused)]
fn main() {
// src/lexer.rs
pub struct Lexer<'a> {
    src: &'a str,
    bytes: &'a [u8],
    pos: usize,          // byte offset of the next unconsumed byte
}

impl<'a> Lexer<'a> {
    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 }

    /// Consume `c` if it is next. This is how maximal munch is expressed.
    fn eat(&mut self, c: u8) -> bool {
        if self.peek() == c { self.pos += 1; true } else { false }
    }

    pub fn next_token(&mut self) -> Result<Token> {
        self.skip_trivia()?;                     // whitespace AND comments
        let start = self.pos as u32;
        if self.pos >= self.bytes.len() {
            return Ok(self.tok(TokenKind::Eof, start));
        }
        let kind = match self.bump() {
            b'+' => TokenKind::Plus,
            b'*' => TokenKind::Star,
            b'%' => TokenKind::Percent,
            b'^' => TokenKind::Caret,
            b'#' => TokenKind::Hash,
            // ── the maximal-munch cases ────────────────────────────────
            b'/' => if self.eat(b'/') { TokenKind::DoubleSlash } else { TokenKind::Slash },
            b'=' => if self.eat(b'=') { TokenKind::Eq }         else { TokenKind::Assign },
            b'<' => if self.eat(b'=') { TokenKind::LessEq }     else { TokenKind::Less },
            b'>' => if self.eat(b'=') { TokenKind::GreaterEq }  else { TokenKind::Greater },
            b'~' => if self.eat(b'=') { TokenKind::NotEq }
                    else { return Err(self.err_at(start, "expected '=' after '~'")) },
            b':' => if self.eat(b':') { TokenKind::DoubleColon } else { TokenKind::Colon },
            b'.' => {
                if self.eat(b'.') {
                    if self.eat(b'.') { TokenKind::Ellipsis } else { TokenKind::DotDot }
                } else if self.peek().is_ascii_digit() {
                    self.pos -= 1;               // ".5" is a float; back up and re-read
                    return self.number(start);
                } else { TokenKind::Dot }
            }
            b'-' => TokenKind::Minus,            // comments were removed by skip_trivia
            // ── the multi-character cases ──────────────────────────────
            b'"' | b'\'' => { self.pos -= 1; return self.string(start); }
            c if c.is_ascii_digit()                  => { self.pos -= 1; return self.number(start); }
            c if c.is_ascii_alphabetic() || c == b'_' => { self.pos -= 1; return self.name(start); }
            c => return Err(self.err_at(start, format!("unexpected character {:?}", c as char))),
        };
        Ok(self.tok(kind, start))
    }
}
}

The parts that carry meaning:

• eat(c) is maximal munch made concrete. Every overlapping-operator decision is one eat.
• The . arm is the tricky one: ., .., ..., and the start of .5, all sharing a first character. Reading it top to bottom is the same order as trying the longest match first.
• self.pos -= 1 before a sub-scanner reads a whole token from its first character. An alternative is to pass the first character down; backing up keeps the sub-scanners callable from tests, which is worth more.
• Comments are removed in skip_trivia, not in the operator match. This is why the b'-' arm is one line. Putting comment handling in the - arm means a comment inside a loop of next_token calls silently produces a token — a bug that shows up as "my parser sees a Minus where the file has a comment".

The number scanner, where the integer/float decision is made:

#![allow(unused)]
fn main() {
fn number(&mut self, start: u32) -> Result<Token> {
    let begin = self.pos;
    if self.peek() == b'0' && (self.peek2() | 32) == b'x' {
        self.pos += 2;
        while self.peek().is_ascii_hexdigit() { self.pos += 1; }
        let text = &self.src[begin + 2..self.pos];
        if text.is_empty() { return Err(self.err_at(start, "malformed hexadecimal number")); }
        // Lua 5.4: hexadecimal integer constants WRAP rather than overflowing to float.
        let v = u64::from_str_radix(text, 16)
            .map_err(|_| self.err_at(start, "hexadecimal constant too large"))?;
        return Ok(self.tok(TokenKind::Int(v as i64), start));
    }

    let mut is_float = false;
    while self.peek().is_ascii_digit() { self.pos += 1; }
    if self.peek() == b'.' { is_float = true; self.pos += 1;
        while self.peek().is_ascii_digit() { self.pos += 1; } }
    if self.peek() | 32 == b'e' {
        is_float = true; self.pos += 1;
        if self.peek() == b'+' || self.peek() == b'-' { self.pos += 1; }
        if !self.peek().is_ascii_digit() {
            return Err(self.err_at(start, "malformed number: exponent has no digits"));
        }
        while self.peek().is_ascii_digit() { self.pos += 1; }
    }

    let text = &self.src[begin..self.pos];
    let kind = if is_float {
        TokenKind::Float(text.parse().map_err(|_| self.err_at(start, "malformed number"))?)
    } else {
        // Lua 5.4 §3.1: a DECIMAL integer numeral that does not fit becomes a FLOAT.
        match text.parse::<i64>() {
            Ok(v)  => TokenKind::Int(v),
            Err(_) => TokenKind::Float(text.parse().map_err(|_| self.err_at(start, "malformed number"))?),
        }
    };
    Ok(self.tok(kind, start))
}
}

Note: That last match is not defensive coding; it is a language rule. Lua 5.4 §3.1 says a numeric constant with a decimal point or exponent is a float; otherwise if it fits in an integer or is hexadecimal it is an integer; otherwise — a decimal integer that overflows — it is a float. Verify it: lua -e 'print(math.type(9223372036854775808))' prints float, while lua -e 'print(math.type(0xFFFFFFFFFFFFFFFF))' prints integer. Two lines of code, one manual section, and a behavior you would otherwise get wrong and never notice.

5. Alternatives

6. Decision

We hand-write the scanner (option A), and are permitted to benchmark against logos in Section 7.

A generated lexer is the right answer for shipping and the wrong answer for learning: the interesting parts — maximal munch, the number rule above, span attachment, error messages that name the actual problem — are exactly the parts a generator hides.

7. Tradeoffs

8. Production concerns

• Never panic. self.src[begin..self.pos] panics if either index falls inside a UTF-8 character. Ember only slices at boundaries it created by scanning ASCII, but the fuzzer in Section 6 exists to prove that. unwrap() on parse() is the other classic; note both call sites above return errors instead.
• Unterminated constructs must terminate. An unterminated string or block comment must hit EOF and produce an error, not loop. Every while in a scanner needs an EOF exit, and peek() returning 0 at EOF is what provides it — but only if 0 is not a valid continuation character in that loop. Check each one.
• Tabs and the caret. Rendering ^ under a span requires knowing the display column, and a tab is not one column. Decide (Ember: tabs count as one column and are echoed verbatim, so the caret aligns in any editor that also uses one column) and test it.
• Nested block comments. Lua's long-bracket syntax --[==[ ... ]==] uses a level count so a comment can contain ]]. Ember implements --[[ ... ]] without levels in Lab 1, and long brackets are a challenge extension. Document the divergence.

9. References

• Lua's llex.c: read_long_string handles both long strings and long comments with a level count. check_next2 is Lua's eat.
• rustc_lexer for a modern hand-written scanner in Rust, including a good treatment of raw strings.
• Go's go/scanner package, for a scanner that must also insert semicolons — an instructive case of a lexer doing something almost-syntactic and the mess it causes.

Concept 3: Lexical Errors

1. Concept

A lexical error is a byte sequence that cannot begin any token: an unterminated string, a malformed number, a stray @, an invalid escape.

2. Problem

The error must be reported, not panic!-ed, and it must carry a span — because a lexer error with no location is the most useless message a compiler can produce, and this lexer runs on attacker-adjacent input in Section 5.

3. Mental model

The lexer is the first place in the pipeline where the program can be wrong. Everything downstream assumes the token stream is well-formed, so this is where "wrong" becomes a Result instead of a crash.

4. Implementation

#![allow(unused)]
fn main() {
fn err_at(&self, start: u32, msg: impl Into<String>) -> EmberError {
    EmberError {
        kind: ErrorKind::Lex,
        message: msg.into(),
        span: Some(Span { start, end: self.pos as u32 }),
        traceback: Vec::new(),
    }
}

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()?;               // Lab 1: stop at the first error
        let done = t.kind == TokenKind::Eof;
        out.push(t);
        if done { return Ok(out); }
    }
}
}

5–7. Alternatives, decision, tradeoffs

Decision: A now, B in Lab 24.

Option A costs one line and gets you to a running language in an hour. Option B is strictly better for humans — "you have 1 error" followed by 40 more on the next run is a bad experience — and it is a mechanical change once the error type carries spans, which is why it is deferred rather than designed around. Option C is a different product: you need it for an editor, not for a runtime, and adopting it here would double the front end for no benefit to Ember's actual use case.

The tradeoff is worth stating precisely: A gives you a correct compiler faster; B gives you a usable one. Knowing that they are separable is the point.

8. Production concerns

• Error messages should name the construct, not the machine state. "unterminated string literal" beats "unexpected EOF in state 7". Every message in Ember's lexer is checked against that rule in Lab 1's tests, by asserting on the message text.
• Error messages must not echo unbounded input. "unexpected character" plus a span is safe; format!("unexpected {}", rest_of_file) is a log-flooding bug.
• The same error type is used at run time in Section 5, where its Display output may be returned to a partially-trusted caller. Nothing in a lexer message should leak host paths — which means the file name is a property of the SourceMap, added at render time, not baked into the message.

9. References

• Rust's diagnostics guide, rustc-dev-guide.rust-lang.org, chapter on emitting errors — the vocabulary of primary spans, secondary spans, and suggestions is worth stealing wholesale.
• ariadne and codespan-reporting crates: read their example output now, build your own in Lab 1, and compare in Section 6.

Reading Exercise

Open Lua's lexer and answer these from the source, not from memory:

rg -n 'static int llex' llex.c            # the main loop
rg -n 'read_numeral' -A 30 llex.c         # compare with our number()
rg -n 'skip_sep|read_long_string' llex.c  # long brackets and their level count
rg -n 'luaX_newstring' llex.c lstring.c   # where identifiers get interned

1. Where does Lua decide that a numeral is an integer versus a float? Is it in the lexer or later?
2. Lua interns every identifier at lex time. What does that buy the parser and the VM, and what does it cost the lexer?
3. check_next2 — find it and explain how it implements maximal munch differently from our eat.
4. Lua's lexer has exactly one token of lookahead (luaX_lookahead). Find the one place the parser needs it, and explain why one is enough.

Common Bugs and Symptoms

Validation / Self-check

1. What are the two jobs of a lexer, and which of them makes good diagnostics possible?
2. State maximal munch, and give three Ember token pairs that require it.
3. Why is there an explicit Eof token instead of an Option<Token>?
4. Give Lua 5.4's rule for whether a numeric constant is an integer or a float, including the overflow cases, and the command that verifies each branch.
5. Give the four token-payload strategies and name a real implementation of each. Why does the borrowed one cost more than it appears to?
6. Why are comments handled in skip_trivia rather than in the - arm?
7. Name three ways a hand-written scanner can hang or panic, and the invariant that prevents each.
8. What changes if you switch from "fail on first error" to "error token and continue", and why is that change deferred rather than designed around?

Next: Grammars and Precedence.