80/20-parsing

Zig day in Boston was a great time! I helped hack on a new parser for the Zig programming language. I learned two things.

  1. We can create a very lean abstract syntax tree by keeping the program text in memory. Then a node in the AST needs to only consist of the node tag (type of node), an index into the program text where the corresponding token starts, and an index into the program text where the node ends.
  2. You have the program text anyway, so you can choose to parse only 80 percent of the language features into an AST. For the other 20 percent, instead of operating on the AST, you go look at the program text to see what is happening.

    3. An example is parsing the pub modifier keyword in Zig. The rules for pub are a bit tricky: it can appear on any container declaration, so every variable definition or function definition in a struct can be pub, but it cannot appear before a local variable definition. In effect pub cannot appear inside a function body, and this is a syntax error, not a semantic error.

    Zig's official grammar solves this by creating a new AST node when it encounters pub. Then the grammar has separate nodes for container declarations and for function body blocks.

    The ZIRP (ZIg Resilient Parser) solution is different: when we encounter pub, we skip the token entirely, and just parse what comes after. If some consumer of the AST wants to know whether a function declaration is pubpub block in the AST, avoiding extra nodes and complexity.

    On reflection, this is a specific instance of two general patterns:

    1. Sometimes it's better to redo a calculation rather than store the result somewhere.
    2. Specializing code to downstream tasks often allows you to skip a bunch of unnecessary work.
    It's probably worth it to write about those in more detail at a later point. For now, I'm going to have a go at implementing the other 79 percent of Zig syntax we still need to parse.

    home