Parser Combinators

Parser Combinators

Parsing is the act of taking less structured input like text, and turning it into more structured data, like objects.

Many of you will be familiar with using regex to parse text, and some of you might know about tree-sitter, a heavy-duty parsing library which powers the syntax highlighting in your code editor.

But regex gets messy on complex tasks, and tree-sitter often is overkill — for this middle ground, parser combinators are perfect. Not many people know about them, so allow me to show you!

The partial parser

The smallest unit of parsing we’ll be looking at is the partial parser. It gets to decide where to cut the input string, and then it returns a tuple consisting of whatever and the rest of the string.

It can be any old function, as long as it returns such a tuple! It can even use regex inside.

const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

Chaining

A single parser function won’t do much on its own; but by applying multiple parsers in sequence, we can consume the entire input step by step.

const pHello: Parser<string> = (input: string) => {
  if (!input.startsWith("Hello")) throw new Error();

  return ["Hello", input.substring(5)];
};

const pIgnoreWhitespace: Parser<null> = (input: string) => {
  const match = input.match(/^\s+/);
  if (match == null) throw new Error();

  const spaces = match[0];
  return [null, input.substring(spaces.length)];
};

const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

const [token1, input2] = pHello("Hello 100");
const [token2, input3] = pIgnoreWhitespace(input2);
const [token3, input4] = pInteger(input3);

console.log(token1, token2, token3); // "Hello", null, 100
console.log(input4); // empty!

Chaining

Or, and this is where the real power of partial parsers comes in: we wrap the chain up as a new parser of its own.

const pHello100: Parser<[string, null, number]> = (input: string) => {
  const [hello, rest1] = pHello(input);
  const [space, rest2] = pIgnoreWhitespace(rest1);
  const [number, rest3] = pInteger(rest2);

  return [[hello, space, number], rest3];
};

pSeq

Or we generalize even further and provide a function that does the chaining! “Feeding the rest of the string into the next parser” is super generic after all, and doesn’t really depend on what any single parser does.

Getting the types right is tricky, but TypeScript is perfectly capable of expressing these complex variadic types.

type Parsers<T extends unknown[]> = { [K in keyof T]: Parser<T[K]> };

const pSeq = <T extends unknown[]>(...parsers: Parsers<T>): Parser<T> =>
  (input) => {
    const results = [] as unknown as T;
    let rest = input;
    for (const p of parsers) {
      const [val, next] = (p as Parser<unknown>)(rest);
      results.push(val);
      rest = next;
    }
    return [results, rest];
  };

Combinators

Since pSeq combines many parsers into a new parser, we call it a parser combinator.

Take a moment to appreciate the functional madness going on: pSeq is a function that takes parsers, which are functions, and it returns another parser, which is also a function.

And only then do we actually start the parsing, by calling the resulting function with data.

It’s like we are building up this construct of nested functions to create a complex program. Kinda cool!

By the way

If splitting a string into many tokens feels somehow related to .reduce then you have good instincts. What we are doing here is actually the dual, which is called an unfold in functional circles (reduce is referred to as a fold).

While a fold uses intermediate state — the accumulator — to combine a list of things into one, an unfold uses intermediate state to split one thing into many.

Yay, maths!

Tuples are unwieldy

If the point of parsing is to get structured, often human-readable data out of raw strings, then a tuple of values like ["Hello", null, 100] can hardly be the end goal.

We could of course map over the result to transform it into a more convenient shape.

const pHello100 = pSeq(...);
const [result, rest] = pHello100("Hello 100");

console.log(result); // ["Hello", null, 100]

const parsed = {
  greeting: result[0],
  who: result[2],
};

pMap

But this is not in the spirit of parser combinators! Like before, we can also wrap the mapping into a new parser combinator itself.

pMap takes a parser and a function; the function will be applied to the eventual result after parsing.

const pMap = <T, R>(parser: Parser<T>, fn: (value: T) => R): Parser<R> =>
  (input: string) => {
    const [value, rest] = parser(input);
    return [fn(value), rest];
  };

const pGreeting = pMap(
  pHello100,
  ([greeting, _, who]) => ({ greeting, who }),
);

const [parsed, rest] = pGreeting("Hello 100");

console.log(parsed); // { greeting: "Hello", who: 100 }

pRepeat

Before we hop into a practical example, let me show the third fundamental parser combinator: pRepeat — it takes a given parser and applies it over and over again until it can’t.

It’s the * of regex, as a combinator!

const pRepeat = <T>(parser: Parser<T>): Parser<T[]> =>
  (input: string) => {
    const values: T[] = [];
    let rest = input;
    while (true) {
      try {
        const [value, next] = parser(rest);
        values.push(value);
        rest = next;
      } catch {
        return [values, rest];
      }
    }
  };

const pNumber: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

const pSemicolon: Parser<string> = (input: string) => {
  if (!input.startsWith(";")) throw new Error();

  return [";", input.substring(1)];
};

const pNumberCsv = pRepeat(pSeq(pNumber, pSemicolon));

pNumberCsv("10;20;30;");
// [[[10, ";"], [20, ";"], [30, ";"]], ""]

Let’s build a parser!

We have enough tools now to start parsing actual, real-world data!

Above is a sample output of me pinging Cloudflare. There’s tons of useful info in there, so let’s parse it into structured data — how about this:

