Crafting a parser, part 1: from source to tokens

A parser is only as good as the tokens it is fed. Before any grammar rule runs, a lexer (or scanner) turns a flat stream of characters into a stream of tokens — the atoms the parser actually reasons about. Get the token shape right and the rest of the front-end falls into place; get it wrong and every later stage pays interest.

This is part one of Crafting a parser in Rust.

What a token is

A token is a small, classified slice of source: a kind plus the span it came from. Keeping the span — not a copied string — is the single most important decision in the whole series, because every diagnostic you ever print needs to point back at real source.

token.rs

1pub struct Token {2    pub kind: TokenKind,3    pub span: Span, // a byte range into the source, never an owned String4}56pub struct Span { pub start: u32, pub end: u32 }

The scanning loop

The lexer holds the source and a cursor. Each call to next_token skips trivia (whitespace, comments), looks at one character, and dispatches.

lexer.rs

1fn next_token(&mut self) -> Token {2    self.skip_trivia();3    let start = self.pos;4    let kind = match self.bump() {5        Some(c) if c.is_ascii_digit() => self.number(),6        Some(c) if is_ident_start(c) => self.ident_or_keyword(start),7        Some('+') => TokenKind::Plus,8        Some('(') => TokenKind::LParen,9        Some(other) => TokenKind::Unknown(other),10        None => TokenKind::Eof,11    };12    Token { kind, span: Span { start, end: self.pos } }13}

Keywords are identifiers, until they aren't

Scan an identifier first, then look it up in a keyword table. Special-casing if / while / fn inside the character match is how lexers grow into unmaintainable spaghetti. One match ident { ... } keeps it honest.

Lookahead and peeking

Parsers need to look without consuming. The cheapest design is a lexer that can peek one token ahead, caching it. Most languages parse with a single token of lookahead — keep that as the default and only reach for more when a real ambiguity forces it (we hit one in part six).

🦀

Ferris' hot tip

Emit an explicit Eof token instead of returning Option<Token>. The parser becomes a clean state machine that always has a current token, and you delete a pile of None handling.

Don't throw on bad input

A lexer that panics on a stray @ is useless in an editor. Emit an Unknown token with its span and keep going — the parser turns it into a diagnostic later. This never-stop-scanning rule is what makes error recovery possible at all.

Takeaways

Tokens carry a kind + span, never owned strings.
Scan identifiers generically, then classify against a keyword table.
One token of lookahead is the default; an explicit Eof simplifies everything.
The lexer never panics — bad characters become tokens, not crashes.

Next: grammars and recursive descent.