Basic Scanning
I didn't know the baby's powers, so I covered the basics.
In the context of programming languages, a scanner can be a very untidy piece of code. As you will see, performing basic scans is rather simple, and Robert Nystrom calls it "a switch statement with delusions of grandeur". This might be true for single characters like ( and {, and also, up to a certain point, for strings in the form "some string". Sometimes, however, a scanner might need to do more than a simple switch statement, for example when reading operators made of two characters like != or decide whether a dot is part of a number, as in 6.42 vs 6.sqrt().
For this reason, while we will start implementing the scanner in a very trivial way, at a certain point we will stop and perform a refactoring of the code that will allow us to easily implement the remaining steps. Granted, the code could be designed properly from the ground up, but it's useful to show less experienced coders that refactoring is an integral part of the software development process, and thus avoid the misconception that you should start writing code with the perfect plan in mind.
Step 1 - Scanning: Empty file
The code that CodeCrafters provides as an initial template is good enough to pass the first test. Let's have a look at what it does.
src/main.rs
use std::env;
use std::fs;
fn main() {
let args: Vec<String> = env::args().collect();
if args.len() < 3 { 1
eprintln!("Usage: {} tokenize <filename>", args[0]);
return;
}
let command = &args[1];
let filename = &args[2];
match command.as_str() {
"tokenize" => { 2
// You can use print statements as follows for debugging, they'll be visible when running tests.
eprintln!("Logs from your program will appear here!");
let file_contents = fs::read_to_string(filename).unwrap_or_else(|_| {
eprintln!("Failed to read file {}", filename);
String::new()
});
// Uncomment this block to pass the first stage
if !file_contents.is_empty() {
panic!("Scanner not implemented"); 3
} else {
println!("EOF null"); // Placeholder, replace this line when implementing the scanner 4
}
}
_ => {
eprintln!("Unknown command: {}", command);
}
}
}The code performs a very simple check of the command line arguments 1, which is sufficient for now. It is usually a good idea to delegate such tasks to a specific library like clap, but the initial template looks good enough.
For the time being, our program has a single command: tokenize 2. The code reads a file using fs::read_to_string [docs] and is supposed to call the code that creates the tokens and print them on the standard output. At the moment, for non-empty files it just calls panic! 3 [docs], which is a good way to handle a final error condition.
The file processed during the first test is, however, empty, so the program prints EOF null 4 and terminates.
CodeCrafters
Stage 1 - Scanning: Empty file
This version of the code passes Stage 1 of the base CodeCrafters challenge.
Step 2 - Scanning: Parentheses
The next step is where we actually start looking at the characters we read from the file and process them.
The output of read_to_string is a String so we can use its method chars [docs] to create an iterator over all characters in it. We can expect the scanner to be a big function, so it's reasonable to isolate the logic into a function tokenize. For now, however, said logic is not too complicated. We just run a loop over the iterator with for_each [docs]. The method accepts a function that is applied to every item, and for now that can be a simple closure [docs].
In this stage, we are tasked with identifying round brackets, or parentheses, which can easily be done with a match expression.
src/main.rs
use std::env;
use std::fs;
use std::str::Chars;
// Process each character in the iterator
// `chars` and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
fn tokenize(chars: Chars) {
chars.for_each(|c| match c {
'(' => println!("LEFT_PAREN ( null"),
')' => println!("RIGHT_PAREN ) null"),
_ => println!("UNDEFINED TOKEN"),
});
}
fn main() {
let args: Vec<String> = env::args().collect();
if args.len() < 3 {
eprintln!("Usage: {} tokenize <filename>", args[0]);
return;
}
let command = &args[1];
let filename = &args[2];
match command.as_str() {
"tokenize" => {
// You can use print statements as follows for debugging, they'll be visible when running tests.
eprintln!("Logs from your program will appear here!");
let file_contents = fs::read_to_string(filename).unwrap_or_else(|_| {
eprintln!("Failed to read file {}", filename);
String::new()
});
// Uncomment this block to pass the first stage
if !file_contents.is_empty() {
panic!("Scanner not implemented");
} else {
println!("EOF null"); // Placeholder, replace this line when implementing the scanner
}
// Call the tokenizer of the whole
// content of the input file.
tokenize(file_contents.chars());
println!("EOF null");
}
_ => {
eprintln!("Unknown command: {}", command);
}
}
}CodeCrafters
Stage 2 - Scanning: Parentheses
This version of the code passes Stage 2 of the base CodeCrafters challenge.
Step 3 - Scanning: Braces
Curly brackets, or braces, are the second type of brackets used in Lox. Given what we did in the previous step, adding support for them is almost trivial.
src/main.rs
// Process each character in the iterator
// `chars` and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
fn tokenize(chars: Chars) {
chars.for_each(|c| match c {
'(' => println!("LEFT_PAREN ( null"),
')' => println!("RIGHT_PAREN ) null"),
'{' => println!("LEFT_BRACE {{ null"),
'}' => println!("RIGHT_BRACE }} null"),
_ => println!("UNDEFINED TOKEN"),
});
}The only caveat in Rust is that the characters {} are used in formatting macros like println! and format! [docs] to act as argument placeholders. For this reason, we need to escape them as {{ and }}.
CodeCrafters
Stage 3 - Scanning: Braces
This version of the code passes Stage 3 of the base CodeCrafters challenge.
Step 4 - Scanning: Other single-character tokens
Now that the basic logic to parse single characters is in place, we can easily extend it to other single-character lexemes. In this stage, we need to add support for the following characters:
, COMMA
. DOT
- MINUS
+ PLUS
; SEMICOLON
* STAR
The easiest solution is to add them to the match expression like we did for brackets.
src/main.rs
// Process each character in the iterator
// `chars` and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
fn tokenize(chars: Chars) {
chars.for_each(|c| match c {
',' => println!("COMMA , null"),
'.' => println!("DOT . null"),
'-' => println!("MINUS - null"),
'+' => println!("PLUS + null"),
';' => println!("SEMICOLON ; null"),
'*' => println!("STAR * null"),
'(' => println!("LEFT_PAREN ( null"),
')' => println!("RIGHT_PAREN ) null"),
'{' => println!("LEFT_BRACE {{ null"),
'}' => println!("RIGHT_BRACE }} null"),
_ => println!("UNDEFINED TOKEN"),
});
}This code passes the test, so we might move on to the next stage.
CodeCrafters
Stage 4 - Scanning: Other single-character tokens
This version of the code passes Stage 4 of the base CodeCrafters challenge.
Step 5 - Scanning: Lexical errors
It's time to start handling errors, and this is usually when things become a bit more complicated. In this case, we want to output a line like
[line N] Error: Unexpected character: <character>
If the message didn't contain any line number, we could do something like
src/main.rs
fn tokenize(chars: Chars) {
chars.for_each(|c| match c {
...
'{' => println!("LEFT_BRACE {{ null"),
'}' => println!("RIGHT_BRACE }} null"),
other => println!("Error: Unexpected character: {}", other),
});
}At the moment the challenge asks us to print [line 1] regardless of the actual line, but it's clear that this won't be the case for much longer.
Even if we didn't need the line number, however, there wouldn't be a way to exit with code 65 as the challenge requires. As a matter of fact, the scanner is supposed to continue its task until it reaches the end of the file, and at that point exit with a code that reflects the presence or the absence of errors.
It's clear that the trivial solution we implemented is not good enough to provide such features. Both the line number and the presence of errors are parts of the state of the scanner, so it's worth creating a structure that contains that state and provides convenient methods.
Step 5.1 - Implement a structure
We can start with something essential. Let's create a new file with a simple structure like
src/tokenizer.rs
pub struct Tokenizer<'a> {
pub iter: Chars<'a>,
}The only field is iter, which is an iterator like the one returned by file_contents.chars(). The signature of that method is
pub fn chars(&self) -> Chars<'_>
which explicitly mentions a lifetime parameter. The reason is simple: the function extracts an iterator from a string slice and the iterator is supposed to be valid only as long as the string slice itself. This is the reason why, when we create the structure Tokenizer, we need to specify the lifetime on Chars and on the struct itself, as the latter is linked to the lifetime of the original string slice.
Lifetimes
Lifetimes are an advanced concept in Rust, but the basic idea is not complicated and I recommend at least getting familiar with the syntax. You can read all about lifetimes in the Rust book.
We can now migrate the code of the function tokenize into a method of Tokenizer.
src/tokenizer.rs
use std::str::Chars;
impl<'a> Tokenizer<'a> {
// Process each character in the iterator
// and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
pub fn tokenize(&self) {
self.iter.clone().for_each(|c| match c {
',' => println!("COMMA , null"),
'.' => println!("DOT . null"),
'-' => println!("MINUS - null"),
'+' => println!("PLUS + null"),
';' => println!("SEMICOLON ; null"),
'*' => println!("STAR * null"),
'(' => println!("LEFT_PAREN ( null"),
')' => println!("RIGHT_PAREN ) null"),
'{' => println!("LEFT_BRACE {{ null"),
'}' => println!("RIGHT_BRACE }} null"),
_ => println!("UNDEFINED TOKEN"),
});
}
}Then, we replace the previous implementation of tokenize, importing the structure Tokenizer and defining the module tokenizer.
src/main.rs
use std::env;
use std::fs;
use std::str::Chars;
// Process each character in the iterator
// `chars` and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
fn tokenize(chars: Chars) {
...
}
use crate::tokenizer::Tokenizer;
mod tokenizer;
fn main() {
match command.as_str() {
// Call the tokenizer of the whole
// content of the input file.
tokenize(file_contents.chars());
// Create a new tokenizer and
// instantiate it with the content
// of the input file.
let t = Tokenizer {
iter: file_contents.chars(),
};
// Call the tokenizer.
t.tokenize();In terms of functionality, this gives us exactly what we had before.
Please note that the code of tokenize changed slightly. In the new version we need to clone the iterator, because for_each takes ownership of it and we can't have a method take ownership of a field of its own structure.
Step 5.2 - Add a field to track errors
To solve the current stage, we need to do the following:
- Print errors on the standard error.
- Include the line number and the unknown character in the message.
- Exit with code 65 if any error occurred.
Printing errors on the standard error is trivial, as Rust provides the macro eprintln! [docs] for that purpose.
Let's add a field to the structure to keep track of the presence of errors.
src/tokenizer.rs
use std::str::Chars;
pub struct Tokenizer<'a> {
pub iter: Chars<'a>,
pub errors: bool,
}
impl<'a> Tokenizer<'a> {
// Process each character in the iterator
// and print a token in the form
// `TYPE LEXEME null` if the token is valid or
// `UNDEFINED TOKEN` if not.
pub fn tokenize(&self) {
// an error message if not.
pub fn tokenize(&mut self) {
self.iter.clone().for_each(|c| match c {
',' => println!("COMMA , null"),
'.' => println!("DOT . null"),
'-' => println!("MINUS - null"),
'+' => println!("PLUS + null"),
';' => println!("SEMICOLON ; null"),
'*' => println!("STAR * null"),
'(' => println!("LEFT_PAREN ( null"),
')' => println!("RIGHT_PAREN ) null"),
'{' => println!("LEFT_BRACE {{ null"),
'}' => println!("RIGHT_BRACE }} null"),
_ => println!("UNDEFINED TOKEN"),
other => {
self.errors = true;
eprintln!("[line 1] Error: Unexpected character: {}", other);
}
});
}
}The signature of tokenize must be changed because in case of errors we need to change one of the fields, so the method must accept a mutable reference to self.
In main, we must reflect the mutability of Tokenizer, add the field to the initialisation, and eventually exit with a specific code. For that purpose, we can use process::exit [docs].
src/main.rs
use std::env;
use std::fs;
use std::process;
use crate::tokenizer::Tokenizer;
mod tokenizer;
fn main() {
match command.as_str() {
// Create a new tokenizer and
// instantiate it with the content
// of the input file.
let t = Tokenizer {
let mut t = Tokenizer {
iter: file_contents.chars(),
errors: false,
};
// Call the tokenizer.
t.tokenize();
println!("EOF null");
if t.errors {
process::exit(65);
}
}CodeCrafters
Stage 5 - Scanning: Lexical errors
This version of the code passes Stage 5 of the base CodeCrafters challenge.