Taming the Flat AST: Ergonomics in the Age of Zero Allocations

Last week, I introduced egg, a modern LL(1) parser generator for Go. The response from the community was insightful, particularly regarding egg’s most distinct feature: the flat AST.

To achieve high performance and low garbage collection pressure, egg encodes the entire Abstract Syntax Tree (AST) into a single []int32 slice. While this is excellent for the CPU cache, it can be intimidating for the developer.

One commenter on the Gophers Slack put it perfectly:

"The ‘Traversing the AST’ section really dissuades me from using this tool... I think coming up with a clean, well-typed API might be harder than I think."

They were right. In my previous post, I showed a raw recursive walker that involved manual index arithmetic. It was fast, but it wasn’t pretty.

However, shortly after that post, I implemented ImportEBNF—a feature allowing egg to bootstrap itself by reading EBNF from HTML files. In doing so, I had to "eat my own dog food" and parse a complex grammar using the flat AST.

I discovered that with just a few lines of helper code—and the power of Go 1.23 iterators—we can have the best of both worlds: the performance of a flat memory layout and the readability of a tree traversal.

Step 1: The "View" Struct

The main friction point of a flat AST is that you lose the concept of a "Node" object. You are just holding an integer slice. To solve this without triggering the Garbage Collector, we can define a lightweight "view" struct. This struct doesn’t contain data; it just points to the relevant section of our integer slice.

In egg, I defined a simple node type:

type node struct {
ast []int32       // Valid if .sym != 0
sym import_Symbol // Valid if != 0
tok int32         // Valid if sym == 0
}

Because we pass this by value (or as a lightweight pointer on the stack), we avoid heap allocations entirely. We are simply passing a "window" into our main []int32 array.

Step 2: The Iterator (The Game Changer)

The raw loop I demonstrated in the previous post required manually checking node headers and slicing arrays. But the structure of the egg AST is sequential, making it a perfect candidate for Go 1.23 iterators.

I wrote a generic iterator function that accepts a flat slice and yields node views. It performs the "pointer arithmetic" so you don’t have to:

func iterator(ast []int32) func(yield func(node) bool) {
return func(yield func(node) bool) {
for len(ast) != 0 {
switch v := ast[0]; {
case v < 0:
// Non-Terminal: [-SymbolID, Size, Children...]
n := ast[1]
if !yield(node{ast: ast[2 : 2+n], sym: import_Symbol(-v)}) {
return
}
ast = ast[2+n:] // Advance past the node
default:
// Terminal: Token Index
if !yield(node{tok: v}) {
return
}
ast = ast[1:] // Advance past the token
}
}
}
}

Step 3: Readable Traversal

With those two small helpers, the code for traversing the grammar transforms from manual array manipulation into clean, idiomatic Go.

Let’s look at a real example from the egg source code. We are parsing an EBNF Expression, which consists of a list of Terms separated by pipes (|).

The Grammar:

Expression = Term { '|' Term } .

The Go Code:

// Expression = Term { '|' Term } .
func (m *importer) expression(n node) {
for n := range iterator(n.ast) {
switch n.sym {
case import_Term:
m.term(n)
case 0:
m.w(" |")
}
}
}

This looks almost exactly like a standard AST traversal. You iterate over children, switch on their type, and recurse. The complexity of the memory layout is completely hidden behind the range iterator.

Advanced Pattern: Lookahead with iter.Pull

Sometimes simple iteration isn’t enough. In LL(1) parsers, you sometimes need to peek at the next item to decide what to do. Go’s iter.Pull allows us to "pause" the iterator and manually step through it.

In the factor method of my importer, I needed to handle tokens that might be followed by a range operator (like 0-9 or a…z). I used iter.Pull to inspect the next node without breaking the abstraction:

func (m *importer) factor(n node) {
next, stop := m.pull(n) // Helper for iter.Pull(iterator(...))
defer stop()

for n, ok := next(); ok; {
switch n.sym {
case 0:
tok := m.tok(n.tok)
// ... check token type ...

// Example: Peek ahead to see if next token is a range dash
// if next_n, ok = next(); ...

case import_Group:
m.group(n)
n, ok = next()

// ... handle other cases ...
}
}
}

Conclusion

The initial feedback was valid: raw []int32 manipulation is prone to off-by-one errors and is hard to read. However, by leveraging Go’s type system to create lightweight views and using the new iterator standard, we can build an abstraction layer that costs almost nothing at runtime.

We ended up with:

• Safety: No manual index math in the business logic.
• Readability: Standard for x := range loops.
• Performance: Still zero heap allocations for the tree structure.

If you were hesitant to try egg because of the flat AST, I encourage you to check out the updated documentation. It turns out you don’t need a tree of pointers to write clean code—you just need the right iterator.