Parser combinators for the "modern" web

To use arcsecond we first have to install it, canonically with:

npm install arcsecond

Let's use ES6 imports to get some helper functions to start working with. These functions are mostly parsers that take other parsers as inputs. If this sounds complicated, I hope it will become more clear later on.

import { sequenceOf, many1, choice, letters, digits, optionalWhitespace,
         str, between, char, many, regex, sepBy, anythingExcept } from "arcsecond";

Remember that to run your program with nodejs, using ES6 imports, you have to use the esm module like so (you may have to install it first):

node -r esm src/utils/parseTextarea.js

So let's start working on our grammar requirements. Bold text is to be enclosed in * so we want to parse text inside of *. This can be easily achieved by using the parser combinator between.

const betweenStars = between (char('*')) (char('*'));
const boldParser = betweenStars (many(wordParser));

console.log(boldParser.run("*this is some bold text*"));

Running this script in nodejs will give us the following result:

{
  isError: false,
  result: [ 'this ', 'is ', 'some ', 'bold ', 'text' ],
  index: 24,
  data: null
}

So we have succesfully parsed the words that need to be bold into an array of results. The results are in an array because each of them is parsed by wordParser and then boldParser checks for many of them between "*". This way we combine the wordParser and the betweenStars parser into a more powerful one. Still in the greater concept this is not yet that useful since we need to add some information about what we parsed, in order to build our AST.

const boldParser = betweenStars (many(wordParser)).map (results => ({
    type: 'boldText',
    value: results.join ('')
}));

In the second implementation of boldParser we are now giving a type to our data. This way we keep the imprortant values, as well as the structure information needed for representing it later. Note that map works on the results array by default. There are also ways to manipulate the data field for stateful parsers, but these will be out of the context of this post.

{
  isError: false,
  result: { type: 'boldText', value: 'this is some bold text' },
  index: 24,
  data: null
}

Those with keen eyes will have noticed that I have used the parser wordParser without introduction or definition. I will introduce it later, but as of now think of it as a parser for everything except special symbols in our text.

With these in mind and the use of of the various helpers from arcsecond we can define the rest cases of our grammar. We can also define two helper functions join and output, that we can use to map over our results.

const join = array => array.join ('');

// notice the use of currying for easier application with map
const output = type => array => ({
  type: type,
  value: array
  });

const replyParser = sequenceOf([
    str('>>'),
    digits
]).map (results => output ('reply') (results));

const quoteParser = sequenceOf([
    char('>'),
    optionalWhitespace,
    wordParser
]).map (output ('quote'));

const betweenParens = between (char('(')) (char(')'));
const betweenBrackets = between (char('[')) (char(']'));
const urlParser = sequenceOf([
    choice([
        str('https://'),
        str('http://'),
        str('/')
    ]),
    letters,
    char('.'),
    letters
]).map(join);
const linkParser = sequenceOf([
    betweenBrackets(wordParser),
    betweenParens(urlParser)
]).map (results => ({
    type: 'link',
    url: results [1],
    desc: results [0]
}));

const plainParser = wordParser.map (output ('plain'));

The (probalby misnamed) wordParser that is the backbone of many of the afformentioned parsers is assumed that it works likeso: it consumes anything, except the special symbols of our grammar. This is an issue that I haven't completely solved, since I've not yet decided if I want to allow the out of context use of these symbols. Naively the wordParser can be implemented as below:

const wordParser = many1 (anythingExcept (regex (/^(\*|\]|\)|\n|>|\(|\[)/))).map(join);

Two things are of notice here. Fist the very powerful regex parser. Second the problems that arise by the implementation. If the symbols { *, [, ], >, (, )} happen to appear in other uses apart from their structural meaning, the rest of the text will be lost and not parsed.

This can be solved by implementing escapes, though I'm not sure this would be useful for inputing comments on a web application.

With all our basic parsers in place we can now define what a paragraph is. For short texts, like the ones we deal with hear, it's enough to assume that a paragraph is denoted by a newline. Our work is mostly done, we just have to combine our work:

const paragraphParser = many (choice ([
    replyParser,
    boldParser,
    urlParser,
    quoteParser,
    linkParser,
    plainParser
])).map (output ('paragraph'));

export const inputParser = sepBy (char ('\n')) (paragraphParser);

So a paragraph is defined as many runs of a choice of parsers. We run the paragraphParser on every body of text that is separated from any other with a newline and done! The result is a tree as the following example:

[{ type: 'paragraph', value: [
    { type: 'plain', value: "This is some text" },
    { type: 'bold', value: "and some bold text." }
]},
 { type: 'paragraph', value: [
     { type: 'quote' value: "> We quote someone."}
 ]}
]

Our AST is ready for any transformation we want to impose on it!

The parser presented here is surely a naive implementation, and barely touches the surface of what parser combinators can do. The case of recursive parsers as left as an exploration for the reader! However with few lines of code and a quite transparent logic we can impose our structure to any kinds of text.

That's all for now! See you next time.