type PingResult = {
  header: PingHeader;
  packets: IcmpPacket[];
  statistics: PingStatistics;
};

type IcmpPacket = {
  byteCount: number; from: string;
  seq: number; ttl: number; time: number;
};

type PingHeader = {
  targetIp: string;        // 1.1.1.1
  resolvedIp: string;      // 1.1.1.1 but in parentheses
  icmpPayloadSize: number; // 56
  totalPacketSize: number; // 84
};

type PingStatistics = {
  packetsTransmitted: number; packetsReceived: number;
  packetLoss: number; time: number;
  rtt: { min: number; avg: number; max: number; mdev: number };
};

Bits and Bobs

We have some recurring things in this output like decimal numbers or IP addresses. So let’s set those up first.

// Exact text, like "PING"
const pString = (text: string): Parser<string> => (input: string) => {
  if (!input.startsWith(text)) throw new Error();

  return [text, input.substring(text.length)];
};

// Whole numbers, like 64
const pInteger: Parser<number> = (input: string) => {
  const match = input.match(/^\d+/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

// Numbers with an optional fraction, like 68.7
const pDecimal: Parser<number> = (input: string) => {
  const match = input.match(/^\d+(\.\d+)?/);
  if (match == null) throw new Error();

  const digits = match[0];
  return [Number(digits), input.substring(digits.length)];
};

// Four bytes and three dots, like 1.1.1.1
const pByte = pMap(pInteger, (n) => {
  if (n > 255) throw new Error();
  return n;
});

const pDot = pString(".");

const pIpV4Address = pMap(
  pSeq(pByte, pDot, pByte, pDot, pByte, pDot, pByte),
  ([a, _1, b, _2, c, _3, d]) => `${a}.${b}.${c}.${d}`,
);

// At least one space
const pWhitespace: Parser<null> = (input: string) => {
  const match = input.match(/^\s+/);
  if (match == null) throw new Error();

  return [null, input.substring(match[0].length)];
};

The header

The first line should be easy, it’s just some pSeq of parsers and then a pMap to finagle it into PingHeader shape.

const pPingHeaderParts = pSeq(
  pString("PING"), pWhitespace, pIpV4Address, pWhitespace,
  pString("("), pIpV4Address, pString(")"), pWhitespace,
  pInteger, pString("("), pInteger, pString(")"),
  pString(" bytes of data."),
);

const pPingHeader = pMap(
  pPingHeaderParts,
  ([a, b, c, d, e, f, g, h, i, j, k, l, m]) => ({
    targetIp: c,
    resolvedIp: f,
    icmpPayloadSize: i,
    totalPacketSize: k,
  }),
);

A packet

Actually the packets are also a pSeq of parsers, followed by a pMap. This parsing stuff is really easy, hey!

const pIcmpPacketParts = pSeq(
  pInteger, pString(" bytes from "), pIpV4Address,
  pString(": icmp_seq="), pInteger,
  pString(" ttl="), pInteger,
  pString(" time="), pDecimal, pString(" ms"),
);

const pIcmpPacket = pMap(
  pIcmpPacketParts,
  ([a, b, c, d, e, f, g, h, i, j]) => ({
    byteCount: a, from: c, seq: e, ttl: g, time: i,
  }),
);

The statistics

Could you imagine doing this in regex by the way?

const pUselessLine = pSeq(
  pString("--- "), pIpV4Address, pString(" ping statistics ---"),
);

const pStatsLine1 = pSeq(
  pInteger, pString(" packets transmitted, "),
  pInteger, pString(" received, "),
  pDecimal, pString("% packet loss, time "),
  pInteger, pString("ms"),
);

const pStatsLine2 = pSeq(
  pString("rtt min/avg/max/mdev = "),
  pDecimal, pString("/"), pDecimal, pString("/"),
  pDecimal, pString("/"), pDecimal,
  pString(" ms"),
);

const pPingStatistics = pMap(
  pSeq(pUselessLine, pWhitespace, pStatsLine1, pWhitespace, pStatsLine2),
  ([_1, _2, [a, b, c, d, e, f, g, h], _3, [i, j, k, l, m, n, o, p, q]]) => ({
    packetsTransmitted: a, packetsReceived: c,
    packetLoss: e, time: g,
    rtt: { min: j, avg: l, max: n, mdev: p },
  }),
);

Ping packets, parsed!

And boom, that’s pretty much it! Just one more pSeq and pMap to wrap all the parts together, and we have built a complete parser for the ping command.

That was super easy, right?

const pPingSummary: Parser<PingResult> = pMap(
  pSeq(
    pPingHeader,
    pRepeat(pMap(pSeq(pWhitespace, pIcmpPacket), ([_, packet]) => packet)),
    pWhitespace,
    pPingStatistics,
  ),
  ([header, packets, _, statistics]) => ({ header, packets, statistics }),
);

Go give it a try

In a single post we built a fairly complicated parser from literally zero, and a hand-rolled parser combinator library along the way!

It’s much easier to create correct and maintainable parsers this way than with a regex; once you start nesting pSeq calls, the equivalent regex would become an unreadable mess, while the combinator approach gives you something squeaky clean.

In case you are missing fancier features like backtracking or lookahead, rest assured that parser combinators can handle those scenarios as well, since at the end of the day it’s all just functions composed together.

Go give them a try next time you have to parse something — parser combinators are a really elegant solution to the parser problem, and many more people should use them!