Zig Parser – Mitchell Hashimoto<br>Mitchell Hashimoto

Mitchell Hashimoto<br>Zig Parser<br>February 11, 2022<br>This is part of the series on Zig compiler internals.

Table of ContentsMultiArrayList<br>Anatomy of the Parser<br>Anatomy of an AST Node<br>AST Node Data<br>Function Declaration<br>Function Prototype<br>Function Identifier<br>AST Data Layout Recap<br>How Parsing Works<br>Parsing a Zig File<br>Parsing a Variable Declaration<br>Parsing a Function Definition<br>Finalizing the AST

Parsing is the next step in the compilation pipeline following tokenization. Parsing is responsible for constructing an abstract syntax tree from a stream of tokens. I’ve previously written about how Zig converts a stream of bytes (source) into a stream of tokens.

The Zig parser is located at lib/std/zig/parser.zig in the Zig source tree. It is available as part of the standard library via std.zig.parse(). The parser takes full source text and returns an std.zig.Ast (defined in lib/std/zig/Ast.zig).

MultiArrayList

From parsing onwards, the Zig compiler uses MultiArrayList structures heavily. You must understand the MultiArrayList in order to understand how the parser works as well as the structure of the created AST.

Before explaining a MultiArrayList, I’ll give a very brief overview of a normal ArrayList (no “Multi”). An ArrayList is a dynamic length array of values. When the array is full, a new larger array is allocated, and existing items are copied into the new array. This is a typical, dynamically allocated, growing (or shrinking) list of items.

For example, consider the Zig structure below:

pub const Tree = struct {<br>age: u32, // trees can be very old, hence 32-bits<br>alive: bool, // is this tree still alive?<br>};

In an ArrayList, many Tree structures are stored like so:

┌──────────────┬──────────────┬──────────────┬──────────────┐<br>array: │ Tree │ Tree │ Tree │ ... │<br>└──────────────┴──────────────┴──────────────┴──────────────┘

Each Tree requires 8 bytes of memory. An array of four trees is 32 bytes of memory.

Why 8 bytes? A u32 requires 4 bytes. A bool only requires 1 byte but since it is in a struct with a u32, it must be 4-byte aligned, so it also takes up 4 bytes (3 bytes wasted). The total is 8 bytes.

A MultiArrayList is similarly a dynamically allocated list of items. However, each field of the type stored in the array list is stored in a separate contiguous array. This has two primary benefits: (1) less wasted bytes due to alignment and (2) better cache locality. Both of these benefits often result in better performance.

Given our Tree structure, a MultiArrayList(Tree) is stored like so:

┌──────┬──────┬──────┬──────┐<br>age: │ age │ age │ age │ ... │<br>└──────┴──────┴──────┴──────┘<br>┌┬┬┬┬┐<br>alive: ││││││<br>└┴┴┴┴┘

Each field for the struct is stored in a separate contiguous array. An array of four trees uses 20 bytes, or 37.5% less memory. This ignores the overhead of the multiple array pointers, but that overhead is fixed so as the number of items in the list grows, it amortizes to a total of 37.5% less memory required for this example.

Why 20 bytes? Since the struct is deconstructed, the age field requires 4 bytes, and our example uses 4 trees, hence 16 bytes. The alive field no longer needs to be 4-byte aligned since it isn’t part of a struct anymore, so it only requires 1 byte (no wasted bytes!). Our example uses 4 trees, hence 4 bytes for alive. This sums to 20 bytes total for both fields.

This page will not dive into how MultiArrayList is implemented. For the purpose of understanding the Zig compiler, it is only important to know that almost every structure (tokens, AST nodes, future IR nodes, etc.) is stored as a MultiArrayList. Compiling a real world program usually generates tens of thousands of “nodes” so this results in huge memory savings and improvements in cache locality.

Anatomy of the Parser

The parser uses a struct called Parser to store in-progress parsing state. This is not a publicly exported struct and is only used to manage internal state of the parse operation. Callers are returned an Ast as a result of a parsing operation, which is explored later in this page.

The structure of the parser at the time of writing is shown below. I’ve inserted newlines to separate the state into functional groups.

const Parser = struct {<br>gpa: Allocator,<br>source: []const u8,

token_tags: []const Token.Tag,<br>token_starts: []const Ast.ByteOffset,<br>tok_i: TokenIndex,

errors: std.ArrayListUnmanaged(AstError),<br>nodes: Ast.NodeList,<br>extra_data: std.ArrayListUnmanaged(Node.Index),<br>scratch: std.ArrayListUnmanaged(Node.Index),<br>};

The first group contains gpa and source. This is the allocator and full original source code of a single Zig file.

In the second group, token_tags and token_starts are the deconstructed results of tokenization. As noted earlier, the parser applies data-oriented design for better memory usage and cache locality. Therefore, token_tags.len == token_starts.len, they’re just the struct fields placed into separate contiguous chunks of...