Scanning source into tokens

The design article ended with a grammar on paper and a promise: the running code starts with the scanner. This step pays that promise. By the end, birch reads source text and produces a list of tokens, every one carrying the line and column it started at — and those positions are not a convenience, they are the foundation every later error message in this track stands on.

Where the reader starts

The previous step shipped the project scaffold in the examples repository as the interpreter-ch01 tag: a cargo project named birch with one honest line in main.rs. Everything in this step replaces that file wholesale, so the article shows it in full — there is no patch to apply, just a file to swap:

git checkout interpreter-ch01
cargo run -q

birch: design only so far - the lexer lands in step 2

If that is what your tree does, you are at the right state. At the end of the article the same command at the interpreter-ch02 tag prints a token table.

What a token is

The grammar named every smallest thing birch source can be: NUMBER, STRING, IDENT, the ten keywords, the punctuation, the operators. The scanner mirrors that list one-to-one in an enum, which means the compiler now enforces the grammar’s vocabulary: nobody can invent a token kind downstream without adding a variant here, and every match over the enum has to reckon with all of them.

A token is three facts: what it is, the exact characters it came from, and where those characters were. The enum is the “what”. The lexeme field is the “which” — without it, two Ident tokens are indistinguishable, and greeting and tick would be the same word. The line and col fields are the “where”, and they exist because step 8 has to print error messages that point at a specific line and column. Retrofitting positions through a pipeline that dropped them at the door is miserable; collecting them at the source is nearly free, because the scanner is already walking the text one character at a time.

Both structs derive Debug, which is a small decision with a large payoff: the whole token list prints with {:?}-style formatting and no manual display code, which is exactly what this step’s main does.

The scan loop

The scanner keeps two cursors into the source. current is the character being looked at right now; start is where the token under construction began. One token per loop iteration: mark start, dispatch on the first character, and when the token is done, slice chars[start..current] as its lexeme. Four tiny helpers do all the cursor work — advance (consume and return the current character), peek and peek2 (look without consuming), and match_next (consume one specific character if it is there, otherwise say no).

Positions ride along for free. advance bumps the column on every character, and the whitespace arm resets it on a newline. Columns count characters, not bytes — irrelevant for birch’s ASCII today, but the scanner already works on a Vec<char>, so counting characters costs nothing and never lies about width.

The parts that sound hard and are not

Scanners have a reputation for edge cases, but birch’s grammar keeps every one of them small:

• = versus ==. The rule is maximal munch: take the longest token the characters support. match_next('=') answers it in one call — and the same three lines handle !/!=, </<=, and >/>=. All four pairs share one shape.
• Comments. A / that is followed by another / is a comment, and the scanner just skips to the newline. A / alone is the division operator. One match_next decides.
• Numbers versus dots. 1.5 is one number; but a dot with no digit behind it is not part of the number, so 1..3 scans as 1, then ., then .3. The fraction is consumed only when peek2 confirms a digit after the dot.
• Keywords. The design article chose keywords that are just words, and this is where that choice pays: scan a full identifier, look it up in the keyword function — a ten-line table — and fall back to Ident when it misses. No sigils, no special lexing rules, one checkable list.
• Strings. A " starts a string that runs to the closing ". Birch strings have no escape sequences yet; adding them later is one more branch inside string, not a redesign. A string that hits the end of the line or the end of the file without closing is an error — but an error that is recorded, not a panic.

That last point is a real design decision. The scanner never stops on a bad character: unexpected characters and unterminated strings go into an errors list, and the scan continues. A compiler that quits at the first mistake is a terrible tutor — you fix one typo, rerun, meet the next one. Collecting every mistake in one pass costs one Vec and gives step 8 something worth printing.

The whole scanner

This is the complete src/main.rs for this step. The main function scans the counter program from the design article and prints one line per token: position, kind, lexeme. Errors, if there were any, print first.

src/main.rs

//! birch, step 2: the scanner.
//!
//! Reads birch source and produces a list of tokens, each carrying the
//! line and column it started at. Errors go into a list instead of
//! stopping the scan, so one bad character does not hide the rest.

#[derive(Debug, Clone)]
enum TokenKind {
    // keywords
    Var,
    Fun,
    If,
    While,
    Return,
    True,
    False,
    Nil,
    And,
    Or,
    // literals
    Ident,
    Number,
    Str,
    // punctuation
    LeftParen,
    RightParen,
    LeftBrace,
    RightBrace,
    LeftBracket,
    RightBracket,
    Comma,
    Semicolon,
    // operators
    Assign,
    Bang,
    BangEqual,
    EqualEqual,
    Greater,
    GreaterEqual,
    Less,
    LessEqual,
    Plus,
    Minus,
    Star,
    Slash,
    Percent,
    // end of input
    Eof,
}

