This series presents the implementation of a parser combinator, step-by-step from scratch explaining how it works.

first, what is a parser combinator?

a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output.

the parser class

This class's object represents the simplest building block of the parser combinator.

class Parser {
  constructor(process) {
    this.process = process;
  }
}

The constructor function takes a function fn = fn(state) -> state, where state is the current state of the parser, and returns a new state.

chaining parsers

The core function is to "chain" parsers, so they can work in sequence, passing the state to each other.

class Parser {
  // ...
  chain(parser) {
    return new Parser(state => {
      return parser.process(this.process(state));
    });
  }
}

The chain method takes a parser as an argument, and return a new parser.

the next function

To be able to do further operations on the result of a parser provided that the status of the parser matches the given status, next method have been added to take the resulting state and operates on it.

class Parser {
  // ...
  next(fn, status) {
    return this.chain(
      new Parser(state => {
        return state.status & status ? fn(state) : state;
      })
    );
  }
}

It simply "chains" a new parser to the current one, which - depending on status value - returns the state that was passed to it as it is, or the state returned from fn.

To simplify working with next, two method have been added.

operating on the state

The ok method works if the status is OK.

class Parser {
  // ...
  ok(fn) {
    return this.next(fn, State.OK);
  }
}

catching errors

The error method works if there was an error.

class Parser {
  // ...
  error(fn) {
    return this.next(fn, State.ERROR);
  }
}

Well, that that doesn't look very useful right now, but in the next post, basic parsers will be implemented using the parser class, and finally they can be "combined" together to make larger parsers.

You can find the full code on github on main branch

npm i pari

import {
  char,
  firstOf,
  sequence,
  zeroOrOne,
  oneOrMore,
  zeroOrMore
} from 'pari';
// the `char` parser matches one char.
// it take a `regex` that matches exactly one char.

const digit = char('[0-9]');

// `firstOf` parser returns the first match in a list of parsers.

const lowerCase = char('[a-z]');
const digitOrLwcase = firstOf([digit, lowerCase]);

// `sequence` parser matches a list of parsers in sequence.

const hex = char('[0-9a-fA-F]');
const byteHex = sequence([char('0'), char('x'), hex, hex]

Thanks for reading 😄.