astmaker — A DSL in Rust for programming language designers

GitHub - linkdd/astmaker: Build Abstract Syntax Trees and tree-walking models quickly in Rust.

While working on Letlang, I’ve had to design its AST with the Rust type system, which is a damn good fit for that use case!

Then, I started writing tree-walking algorithms to walk through that AST during the different phases of compilation (scope analysis, code generation, …).

But it has a lot of boilerplate code which I would love to remove.

This is why I made the astmaker Rust crate. It provides a simple DSL to define an AST and a tree-walking algorithm for it. Let’s dive in!

Installation

Simply add to your Cargo.toml:

[dependencies]
astmaker = "0.1"

Define your AST

In this example, we will create an AST for simple math expressions. It will support binary operations (addition, subtraction, multiplication, division) and unary operations (plus sign, minus sign).

To do this, we use the ast! macro:

use astmaker::ast;

#[derive(Debug, Clone, PartialEq)]
pub enum BinOp {
  Add,
  Sub,
  Mul,
  Div,
}

#[derive(Debug, Clone, PartialEq)]
pub enum UnOp {
  Add,
  Sub,
}

ast!{
  location = ();

  pub node Expression =
    | BinOp -> Node<BinaryOperation>
    | UnOp -> Node<UnaryOperation>
    | Num -> Node<Number>
    ;

  pub node BinaryOperation = {
    lhs: Node<Expression>,
    op: BinOp,
    rhs: Node<Expression>,
  }

  pub node UnaryOperation = {
    op: UnOp,
    expr: Node<Expression>,
  }

  pub node Number = {
    value: f64,
  }
}

The first statement of the DSL is to specify what type to use to store the location information of each node. This is useful if you want to map a node to the source code that generated it.

ast!{
  location = ();

  // ...
}

Here, we don’t need any so we set it to the unit type. But the following could have been equally valid:

ast!{
  location = (usize, usize);

  // ...
}

struct LocationInfo {
  filename: String,
  line: usize,
  col: usize,
}

ast!{
  location = LocationInfo;

  // ...
}