(DRAFT) Implementing a parser

tl;dr; If you're in a hurry, this article explains how I created a forgiving, streaming parser for XML-like tags, by trying to imagine that the parser is a coffee machine. I explain what I did right and what went wrong.

I always avoided writing my own parser, because I read articles, and watched videos about implementing lexers/ parsers, and for some reason I got to the conclusion that it's the ultimate skill you can have as a software developer... so I kind of thought "maybe I'm not ready yet..."
I hope by the end of this article, you'll discover it's not the case.

If you're curious to find out more this "adventure", read below and I'll explain how I created my first lexer/ parser in Node.js.

The problem

This is the kind of text I want to parse:

Some text... blah, blah, < blah >
<brokenTag meta1=data1 ... Some more text
Even more text
spam spam spam 
The end of the text
unfinished tag <tag3 />

This looks like XML, but it's not just that.
Tipically 99% of the text should be just normal text and only a few XML-like tags would be processed.
It's expected that a large number of tags are badly formed, invalid XML and they shouldn't crash the parser.

I admit I avoided creating this parser many, many times. But after trying a lot of Node.js parsing libraries, failing miserably, and wasting a lot of time, I thought to myself: "Ok, I have no other choice but to write my own parser".

If you read articles about text parsing, you'll often read that it's recommended to create a lexer, then a separate parser, a separate interpreter, a separate compiler, etc.
I didn't do that the first time (And I regretted it dearly...)

Instead, I tried a different approach: I wanted to think about the parser like it's a real, physical object, that consumes things and generates new things.

Thinking about abstract stuff as physical objects is a very efficient technique and it's used since forever (just look for the terms: spatial memory, memory palaces)

High level approach

I believe it's useful to start with the high level API and slowly build the details when they're needed. Because starting with the low level implementation will just end up building a huge pile of functions, not really designed to work together, so the library will need a refactor anyway.

So, let's try to imagine processing text like grinding a sack of coffee, with a grinder.
We can interact with the coffee grinder in only 2 ways:

  1. fill the drawer with beans, scoop by scoop; the grinder will process the beans automatically until the drawer is empty;
  2. push the finish button to get the final product.
    Once we press "finish", we cannot use the grinder again, we need a new one. Not environment friendly at all, I know!! But this is an imaginary grinder, so it's OK.

So the "english-code" would look like this:

I have a sack of coffee
I have a new coffee grinder
While there's still coffee in the sack:

  • get a scoop from the sack
  • push the scoop into the grinder
  • the coffee beans are crushed one by one
    Once the sack is empty, press "finish" and get the product.

So what are the beans and what is the product? Before implementing anything, we have to know what's the input and what's the output.
The "beans" are Javascript strings. A "bean" is a single character.
The output is a Syntax Tree that represents the text in a such a way to be traversed depth-first, because the leafs of the tree need to be interpreted/ executed.
There's no "standard" way, or structure for implementing a Syntax Tree, every implementation is different. But in general you want to have each logical chunk separated and some information like: the full text, the type, other meta-data that makes sense, the position where it starts in the original text (useful for debug) and a list of children.

The high level "english-JS" code would look like this:

const sackOfCoffee = fs.createReadStream(file, { encoding: 'utf8' })
const grinder = new Parser()
sackOfCoffee.on('data', scoop => {
  grinder.push(scoop)
})
sackOfCoffee.on('end', () => {
  product = grinder.finish()
})

If we ignore some stuff around this code and use different variable names, that's the high level parser API right there!

Internals of the parser

Ok, so the parser is not an opaque "thing"... We have to look under the hood and think about the internals.

Let's try to imagine the internal components as physical objects too:

  • the crushing mechanism takes the beans one by one and looks at the specific caracteristics of each one and ...?
  • the state is a delicate and precise mechanism of gears that changes with the caracteristics of the current bean

In other words, the parser is just a huge if / else-if / else block.

Initially I built just a Parser, it was supposed to identify Tokens and build the Syntax Tree.

Many lexers use a function called "Peek" to look at the next character and decide the state based on that. This parser can't use that, because the data is a steam, so it can't know what characters are coming next.
This also means that there are no intermediary states. If the parser receives 1 character, it processes that and it stops and waits to receive another character, or for the "finish" button to be pressed.
There's a bit of processing once the "Finish" function is called, in case for example, the last processed tag is a open and not closed double tag, so it has to be converted to raw text.

Benchmarks

I don't care about the speed of the parser per se. Also I don't want to praise my libary, or point the finger to other libraries that might be slower. This kind of parser is a bit unique anyway, because most of them will crash loudly as soon as they find a syntax error.

Benchmarks are useful just to make sure I'm not doing something obviously wrong, by comparison to similar tools. If for example my parser takes 2x more time (or less time!) to process the same file compared to other similar tools, it's a sign I'm doing something wrong.

@notes #