Reading Source and Recognising Tokens
Open a source file and you get bytes. Before we can work with the functions in a source file, we need to recognize its words and punctuation: identifiers, keywords, numbers, braces, and operators.
This phase is called lexing, tokenization, or scanning. The terms are often interchangeable. I tend to use "lexer" for the component and "scanner" for the process of moving through the input, one character at a time.
We can use the small program from chapter 01 to follow this step. The lexer reads add as an identifier; it hasn't identified it as a function or grouped a + b into an expression. It reports + as a plus token and { as a left brace. Later phases will work out how those pieces fit together.
Why this phase matters
Without tokens, the parser would have to handle individual characters while also recognizing larger structures such as function definitions. A separate lexer lets us deal with those tasks independently.
Tokens also carry source locations. If the user writes let x: i32 = 5 @ 3;, the lexer can report the unexpected character before parsing begins.
Preserving these locations lets rustc point to a mistake and sometimes suggest a correction. MicroRust's messages will be simpler, but they can still point at the right character.
What we are building here
We are building a hand-written lexer for the MicroRust subset from the series setup. It will recognize keywords, identifiers, integer literals, string literals only for the special "{}" in println!("{}", value), punctuation, arithmetic operators, ->, and // line comments.
More precisely, this is a deterministic, hand-written scanner for a regular token language. A regular language can be recognized with a finite amount of state: the scanner walks left to right, remembering which mode it's in. A finite automaton describes that process through states, transitions, and accepting states. For an identifier, we start with a letter or underscore and continue consuming letters, digits, and underscores.
Rust's full syntax needs more cases. MicroRust leaves out raw strings, lifetimes, attributes, byte strings, char literals, modules, and a Unicode identifier policy. Those omissions keep the scanner small enough to write by hand.
First, we need to read the file:
use std::fs;
fn read_source(path: &str) -> std::io::Result<String> {
fs::read_to_string(path)
}read_to_string validates UTF-8 while reading. Our identifiers are ASCII, but UTF-8 text in line comments is harmless because we skip it. The scanner stores byte offsets, so a diagnostic can still slice the original source correctly.
A token has a kind, the exact text that produced it, and a span. The text is called a lexeme. The token kind says what role the lexeme plays.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
Fn,
Let,
Return,
Ident,
Int,
String,
I32,
Plus,
Minus,
Star,
Slash,
Colon,
Semicolon,
Comma,
LParen,
RParen,
LBrace,
RBrace,
Arrow,
Eq,
Bang,
Eof,
}
#[derive(Debug, Clone)]
pub struct Token {
pub kind: TokenKind,
pub lexeme: String,
pub span: Span,
}We keep the lexeme for diagnostics and later phases: Ident gives us the category, while result gives us the spelling.
MicroRust skips whitespace and comments, accounting for them in source locations without emitting tokens. Other languages need different rules: Python makes indentation part of syntax, and JavaScript's semicolon insertion means newlines can affect parsing. Neither complicates the Rust subset we're handling here.
Inside lex, the scanning loop first skips whitespace and line comments. This is an excerpt from the syntax module that we'll keep in main.rs:
if bytes[pos].is_ascii_whitespace() {
pos += 1;
continue;
}
if source[pos..].starts_with("//!")
|| (source[pos..].starts_with("///") && !source[pos..].starts_with("////"))
{
return Err(Error::new(
"lex",
Span {
start: pos,
end: pos + 3,
},
"doc comments are outside MicroRust",
));
}
if source[pos..].starts_with("//") {
while pos < bytes.len() && bytes[pos] != b'\n' {
pos += 1;
}
continue;
}Each continue returns to the loop's bounds check. That matters when a comment reaches the end of the file. Rust doc comments become attributes, so we reject those explicitly instead of discarding them as ordinary whitespace. The rest of lex classifies a token, records its span, and finally appends Eof. The complete function is compiled and tested in the companion, including input that ends in a comment.
Identifiers and keywords share the same character shape, so the scanner reads the whole word first, then classifies it:
pub fn ident_or_keyword(text: &str) -> TokenKind {
match text {
"fn" => TokenKind::Fn,
"let" => TokenKind::Let,
"return" => TokenKind::Return,
"i32" => TokenKind::I32,
_ => TokenKind::Ident,
}
}The keyword lookup classifies return as a keyword and leaves result as an identifier.
C, Java, Rust, and JavaScript all classify keywords, though the details vary. Python and Ruby do too, with extra context for their syntax. Ruby's flexible method-call forms, for example, make tokenization and parsing less neatly separated. Our restricted syntax lets the MicroRust scanner make this decision locally.
For operators, most tokens are one character, except ->. So the byte-matching part of lex gives - two cases:
b'-' if bytes.get(pos) == Some(&b'>') => {
pos += 1;
TokenKind::Arrow
}
b'-' => TokenKind::Minus,The outer loop has already consumed the first byte. Seeing > consumes a second byte and chooses Arrow; otherwise we keep Minus. The same idea handles // comments. If the scanner sees / and the next character is /, it skips until the end of the line. Otherwise it returns Slash.
The b prefix matches how we're reading the source. source.as_bytes() gives us bytes of type u8, so we use b'+' when matching a plus sign. A plain '+' has type char, Rust's Unicode character type, and won't match a u8. If we used source.chars() instead, '+' would be the right pattern. Working with bytes suits our ASCII tokens and keeps the positions in the same units as our spans. The Rust Reference describes both literal types.
String support is deliberately tiny. We only need "{}" for our canonical program:
println!("{}", result);Real Rust string lexing handles escapes, raw strings, byte strings, and Unicode, each with its own error cases. The scanner recognises ordinary ASCII quoted strings without escapes. The parser then accepts only the exact format string "{}". Strings are not general MicroRust values.
This small program contains a character our lexer won't accept:
fn main() {
let x: i32 = 5 @ 3;
}The lexer should reject @ because MicroRust has no token for it:
error: unexpected character '@'
--> example.mrs:2:20
|
2 | let x: i32 = 5 @ 3;
| ^Here the character itself is unsupported. A parse error, which we'll handle next, involves recognizable tokens in an invalid arrangement.
Regex-based lexers are a reasonable alternative. Identifiers, integers, whitespace, and line comments follow regular patterns, and tools such as lex, flex, or modern library equivalents can turn them into efficient scanners. I prefer a hand-written scanner here because we can follow each decision in the code. With so few token kinds, that remains manageable.
Whether a regex engine or our own loop recognizes [0-9]+, the token language for integer literals is regular. Balanced braces are different: recognizing arbitrary nesting requires a stack rather than finite state alone. We'll leave that structure to the parser.
Byte offsets are cheap to maintain and convenient for slicing the source. Our diagnostic renderer derives a one-based line and character column only when an error occurs. That avoids storing counters on every token. It still isn't a complete display-width calculation: tabs and wide characters need more care in a production renderer.
We store each span as two byte offsets:
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
pub start: usize,
pub end: usize,
}These offsets identify a half-open range: the start is included and the end is excluded. The source file remains available when we need to turn the range into a diagnostic.
Block comments are rejected explicitly. Full Rust permits nested block comments, which need a nesting counter and do not fit the finite-state account above. Limiting ourselves to line comments is what keeps that account accurate.
Reading the longest matching lexeme is often called "maximal munch." It keeps i32, main, and result intact before keyword classification checks their full spellings.
When we run the lexer on the canonical program, the beginning of the stream looks like this:
Fn "fn"
Ident "add"
LParen "("
Ident "a"
Colon ":"
I32 "i32"
Comma ","
Ident "b"
Colon ":"
I32 "i32"
RParen ")"
Arrow "->"
I32 "i32"
LBrace "{"
Return "return"
Ident "a"
Plus "+"
Ident "b"
Semicolon ";"
RBrace "}"The stream preserves token order and spelling. The parser will group fn add(a: i32, b: i32) -> i32 { ... } into a function item and a + b into an expression whose + binds two operands.
The lexer recognizes println as an identifier and ! as a bang token. Recognizing our special println! form belongs to the parser, which has enough context to inspect its syntax. This division keeps scanner tests concerned with spelling and positions.
Run this version
This is the first working version of microrustc. It reads a file and shows its tokens. We'll keep this code when we add the parser in the next chapter.
Create a folder called microrust if you haven't already. Put the two files below in it. If you saved golden.mrs from chapter 01, keep it there too; this tree shows the files used for today's smaller example:
microrust/
|-- main.rs
`-- example.mrsCopy the whole listing into main.rs. It contains the scanner, source spans, error reporting, and the command-line entry point. The syntax module is inside this file; it doesn't need a separate directory.
main.rs: compiler through the lexer stage
// Chapter 02: source input and tokenization.
use std::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
pub start: usize,
pub end: usize,
}
#[derive(Debug, Clone)]
pub struct Error {
pub phase: &'static str,
pub span: Span,
pub message: String,
}
impl Error {
pub fn new(phase: &'static str, span: Span, message: impl Into<String>) -> Self {
Self {
phase,
span,
message: message.into(),
}
}
pub fn render(&self, path: &str, source: &str) -> String {
let start = self.span.start.min(source.len());
let prefix = &source[..start];
let line = prefix.bytes().filter(|b| *b == b'\n').count() + 1;
let column = prefix.rsplit('\n').next().unwrap_or("").chars().count() + 1;
let text = source.lines().nth(line - 1).unwrap_or("");
format!(
"{}\n --> {path}:{line}:{column}\n{line} | {text}\n | {}^",
self,
" ".repeat(column - 1)
)
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} error: {}", self.phase, self.message)
}
}
impl std::error::Error for Error {}
mod syntax {
use crate::{Error, Span};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
Fn,
Let,
Return,
Ident,
Int,
String,
I32,
Plus,
Minus,
Star,
Slash,
Colon,
Semicolon,
Comma,
LParen,
RParen,
LBrace,
RBrace,
Arrow,
Eq,
Bang,
Eof,
}
#[derive(Debug, Clone)]
pub struct Token {
pub kind: TokenKind,
pub lexeme: String,
pub span: Span,
}
pub fn ident_or_keyword(text: &str) -> TokenKind {
match text {
"fn" => TokenKind::Fn,
"let" => TokenKind::Let,
"return" => TokenKind::Return,
"i32" => TokenKind::I32,
_ => TokenKind::Ident,
}
}
pub fn lex(source: &str) -> Result<Vec<Token>, Error> {
let bytes = source.as_bytes();
let mut pos = 0;
let mut tokens = Vec::new();
while pos < bytes.len() {
if bytes[pos].is_ascii_whitespace() {
pos += 1;
continue;
}
if source[pos..].starts_with("//!")
|| (source[pos..].starts_with("///") && !source[pos..].starts_with("////"))
{
return Err(Error::new(
"lex",
Span {
start: pos,
end: pos + 3,
},
"doc comments are outside MicroRust",
));
}
if source[pos..].starts_with("//") {
while pos < bytes.len() && bytes[pos] != b'\n' {
pos += 1;
}
continue;
}
let start = pos;
let c = bytes[pos];
pos += 1;
let kind = if c.is_ascii_alphabetic() || c == b'_' {
while pos < bytes.len()
&& (bytes[pos].is_ascii_alphanumeric() || bytes[pos] == b'_')
{
pos += 1;
}
ident_or_keyword(&source[start..pos])
} else if c.is_ascii_digit() {
while pos < bytes.len() && bytes[pos].is_ascii_digit() {
pos += 1;
}
TokenKind::Int
} else {
match c {
b'+' => TokenKind::Plus,
b'-' if bytes.get(pos) == Some(&b'>') => {
pos += 1;
TokenKind::Arrow
}
b'-' => TokenKind::Minus,
b'*' => TokenKind::Star,
b'/' if bytes.get(pos) == Some(&b'*') => {
return Err(Error::new(
"lex",
Span {
start,
end: pos + 1,
},
"block comments are outside MicroRust; use //",
))
}
b'/' => TokenKind::Slash,
b':' => TokenKind::Colon,
b';' => TokenKind::Semicolon,
b',' => TokenKind::Comma,
b'(' => TokenKind::LParen,
b')' => TokenKind::RParen,
b'{' => TokenKind::LBrace,
b'}' => TokenKind::RBrace,
b'=' => TokenKind::Eq,
b'!' => TokenKind::Bang,
b'"' => {
while pos < bytes.len() && bytes[pos] != b'"' {
if !bytes[pos].is_ascii() || matches!(bytes[pos], b'\\' | b'\n' | b'\r')
{
return Err(Error::new(
"lex",
Span { start, end: pos },
"only the unescaped format string \"{}\" is supported",
));
}
pos += 1;
}
if pos == bytes.len() {
return Err(Error::new(
"lex",
Span { start, end: pos },
"unterminated string",
));
}
pos += 1;
TokenKind::String
}
_ => {
let ch = source[start..].chars().next().unwrap();
return Err(Error::new(
"lex",
Span {
start,
end: start + ch.len_utf8(),
},
format!("unexpected character '{ch}'"),
));
}
}
};
tokens.push(Token {
kind,
lexeme: source[start..pos].into(),
span: Span { start, end: pos },
});
}
tokens.push(Token {
kind: TokenKind::Eof,
lexeme: String::new(),
span: Span {
start: pos,
end: pos,
},
});
Ok(tokens)
}
}
fn main() {
if let Err(error) = run() {
eprintln!("{error}");
std::process::exit(1);
}
}
fn run() -> Result<(), String> {
const USAGE: &str = "usage: microrustc tokens FILE";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
let path = args.next().ok_or(USAGE)?;
if mode != "tokens" || args.next().is_some() {
return Err(USAGE.into());
}
let source = std::fs::read_to_string(&path).map_err(|error| format!("{path}: {error}"))?;
let tokens = syntax::lex(&source).map_err(|error| error.render(&path, &source))?;
print_tokens(&tokens);
Ok(())
}
fn print_tokens(tokens: &[syntax::Token]) {
for token in tokens {
println!(
"{:?} {:?} {}..{}",
token.kind, token.lexeme, token.span.start, token.span.end
);
}
}The command-line code reads one source file and prints each token's kind, spelling, and byte range. The scanner is the same one used in the excerpts above.
Put this short input in example.mrs. It gives us names, braces, and arithmetic to recognise:
fn main() {
let x: i32 = 5 + 3 * 2;
}The .mrs suffix marks this as a MicroRust input file. Its contents are valid Rust. Our lexer will only read the tokens; it won't calculate the value of x.
You'll need Rust installed. These commands use a macOS or Linux terminal; run them from the folder that contains microrust:
cd microrust
rustc main.rs -o microrustc
./microrustc tokens example.mrsSkip cd microrust if you're already in that folder. rustc builds main.rs into our compiler, microrustc. The next command runs it on example.mrs and asks for the tokens. We don't need an edition flag or any Cargo dependencies for this code.
After that first build, you can use just ./microrustc tokens example.mrs while changing the input. Rebuild whenever you change main.rs, including when you copy the next chapter's compiler. With the input copied exactly, including its final newline, the output is:
Fn "fn" 0..2
Ident "main" 3..7
LParen "(" 7..8
RParen ")" 8..9
LBrace "{" 10..11
Let "let" 16..19
Ident "x" 20..21
Colon ":" 21..22
I32 "i32" 23..26
Eq "=" 27..28
Int "5" 29..30
Plus "+" 31..32
Int "3" 33..34
Star "*" 35..36
Int "2" 37..38
Semicolon ";" 38..39
RBrace "}" 40..41
Eof "" 42..42The ranges count bytes from zero. Whitespace changes those numbers, so keep the sample's indentation when comparing the output. Without the final newline, the last line will read Eof "" 41..41. The + and * are still separate tokens; their grouping comes later.
You can also give this same input to Rust: run rustc --crate-name example example.mrs -o example-rust, then ./example-rust. Rust will warn that x is unused. The program exits successfully without printing anything, since it has no output statement. That checks the input's Rust syntax; the token list above comes from our compiler.
Try replacing + with @ in example.mrs and run ./microrustc tokens example.mrs again. The lexer should report the character and its location, then exit with an error. Restore the sample and keep both files for the next chapter.
We now have tokens and their source locations. Next we need to group them: which braces belong together, and why does * bind more tightly than +? We'll work through those questions in the parser and AST.