Capstone 1: the parser
The tokenizer of the previous lesson turned a document into a flat stream of tokens. The parser turns the stream into a value: a number, a string, a boolean, null, an array of values or an object of key and value pairs. Every value of a JSON document is built by the same four functions, and the grammar of the language is small enough to fit in one screen.
A recursive descent parser has one function per rule of the grammar. value looks at the next token and decides which rule to use, object and array call value again, and the recursion follows the nesting of the document. The parser keeps one index into the token vector and never looks back.
Each section is the whole program at that step, so the last section is the parser that the next lesson starts from.
An object and its keys
Value is an enum with one variant per kind of JSON value, and an object is a Vec of pairs rather than a map. That keeps the order of the keys, which the writer of lesson 126 needs for a round trip, and it is honest about the size of an object in a configuration file.
The parser holds the tokens and an index. peek reads without moving, next returns a token and moves, and the End token from the tokenizer means that both can be written without a bounds check.
#[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);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
fn main() {
for document in [r#"{"name": "rust", "stable": true, "version": 1.0, "extra": null}"#] {
match parse(document) {
Ok(value) => println!("{value:?}"),
Err(error) => println!("error: {error}"),
}
}
}
rustc --edition 2024 object.rs
./object
Object([("name", Text("rust")), ("stable", Bool(true)), ("version", Number(1.0)), ("extra", Null)])
The output is the debug format of the tree, which is the shortest proof that the parser built the right shape: every key is next to its value, and the four scalar kinds appear in the order of the document. The lesson on enums covers variants with data, and pattern matching covers the match in value.
peek().clone() copies the token before matching, which is cheap for the punctuation and a string copy for the text and number tokens. A parser that wanted to avoid the copy would match on a reference and clone only the data it keeps; the shape here is the one to start with, because it keeps the borrow checker out of the grammar.
Arrays and nesting
An array adds one arm to value and one function next to object. The two containers are the only recursive rules, and both call value, which is what makes {"a": [1, {"b": 2}]} parse with the same code as a flat document.
The program parses a document with both containers and an empty array. The empty case is written before the loop in each function, because a loop that expects at least one element cannot handle [] or {}.
#[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);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
fn main() {
for document in [
r#"{"name": "rust", "tags": ["fast", "safe"], "nested": {"ok": true}}"#,
r#"[]"#,
] {
match parse(document) {
Ok(value) => println!("{value:?}"),
Err(error) => println!("error: {error}"),
}
}
}
rustc --edition 2024 parser.rs
./parser
Object([("name", Text("rust")), ("tags", Array([Text("fast"), Text("safe")])), ("nested", Object([("ok", Bool(true))]))])
Array([])
The nesting of the output follows the nesting of the document, and the recursion in the code follows it in the same way. A document nested a thousand levels deep would recurse a thousand times on the stack, which is the limit a parser for untrusted input has to impose for itself; the lesson on recursion covers the stack frames.
A parser is also a place where the cost is visible: every value of the document becomes one Value on the heap, inside a Vec, and a large document spends its time in allocation rather than in the scan. That is the price of a tree that outlives the text, and a program that only reads a field or two should stream the tokens instead of building the whole value. The order of the arms in value does not matter, because the tokens are disjoint. The order of the checks inside object does: the key comes first, then the colon, then the value, then either a comma or the closing brace.
The token that breaks the grammar
Every function returns Result, and every unexpected token is an error with the token that was found. That is what makes the parser useful: a message that names the token is enough to find the missing comma in a configuration file.
The program parses two broken objects. The first is missing the comma between two fields and the second has a comma before the closing brace, which JSON does not allow.
#[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);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
fn main() {
for document in [r#"{"name": "rust" "version": 1.0}"#, r#"{"version": 1.0,}"#] {
match parse(document) {
Ok(value) => println!("{value:?}"),
Err(error) => println!("error: {error}"),
}
}
}
rustc --edition 2024 missing.rs
./missing
error: expected a comma, found Text("version")
error: expected a key, found CloseBrace
The first message names the field that arrived where a comma belonged. The second says that a key was expected, which is exactly what a trailing comma leaves: the parser has read the comma and now wants a string. A message with the byte position from the tokenizer would be better still, and the lesson on error types shows the structure that carries it.
The parser reports the first error and stops, which is the right choice for a configuration file: a reader fixes that one and runs the program again. A compiler would collect several errors, and the loop that does it needs a way to skip to the next comma or brace, which is a much larger design.
The document that stops too early
A truncated file is the common case for a parser that reads a document written by a program that crashed halfway. The End token turns it into an ordinary error rather than an index out of bounds, and the object rule says so with a message of its own.
The program parses an array that closes with a brace and an object with no closing brace at all.
#[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);
}
}
#[derive(Debug, Clone, PartialEq)]
enum Value {
Null,
Bool(bool),
Number(f64),
Text(String),
Array(Vec<Value>),
Object(Vec<(String, Value)>),
}
struct Parser {
tokens: Vec<Token>,
position: usize,
}
impl Parser {
fn new(tokens: Vec<Token>) -> Parser {
Parser { tokens, position: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.position]
}
fn next(&mut self) -> Token {
let token = self.tokens[self.position].clone();
self.position += 1;
token
}
fn value(&mut self) -> Result<Value, String> {
match self.peek().clone() {
Token::OpenBrace => self.object(),
Token::OpenBracket => self.array(),
Token::Text(text) => {
self.next();
Ok(Value::Text(text))
}
Token::Number(number) => {
self.next();
Ok(Value::Number(number))
}
Token::Word(word) => {
self.next();
match word.as_str() {
"true" => Ok(Value::Bool(true)),
"false" => Ok(Value::Bool(false)),
"null" => Ok(Value::Null),
other => Err(format!("unknown word {other}")),
}
}
other => Err(format!("expected a value, found {other:?}")),
}
}
fn array(&mut self) -> Result<Value, String> {
self.next();
let mut items = Vec::new();
if matches!(self.peek(), Token::CloseBracket) {
self.next();
return Ok(Value::Array(items));
}
loop {
let value = self.value()?;
items.push(value);
match self.next() {
Token::Comma => continue,
Token::CloseBracket => return Ok(Value::Array(items)),
Token::End => return Err("document ended inside an array".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
fn object(&mut self) -> Result<Value, String> {
self.next();
let mut fields = Vec::new();
if matches!(self.peek(), Token::CloseBrace) {
self.next();
return Ok(Value::Object(fields));
}
loop {
let key = match self.next() {
Token::Text(text) => text,
other => return Err(format!("expected a key, found {other:?}")),
};
match self.next() {
Token::Colon => {}
other => return Err(format!("expected a colon, found {other:?}")),
}
let value = self.value()?;
fields.push((key, value));
match self.next() {
Token::Comma => continue,
Token::CloseBrace => return Ok(Value::Object(fields)),
Token::End => return Err("document ended inside an object".to_string()),
other => return Err(format!("expected a comma, found {other:?}")),
}
}
}
}
fn parse(text: &str) -> Result<Value, String> {
let tokens = tokenize(text)?;
let mut parser = Parser::new(tokens);
let value = parser.value()?;
match parser.peek() {
Token::End => Ok(value),
other => Err(format!("trailing token {other:?}")),
}
}
fn main() {
for document in [r#"{"a": [1, 2}"#, r#"{"a": 1"#] {
match parse(document) {
Ok(value) => println!("{value:?}"),
Err(error) => println!("error: {error}"),
}
}
}
rustc --edition 2024 unclosed.rs
./unclosed
error: expected a comma, found CloseBrace
error: document ended inside an object
The first document ends with the wrong bracket and the array rule reports it as a missing comma, because a closing brace is neither a comma nor a bracket. The second document runs out of tokens and the object rule has a message for that case alone.
The next lesson replaces the debug print with accessors and a readable form, and the writer of lesson 126 turns the same tree back into text. The debug format stays useful for exactly the reason it appears here: it shows the shape of the tree without a single line of formatting code.
Exercises
- Add the byte position to the parser errors and print it with each message.
- Accept a trailing comma in an array and decide whether the same rule should apply to an object.
- Add a depth counter to Parser and refuse a document nested more than sixty-four levels deep.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a recursive descent parser have one function per?
Answer
Rule of the grammar
Each rule of the grammar becomes a function that calls the functions of the rules it uses.
-
Why does
Valuestore an object as a vector of pairs?Answer
The order of the keys is kept, which the writer needs for a round trip
The vector keeps the document order, and a map would lose it.
-
Why is the empty container checked before the parsing loop?
Answer
A loop that expects one element cannot handle
[]or{}The first iteration would read the closing bracket as a value and fail.
-
What is the role of the
Endtoken in the parser?Answer
It lets the parser report a truncated document instead of indexing past the end
Every rule can look at a token, and End becomes an ordinary error message.
-
What does the parser do with the first error it finds?
Answer
It returns it and stops, which is enough for a configuration file
The Result carries one error and the caller reports it; recovery is a larger design.
-
What does this program print?
#[derive(Debug)] enum Value { Number(f64), Text(String), Array(Vec<Value>), } fn main() { let value = Value::Array(vec![ Value::Number(1.0), Value::Text("two".to_string()), Value::Array(vec![]), ]); match &value { Value::Array(items) => println!("{} {}", items.len(), matches!(items[2], Value::Array(_))), _ => println!("not an array"), } }Answer
3 true
The array holds three values and the third one is an empty array.
-
What does this program print?
fn parse_pair(tokens: &[&str], position: &mut usize) -> Result<(String, String), String> { let key = tokens.get(*position).ok_or("expected a key")?; *position += 1; let colon = tokens.get(*position).ok_or("expected a colon")?; if *colon != ":" { return Err(format!("expected a colon, found {colon}")); } *position += 1; let value = tokens.get(*position).ok_or("expected a value")?; *position += 1; Ok((key.to_string(), value.to_string())) } fn main() { let tokens = ["name", ":", "rust"]; let mut position = 0; println!("{:?}", parse_pair(&tokens, &mut position)); println!("{:?}", parse_pair(&tokens, &mut position)); }Answer
Ok(("name", "rust")) / Err("expected a key")
The first call consumes all three tokens and the second finds the slice empty.
-
What does this program print?
#[derive(Debug, Clone, PartialEq)] enum Token { Open, Close, Text(String), End, } fn parse(tokens: &[Token]) -> Result<String, String> { match tokens.first() { Some(Token::Open) => match tokens.get(2) { Some(Token::Close) => Ok("object".to_string()), _ => Err("no close".to_string()), }, Some(Token::Text(text)) => Ok(text.clone()), Some(Token::End) => Err("end".to_string()), None => Err("empty".to_string()), _ => Err("unexpected".to_string()), } } fn main() { println!("{:?}", parse(&[Token::Open, Token::Text("a".to_string())])); println!("{:?}", parse(&[])); }Answer
Err("no close") / Err("empty")
The second token of the first call is not Close, and the empty slice has no first token.
-
What does this program print?
#[derive(Debug)] enum Value { Number(f64), Text(String), Object(Vec<(String, Value)>), } fn main() { let fields = vec![ ("a".to_string(), Value::Number(1.0)), ("b".to_string(), Value::Text("x".to_string())), ]; let object = Value::Object(fields); if let Value::Object(pairs) = &object { let names: Vec<&str> = pairs.iter().map(|(name, _)| name.as_str()).collect(); println!("{}", names.join(",")); } }Answer
a,b
The pairs keep their order and join inserts the comma between the names.
-
What is the first line of the compiler output for this program?
enum Value { Number(f64), Text(String), } fn main() { let value = Value::Number(1.0); println!("{}", value.len()); }Answer
error[E0599]: no method named
lenfound for enumValuein the current scopeAn enum has no length, and the method does not exist on the type.
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
