Abstract Syntax Trees

An abstract Syntax Tree (AST)

is a tree representation of the abstract syntactic structure of source code written in a programming language

For us it will just be an instance of a Rust data structure, that corresponds with the grammar we want to represent.

Nadezhda AST as enums

Rust has enums that are well suited for the task of modeling ASTs. Once you have a grammar, it is a small step to implement in Rust.

You will encounter one small problem. We will illustrate that with an example. Take the Nadezhda grammar

1 Program -> forward Program
2          | backward Program
3          | stop

If we would translate this into Rust without really thinking we would come up with something like the following code

1 enum Program {
2     Forward(Program),
3     Backward(Program),
4     Stop,
5 }

Which is almost a direct translation. Unfortunately this does not compile. The rust compiler spits out the following warning.

1 error: recursive type `Program` has infinite size [E0072]
2 enum Program {
3     Forward(Program),
4     Backward(Program),
5     Stop,
6 }
7 help: run `rustc --explain E0072` to see a detailed explanation
8 help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Pr\
9 ogram` representable

We remedy this by wrapping the inner programs in a Box.

1 pub enum Program {
2     Forward(Box<Program>),
3     Backward(Box<Program>),
4     Stop,
5 }

Exercises

1. What would be other options to appease the Rust compiler when building recursive types? How would that differ from using Box.
2. Is stop necessary in the Nadezhda grammar?