Parser Combinators

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

▸Code definition·pInteger

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.

▸Code definition·pHello

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

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

▸Code definition·pIgnoreWhitespace

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)];
};

▸Code definition·pInteger

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.

▸Code definition·pHello100

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.

▸Code definition·pSeq

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.

▸Code definition·pMap

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!

▸Code definition·pRepeat

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];
      }
    }
  };

▸Code definition·pNumber

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)];
};

▸Code definition·pSemicolon

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.

▸Code definition·pString

// 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)];
};

▸Code definition·pInteger

// 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)];
};

▸Code definition·pDecimal

// 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)];
};

▸Code definition·pIpV4Address

// 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}`,
);

▸Code definition·pWhitespace

// 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.

▸Code definition·pPingHeaderParts

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

▸Code definition·pPingHeader

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!

▸Code definition·pIcmpPacketParts

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

▸Code definition·pIcmpPacket

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?

▸Code definition·pUselessLine

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

▸Code definition·pStatsLine1

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

▸Code definition·pStatsLine2

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

▸Code definition·pPingStatistics

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?

▸Code definition·pPingSummary

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!