struct Token {
    kind: TokenKind,
    lexeme: String,
    line: usize,
    col: usize,
}

struct ScanError {
    line: usize,
    col: usize,
    message: String,
}

struct Scanner {
    chars: Vec<char>,
    start: usize, // first char of the token being scanned
    current: usize,
    line: usize,
    col: usize,
    tokens: Vec<Token>,
    errors: Vec<ScanError>,
}

impl Scanner {
    fn new(source: &str) -> Self {
        Scanner {
            chars: source.chars().collect(),
            start: 0,
            current: 0,
            line: 1,
            col: 1,
            tokens: Vec::new(),
            errors: Vec::new(),
        }
    }

    fn scan_tokens(mut self) -> (Vec<Token>, Vec<ScanError>) {
        while !self.at_end() {
            self.start = self.current;
            self.scan_token();
        }
        self.tokens.push(Token {
            kind: TokenKind::Eof,
            lexeme: String::new(),
            line: self.line,
            col: self.col,
        });
        (self.tokens, self.errors)
    }

    fn scan_token(&mut self) {
        let line = self.line;
        let col = self.col;
        let c = self.advance();
        match c {
            '(' => self.add(TokenKind::LeftParen, line, col),
            ')' => self.add(TokenKind::RightParen, line, col),
            '{' => self.add(TokenKind::LeftBrace, line, col),
            '}' => self.add(TokenKind::RightBrace, line, col),
            '[' => self.add(TokenKind::LeftBracket, line, col),
            ']' => self.add(TokenKind::RightBracket, line, col),
            ',' => self.add(TokenKind::Comma, line, col),
            ';' => self.add(TokenKind::Semicolon, line, col),
            '+' => self.add(TokenKind::Plus, line, col),
            '-' => self.add(TokenKind::Minus, line, col),
            '*' => self.add(TokenKind::Star, line, col),
            '%' => self.add(TokenKind::Percent, line, col),
            '/' => {
                if self.match_next('/') {
                    // a comment runs to the end of the line
                    while self.peek() != Some('\n') && self.peek().is_some() {
                        self.advance();
                    }
                } else {
                    self.add(TokenKind::Slash, line, col);
                }
            }
            '=' => {
                let kind = if self.match_next('=') {
                    TokenKind::EqualEqual
                } else {
                    TokenKind::Assign
                };
                self.add(kind, line, col);
            }
            '!' => {
                let kind = if self.match_next('=') {
                    TokenKind::BangEqual
                } else {
                    TokenKind::Bang
                };
                self.add(kind, line, col);
            }
            '<' => {
                let kind = if self.match_next('=') {
                    TokenKind::LessEqual
                } else {
                    TokenKind::Less
                };
                self.add(kind, line, col);
            }
            '>' => {
                let kind = if self.match_next('=') {
                    TokenKind::GreaterEqual
                } else {
                    TokenKind::Greater
                };
                self.add(kind, line, col);
            }
            '"' => self.string(line, col),
            c if c.is_ascii_digit() => self.number(line, col),
            c if c.is_ascii_alphabetic() || c == '_' => self.identifier(line, col),
            c if c.is_whitespace() => {
                if c == '\n' {
                    self.line += 1;
                    self.col = 1;
                }
            }
            other => self.errors.push(ScanError {
                line,
                col,
                message: format!("unexpected character `{other}`"),
            }),
        }
    }

    fn string(&mut self, line: usize, col: usize) {
        loop {
            match self.peek() {
                Some('"') => {
                    self.advance();
                    self.add(TokenKind::Str, line, col);
                    return;
                }
                Some('\n') | None => {
                    self.errors.push(ScanError {
                        line,
                        col,
                        message: String::from("unterminated string"),
                    });
                    return;
                }
                Some(_) => {
                    self.advance();
                }
            }
        }
    }

    fn number(&mut self, line: usize, col: usize) {
        while self.peek().is_some_and(|c| c.is_ascii_digit()) {
            self.advance();
        }
        // a fraction, but only when the dot is followed by a digit:
        // `1.5` is one number, `1..3` is `1`, `.`, `.3`
        if self.peek() == Some('.') && self.peek2().is_some_and(|c| c.is_ascii_digit()) {
            self.advance(); // the dot
            while self.peek().is_some_and(|c| c.is_ascii_digit()) {
                self.advance();
            }
        }
        self.add(TokenKind::Number, line, col);
    }

