Learn Rust by building a Brainfuck interpreter, part 3: how you should not build a parser
Introduction¶
This is the third post in a series that builds a Brainfuck interpreter in Rust.
- In the first post, we created the first building blocks for our Brainfuck interpreter in Rust: a data structure for the tape, and a data type for the instructions. The instructions are based on Rust's enums, which allow to build powerful algebraic data types.
- In the second post, we built an execution engine that can execute a Brainfuck program which is represented by an abstract syntax tree in the context of a tape. We used the
Read
andWrite
traits to make our execution function generic, such that we could not only read from standard input and write to standard output, but also, e.g., read from byte slices and write to a vector of bytes. This makes unit testing easy.
Currently, we can only execute programs which are given as abstract syntax trees in Rust data structures, such as this one:
// read two byte values and write their sum
vec![
Read, Right, Read,
Loop(vec![Dec, Left, Inc, Right]),
Left, Write
];
This corresponds to ,>,[-<+>]<.
in Brainfuck source code.
In the current post, we will find ways to transform the latter into the former, i.e., to parse Brainfuck source code and generate an abstract syntax tree.
Please note: I intentionally did this without using libraries because I wanted to build a simple parser from scratch. Since I learned a lot this way, I found it appropriate to write a blog post about the process. However, building a parser with the help of libraries that are designed for this purpose is much easier and less error-prone. In a future post in this series, we will implement a better parser using the Rust crate nom.