pub fn expression(){
...
self.primary()
...
}
fn primary(){
...
}And by the way, as a token of my appreciation, I would like to offer you a discount.
At this point of the challenge, we introduce another important component of an interpreter: the parser.
Parsers are interesting beasts. I agree with Robert Nystrom when he says you don't need to know everything that has been discovered about compilers in the past 60 years to create a decent parser. At the same time, as soon as you start working on it, you have to face problems like ambiguity, the direction of parsing, and precedence between rules.
So, while the game is far from being impossible to play, its complexity clearly increases. As usual, the CodeCrafters challenge will guide us step by step while we write a parser for expressions following the strategy shown in "Crafting Interpreters", and the size of every step is small enough to be understandable and leave the system in a working state.
In the very first step we need to be able to parse the reserved word tokens true, false, and nil, and for the time being the challenge tests will contain a single token.
As we learn in Nystrom's book, this type of parser is implemented through recursive function calls: the main function expression calls equality, which in turn calls comparison, which in turn calls term, and so on. This means that expression is actually the entry point of the whole process. Therefore, it is worth implementing it straight away and progressively changing its code to call the functions we need. This will keep the API stable and require fewer changes to the tests. So, in the first step expression will call primary:
pub fn expression(){
...
self.primary()
...
}
fn primary(){
...
}Later, when we implement unary, we will change the call structure to:
pub fn expression(){
...
self.unary()
...
}
fn unary(){
...
self.primary()
...
}
fn primary(){
...
}Let's start, as we often do, with the definition of a new type that we will use to represent syntax trees.
src/parser.rs use std::fmt;
#[derive(Debug, PartialEq, Eq)]
pub enum Literal {
Boolean(bool),
Nil,
}
impl fmt::Display for Literal {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Boolean(b) => write!(f, "{b}"),
Self::Nil => f.write_str("nil"),
}
}
}
#[derive(Debug, PartialEq, Eq)]
pub enum Expression {
Literal(Literal),
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name: String = match self {
Self::Literal(s) => s.to_string(),
};
write!(f, "{}", name)
}
}We can also directly add a structure Parser that will contain the parsing logic. While a scanner is a pure iterator with look-ahead functions, a parser is more complicated and we might need to trace back our steps to undo actions. It is therefore worth storing tokens as a vector and keeping track of the current index in a variable.
src/parser.rs use crate::token::{Keyword, Token, TokenType};
pub struct Parser {
// The list of tokens generated by
// the scanner.
pub tokens: Vec<Token>,
// The index of the current token
// in the tokens vector.
pub index: usize,
}To interact with the current token and the index we can implement a helper function. The idea is that, as it happened with the scanner, we need to constantly check if we reached the end of the input, and for that there is no better data type than Option, which is conveniently returned by Vec::get.
src/parser.rs impl Parser {
// Return the current token as an Option.
fn current_token(&self) -> Option<&Token> {
self.tokens.get(self.index)
}
}It's time to implement the function primary that identifies booleans and nil. There is nothing too complicated here, we just have to convert instances of Token into instances of Expression.
src/parser.rs impl Parser {
// Parse the current token and try to
// identify a primary element.
//
// primary -> "true" | "false" | "nil"
fn primary(&mut self) -> Option<Expression> {
// If the current token is None return None.
let c: &Token = self.current_token()?;
// Check the type of the current token.
let result = match &c.ttype {
TokenType::Reserved(s) => match s {
Keyword::True => Expression::Literal(Literal::Boolean(true)),
Keyword::False => Expression::Literal(Literal::Boolean(false)),
Keyword::Nil => Expression::Literal(Literal::Nil),
_ => return None,
},
_ => {
eprintln!("Invalid token {}", c);
return None;
}
};
// If we reach this point, the token we
// found was valid. Advance the index.
self.index += 1;
// Return the token as an Option.
Some(result)
}Since the parser is recursive, when primary returns None the process is interrupted. There is an interesting discussion in Nystrom's book regarding panic mode and synchronisation, but for the time being the CodeCrafters challenge doesn't require any effort in that direction.
As explained at the beginning, in this initial version the entry point is represented by the method expression, which calls primary directly.
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.primary()
}Naturally, all these data types and methods can and should be tested.
src/parser.rs #[cfg(test)]
mod tests {
use crate::token::TokenLiteral;
use super::*;
fn dummy_token(ttype: TokenType) -> Token {
Token {
ttype,
lexeme: String::new(),
literal: TokenLiteral::Null,
}
}
#[test]
// Test that the method `current_token`
// returns the correct value.
fn test_current_token() {
let tokens = vec![dummy_token(TokenType::Identifier)];
let parser = Parser { tokens, index: 0 };
assert_eq!(
parser.current_token(),
Some(&dummy_token(TokenType::Identifier))
);
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains reserved word `true`.
fn test_primary_true() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::True)),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Boolean(true))));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains reserved word `false`.
fn test_primary_false() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::False)),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Boolean(false))));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains reserved word `nil`.
fn test_primary_nil() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::Nil)),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Nil)));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains a reserved word that is
// currently unknown.
fn test_primary_unknown_reserved() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::Class)),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, None);
assert_eq!(parser.index, 0);
}
}Finally, we need to implement the command parse in main. The code is mostly copied from tokenize, as we need to create the tokens first. There are ways to implement this without code duplication, but for now copying the code doesn't look that harmful. Please note that the code is not exactly the same. The command tokenize prints all tokens on the standard output, while parse needs to store them in a vector for the parsing process.
src/main.rs use std::env;
use std::fs;
use std::process;
use crate::token::TokenResult;
use crate::parser::Parser;
use crate::token::{Token, TokenResult};
use crate::tokenizer::tokenize;
mod parser;
mod token;
mod tokenizer;
fn main() {
match command.as_str() {
"tokenize" => {
...
}
"parse" => {
// Open the input file and read the content
let file_contents = fs::read_to_string(filename).unwrap_or_else(|_| {
eprintln!("Failed to read file {}", filename);
String::new()
});
let mut errors: bool = false;
// Process the file and extract the
// token results.
let results: Vec<TokenResult> = tokenize(file_contents.chars().peekable());
let mut tokens: Vec<Token> = Vec::new();
// Iterate through the results and store
// them or print them on the stderr according
// to their nature.
for result in results {
match result {
Ok(token) => tokens.push(token),
Err(e) => {
eprintln!("{}", e);
errors = true;
}
}
}
// In case there were errors
// exit with a specific code.
if errors {
process::exit(65);
}
let mut p = Parser { tokens, index: 0 };
match p.expression() {
Some(v) => println!("{}", v),
None => panic!(),
}
}
_ => {
eprintln!("Unknown command: {}", command);
}Stage 1 - Booleans & Nil
This version of the code passes Stage 1 of the extension "Parsing Expressions".
The addition of number literals to the set of parsed elements doesn't represent a big challenge. Numbers are terminals (see 5.1.1 - Rules for grammars in "Crafting Interpreters"), so we can represent them using Expression::Literal as we did for booleans and nil.
To do that, however, we first have to add a variant of Literal itself.
src/parser.rs #[derive(Debug, PartialEq, Eq)]
#[derive(Debug, PartialEq)]
pub enum Literal {
Boolean(bool),
Nil,
Number(f64),
}
impl fmt::Display for Literal {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Boolean(b) => write!(f, "{b}"),
Self::Nil => f.write_str("nil"),
Self::Number(n) => write!(f, "{n}"),
}
}
}
#[derive(Debug, PartialEq, Eq)]
#[derive(Debug, PartialEq)]
pub enum Expression {
Literal(Literal),
}As happened for TokenLiteral, the introduction of an f64 forces us to drop the trait Eq. In Parser::primary, we need to extract the content of the token's literal, which is the actual f64 corresponding to the number that we are parsing, and this means that we need to change the match construct a little to look at the token type and the literal value at the same time:
src/parser.rs use crate::token::{Keyword, Token, TokenType};
use crate::token::{Keyword, Token, TokenLiteral, TokenType};
impl Parser {
// Parse the current token and try to
// identify a primary element.
//
// primary -> "true" | "false" | "nil"
// primary -> NUMBER | "true" | "false" | "nil"
fn primary(&mut self) -> Option<Expression> {
// Check the type of the current token.
let result = match &c.ttype {
TokenType::Reserved(s) => match s {
let result = match (&c.ttype, &c.literal) {
(TokenType::Number, TokenLiteral::Number(n)) => {
Expression::Literal(Literal::Number(*n))
}
(TokenType::Reserved(s), _) => match s {
Keyword::True => Expression::Literal(Literal::Boolean(true)),
Keyword::False => Expression::Literal(Literal::Boolean(false)),
Keyword::Nil => Expression::Literal(Literal::Nil),
_ => return None,
},
_ => {
eprintln!("Invalid token {}", c);
return None;
}
};
The new piece of logic can be obviously tested:
src/parser.rs mod tests {
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains an integer number.
fn test_primary_number_integer() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Number(123.0))));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains a float number.
fn test_primary_number_float() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Number(123.4))));
assert_eq!(parser.index, 1);
}There is a problem in the CodeCrafters tests, however. The current implementation of Literal::fmt represents integers without decimals, while the Lox convention (and therefore the challenge) wants integers to have a .0 decimal. This can be solved directly in the implementation of Display:
src/parser.rs impl fmt::Display for Literal {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Boolean(b) => write!(f, "{b}"),
Self::Nil => f.write_str("nil"),
Self::Number(n) if n.fract() == 0.0 => write!(f, "{n:.1}"),
Self::Number(n) => write!(f, "{n}"),
}
}
}Normally, the implementation of fmt::Display doesn't require tests, but in this case there is some business logic that we want to verify:
src/parser.rs mod tests {
#[test]
// Test that integer numbers are displayed
// correctly with a decimal part of `.0`.
fn test_literal_display_integer_number() {
assert_eq!(Literal::Number(42.0).to_string(), "42.0");
}
#[test]
// Test that float numbers are displayed
// correctly with a decimal part.
fn test_literal_display_decimal_number() {
assert_eq!(Literal::Number(42.5).to_string(), "42.5");
}Stage 2 - Number literals
This version of the code passes Stage 2 of the extension "Parsing Expressions".
What we have done with number literals can be replicated almost verbatim when dealing with string literals. Strings, like numbers, are terminals, so they end up being represented by Expression::Literal as well. To do that, however, we first need to introduce them as a variant of Literal:
src/parser.rs #[derive(Debug, PartialEq)]
pub enum Literal {
Boolean(bool),
Nil,
Number(f64),
String(String),
}
impl fmt::Display for Literal {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::Boolean(b) => write!(f, "{b}"),
Self::Nil => f.write_str("nil"),
Self::Number(n) if n.fract() == 0.0 => write!(f, "{n:.1}"),
Self::Number(n) => write!(f, "{n}"),
Self::String(s) => f.write_str(s),
}
}
}At this point we can change Parser::primary to introduce the new element.
src/parser.rs impl Parser {
// Parse the current token and try to
// identify a primary element.
//
// primary -> NUMBER | "true" | "false" | "nil"
// primary -> NUMBER | STRING | "true" | "false" | "nil"
fn primary(&mut self) -> Option<Expression> {
// Check the type of the current token.
let result = match (&c.ttype, &c.literal) {
(TokenType::Number, TokenLiteral::Number(n)) => {
Expression::Literal(Literal::Number(*n))
}
(TokenType::Reserved(s), _) => match s {
Keyword::True => Expression::Literal(Literal::Boolean(true)),
Keyword::False => Expression::Literal(Literal::Boolean(false)),
Keyword::Nil => Expression::Literal(Literal::Nil),
_ => return None,
},
(TokenType::String, TokenLiteral::String(s)) => {
Expression::Literal(Literal::String(s.to_string()))
}
_ => {
eprintln!("Invalid token {}", c);
return None;
}
};And we can write a test for the new logic.
src/parser.rs mod tests {
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains a string.
fn test_primary_string() {
let tokens = vec![
Token {
ttype: TokenType::String,
lexeme: String::new(),
literal: TokenLiteral::String(String::from("Some string")),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(
result,
Some(Expression::Literal(Literal::String(String::from(
"Some string"
))))
);
assert_eq!(parser.index, 1);
}Stage 3 - String literals
This version of the code passes Stage 3 of the extension "Parsing Expressions".
Parentheses are the first nonterminal we encounter in our parser. While the two brackets ( and ) are single characters, they surround another symbol, which might or might not be a terminal itself.
A good strategy to parse this type of nonterminal is to go through the following steps:
(.).To support the first and the last actions we can create two methods. The first skips the current token, unless it's the Eof:
src/parser.rs impl Parser {
// Skip the current token, unless
// we already reached the end.
fn consume(&mut self) {
if self
.current_token()
.is_some_and(|t| t.ttype != TokenType::Eof)
{
self.index += 1;
}
}As you can see, an idiomatic way to check the token and conditionally skip it is to process the Option returned by current_token with is_some_and [docs], which adds a condition to the check.
The tests for this function are:
src/parser.rs mod tests {
#[test]
// Test that consuming a token makes the
// next one the current token.
fn test_consume() {
let tokens = vec![
dummy_token(TokenType::Identifier),
dummy_token(TokenType::Plus),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
parser.consume();
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Plus)));
}
#[test]
// Test that consuming `Eof` doesn't move
// the index and keeps the current
// token unchanged.
fn test_consume_end() {
let tokens = vec![dummy_token(TokenType::Eof)];
let mut parser = Parser { tokens, index: 0 };
parser.consume();
parser.consume();
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Eof)));
}
#[test]
// Test that consuming an empty list of
// tokens just returns `None`.
fn test_consume_empty() {
let mut parser = Parser {
tokens: vec![],
index: 0,
};
parser.consume();
assert_eq!(parser.current_token(), None);
}Second, we can create a method that checks if a token matches a given type and is not Eof. This time, we can use Option::filter [docs] that processes every Some(t) value through the given predicate.
src/parser.rs impl Parser {
// Check if the type of the current token
// corresponds to the given `TokenType` variant.
// `Option::filter` returns `Some` only when
// the condition is satisfied.
// So, in this case, only if the current token
// is not `Eof` and if there is a match between
// the current token and the given token type.
fn check_current(&self, token_type: &TokenType) -> Option<&Token> {
self.current_token()
.filter(|t| t.ttype != TokenType::Eof && t.ttype == *token_type)
}The tests for this method are the following:
src/parser.rs mod tests {
#[test]
fn test_check_current_true() {
let tokens = vec![dummy_token(TokenType::Plus)];
let parser = Parser { tokens, index: 0 };
assert_eq!(
parser.check_current(&TokenType::Plus),
Some(dummy_token(TokenType::Plus)).as_ref()
);
assert_eq!(parser.index, 0);
}
#[test]
fn test_check_current_false() {
let tokens = vec![dummy_token(TokenType::Plus)];
let parser = Parser { tokens, index: 0 };
assert_eq!(parser.check_current(&TokenType::Number), None);
assert_eq!(parser.index, 0);
}
#[test]
fn test_check_current_end() {
let tokens = vec![dummy_token(TokenType::Eof)];
let parser = Parser { tokens, index: 0 };
// If we reached the end of the token sequence
// we return `None` without checking the type.
assert_eq!(parser.check_current(&TokenType::Eof), None);
assert_eq!(parser.index, 0);
}The code of the method check_current contains the explicit dereference *token_type:
src/parser.rs self.current_token()
.filter(|t| t.ttype != TokenType::Eof && t.ttype == *token_type)As Rust often performs auto-dereferencing, it is worth highlighting why it doesn't happen here. Please note that in this piece of code t is &&Token and token_type is &TokenType.
Rust auto-dereferences variables in specific places, in particular:
* or & until it finds a suitable implementation. The Rust reference says that "when looking up a method call, the receiver may be automatically dereferenced or borrowed in order to call a method."Deref or DerefMut depending on whether the operand is mutable, it is automatically dereferenced as many times as necessary to make the field access possible." In this case, t.ttype works on an &&Token because Rust automatically dereferences it twice.return statements.A function call is a coercion site, but in this case we have a comparison, which behaves like a generic function where a == b corresponds to eq(&self, other: &Rhs) [docs], so the type Rhs is not known and must be inferred from the call.
Hence, in this case we cannot rely on auto-dereferencing for token_type and must explicitly provide *token_type.
Once we have those methods in place we can create a variant of Expression that will host a "group":
src/parser.rs #[derive(Debug, PartialEq)]
pub enum Expression {
Group(Box<Self>),
Literal(Literal),
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name: String = match self {
Self::Group(p) => format!("(group {})", p),
Self::Literal(s) => s.to_string(),
};
write!(f, "{}", name)
}
}When Rust is compiled, the size of every type must be known, and thus we cannot have a type that contains itself: in that case, the size of the type would include the size of the type, and this would generate an infinite recursion. This is the reason why we need to include an indirection through Box [docs].
Actually, there are several ways to introduce such an indirection, for example using references, Rc [docs], or Vec [docs]. In this case we are representing a syntax tree, and since Box enforces ownership it looks like the most natural choice.
The new variant and the helper methods are then composed into the actual logic:
src/parser.rs impl Parser {
// Parse the current token and try to
// identify a primary element.
//
// primary -> NUMBER | STRING | "true" | "false" | "nil"
// primary -> NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"
fn primary(&mut self) -> Option<Expression> {
let result = match (&c.ttype, &c.literal) {
(TokenType::String, TokenLiteral::String(s)) => {
Expression::Literal(Literal::String(s.to_string()))
}
(TokenType::LParen, _) => {
// Consume the opening round bracket `(`.
self.consume();
// Parse the expression between brackets.
let p = self.expression()?;
// Check that the next token is
// the closing round bracket `)`.
// No need to consume it as it will
// be consumed below as the valid token.
self.check_current(&TokenType::RParen)?;
Expression::Group(Box::new(p))
}
_ => {
eprintln!("Invalid token {}", c);
return None;
}Finally, we can test the logic.
src/parser.rs mod tests {
#[test]
fn test_primary_group() {
let tokens = vec![
dummy_token(TokenType::LParen),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::RParen),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(
result,
Some(Expression::Group(Box::new(Expression::Literal(
Literal::Number(123.4)
))))
);
assert_eq!(parser.index, 3);
}Stage 4 - Parentheses
This version of the code passes Stage 4 of the extension "Parsing Expressions".
Unary operators are another step further in complexity for our parser, as they introduce the concept of precedence between grammar rules.
You can read the gory details in Nystrom's book (and in many other resources about compilers and grammars), but in short here we need the parser to process unary operators with a lower precedence than primaries, which in a parser like this means that we need to introduce a method unary between expression and primary.
We can start the implementation of unary operators with a variant of Expression:
src/parser.rs #[derive(Debug, PartialEq)]
pub enum Expression {
Group(Box<Self>),
Literal(Literal),
Unary { operator: Token, right: Box<Self> },
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name: String = match self {
Self::Group(p) => format!("(group {})", p),
Self::Literal(s) => s.to_string(),
Self::Unary { operator, right } => format!("({} {})", operator.lexeme, right),
};
write!(f, "{}", name)
}
}To offer a better overview of the problem, this aside briefly shows the issues that come from two alternative solutions.
Alternative grammar 1: group becomes an operator.
expression → unary
unary → ( "!" | "-" ) unary | expression
group → "(" expression ")"
primary → NUMBER | STRING | "true" | "false" | "nil"Here we have an infinite loop between unary and expression. For example -1 would fail because after - is consumed, 1 would be processed by expression that calls unary, that calls expression, and so on. Even just 1 fails, as group and primary are never reached.
Alternative grammar 2: expression processes the alternatives.
expression → group | primary | unary
unary → ( "!" | "-" ) unary | expression
group → "(" expression ")"
primary → NUMBER | STRING | "true" | "false" | "nil"In this case, code like -(1) works, as expression is called after - is consumed, and group is tried first. However, a single - would generate an infinite loop between unary and expression.
Correct grammar: unary with low precedence, group with highest.
expression → unary
unary → ( "!" | "-" ) unary | primary
primary → NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"Here, all previous examples work: 1, -1, -1 + 2, and so on.
Interestingly, putting groups at the very bottom of the chain is what gives parentheses the highest precedence in the grammar: in a recursive descent parser, the deeper a rule is the higher the precedence.
Once again, we use Box for the reason explained above when discussing Expression::Group. At this point, we realise that we need a helper method that checks the current token against a list of token types, but that also returns the token if there is a match. A way to implement it is to change Parser::consume so that it returns the consumed token and to implement a new method:
src/parser.rs impl Parser {
// Skip the current token, unless
// we already reached the end.
fn consume(&mut self) {
// Return the previous token.
fn consume(&mut self) -> Option<&Token> {
let previous = self.index;
if self
.current_token()
.is_some_and(|t| t.ttype != TokenType::Eof)
{
self.index += 1;
}
self.tokens.get(previous)
}
// Check if the type of the current token matches
// one of the provided token types. If there is a
// match, it consumes the token and returns it.
fn match_current(&mut self, token_types: &[TokenType]) -> Option<&Token> {
if token_types
.iter()
.any(|ttype| self.check_current(ttype).is_some())
{
self.consume()
} else {
None
}
}This is clearly not the only way to achieve the correct behaviour, and the specific implementation is often a matter of personal preference. In this case, we use Iterator::any [docs] to test if any element of the iterator matches the given rule.
The change to Parser::consume allows us to skip the token and return it in one single command, but it requires some changes to existing tests that use the method.
src/parser.rs mod tests {
#[test]
// Test that consuming a token makes the
// next one the current token.
fn test_consume() {
let tokens = vec![
dummy_token(TokenType::Identifier),
dummy_token(TokenType::Plus),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
parser.consume();
let previous = parser.consume();
assert_eq!(previous, Some(&dummy_token(TokenType::Identifier)));
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Plus)));
}
#[test]
// Test that consuming `Eof` doesn't move
// the index and keeps the current
// token unchanged.
fn test_consume_end() {
let tokens = vec![dummy_token(TokenType::Eof)];
let mut parser = Parser { tokens, index: 0 };
parser.consume();
parser.consume();
let previous = parser.consume();
assert_eq!(previous, Some(&dummy_token(TokenType::Eof)));
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Eof)));
}
#[test]
// Test that consuming an empty list of
// tokens just returns `None`.
fn test_consume_empty() {
let mut parser = Parser {
tokens: vec![],
index: 0,
};
parser.consume();
let previous = parser.consume();
assert_eq!(previous, None);
assert_eq!(parser.current_token(), None);
}The method Parser::match_current can be tested in isolation:
src/parser.rs mod tests {
#[test]
// Check that the method `match_current` works
// when the type of the current token is
// included in the matching list.
fn test_match_current_true() {
let tokens = vec![
dummy_token(TokenType::Number),
dummy_token(TokenType::Identifier),
];
let mut parser = Parser { tokens, index: 0 };
let matched = parser.match_current(&[TokenType::Number, TokenType::Plus]);
assert_eq!(matched, Some(dummy_token(TokenType::Number)).as_ref());
assert_eq!(parser.index, 1);
}
#[test]
// Check that the method `match_current` works
// when the type of the current token is not
// included in the matching list.
fn test_match_current_false() {
let tokens = vec![
dummy_token(TokenType::Identifier),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let matched = parser.match_current(&[TokenType::Number]);
assert_eq!(matched, None);
assert_eq!(parser.index, 0);
}Finally, we can introduce the method Parser::unary and call it from Parser::expression:
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.primary()
self.unary()
}
// Parse the next two tokens and try to
// identify a unary operation.
//
// unary -> ( "!" | "-" ) unary | primary
fn unary(&mut self) -> Option<Expression> {
if let Some(t) = self.match_current(&[TokenType::Bang, TokenType::Minus]) {
return Some(Expression::Unary {
operator: t.clone(),
right: Box::new(self.unary()?),
});
}
self.primary()
}The code of Parser::unary is not particularly complicated: if there is a match with TokenType::Bang or TokenType::Minus the code builds an Expression::Unary, otherwise it falls back to the result of Parser::primary.
This function clones a Token variable, so we need to derive the trait Clone:
src/token.rs #[derive(Debug, PartialEq)]
#[derive(Clone, Debug, PartialEq)]
pub enum TokenLiteral {
Null,
Number(f64),
String(String),
}
#[derive(Debug, PartialEq)]
#[derive(Clone, Debug, PartialEq)]
pub struct Token {
pub ttype: TokenType,
pub lexeme: String,
pub literal: TokenLiteral,
}Last, the logic of unary operators can be tested in several ways:
src/parser.rs mod tests {
#[test]
// Test that the method `unary` works
// correctly with a token `Minus` in front
// of a number.
fn test_unary_minus() {
let tokens = vec![
dummy_token(TokenType::Minus),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.unary();
assert_eq!(
result,
Some(Expression::Unary {
operator: dummy_token(TokenType::Minus),
right: Box::new(Expression::Literal(Literal::Number(123.4)))
})
);
assert_eq!(parser.index, 2);
}
#[test]
// Test that the method `unary` works
// correctly with a token `Bang` in front
// of a number.
fn test_unary_bang() {
let tokens = vec![
dummy_token(TokenType::Bang),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.unary();
assert_eq!(
result,
Some(Expression::Unary {
operator: dummy_token(TokenType::Bang),
right: Box::new(Expression::Literal(Literal::Number(123.4)))
})
);
assert_eq!(parser.index, 2);
}
#[test]
// Test that the method `unary` works
// correctly with a double token `Bang` in front
// of a number.
fn test_unary_double_bang() {
let tokens = vec![
dummy_token(TokenType::Bang),
dummy_token(TokenType::Bang),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.unary();
assert_eq!(
result,
Some(Expression::Unary {
operator: dummy_token(TokenType::Bang),
right: Box::new(Expression::Unary {
operator: dummy_token(TokenType::Bang),
right: Box::new(Expression::Literal(Literal::Number(123.4)))
}),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `primary` works
// correctly when the list of tokens contains
// a group that wraps a unary expression.
fn test_primary_group_can_contain_unary() {
let tokens = vec![
dummy_token(TokenType::LParen),
dummy_token(TokenType::Bang),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.4),
},
dummy_token(TokenType::RParen),
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(
result,
Some(Expression::Group(Box::new(Expression::Unary {
operator: dummy_token(TokenType::Bang),
right: Box::new(Expression::Literal(Literal::Number(123.4)))
})))
);
assert_eq!(parser.index, 4);
}Stage 5 - Unary Operators
This version of the code passes Stage 5 of the extension "Parsing Expressions".
Now that we have a good basic structure, adding the implementation of the remaining rules of the grammar is extremely simple. In this step we need to add multiplication and division, which come before addition and subtraction but after unary operations to establish precedence.
Multiplication and division, just like addition, subtraction, and comparisons, are binary operators in the form LEFT OPERATOR RIGHT. Therefore, we can create a variant Expression::Binary that is used for all of them:
src/parser.rs #[derive(Debug, PartialEq)]
pub enum Expression {
Binary {
left: Box<Self>,
operator: Token,
right: Box<Self>,
},
Group(Box<Self>),
Literal(Literal),
Unary { operator: Token, right: Box<Self> },
Unary {
operator: Token,
right: Box<Self>,
},
}
impl fmt::Display for Expression {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let name: String = match self {
Self::Binary {
left,
operator,
right,
} => format!("({} {} {})", operator.lexeme, left, right),
Self::Group(p) => format!("(group {})", p),
Self::Literal(s) => s.to_string(),
Self::Unary { operator, right } => format!("({} {})", operator.lexeme, right),
};
write!(f, "{}", name)
}
}To parse the two binary operations we can first identify a unary operation, then check if the next token is TokenType::Slash or TokenType::Star, and finally identify the second unary operation.
The first call to self.unary() is decorated with ? to trigger an exit in case the identification failed. In that case, we are not looking at a binary operation. However, the function supports chains of binary operations like 2 * 4 / 3 and the second self.unary() is also decorated with ? to trigger an exit whenever one of the operands fails to parse.
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.unary()
self.factor()
}
// Parse the next three tokens and try to
// identify a multiplication or a division.
//
// factor -> unary ( ( "/" | "*" ) unary )*
fn factor(&mut self) -> Option<Expression> {
let mut expression = self.unary()?;
while let Some(t) = self.match_current(&[TokenType::Slash, TokenType::Star]) {
let operator = t.clone();
let right = self.unary()?;
expression = Expression::Binary {
left: Box::new(expression),
operator,
right: Box::new(right),
};
}
Some(expression)
}The method Parser::factor can then be tested in isolation:
src/parser.rs mod tests {
#[test]
// Test that the method `factor` works
// correctly with two primaries and
// a token `Slash`.
fn test_factor_slash() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Slash),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.factor();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Slash),
right: Box::new(Expression::Literal(Literal::Number(456.0)))
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `factor` works
// correctly with two primaries and
// a token `Star`.
fn test_factor_star() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Star),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.factor();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Star),
right: Box::new(Expression::Literal(Literal::Number(456.0)))
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `factor` works
// correctly with multiple primaries
// chained by either Slash or Star
// tokens.
fn test_factor_chain() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Star),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Slash),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(789.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.factor();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Star),
right: Box::new(Expression::Literal(Literal::Number(456.0)))
}),
operator: dummy_token(TokenType::Slash),
right: Box::new(Expression::Literal(Literal::Number(789.0)))
})
);
assert_eq!(parser.index, 5);
}Stage 6 - Arithmetic operators (1/2)
This version of the code passes Stage 6 of the extension "Parsing Expressions".
Parsing addition and subtraction is basically a repetition of what we have done with multiplication and division, the only difference being the precedence. The new method Parser::term will identify factor ("+" | "-") factor while Parser::factor identifies unary ( "/" | "*" ) unary.
The code would be the following:
src/parser.rs impl Parser {
fn term(&mut self) -> Option<Expression> {
let mut expression = self.factor()?;
while let Some(t) = self.match_current(&[TokenType::Plus, TokenType::Minus]) {
let operator = t.clone();
let right = self.factor()?;
expression = Expression::Binary {
left: Box::new(expression),
operator,
right: Box::new(right),
};
}
Some(expression)
}This is going to be the case also for comparisons and equalities, so to avoid code duplication we can extract a method that parses a generic binary operator:
src/parser.rs impl Parser {
// Parse the next three tokens and try to
// identify a binary operation that uses
// one of the given operators.
// Fall back to the provided next function
// if the binary operation cannot be identified.
//
// binary -> next ( ( operators ) next )*
fn binary(
&mut self,
operators: &[TokenType],
next: fn(&mut Self) -> Option<Expression>,
) -> Option<Expression> {
let mut expression = next(self)?;
while let Some(t) = self.match_current(operators) {
let operator = t.clone();
let right = next(self)?;
expression = Expression::Binary {
left: Box::new(expression),
operator,
right: Box::new(right),
};
}
Some(expression)
}The method is simply the logic of the function Parser::factor with a couple of changes to make it generic. The first change is that the function accepts a slice of TokenType to check the binary operator and the second change is that a function is passed to parse the two operands. The function will be Parser::unary for Parser::factor, Parser::factor for Parser::term, and so on.
With this function we can replace the implementation of Parser::factor and add the implementation of Parser::term:
src/parser.rs impl Parser {
// Parse the next three tokens and try to
// identify an addition or a subtraction.
//
// term -> factor ( ( "+" | "-" ) factor )*
fn term(&mut self) -> Option<Expression> {
self.binary(&[TokenType::Plus, TokenType::Minus], Self::factor)
}
// Parse the next three tokens and try to
// identify a multiplication or a division.
//
// factor -> unary ( ( "/" | "*" ) unary )*
fn factor(&mut self) -> Option<Expression> {
let mut expression = self.unary()?;
while let Some(t) = self.match_current(&[TokenType::Slash, TokenType::Star]) {
let operator = t.clone();
let right = self.unary()?;
expression = Expression::Binary {
left: Box::new(expression),
operator,
right: Box::new(right),
};
}
Some(expression)
self.binary(&[TokenType::Slash, TokenType::Star], Self::unary)
}We can also call Parser::term from Parser::expression:
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.factor()
self.term()
}Last, we can add several tests for the new method:
src/parser.rs mod tests {
#[test]
// Test that the method `term` works
// correctly with two primaries and
// a token `Plus`.
fn test_term_plus() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Plus),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.term();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Plus),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `term` works
// correctly with two primaries and
// a token `Minus`.
fn test_term_minus() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Minus),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.term();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Minus),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `term` works
// correctly with multiple primaries
// chained by either Plus or Minus
// tokens.
fn test_term_chain() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Minus),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Plus),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(789.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.term();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Minus),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
}),
operator: dummy_token(TokenType::Plus),
right: Box::new(Expression::Literal(Literal::Number(789.0))),
})
);
assert_eq!(parser.index, 5);
}Stage 7 - Arithmetic operators (2/2)
This version of the code passes Stage 7 of the extension "Parsing Expressions".
With the method Parser::binary in place, parsing comparison operators is just a matter of listing the correct operator tokens and rerouting Parser::expression.
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.term()
self.comparison()
}
// Parse the next three tokens and try to
// identify a comparison.
//
// comparison -> term ( ( ">" | ">=" | "<" | "<=" ) term )*
fn comparison(&mut self) -> Option<Expression> {
self.binary(
&[
TokenType::Less,
TokenType::LessEqual,
TokenType::Greater,
TokenType::GreaterEqual,
],
Self::term,
)
}Naturally, we have tests for the new method Parser::comparison:
src/parser.rs mod tests {
#[test]
// Test that the method `comparison` works
// correctly with two primaries and
// a token `Less`.
fn test_comparison_less() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Less),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.comparison();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Less),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `comparison` works
// correctly with two primaries and
// a token `LessEqual`.
fn test_comparison_less_equal() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::LessEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.comparison();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::LessEqual),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `comparison` works
// correctly with two primaries and
// a token `Greater`.
fn test_comparison_greater() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Greater),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.comparison();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Greater),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `comparison` works
// correctly with two primaries and
// a token `GreaterEqual`.
fn test_comparison_greater_equal() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::GreaterEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.comparison();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::GreaterEqual),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `comparison` works
// correctly with multiple primaries
// chained by comparison
// tokens.
fn test_comparison_chain() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::Less),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::GreaterEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(789.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.comparison();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::Less),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
}),
operator: dummy_token(TokenType::GreaterEqual),
right: Box::new(Expression::Literal(Literal::Number(789.0))),
})
);
assert_eq!(parser.index, 5);
}Stage 8 - Comparison operators
This version of the code passes Stage 8 of the extension "Parsing Expressions".
The implementation of equality operators follows exactly the same pattern. The new method Parser::equality:
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
self.comparison()
self.equality()
}
// Parse the next three tokens and try to
// identify an equality.
//
// equality -> comparison ( ( "!=" | "==" ) comparison )*
fn equality(&mut self) -> Option<Expression> {
self.binary(
&[TokenType::BangEqual, TokenType::EqualEqual],
Self::comparison,
)
}And the corresponding tests:
src/parser.rs mod tests {
#[test]
// Test that the method `equality` works
// correctly with two primaries and
// a token `BangEqual`.
fn test_equality_bang_equal() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::BangEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.equality();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::BangEqual),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `equality` works
// correctly with two primaries and
// a token `EqualEqual`.
fn test_equality_equal_equal() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::EqualEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.equality();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::EqualEqual),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
})
);
assert_eq!(parser.index, 3);
}
#[test]
// Test that the method `equality` works
// correctly with multiple primaries
// chained by equality tokens.
fn test_equality_chain() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
},
dummy_token(TokenType::BangEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(456.0),
},
dummy_token(TokenType::EqualEqual),
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(789.0),
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.equality();
assert_eq!(
result,
Some(Expression::Binary {
left: Box::new(Expression::Binary {
left: Box::new(Expression::Literal(Literal::Number(123.0))),
operator: dummy_token(TokenType::BangEqual),
right: Box::new(Expression::Literal(Literal::Number(456.0))),
}),
operator: dummy_token(TokenType::EqualEqual),
right: Box::new(Expression::Literal(Literal::Number(789.0))),
})
);
assert_eq!(parser.index, 5);
}Stage 9 - Equality operators
This version of the code passes Stage 9 of the extension "Parsing Expressions".
As any software developer knows, error management represents the vast majority of the code we write. Usually, there is only one happy path but countless ways things can go wrong, and our code should manage them all.
An interpreter reads free text and tries to match it against strict (and hopefully unambiguous) syntax rules, so often realising that something is wrong is not extremely difficult. The difficult part is understanding exactly what is wrong, and how to deal with it.
The final step in this part of the extension "Parsing Expressions", "Syntactic errors", checks if our code exits with the error code 65 when something is wrong. For the time being, it doesn't check the error message, and it doesn't require the interpreter to try to look past the error to continue parsing.
The stage could be cleared with a simple change in src/main.rs:
src/main.rs fn main() {
match command.as_str() {
"parse" => {
// In case there were errors
// exit with a specific code.
if errors {
process::exit(65);
}
let mut p = Parser { tokens, index: 0 };
match p.expression() {
Some(v) => println!("{}", v),
None => panic!(),
None => process::exit(65),
}This step is however a great opportunity to review error management and to refactor code in order to be able to output useful error messages. At the moment, Parser::expression returns an Option<Expression>, which in case of errors becomes a plain None without further explanations. The idea is to change the methods of Parser so that they return a Result, where the error can be a structure that contains data like an error message, the position of the error, the token that was being processed, and so on.
Since we wrote a lot of code, changing the internal interface of methods might result in a lot of edits, which might become complicated to see in isolation. Therefore, this refactoring has been split into several sub-steps that should be small enough to be understandable.
The first change is to add a line number to each token, so that at any time we can print a message that contains relevant information for the user.
src/token.rs #[derive(Clone, Debug, PartialEq)]
pub struct Token {
pub ttype: TokenType,
pub lexeme: String,
pub literal: TokenLiteral,
pub line: u16,
}This has several effects. First of all, the code of Tokenizer needs to be adjusted as there are several places where tokens are created.
src/tokenizer.rs impl<'a> Tokenizer<'a> {
fn multi_character_token(&mut self) -> Option<TokenResult> {
// If the full token is not in the multi-character
// tokens just return None.
let ttype = self.mc_lexemes.get(&String::from(&full))?.clone();
// If we found a proper token we must
// take note of the line number as
// later we might move to the next line.
let token_line = self.current_line;
...
Some(Ok(Token {
ttype,
lexeme: full,
literal: TokenLiteral::Null,
line: token_line,
}))
}
fn single_character_token(&mut self) -> Option<TokenResult> {
// Look for the current character in
// the map of single-character lexemes.
// Return None if no character can be found.
let ttype = self.sc_lexemes.get(&String::from(c))?.clone();
// If we found a proper token we must
// take note of the line number as
// later we might move to the next line.
let token_line = self.current_line;
...
Some(Ok(Token {
ttype,
lexeme: String::from(c),
literal: TokenLiteral::Null,
line: token_line,
}))
}
fn string(&mut self) -> Option<TokenResult> {
// Return the token using the full string
// with quotes as lexemes (this is what we processed)
// and the string without quotes as literal value.
return Some(Ok(Token {
ttype: TokenType::String,
lexeme: s.clone(),
literal: TokenLiteral::String(s.trim_matches('"').to_owned()),
line: self.current_line,
}));
fn number(&mut self) -> Option<TokenResult> {
// We don't need to advance as the current
// character is already something that doesn't
// belong to the number.
Some(Ok(Token {
ttype: TokenType::Number,
lexeme: s.clone(),
literal,
line: self.current_line,
}))
fn identifier(&mut self) -> Option<TokenResult> {
// Check if this is a reserved word.
if let Ok(k) = s.parse::<Keyword>() {
return Some(Ok(Token {
ttype: TokenType::Reserved(k),
lexeme: s.clone(),
literal: TokenLiteral::Null,
line: self.current_line,
}));
}
// We don't need to advance as the current
// character is already something that doesn't
// belong to the identifier
Some(Ok(Token {
ttype: TokenType::Identifier,
lexeme: s.clone(),
literal: TokenLiteral::Null,
line: self.current_line,
}))
pub fn tokenize(chars: Peekable<Chars>) -> Vec<TokenResult> {
// Make sure the last token is the End Of File
results.push(Ok(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
}));Second, multiple tests and helpers need to be adjusted. You can use cargo test to find out which tests need to be fixed. Since all tests process code on a single line of code, we can add the same line number to all of them.
src/parser.rs mod tests {
fn dummy_token(ttype: TokenType) -> Token {
Token {
ttype,
lexeme: String::new(),
literal: TokenLiteral::Null,
line: 1,
}
}
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains an integer number.
fn test_primary_number_integer() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
},
dummy_token(TokenType::Eof),
];
let mut parser = Parser { tokens, index: 0 };
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Number(123.0))));
assert_eq!(parser.index, 1);
}
// FIX ALL THE REMAINING TESTSCurrently, the parser has helper functions like consume and check_current that return Option<&Token>. This means that there are multiple failure points, one for each time one of those functions is called. The system can be made much less error-prone, however, with a simple change: if we ensure the list of tokens always contains at least one token, there is no way for those functions to fail, which means that their return value can become &Token and all the failure points related to them disappear.
We can ensure the presence of the token Eof with a simple constructor for Parser:
src/parser.rs impl Parser {
// Create a new Parser and ensure
// the list of tokens includes at
// least an Eof.
pub fn new(mut tokens: Vec<Token>) -> Self {
if tokens.last().is_none_or(|t| t.ttype != TokenType::Eof) {
tokens.push(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
});
}
Self { tokens, index: 0 }
}As you can see, the method checks if the last token exists and is Eof and otherwise adds it to the list. We can test the logic with three use cases:
src/parser.rs mod tests {
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens ends with an Eof.
fn test_parser_new_last_token_is_eof() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
},
Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
},
];
let mut parser = Parser::new(tokens);
// Consume the first token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens doesn't end with an Eof.
fn test_parser_new_last_token_is_not_eof() {
let tokens = vec![Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
}];
let mut parser = Parser::new(tokens);
// Consume the first and only token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens is empty.
fn test_parser_new_no_tokens() {
let tokens = Vec::new();
let mut parser = Parser::new(tokens);
// Try to consume a token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.index, 0);
}We can then propagate the change everywhere we build Parser. You can run a global search for Parser { to find all the places where you can use Parser::new:
src/parser.rs mod tests {
#[test]
// Test that the method `current_token`
// returns the correct value.
fn test_current_token() {
let tokens = vec![dummy_token(TokenType::Identifier)];
let parser = Parser { tokens, index: 0 };
let parser = Parser::new(tokens);
assert_eq!(
parser.current_token(),
Some(&dummy_token(TokenType::Identifier))
);
}
// FIX ALL THE REMAINING TESTSThe test test_consume_empty requires a bit more care as it involves the added token Eof:
src/parser.rs mod tests {
// Test that consuming an empty list of
// tokens just returns `None`.
// tokens returns `Eof`.
fn test_consume_empty() {
let mut parser = Parser {
tokens: vec![],
index: 0,
};
let mut parser = Parser::new(Vec::new());
let previous = parser.consume();
assert_eq!(previous, None);
assert_eq!(parser.current_token(), None);
assert_eq!(
previous,
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
}The last change of this type can be made in the main function:
src/main.rs fn main() {
match command.as_str() {
"parse" => {
// In case there were errors
// exit with a specific code.
if errors {
process::exit(65);
}
let mut p = Parser { tokens, index: 0 };
let mut p = Parser::new(tokens);Since we are not explicitly handling the fields of the structure Parser any more, we can make them private to strengthen the implementation.
src/parser.rs pub struct Parser {
// The list of tokens generated by
// the scanner.
pub tokens: Vec<Token>,
tokens: Vec<Token>,
// The index of the current token
// in the tokens vector.
pub index: usize,
index: usize,
}As you have surely noticed, in the previous step we initialised the token Eof multiple times, and it is definitely worth creating a helper method to make sure the token is always initialised in the same way.
src/token.rs impl Token {
pub const fn eof() -> Self {
Self {
ttype: TokenType::Eof,
lexeme: String::new(),
literal: TokenLiteral::Null,
line: 1,
}
}
}
mod tests {
#[test]
// Test that an Eof token can
// be correctly created.
fn test_eof() {
assert_eq!(
Token::eof(),
Token {
ttype: TokenType::Eof,
lexeme: String::new(),
literal: TokenLiteral::Null,
line: 1,
}
);
}This allows us to reduce duplication first in the tokeniser:
src/tokenizer.rs pub fn tokenize(chars: Peekable<Chars>) -> Vec<TokenResult> {
// Make sure the last token is the End Of File
results.push(Ok(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
}));
results.push(Ok(Token::eof()));
mod tokenize_tests {
fn test_tokenize() {
assert_eq!(
results,
[
...
Ok(Token {
ttype: TokenType::RParen,
lexeme: String::from(")"),
literal: TokenLiteral::Null,
line: 1
}),
Ok(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1
}),
Ok(Token::eof()),
]And then in the parser:
src/parser.rs impl Parser {
// Create a new Parser and ensure
// the list of tokens includes at
// least an Eof.
pub fn new(mut tokens: Vec<Token>) -> Self {
if tokens.last().is_none_or(|t| t.ttype != TokenType::Eof) {
tokens.push(Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
});
tokens.push(Token::eof());
}
Self { tokens, index: 0 }
}
Since we have a specific way to build the Eof token, it's a good idea to use it everywhere, even in tests, where we can replace every instance of dummy_token(TokenType::Eof) with Token::eof().
src/parser.rs mod tests {
#[test]
// Test that consuming a token makes the
// next one the current token.
fn test_consume() {
let tokens = vec![
dummy_token(TokenType::Identifier),
dummy_token(TokenType::Plus),
dummy_token(TokenType::Eof),
Token::eof(),
];
let mut parser = Parser::new(tokens);
let previous = parser.consume();
assert_eq!(previous, Some(&dummy_token(TokenType::Identifier)));
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Plus)));
}
// FIX ALL THE REMAINING TESTSSome tests like test_consume_empty use Eof tokens initialised explicitly:
src/parser.rs #[test]
// Test that consuming an empty list of
// tokens returns `Eof`.
fn test_consume_empty() {
let mut parser = Parser::new(Vec::new());
let previous = parser.consume();
assert_eq!(
previous,
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(previous, Some(&Token::eof()));
assert_eq!(parser.current_token(), Some(&Token::eof()));
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens ends with an Eof.
fn test_parser_new_last_token_is_eof() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
},
Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
},
Token::eof(),
];
let mut parser = Parser::new(tokens);
// Consume the first token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens doesn't end with an Eof.
fn test_parser_new_last_token_is_not_eof() {
let tokens = vec![Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
}];
let mut parser = Parser::new(tokens);
// Consume the first and only token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens is empty.
fn test_parser_new_no_tokens() {
let tokens = Vec::new();
let mut parser = Parser::new(tokens);
// Try to consume a token.
parser.consume();
assert_eq!(
parser.current_token(),
Some(&Token {
ttype: TokenType::Eof,
lexeme: String::from(""),
literal: TokenLiteral::Null,
line: 1,
})
);
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.index, 0);
}The new implementation of the parser ensures that tokens are always present, so we can relax the implementation of the helper functions by removing the Option from their returned type.
First, let's change current_token:
src/parser.rs impl Parser {
// Return the current token as an Option.
fn current_token(&self) -> Option<&Token> {
self.tokens.get(self.index)
}
// Return the current token.
fn current_token(&self) -> &Token {
&self.tokens[self.index]
}The function now directly returns a reference to a token. This impacts directly the code of the function consume. We can remove the call to Option::is_some_and and change the return type:
src/parser.rs impl Parser {
// Skip the current token, unless
// we already reached the end.
// Return the previous token.
fn consume(&mut self) -> Option<&Token> {
fn consume(&mut self) -> &Token {
let previous = self.index;
if self
.current_token()
.is_some_and(|t| t.ttype != TokenType::Eof)
{
if self.current_token().ttype != TokenType::Eof {
self.index += 1;
}
self.tokens.get(previous)
&self.tokens[previous]
}The function check_current can now directly return a bool. This was possible even before, but with the previous implementation it seemed more natural to return an Option:
src/parser.rs impl Parser {
// Check if the type of the current token
// corresponds to the given `TokenType` variant.
// `Option::filter` returns `Some` only when
// the condition is satisfied.
// So, in this case, only if the current token
// This is true only if the current token
// is not `Eof` and if there is a match between
// the current token and the given token type.
fn check_current(&self, token_type: &TokenType) -> Option<&Token> {
self.current_token()
.filter(|t| t.ttype != TokenType::Eof && t.ttype == *token_type)
}
fn check_current(&self, token_type: &TokenType) -> bool {
let current_token = self.current_token();
current_token.ttype != TokenType::Eof && current_token.ttype == *token_type
}Finally, the function match_current needs changes where it calls check_current but keeps the return type as Option. In this case it is useful to have a type that merges a boolean result (Some or None) with an actual value when the match is positive.
src/parser.rs impl Parser {
// Check if the type of the current token matches
// one of the provided token types. If there is a
// match, it consumes the token and returns it.
fn match_current(&mut self, token_types: &[TokenType]) -> Option<&Token> {
if token_types
.iter()
.any(|ttype| self.check_current(ttype).is_some())
{
self.consume()
if token_types.iter().any(|ttype| self.check_current(ttype)) {
Some(self.consume())
} else {
None
}
}Such changes cascade into several other changes. First of all Parser::primary:
src/parser.rs impl Parser {
fn primary(&mut self) -> Option<Expression> {
// If the current token is None return None.
let c: &Token = self.current_token()?;
// Get the current token.
let c: &Token = self.current_token();
...
// Check that the next token is
// the closing round bracket `)`.
// No need to consume it as it will
// be consumed below as the valid token.
self.check_current(&TokenType::RParen)?;
if !self.check_current(&TokenType::RParen) {
return None;
}
Expression::Group(Box::new(p))
}
...
// If we reach this point, the token we
// found was valid. Advance the index.
self.index += 1;
// found was valid. Advance the index
// consuming the current token.
self.consume();Second, several tests:
src/parser.rs mod tests {
#[test]
// Test that the method `current_token`
// returns the correct value.
fn test_current_token() {
let tokens = vec![dummy_token(TokenType::Identifier)];
let parser = Parser::new(tokens);
assert_eq!(
parser.current_token(),
Some(&dummy_token(TokenType::Identifier))
);
assert_eq!(parser.current_token(), &dummy_token(TokenType::Identifier));
}
#[test]
// Test that consuming a token makes the
// next one the current token.
fn test_consume() {
let tokens = vec![
dummy_token(TokenType::Identifier),
dummy_token(TokenType::Plus),
Token::eof(),
];
let mut parser = Parser::new(tokens);
let previous = parser.consume();
assert_eq!(previous, Some(&dummy_token(TokenType::Identifier)));
assert_eq!(parser.current_token(), Some(&dummy_token(TokenType::Plus)));
assert_eq!(previous, &dummy_token(TokenType::Identifier));
assert_eq!(parser.current_token(), &dummy_token(TokenType::Plus));
}
#[test]
// Test that consuming `Eof` doesn't move
// the index and keeps the current
// token unchanged.
fn test_consume_end() {
let tokens = vec![Token::eof()];
let mut parser = Parser::new(tokens);
parser.consume();
let previous = parser.consume();
assert_eq!(previous, Some(&Token::eof()));
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(previous, &Token::eof());
assert_eq!(parser.current_token(), &Token::eof());
}
#[test]
// Test that consuming an empty list of
// tokens returns `Eof`.
fn test_consume_empty() {
let mut parser = Parser::new(Vec::new());
let previous = parser.consume();
assert_eq!(previous, Some(&Token::eof()));
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(previous, &Token::eof());
assert_eq!(parser.current_token(), &Token::eof());
}
#[test]
fn test_check_current_true() {
let tokens = vec![dummy_token(TokenType::Plus)];
let parser = Parser::new(tokens);
assert_eq!(
parser.check_current(&TokenType::Plus),
Some(dummy_token(TokenType::Plus)).as_ref()
);
assert!(parser.check_current(&TokenType::Plus));
assert_eq!(parser.index, 0);
}
#[test]
fn test_check_current_false() {
let tokens = vec![dummy_token(TokenType::Plus)];
let parser = Parser::new(tokens);
assert_eq!(parser.check_current(&TokenType::Number), None);
assert!(!parser.check_current(&TokenType::Number));
assert_eq!(parser.index, 0);
}
#[test]
fn test_check_current_end() {
let tokens = vec![Token::eof()];
let parser = Parser::new(tokens);
// If we reached the end of the token sequence
// we return `None` without checking the type.
assert_eq!(parser.check_current(&TokenType::Eof), None);
// we return false without checking the type.
assert!(!parser.check_current(&TokenType::Eof));
assert_eq!(parser.index, 0);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens ends with an Eof.
fn test_parser_new_last_token_is_eof() {
let tokens = vec![
Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
},
Token::eof(),
];
let mut parser = Parser::new(tokens);
// Consume the first token.
parser.consume();
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.current_token(), &Token::eof());
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens doesn't end with an Eof.
fn test_parser_new_last_token_is_not_eof() {
let tokens = vec![Token {
ttype: TokenType::Number,
lexeme: String::new(),
literal: TokenLiteral::Number(123.0),
line: 1,
}];
let mut parser = Parser::new(tokens);
// Consume the first and only token.
parser.consume();
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.current_token(), &Token::eof());
assert_eq!(parser.index, 1);
}
#[test]
// Test that the method `new` works
// correctly when the list of provided
// tokens is empty.
fn test_parser_new_no_tokens() {
let tokens = Vec::new();
let mut parser = Parser::new(tokens);
// Try to consume a token.
parser.consume();
assert_eq!(parser.current_token(), Some(&Token::eof()));
assert_eq!(parser.current_token(), &Token::eof());
assert_eq!(parser.index, 0);
}Before we can fully migrate the parser functions from Option<Expression> to Result we need to create a couple of custom types:
src/parser.rs #[derive(Debug, PartialEq)]
pub struct ParserError {
pub message: String,
pub token: Token,
}
impl fmt::Display for ParserError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(
f,
"[line {}] Error: {} - Token: {}",
self.token.line, self.message, self.token.lexeme
)
}
}
pub type ParserResult<T> = Result<T, ParserError>;The choice of creating the parametric type ParserResult<T> instead of hard coding Expression is just to provide more flexibility to code we will create in the future. Should we need it, we can always create a custom type ParserResultExpression, but this doesn't look like a real improvement over ParserResult<Expression>.
The type ParserError is the key addition here. The whole point of this refactoring is to introduce a richer error message that mentions a token and the line where it was found.
We can finally migrate the parser methods from the old output type Option<Expression> to the new type ParserResult<Expression>. We can start with Parser::binary which is at the core of several other methods:
src/parser.rs impl Parser {
// Parse the next three tokens and try to
// identify a binary operation that uses
// one of the given operators.
// Fall back to the provided next function
// if the binary operation cannot be identified.
//
// binary -> next ( ( operators ) next )*
fn binary(
&mut self,
operators: &[TokenType],
next: fn(&mut Self) -> Option<Expression>,
) -> Option<Expression> {
next: fn(&mut Self) -> ParserResult<Expression>,
) -> ParserResult<Expression> {
let mut expression = next(self)?;
while let Some(t) = self.match_current(operators) {
let operator = t.clone();
let right = next(self)?;
expression = Expression::Binary {
left: Box::new(expression),
operator,
right: Box::new(right),
};
}
Some(expression)
Ok(expression)
}Indeed, this change cascades into other changes:
src/parser.rs impl Parser {
// The main entry point of the parser.
pub fn expression(&mut self) -> Option<Expression> {
pub fn expression(&mut self) -> ParserResult<Expression> {
self.equality()
}
// Parse the next three tokens and try to
// identify an equality.
//
// equality -> comparison ( ( "!=" | "==" ) comparison )*
fn equality(&mut self) -> Option<Expression> {
fn equality(&mut self) -> ParserResult<Expression> {
self.binary(
&[TokenType::BangEqual, TokenType::EqualEqual],
Self::comparison,
)
}
// Parse the next three tokens and try to
// identify a comparison.
//
// comparison -> term ( ( ">" | ">=" | "<" | "<=" ) term )*
fn comparison(&mut self) -> Option<Expression> {
fn comparison(&mut self) -> ParserResult<Expression> {
self.binary(
&[
TokenType::Less,
TokenType::LessEqual,
TokenType::Greater,
TokenType::GreaterEqual,
],
Self::term,
)
}
// Parse the next three tokens and try to
// identify an addition or a subtraction.
//
// term -> factor ( ( "+" | "-" ) factor )*
fn term(&mut self) -> Option<Expression> {
fn term(&mut self) -> ParserResult<Expression> {
self.binary(&[TokenType::Plus, TokenType::Minus], Self::factor)
}
// Parse the next three tokens and try to
// identify a multiplication or a division.
//
// factor -> unary ( ( "/" | "*" ) unary )*
fn factor(&mut self) -> Option<Expression> {
fn factor(&mut self) -> ParserResult<Expression> {
self.binary(&[TokenType::Slash, TokenType::Star], Self::unary)
}
// Parse the next two tokens and try to
// identify a unary operation.
//
// unary -> ( "!" | "-" ) unary | primary
fn unary(&mut self) -> Option<Expression> {
fn unary(&mut self) -> ParserResult<Expression> {
if let Some(t) = self.match_current(&[TokenType::Bang, TokenType::Minus]) {
return Some(Expression::Unary {
return Ok(Expression::Unary {
operator: t.clone(),
right: Box::new(self.unary()?),
});
}
self.primary()
}The core changes, however, happen in the deepest method of the parser, Parser::primary. This is the only place where errors can be generated at the moment:
src/parser.rs impl Parser {
// Parse the current token and try to
// identify a primary element.
//
// primary -> NUMBER | STRING | "true" | "false" | "nil" | "(" expression ")"
fn primary(&mut self) -> Option<Expression> {
fn primary(&mut self) -> ParserResult<Expression> {
// Get the current token.
let c: &Token = self.current_token();
// Check the type of the current token.
let result = match (&c.ttype, &c.literal) {
(TokenType::Number, TokenLiteral::Number(n)) => {
Expression::Literal(Literal::Number(*n))
}
(TokenType::Reserved(s), _) => match s {
Keyword::True => Expression::Literal(Literal::Boolean(true)),
Keyword::False => Expression::Literal(Literal::Boolean(false)),
Keyword::Nil => Expression::Literal(Literal::Nil),
_ => return None,
_ => {
return Err(ParserError {
message: String::from("Invalid primary token"),
token: c.clone(),
})
}
},
(TokenType::String, TokenLiteral::String(s)) => {
Expression::Literal(Literal::String(s.to_string()))
}
(TokenType::LParen, _) => {
// Consume the opening round bracket `(`.
self.consume();
// Parse the expression between brackets.
let p = self.expression()?;
// Check that the next token is
// the closing round bracket `)`.
// No need to consume it as it will
// be consumed below as the valid token.
if !self.check_current(&TokenType::RParen) {
return None;
return Err(ParserError {
message: String::from("Missing closing round bracket ')'"),
token: self.current_token().clone(),
});
}
Expression::Group(Box::new(p))
}
_ => {
eprintln!("Invalid token {}", c);
return None;
return Err(ParserError {
message: String::from("Invalid primary token"),
token: c.clone(),
});
}
};
// If we reach this point, the token we
// found was valid. Advance the index
// consuming the current token.
self.consume();
// Return the token as an Option.
Some(result)
// Return the token as a Result.
Ok(result)
}
}As happened before, this API change heavily impacts tests. Fortunately, once again it's a matter of applying the same change to all of them:
src/parser.rs mod tests {
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains reserved word `true`.
fn test_primary_true() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::True)),
Token::eof(),
];
let mut parser = Parser::new(tokens);
let result = parser.primary();
assert_eq!(result, Some(Expression::Literal(Literal::Boolean(true))));
assert_eq!(result, Ok(Expression::Literal(Literal::Boolean(true))));
assert_eq!(parser.index, 1);
}
// FIX ALL THE REMAINING TESTSThe only test that requires a different set of changes is test_primary_unknown_reserved:
src/parser.rs mod tests {
#[test]
// Test that the method `primary` works
// correctly on a list of tokens that
// contains a reserved word that is
// currently unknown.
fn test_primary_unknown_reserved() {
let tokens = vec![
dummy_token(TokenType::Reserved(Keyword::Class)),
Token::eof(),
];
let mut parser = Parser::new(tokens);
let result = parser.primary();
assert_eq!(result, None);
assert_eq!(
result,
Err(ParserError {
message: String::from("Invalid primary token"),
token: dummy_token(TokenType::Reserved(Keyword::Class))
})
);
assert_eq!(parser.index, 0);
}Last, we need to fix the call to Parser::expression in the main function:
src/main.rs fn main() {
match command.as_str() {
"parse" => {
match p.expression() {
Some(v) => println!("{}", v),
None => panic!(),
Ok(v) => println!("{}", v),
_ => panic!(),
}After all these changes, we can finally return the correct error code according to the requirements of the extension "Parsing Expressions", and we can also add a good error message to the output.
src/main.rs fn main() {
match command.as_str() {
"parse" => {
match p.expression() {
Ok(v) => println!("{}", v),
_ => panic!(),
Err(e) => {
eprintln!("{}", e);
process::exit(65);
}
}Running the challenge tests now produces the following output, where we can see the error messages:
[stage_210] Running tests for Stage #210: Parsing: Errors
[stage_210] [test-1] Running test case: 1
[stage_210] [test-1] Writing contents to ./test.lox:
[stage_210] [test-1.lox] "world
[stage_210] [test-1] $ ./your_program.sh parse test.lox
[your_program] Finished `release` profile [optimized] target(s) in 0.01s
[your_program] [line 1] Error: Unterminated string.
[stage_210] [test-1] ✓ 1 line(s) match on stdout
[stage_210] [test-1] ✓ Received exit code 65.
[stage_210] [test-2] Running test case: 2
[stage_210] [test-2] Writing contents to ./test.lox:
[stage_210] [test-2.lox] (foo
[stage_210] [test-2] $ ./your_program.sh parse test.lox
[your_program] Finished `release` profile [optimized] target(s) in 0.01s
[your_program] [line 1] Error: Invalid primary token - Token: foo
[stage_210] [test-2] ✓ 1 line(s) match on stdout
[stage_210] [test-2] ✓ Received exit code 65.
[stage_210] [test-3] Running test case: 3
[stage_210] [test-3] Writing contents to ./test.lox:
[stage_210] [test-3.lox] (89 +)
[stage_210] [test-3] $ ./your_program.sh parse test.lox
[your_program] Finished `release` profile [optimized] target(s) in 0.02s
[your_program] [line 1] Error: Invalid primary token - Token: )
[stage_210] [test-3] ✓ 1 line(s) match on stdout
[stage_210] [test-3] ✓ Received exit code 65.
[stage_210] [test-4] Running test case: 4
[stage_210] [test-4] Writing contents to ./test.lox:
[stage_210] [test-4.lox] +
[stage_210] [test-4] $ ./your_program.sh parse test.lox
[your_program] Finished `release` profile [optimized] target(s) in 0.01s
[your_program] [line 1] Error: Invalid primary token - Token: +
[stage_210] [test-4] ✓ 1 line(s) match on stdout
[stage_210] [test-4] ✓ Received exit code 65.
[stage_210] Test passed.Stage 10 - Syntactic errors
This version of the code passes Stage 10 of the extension "Parsing Expressions".