Capstone 1: a JSON tokenizer
The first capstone is a JSON reader and writer in five lessons. It starts here, with the layer that turns text into tokens, and each lesson adds a layer on top: the parser builds a tree, the value type stores it, the writer prints it and the tests check all of it.
A lexer reads the document once, left to right, and emits a token for every punctuation mark, string, number or word. The parser of the next lesson never looks at a character again, which is the point of the split: the hard byte-level questions (where a string ends, what an escape means, where a number stops) are answered in one place.
Every section below is the whole program at that step, built with rustc and run on the documents in its main. By the last section the file is the lexer that the parser lesson starts from.
The token type and the loop
A token is a variant of an enum with the data it carries: a string holds its decoded text, a number holds the value, and the punctuation holds nothing. The end marker is part of the stream on purpose, so the parser can stop on it without a special case for the end of the buffer.
The loop is the whole shape of a lexer: skip whitespace, look at one byte, consume what belongs to the token, repeat. The program scans a short array of numbers and prints each token with the debug format.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Number(f64),
End,
}
fn tokenize(text: &str) -> Vec<Token> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return tokens;
}
let start = position;
let token = match bytes[position] {
b'{' => { position += 1; Token::OpenBrace }
b'}' => { position += 1; Token::CloseBrace }
b'[' => { position += 1; Token::OpenBracket }
b']' => { position += 1; Token::CloseBracket }
b':' => { position += 1; Token::Colon }
b',' => { position += 1; Token::Comma }
b'-' | b'0'..=b'9' => {
while position < bytes.len()
&& matches!(bytes[position], b'0'..=b'9' | b'-' | b'+' | b'.' | b'e' | b'E')
{
position += 1;
}
let slice = std::str::from_utf8(&bytes[start..position]).unwrap();
Token::Number(slice.parse().unwrap())
}
_ => break,
};
tokens.push(token);
}
tokens.push(Token::End);
tokens
}
fn main() {
let document = "[1, 2.5, -3]";
for token in tokenize(document) {
println!("{token:?}");
}
}
rustc --edition 2024 tokens.rs
./tokens
OpenBracket
Number(1.0)
Comma
Number(2.5)
Comma
Number(-3.0)
CloseBracket
End
Every arm advances position itself, and the number arm advances it in a loop. The first version of this file advanced it once more after the match, which silently skipped the byte after every number: the commas disappeared from the output above and the parser would have accepted [1 2]. Keeping the advance inside each arm is the rule that makes that class of bug impossible.
f64 is the type of a JSON number, and the parse is unchecked in this section because the byte loop has already decided that the slice looks like a number. The fourth section makes that check explicit. The lesson on bytes covers the byte view of a string that the loop uses.
Strings and their escapes
A string is the only token whose end depends on its content. The reader consumes the opening quote, copies bytes until the closing quote, and turns a backslash plus a letter into the character it stands for, so the token carries the decoded text rather than the source text.
The document below holds a message with an escaped quote and a newline. The printed token shows the decoded value with the escapes that the debug format puts back.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
Colon,
Text(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Token {
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
_ => value.push(\'?\'),
}
} else {
value.push(byte as char);
}
*position += 1;
}
*position += 1;
Token::Text(value)
}
fn tokenize(text: &str) -> Vec<Token> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return tokens;
}
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\':\' => { position += 1; Token::Colon }
b\'"' => text_token(bytes, &mut position),
_ => break,
};
tokens.push(token);
}
tokens.push(Token::End);
tokens
}
fn main() {
let document = r#"{"msg": "a \"b\"\n"}"#;
for token in tokenize(document) {
println!("{token:?}");
}
}
rustc --edition 2024 text.rs
./text
OpenBrace
Text("msg")
Colon
Text("a \"b\"\n")
CloseBrace
End
The newline in the source is two characters, a backslash and an n, and the token holds the single newline character the escape means. A reader that copies the bytes without decoding would hand the parser a string with a literal backslash in it, and the writer would escape it a second time.
The four escapes of JSON are \", \\, \n and \t. The last section adds \u with its four hex digits, which needs the character type rather than a byte push, and returns an error for an escape that is not one of them. The lesson on UTF-8 explains why a decoded character may take more than one byte.
Numbers and words
A bare word in JSON is one of three: true, false and null. The lexer does not decide which one it is; it reads the letters and lets the parser match the word, because a document with an unknown word should be reported by the layer that knows the grammar.
The program scans an array with the three words and one number, so the output shows the same token type three times next to a number.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBracket,
CloseBracket,
Comma,
Word(String),
Number(f64),
End,
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Vec<Token> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return tokens;
}
let start = position;
let token = match bytes[position] {
b'[' => { position += 1; Token::OpenBracket }
b']' => { position += 1; Token::CloseBracket }
b',' => { position += 1; Token::Comma }
b'a'..=b'z' => word_token(bytes, &mut position),
b'-' | b'0'..=b'9' => {
while position < bytes.len()
&& matches!(bytes[position], b'0'..=b'9' | b'-' | b'+' | b'.')
{
position += 1;
}
let slice = std::str::from_utf8(&bytes[start..position]).unwrap();
Token::Number(slice.parse().unwrap())
}
_ => break,
};
tokens.push(token);
}
tokens.push(Token::End);
tokens
}
fn main() {
let document = "[true, false, null, 42]";
for token in tokenize(document) {
println!("{token:?}");
}
}
rustc --edition 2024 words.rs
./words
OpenBracket
Word("true")
Comma
Word("false")
Comma
Word("null")
Comma
Number(42.0)
CloseBracket
End
The number arm stops at the first byte that cannot be part of a number, which is why the comma after 42 is a token of its own. A number followed by a letter, as in 42x, produces a number and then a word, and it is the parser that rejects the pair when it expects a comma.
The matches! macro keeps the character class readable, and the lesson on macros explains the repetition behind it. The word arm is the place to add the letters JSON does not use, and a lexer that rejects them early gives a better message than a parser that expects a value.
The character it cannot read
The full lexer returns a Result, so every reader can fail with a message and a position instead of panicking. Three failures are worth reporting: a character that starts no token, a string that never closes, and an escape that is not one of the five.
The program scans three documents: a good object, one with an at sign and one with an unterminated string. The good one prints a count and the other two print the error and the position where the scan stopped.
#[derive(Debug, Clone, PartialEq)]
enum Token {
OpenBrace,
CloseBrace,
OpenBracket,
CloseBracket,
Colon,
Comma,
Text(String),
Number(f64),
Word(String),
End,
}
fn text_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
*position += 1;
let mut value = String::new();
while *position < bytes.len() && bytes[*position] != b'"\' {
let byte = bytes[*position];
if byte == b\'\\\' {
*position += 1;
match bytes.get(*position) {
Some(b\'"') => value.push('"\'),
Some(b\'\\\') => value.push(\'\\\'),
Some(b\'n\') => value.push(\'\n\'),
Some(b\'t\') => value.push(\'\t\'),
Some(b\'u\') => {
let digits = bytes.get(*position + 1..*position + 5)
.ok_or_else(|| format!("short unicode escape at {}", *position))?;
let hex = std::str::from_utf8(digits)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
let code = u32::from_str_radix(hex, 16)
.map_err(|_| format!("bad unicode escape at {}", *position))?;
value.push(char::from_u32(code)
.ok_or_else(|| format!("bad code point at {}", *position))?);
*position += 4;
}
_ => return Err(format!("bad escape at {}", *position)),
}
} else {
value.push(byte as char);
}
*position += 1;
}
if *position == bytes.len() {
return Err(format!("unterminated text at {start}"));
}
*position += 1;
Ok(Token::Text(value))
}
fn number_token(bytes: &[u8], position: &mut usize) -> Result<Token, String> {
let start = *position;
while *position < bytes.len()
&& matches!(bytes[*position], b\'0\'..=b\'9\' | b\'-\' | b\'+\' | b\'.\' | b\'e\' | b\'E\')
{
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
match slice.parse() {
Ok(value) => Ok(Token::Number(value)),
Err(_) => Err(format!("bad number at {start}")),
}
}
fn word_token(bytes: &[u8], position: &mut usize) -> Token {
let start = *position;
while *position < bytes.len() && bytes[*position].is_ascii_alphabetic() {
*position += 1;
}
let slice = std::str::from_utf8(&bytes[start..*position]).unwrap();
Token::Word(slice.to_string())
}
fn tokenize(text: &str) -> Result<Vec<Token>, String> {
let bytes = text.as_bytes();
let mut position = 0;
let mut tokens = Vec::new();
loop {
while position < bytes.len() && bytes[position].is_ascii_whitespace() {
position += 1;
}
if position == bytes.len() {
tokens.push(Token::End);
return Ok(tokens);
}
let start = position;
let token = match bytes[position] {
b\'{\' => { position += 1; Token::OpenBrace }
b\'}\' => { position += 1; Token::CloseBrace }
b\'[\' => { position += 1; Token::OpenBracket }
b\']\' => { position += 1; Token::CloseBracket }
b\':\' => { position += 1; Token::Colon }
b\',\' => { position += 1; Token::Comma }
b\'"' => text_token(bytes, &mut position)?,
b'-' | b'0'..=b'9' => number_token(bytes, &mut position)?,
b'a'..=b'z' => word_token(bytes, &mut position),
other => return Err(format!("unexpected character \'{}\' at {start}", other as char)),
};
tokens.push(token);
}
}
fn main() {
for document in [r#"{"a": [1, true]}"#, r#"{"a": @}"#, r#""open"#] {
match tokenize(document) {
Ok(tokens) => println!("{} tokens", tokens.len()),
Err(error) => println!("error: {error}"),
}
}
}
rustc --edition 2024 lexer.rs
./lexer
10 tokens
error: unexpected character '@' at 6
error: unterminated text at 0
The position is a byte offset, which is what a text editor needs to put the cursor on the character and what a compiler prints in its own diagnostics. The at sign is the seventh byte of {"a": @}, and the string that never closes reports the position of its opening quote.
The ? after each reader is the whole error path: a failure inside text_token leaves tokenize with the same message, and no layer has to know which reader failed. The lesson on Result covers the operator, and the next lesson takes this Vec<Token> and builds a tree out of it.
Exercises
- Add a Position field to every token and print it with the token.
- Make a document with a \u00e9 escape and print the decoded character.
- Add a check that rejects a second decimal point in one number with a message of its own.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does the token stream end with an
Endmarker?Answer
The parser can stop on a token instead of checking the buffer length
Every reader can assume a token exists and stop on End, which removes a special case.
-
What does a
Texttoken hold?Answer
The decoded string, with escapes already turned into characters
The lexer is the layer that understands escapes, so the parser sees plain text.
-
Why does the lexer emit a
Wordinstead ofBoolandNull?Answer
The lexer does not know the grammar, so the parser decides which word is valid
The token layer reports what it read and leaves the meaning to the layer above.
-
What is the position in a lexer error?
Answer
The byte offset where the scan stopped
The loop counts bytes, so the offset is what it can report without a second pass.
-
Why must every match arm advance the position itself?
Answer
Because a shared advance after the match skips the byte after a multi-byte token
A number arm already moved the position, so one more step would eat the next byte.
-
What does this program print?
#[derive(Debug)] enum Token { Open, Close, End, } fn tokenize(text: &str) -> Vec<Token> { let mut tokens = Vec::new(); for byte in text.bytes() { match byte { b'[' => tokens.push(Token::Open), b']' => tokens.push(Token::Close), _ => {} } } tokens.push(Token::End); tokens } fn main() { for token in tokenize("[[]]") { println!("{token:?}"); } }Answer
Open / Open / Close / Close / End
The loop walks the bytes in order, so the nested pair opens twice before it closes.
-
What does this program print?
fn main() { let text = "1, 22, 333"; let mut position = 0; let bytes = text.as_bytes(); let mut count = 0; while position < bytes.len() { if bytes[position].is_ascii_digit() { while position < bytes.len() && bytes[position].is_ascii_digit() { position += 1; } count += 1; } else { position += 1; } } println!("{count}"); }Answer
3
Each run of digits is counted once: one, twenty-two and three hundred thirty-three.
-
What does this program print?
fn main() { let text = r#"a\nb"#; let mut value = String::new(); let mut bytes = text.bytes(); while let Some(byte) = bytes.next() { if byte == b'\\' { if let Some(next) = bytes.next() { if next == b'n' { value.push('\n'); } } } else { value.push(byte as char); } } println!("{}", value.lines().count()); }Answer
2
The escape becomes a real newline, so the string has two lines.
-
What does this program print?
fn scan(text: &str) -> Result<usize, String> { let bytes = text.as_bytes(); let mut position = 0; while position < bytes.len() { if bytes[position] == b'"' { position += 1; while position < bytes.len() && bytes[position] != b'"' { position += 1; } if position == bytes.len() { return Err(format!("open at {}", position - 1)); } } position += 1; } Ok(position) } fn main() { println!("{:?}", scan(r#"{"a"}"#)); println!("{:?}", scan(r#""abc"#)); }Answer
Ok(5) / Err("open at 3")
The closed string ends the scan at the length of the text, and the open one reports its start.
-
What is the first line of the compiler output for this program?
fn tokenize(text: &str) -> Vec<u8> { let mut tokens = Vec::new(); for byte in text.bytes() { tokens.push(&byte); } tokens } fn main() { println!("{:?}", tokenize("ab")); }Answer
error[E0308]: mismatched types
Indexing a vector gives a reference, and a reference cannot be added to a byte.
The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev
