tabnas

Why tabnas

tabnas is a parsing engine that can handle any language. It is a compilation target, a “parser VM”, providing a simple state and lookup engine. That makes it fast, and an easy target for agents. Humans can use compiled grammars like ABNF.

The state and lookup engine architecture means it is very easy to extend. You write a parser for JSONC by adding rules to the parser for JSON, and you can keep going all the way to YAML. Every grammar is a plugin, building on other plugins.

The architecture also means you can get nice debugging since the states and lookups are easy to represent in multiple ways including visually, so you can see what’s going on.

The Technical TLDR

“A deterministic top-down predictive rule machine.”

You write a for-loop over parsing tokens. There’s no recursion. Instead you have a stack to keep track of rule depth. Each rule represents a semantic element of your language, and you move to the next rule using a lookup table of token alternates. Rules are hit twice, once on descent and once on ascent, and thus have two states, open and close, and two token lookup tables.

You extend by adding new rules, and modifying the lookup tables (mostly by addition of new token alternates). Each rule and each alternate can have a condition and an action - that’s where you control wierd stuff (left recusion, my old friend), and build your AST, or whatever you want. Defining a grammar this way is surprisingly “not too hard” for humans, and really easy for agents. That’s it. It’s fast, it’s ugly, and it’s a good compile target for BNF.





The Whole Story

I wanted to build a general parser that could be extended by plugins. Say you have plain old JSON, but the values could be expressions, not just fixed values. For example: { "foo": 1+2+3 }. Well, originally I wanted to build a better JSON parser (who doesn’t?) that could handle a more relaxed syntax. I’m lazy and don’t want to quote everything. That accidentally became an extensible parser.

How do you make a parser that can be extended? Most parsers take a grammar and turn it into generated (and yucky) code. Or you write recursive descent by hand. I always believed you had to have some serious computer science mechanism, like ANTLR (which is pretty cool). Then I read a great article about how most real language parsers are written by hand. No, for real. So can you make a hand-written parser extensible? We’ll get back to that…

The original version of my easy-going JSON parser was jsonic, built with pegjs (also cool). So during COVID, with a failing startup (you know the way you are advised to never start a land war in Asia? Well, never do an event management startup. Same thing), a little time on my hands, and permission from some random blog post, I decided, feck it, I’ll just rewrite my JSON parser by hand!

And the initial rewrite was just a manual recursive descent. But then I used some lookup tables to get better performance. And JSON is well-structured, so only has a few rules. That makes it easy-ish to convert recursive descent into a for-loop with a stack. Entering each child structure (object or array), you push a stack entry representing a rule instance, and then pop it again on the way out.

JSON object and its corresponding parser stack states

My real goal was to go beyond JSON, and to parse jsonic - an extension to JSON that has comments, no quotes, and the usual conveniences similar to jsonc and other variants. I needed to parse this specific dialect because it was used as a convenience format in a message-based microservices framework I wrote and maintain - Seneca. And also, yes, not-invented-here syndrome, and just, fun.

Also, the rewrite was my first serious TypeScript project. Thank goodness we don’t have to hand port code anymore! But I learned a lot. During development it became increasingly clear that I could also provide a pure JSON parser just by removing entries from the lookup table. And if that was true, you could turn it around: start with JSON, and then extend the parser to handle jsonic. Hmm. That looks like a general purpose idea! Other formats like YAML and TOML are achievable in the same way!

How tabnas works

Let’s step back and look at how tabnas works. That way you can see how the extensibility falls out of the basic algorithm. Not by design. It was a happy accident. But here we are.

To parse {"foo":1} you want to break the source into a stream of tokens. This is called lexing. Tabnas has a set of registered lexers that do this part (and you add you own). They are mostly pretty braindead (but you can write context driven lexers - if you like) and just attempt to match in order of registration.

After lexing we end up with a token stream:

{"foo":1}

becomes:

{   foo  :   1    }
OB  KEY  CN  VAL  CB

where we give each token a code name, such as OB, “Open Brace”, for {.

Many parsing systems mix lexing (clumps of characters) and parsing (semantic units), forcing both into the grammar with equal status. For example ABNF format, used in most Internet RFCs, often looks like:

   FWS             =   ([*WSP CRLF] 1*WSP) /  obs-FWS
                                          ; Folding white space

   ctext           =   %d33-39 /          ; Printable US-ASCII
                       %d42-91 /          ;  characters not including
                       %d93-126 /         ;  "(", ")", or "\"
                       obs-ctext

   ccontent        =   ctext / quoted-pair / comment

   comment         =   "(" *([FWS] ccontent) [FWS] ")"

   CFWS            =   (1*([FWS] comment) [FWS]) / FWS

This is from https://datatracker.ietf.org/doc/html/rfc5322#section-3.2.2

tabnas has a hard division, and is really all about the parsing stage. Lexing, as far as tabnas is concerned, is something you mostly do yourself, with handwritten functions, or regular expressions. Now, tabnas does provide you with a lot of tools to do this, but fundamentally, you think in terms of rules over tokens, not tokens over characters. Because in general, lexing is the easy and boring part.

Your First Mini Lang

Let’s make a grammar for a miniature language! How about adding numbers?

1+2+3 # and the result should be 6

The builtin lexer already handles numbers and fixed strings, so we can assume our tokens are:

NR - number
PL - plus character

That means we have to parse this series of tokens:

NR PL NR PL NR

Each time we see a number NR we want to add it to the running total. If we see a plus character after a number, then we keep going, otherwise we’re done.

If you’re familiar with ABNF (Augmented Backus-Naur Form) from Internet RFCs, here is our little grammar:

val = add
add = NR [ PL add ]

NR = <number>
PL = "+"

Even if you’re not familiar with ABNF, this probably looks reasonable. We have a rule called val that is built from a child rule called add. The add rule is built from a number token NR, and then an optional section - a plus token PL followed by the add rule again.

Now you could stop here and use the @tabnas/abnf plugin to just compile this ABNF grammar and call it a day, but let’s do the hard work ourselves.

We’ll use Typescript but you could also write this in Golang.

Let’s create a tabnas parser and define its grammar. You can do this with declarative JSON (apart from actions). First, we set some options. We want to have a special custom token PL that represents the + character. And we want to start with the grammar rule val. That means the top level of the grammar tree is a val, representing the final value of the additions.

const { Tabnas } = require('@tabnas/parser')

// Create a new parser.
const tn = new Tabnas()

// Define the grammar.
tn.grammar({

  options: {

    // Define a new token named #PL, a "+" character.
    fixed: { token: { '#PL': '+' } },

    // Start parsing at the 'val' rule.
    rule: { start: 'val' },
  },
  ...

Now we can define our rules. Let’s start with val, which sets up our accumulator for the addition, and expects to have add as a child rule:

  ...
  rule: {
  
    // The 'val' rule holds the running total.
    // Each rule instance has a 'node' representing its value.
    val: {
    
      // Define the "opening" phase of the rule.
      open:  [
      
        // This is an "alternate", it matches any tokens.
        { 
          // "push" down into an 'add' rule.
          p: 'add', 
          
          // An "action" - set the counter to 0.
          a: (r) => { r.node = 0 } 
        }
       ],
  ...

The open array is a list of alternates. We try to match tokens and then perform associated actions. But in this case we are just starting, in the “open” state of the val rule, so we don’t look at any tokens, we just immediately “push” the add rule onto the rule stack. That means the add rule is the next rule to run.

Our action at this point is to set our result value to 0, since nothing has been added yet. Every rule gets an instance, and each rule instance has a node value, where you store the value of that rule.

let’s do some addition!

    ...
    
    // The 'add' rule performs the addition.
    add: {
      open:  [
        { 
          // Match a number - #NR is a built-in token for numbers.
          s: '#NR',
          
          // Add the number to the total.
          a: (r) => { 
            r.parent.node +=  // The parent is the 'val'. 
              r.o[0].val      // Get the value of the first opening token. 
          } 
        }
      ],
    ...

Most alternates try to match a sequence of tokens. In this case the first alternate of the add rule looks for NR, a number. Token names are prefixed with # to make them easier to see.

If we do match a number, our action is to add it to the running total we set up in the val rule. We get our parent’s node (r.parent.node) and add the value of the first token we matched (r.o[0].val). We’re in the “open” state, so r.o holds the sequence of tokens we matched. The val field of a token holds it’s evaluated value, which for numbers NR, is an actual numeric value (thanks lexer!).

Now what?

Well we can’t go any deeper, there are no child rules. So the “open” state transitions to the “close” - we bounce off the bottom of the rule stack. Now we’re going back up again.

  ...
    add:
      ...
      close: [
        // If there is a "+" following the number, keep going.
        { 
          s: '#PL', // This is our "+" token, #PL
          r: 'add'  // "Repeat" the 'add' rule
        }, 
        
        // Else end the rule.
        {}
      ]
  ...

In the first alternate, we try to match a plus token (PL). If it does match, we “repeat” the rule - run the add rule again. A new instance starts in the “open” state, looking for another number to add.

If the first alternate does not match, then we hit the second alternate, and do nothing. This will close our rule, and head back up to the val rule. We do need this empty alternate, because when no alternate matches, that’s a parse error.

Now we’re back up the stack, closing the val rule:

  ...
  val:
    ...
    // Define the "closing" phase of the rule.
    close: [
      {} // Ending "alternate" - does nothing.
    ]
  ...

Again nothing to do, so we successfully complete the parse. The grammar has accepted the input, and we return the value of the top level node:

tn.parse('1+2+3')   // => 6

To recap, you have rules, they can have two states, open and close. Each rule state has a list of alternates, checked in turn. Each alternate can push a new rule onto the rule stack, or repeat a rule at the same stack position. Parsing ends when you’ve walked all the way back up the rule stack. Hence, Tábla na nAistrithe, a Table of Transitions.

You can do this at three levels. You’ve seen the human friendly ABNF grammar, and you’ve seen the agent friendly JSON version. You can also build grammars at the lowest level - a programmatic API. This lets you create parameterised grammars. Many of the standard plugins use this method, so all you have to worry about is configuration. See for example @tabnas/directive, or the monster @tabnas/expr.

Where that leaves us

The grammar is the parser. There’s no generated code to fall out of sync — you install a grammar and it parses, or you compile one from ABNF at runtime. Because the machine is a table, you can inspect it live, render it back to ABNF, or draw it as a railroad diagram. And every parse yields the same shape, { rule, src, kids }, so a walker written once works for every language you define.

Which gets to the point of the whole exercise. Parsers are expensive to write, so most formats never get a good one, and extending a language someone else defined means forking their parser. Here, extension is the normal case, and the grammar is dull enough data that a language model can write it. Between those two, parsing something new stops being a project and starts being an afternoon. That’s the bet, anyway.

(The engine is implemented in both TypeScript and Go, incidentally. The Go port tracks the TypeScript one and runs the same fixtures, so a grammar behaves the same in both. Useful, but not the point.)

Related reading: