Parser Patterns: Flat AST

An area of computer science that I find particularly enjoyable is text parsing. There is a lot more depth to it than you expect, especially when you start to look at ways to squeeze out more performance. In this endeavor, I think it is beneficial to read the source code of existing solutions, because often people that have approached this problem before you have thought of interesting approaches to solving this kind of problem.

The source that I read most recently was Zig's AST parser. To simplify and put their approach into words, they gather the tokens produced by the lexer into an array, and then feed this to the parser. The parser can then reference tokens by index. As the parser constructs nodes, it pushes them into an array, and so nodes can also reference each other by index. Eventually you end up with an array of tokens and an array of nodes, referencing each other by their positions in their arrays, which represents the entire AST. In contrast to the way you might have learnt to build a parser for the first time, where you likely were allocating a node each time you needed one, this approach just needs to allocate space for the arrays, reducing the number of allocations required, and making cleanup much easier. This style is reminiscent of the handle-based approach to referencing that you might see in code for a game engine.

For the most part, Zig doesn't create a unique payload of data per kind of node, as a lot of nodes actually share similar shapes. For instance, an identifier and an integer might both simply reference a token index, so we can create a shared structure that both of these kinds of nodes use.

Where this gets interesting is when you have a node that can reference any number of other nodes. A "block statement" is a good example of this. In C-like languages this is code that is fenced in by braces:

{
    let a = 123;
    let b = 456;
}

How does a parser like this represent an arbitrary long set of nodes if we aren't just allocating a new node every time we see one? A simple approach might be to mark the start and end indices of the nodes that are contained in the block, so from our example above:

[0] = Block
[1] = Let(a)
[2] = Let(b)

The node for the block would contain a range of [1-3) to tell the parser which nodes are inside of the block. This however falls apart once we introduce some nesting. Consider the following code:

{
    let a = 123;
    {
        let b = 456;
    }
    let c = 789;
}

The resulting node array might look like:

[0] = Block
[1] = Let(a)
[2] = Block
[3] = Let(b)
[4] = Let(c)

If we took the same approach as before, the outer block would have a range of [1-5), but this overlaps with the inner block's range. We are accidentally including the let statement that is inside the inner block.

Instead of storing ranges of nodes, we could store a list of node indices. Then in the example above, the outer block would store the indices [1, 2, 4], and the inner block would store [3]. However, we don't want to store these arrays directly on the nodes themselves, because our current solution intentionally keeps nodes a fixed size. By ensuring that all nodes are of the same size, we can store them compactly in a contiguous array, which results in better cache locality; a great trait for a parser/compiler. We'll take the "Struct of Arrays" (SoA) approach and add another array to our AST; this one for "node sequences".

As we parse the nested blocks, we'll push into our node sequences array the indices of the nodes that matter for the blocks, and then keep a note of the start/end indices into the node sequences array in the nodes themselves. There's a bit of complexity here as you can tell from the wordy language, but the performance gain is often worth it. Our resulting AST might look something like:

// ast
{
    tokens = [...]
    nodes = [Block, Let(a), Block, Let(b), Let(c)]
    node_sequences = [1, 2, 4, 3]
}

// outer block node
{
    kind = Block
    data = { start = 0, end = 3 } // child nodes are at the indices stored in node_sequences from 0..3
}

// inner block node
{
    kind = Block
    data = { start = 3, end = 4 } // child nodes are at the indices stored in node_sequences from 3..4
}

We still need to store the indices in the node sequences array in the correct order, and it can be quite easy to trip over yourself and accidentally overlap two or more sequences when dealing with nested nodes. The way to deal with this is to create a temporary array that holds the sequence until you are done parsing your node, and then push those indices into the array on the AST at the same time. I've found that usually my nodes and node sequences arrays tend to end up "reversed", because I'm parsing child nodes completely before their parents, so I end up pushing those into the arrays first.