    fn identifier(&mut self, line: usize, col: usize) {
        while self
            .peek()
            .is_some_and(|c| c.is_ascii_alphanumeric() || c == '_')
        {
            self.advance();
        }
        let word: String = self.chars[self.start..self.current].iter().collect();
        self.add(keyword(&word), line, col);
    }

    // -- cursor helpers -------------------------------------------------

    fn at_end(&self) -> bool {
        self.current >= self.chars.len()
    }

    fn advance(&mut self) -> char {
        let c = self.chars[self.current];
        self.current += 1;
        self.col += 1;
        c
    }

    fn peek(&self) -> Option<char> {
        self.chars.get(self.current).copied()
    }

    fn peek2(&self) -> Option<char> {
        self.chars.get(self.current + 1).copied()
    }

    fn match_next(&mut self, expected: char) -> bool {
        if self.peek() == Some(expected) {
            self.advance();
            true
        } else {
            false
        }
    }

    fn add(&mut self, kind: TokenKind, line: usize, col: usize) {
        let lexeme: String = self.chars[self.start..self.current].iter().collect();
        self.tokens.push(Token {
            kind,
            lexeme,
            line,
            col,
        });
    }
}

fn keyword(word: &str) -> TokenKind {
    match word {
        "var" => TokenKind::Var,
        "fun" => TokenKind::Fun,
        "if" => TokenKind::If,
        "while" => TokenKind::While,
        "return" => TokenKind::Return,
        "true" => TokenKind::True,
        "false" => TokenKind::False,
        "nil" => TokenKind::Nil,
        "and" => TokenKind::And,
        "or" => TokenKind::Or,
        _ => TokenKind::Ident,
    }
}

fn main() {
    let source = r#"// the counter, from the design article
var greeting = "hi";
fun makeCounter(start) {
  var n = start;
  return n;
}

var tick = makeCounter(10);
print tick();
"#;

    let (tokens, errors) = Scanner::new(source).scan_tokens();

    for e in &errors {
        println!("error: {}:{} {}", e.line, e.col, e.message);
    }
    for t in &tokens {
        println!("{:3}:{:<3} {:<12} {}", t.line, t.col, format!("{:?}", t.kind), t.lexeme);
    }
}

▶Run this in the Rust Playground

One detail worth pausing on: after the loop ends, the scanner appends one final Eof token. Every later stage then has a guaranteed stopping point — the parser never has to ask “is there more?” because the answer is always a token, and the last one is Eof.

What running it shows

git checkout interpreter-ch02
cargo run -q

  2:1   Var          var
  2:5   Ident        greeting
  2:14  Assign       =
  2:16  Str          "hi"
  2:20  Semicolon    ;
  3:1   Fun          fun
  3:5   Ident        makeCounter
  3:16  LeftParen    (
  3:17  Ident        start
  3:22  RightParen   )
  3:24  LeftBrace    {
  4:3   Var          var
  4:7   Ident        n
  4:9   Assign       =
  4:11  Ident        start
  4:16  Semicolon    ;
  5:3   Return       return
  5:10  Ident        n
  5:11  Semicolon    ;
  6:1   RightBrace   }
  8:1   Var          var
  8:5   Ident        tick
  8:10  Assign       =
  8:12  Ident        makeCounter
  8:23  LeftParen    (
  8:24  Number       10
  8:26  RightParen   )
  8:27  Semicolon    ;
  9:1   Ident        print
  9:7   Ident        tick
  9:11  LeftParen    (
  9:12  RightParen   )
  9:13  Semicolon    ;
 10:1   Eof

Check a few lines against the source. Line 4 is var n = start; — the tokens say 4:3, because the statement is indented two columns in. The comment on line 1 produced nothing at all: comments are for people, and the parser never sees them. And print came out as Ident, not a keyword — the design article decided that builtins like print and len are ordinary functions, and the scanner is where that decision becomes visible. When a step 9 REPL prints the value of a call, there will be no keyword in the way.

Where this leaves the track

The tree at interpreter-ch02 contains a cargo project whose main turns any birch source you paste into it into a flat list of tokens with honest positions — or a list of errors with positions, when the source is not birch. That flat list is exactly the input the next step wants: A Pratt parser for expressions takes the tokens and builds the first real trees of the grammar, the expression side, without turning the precedence table into a pile of nested functions. Until then, the track overview has the full itinerary.