Creating an ARM32 emulator in JavaScript, part 7 — Parser combinators

In the previous part we added tests, which keep our code honest as it grows more complex. In this part we get to the fun stuff: parsing assembly. (I can hear the excitement) Since our whole goal is to write assembly and have it turned into real instructions, getting that text into a form we can actually work with is a crucial step.

Parser combinators

How might we parse assembly? There are a lot of parsing methods out there. We are going to use parser combinators for the job. Why parser combinators? Because it is a fairly easy parsing method compared to the alternatives. So what are parser combinators and how do they work?

Parser

A parser is a function that takes an input — the thing that needs to be parsed — and returns a parse result. The result is either a success or a failure. The idea is that these functions are really simple in nature; what they parse is trivial. For example, we can have a parser that just parses the character a. A parser function can be as simple as the following.

const a = (input: string): boolean => input[0] === 'a';

In its most primitive form, this is basically what a parser is: it takes an input and returns whether or not it succeeded.

Because parsers are such simple functions, they are also easy to test.

Nothing stops us from cramming all the logic for parsing everything into a single parser — it just defeats the purpose of this method.

Combinator

These simple functions usually aren’t particularly useful on their own. That’s where the combinator part comes into play. Combinators are higher-order functions that let us combine simple parsers to construct more complex ones. Say our language allows the characters a and b. We now have two parsers, one that parses the character a and one that parses the character b. We can construct a combinator that takes these parsers and succeeds if either of them succeeds, and fails only if both fail.

A good analogy is to think of the simplest parsers as atoms, which compose into molecules, which eventually lead to an entire organism.

A common combinator is either. It takes one or more parsers and succeeds with the first one that matches, failing only if none do.

const either = (...parsers: Parser[]) => (input: string): boolean =>
  parsers.some(parser => parser(input));

As we can see, this function takes parsers — we assume the Parser type is defined for now; we'll give it a proper definition below — and returns another parser. If any of the given parsers succeeds, the combined parser succeeds; otherwise it fails. With higher-order functions like this we can build up arbitrarily complex parsers.

Let’s create a trivial example to see how it works. First, a second parser called b.

const b = (input: string): boolean => input[0] === 'b';

Now assume we have the input "b".

const abParser = either(a, b);

/* this evaluates to true */
abParser('b');

We constructed an ab parser with the either combinator and gave it the parsers a and b. We then call that parser with the input "b". Although the first parser failed, the second one didn't, so our combined parser succeeds.

A quick note on naming: in the source for this project the variadic combinator above is called either, and or is a small two-argument convenience wrapper around it (or(a, b) → either(a, b)). We'll use either from here on.

You might be thinking: what if our input is longer than one character — it never advances through the input. You’re right; that wouldn’t work, so we need to return some kind of state describing where in the input we are. This is the key idea that turns these toy functions into a real parser, and we’ll get to it shortly.

Grammar

Here’s another nice thing about this approach: it maps neatly onto a formal grammar for a language. But hang on — what is a formal grammar? Basically, it’s a blueprint for a language. With a grammar we can check whether a construct is allowed in the language. Conversely, from the grammar we can generate every construct that can be derived from its rules. In other words, a grammar can be used both to recognize and to generate.

A popular format is Backus–Naur Form (BNF), along with Extended Backus–Naur Form (EBNF), which adds some additions to BNF. The format consists of a set of production rules: a symbol on the left-hand side — think of it as the name of the rule — and a right-hand side consisting of one or more symbols or terminals (a literal element). The right-hand side can also contain alternatives, denoted by the | character. To keep things simple, we won't follow it strictly; we just use it as a reference point. A grammar always has a start symbol.

This might sound abstract, so let’s look at an example. Take the following grammar — not strict BNF/EBNF — that we’ll create for our assembly. Assume this is our entire grammar and GeneralPurposeRegister is our start symbol.

GeneralPurposeRegister :
    RegisterNamePrefix RegisterNumberRegisterNamePrefix :
    "R"
  | "r"
RegisterNumber :
    [0-15]

The rule GeneralPurposeRegister is made up of two rules that map to specific values. This can be turned into a parser for GeneralPurposeRegister that is composed of two other parsers, RegisterNamePrefix and RegisterNumber. RegisterNamePrefix is either the literal R or r. RegisterNumber is in the range 0 up to and including 15, which we denote [0-15] (again, not formal BNF/EBNF).

Say we have the input R15.

We can clearly see that it falls within our grammar, but let’s walk through the process.

We start at GeneralPurposeRegister. This rule has two symbols on its right-hand side. The first, RegisterNamePrefix, is a non-terminal, so we expand it. RegisterNamePrefix has two alternative terminals; the first is a capital R, which matches the first character of our input, so RegisterNamePrefix is satisfied. Next we expand RegisterNumber; its right-hand side is the range 0–15. Treating 15 as a single token, it falls within that range, so RegisterNumber is recognized, which completes GeneralPurposeRegister. And voilà — we've verified that our input is allowed by our grammar.

We don’t have to write a formal grammar, but doing so makes our language explicit and easier to reason about.

Implementation

Enough theory — let’s build the actual parser. We start by creating a folder parser-combinators in our modules folder.

Parser class

Next we create our Parser class in parser-combinators/parser.ts.

import { ParserFunction, ParserInterface, ParserState, Result } from './types';

export class Parser<T = any> implements ParserInterface<T> {
  #parserFunction: ParserFunction<T>;

  constructor(parserFunction: ParserFunction<T>) {
    this.#parserFunction = parserFunction;
  }

  parse(input: string, state: ParserState = { position: { index: 0, line: 1, column: 1 } }): Result<T> {
    return this.#parserFunction(input, state);
  }
}

This looks more complex than our earlier examples. What we have is a Parser class that encapsulates a parse function — the thing we wrote in the toy examples — and exposes an explicit parse method.

The parse method takes an input string and, optionally, a parser state. If no state is supplied, a starting state is used as the default. This state gives the parser information about its position in the input, which fixes the problem from earlier where we were stuck at index 0. Alongside the index, we also track the line and column. The method returns a Result<T>, where T is the type of value the result will contain on success, inferred from the type argument passed to the parser.

Types

Let’s create the types we imported. Create a file parser-combinators/types.ts with the following content.

export interface ParserInterface<T> {
  parse(input: string, parserState: ParserState): Result<T>;
}

export type Result<T = any> = Success<T> | Failure;

export type Position = {
  index: number;
  column: number;
  line: number;
};

export type Success<T> = {
  success: true;
  value: T;
  position: Position;
};

export type Failure = {
  success: false;
  message: string;
  position: Position;
};

export type ParserState = {
  position: Position;
};

export type ParserFunction<T = any> = (input: string, parserState: ParserState) => Result<T>;

Let’s take a closer look at Result and ParserState.

Result is either a Failure or a Success. On success we return an object where success is true, value is whatever the parser produced, and position holds the index, column and line. Failure has success set to false and also carries a message describing the error.

ParserState holds the position used by the parse function so it knows where it is in the input.

That’s all there is to the parser itself — pretty simple, right? Now that we have our Parser class, we need some concrete parsers to do the actual work.

Parsers

We are going to divide our parsers into primary, combinator, and utility parsers. The last category is used for introspection rather than for consuming input. Since the source is available on GitHub, we won’t walk through every file here — we’ll go through a representative few to get the hang of how they’re built.

In our parser-combinators folder we create a folder for each category. We'll start with the primary parsers. The first one is char, in primary/char.ts.

import { Parser } from '../../parser';

export const char = (char: string) =>
  new Parser((input, { position }) => {
    const { index, column, line } = position;
    if (input[index] === char) {
      return { success: true, value: char, position: { index: index + 1, column: column + 1, line } };
    }
    return { success: false, message: `Expected ${char}`, position: { ...position } };
  });

Just like the a and b parsers, this parses a single character. It takes a character as input and returns a parser. That parser checks the character at the current index in the input. Crucially — and this is what was missing from our toy examples — it returns the new position: on a match the index advances by one, so the next parser knows where to pick up.

This is the whole trick. Every parser threads position through its result, so we can run them one after another and each starts where the previous one stopped.

Combinators: threading the state

Now that a single parser reports where it ended, we can write combinators that respect that. The most fundamental one is sequence, which runs parsers back to back and only succeeds if all of them do — exactly what we need for a rule like RegisterNamePrefix RegisterNumber.

import { Parser } from '../../parser';

export const sequence = <T = any>(...parsers: Parser[]) =>
  new Parser<T[]>((input, { position }) => {
    const { index, column, line } = position;

    let nextIndex = index;
    let nextColumn = column;
    let nextLine = line;

    const value = [];

    for (const parser of parsers) {
      const result = parser.parse(input, { position: { index: nextIndex, column: nextColumn, line: nextLine } });

      if (!result.success) return result;

      value.push(result.value);

      nextIndex = result.position.index;
      nextColumn = result.position.column;
      nextLine = result.position.line;
    }
    return { success: true, value, position: { index: nextIndex, column: nextColumn, line: nextLine } };
  });

Notice how each iteration feeds the previous result’s position into the next parser. If any parser fails, sequence short-circuits and returns that failure. On success it collects each parser's value into an array and reports the final position.

The real either is the same idea as our toy version, but state-aware. It tries each choice from the same starting position and returns the first success — ordered choice.

import { Parser } from '../../parser';

export const either = <T = string>(...choices: Parser[]) =>
  new Parser<T>((input, state) => {
    for (const parser of choices) {
      const result = parser.parse(input, state);

      if (result.success) return result;
    }
    return { success: false, message: 'Unexpected token', position: { ...state.position } };
  });

Order matters here: either commits to the first match, so when alternatives overlap you list the most specific one first. We'll see exactly that in a moment.

To match repetition — “one or more of something” — we use many.

import { Parser } from '../../parser';

export const many = <T = string>(parser: Parser<T>) =>
  new Parser((input, { position }) => {
    const { index, column, line } = position;
    const value = [];

    let nextIndex = index;
    let nextColumn = column;
    let nextLine = line;

    while (true) {
      if (nextIndex >= input.length) break;

      const result = parser.parse(input, { position: { index: nextIndex, column: nextColumn, line: nextLine } });

      if (!result.success) break;

      value.push(result.value);

      nextIndex = result.position.index;
      nextColumn = result.position.column;
      nextLine = result.position.line;
    }
    if (value.length === 0) return { success: false, message: 'No matches', position: { index, column, line } };

    return { success: true, value, position: { index: nextIndex, column: nextColumn, line: nextLine } };
  });

It keeps applying the same parser, advancing the position each time, until the parser fails or we run out of input. (There’s a sibling, many0, that succeeds with an empty array instead of failing when there are zero matches — handy for optional repetition.)

From match to meaning: map

So far our parsers hand back the raw characters they matched. To build an actual syntax tree we need to transform a successful result into something meaningful — a register node, a number, an instruction. That’s what map does.

import { Parser } from '../../parser';

export const map = <T, U>(parser: Parser<T>, fn: (value: T) => U) =>
  new Parser<U>((input, { position }) => {
    const result = parser.parse(input, { position: { ...position } });

    if (!result.success) return result;

    return { success: true, value: fn(result.value), position: { ...result.position } };
  });

map runs a parser and, if it succeeds, passes the value through a function fn while leaving the position untouched. This is the bridge from "did the text match?" to "what does the text mean?".

Putting it together

We now have everything we need to turn our GeneralPurposeRegister grammar rule into a real parser. Compare the grammar to the code side by side:

import { char, either, regexp, sequence, map } from '../parser-combinators';

// RegisterNamePrefix : "R" | "r"
const registerNamePrefix = either(char('R'), char('r'));
// RegisterNumber : [0-15]   (10–15 listed first so "15" wins over "1")
const registerNumber = regexp(/1[0-5]|[0-9]/);
// GeneralPurposeRegister : RegisterNamePrefix RegisterNumber
const generalPurposeRegister = map(
  sequence(registerNamePrefix, registerNumber),
  ([, number]) => ({ type: 'Register', value: Number(number) }),
);
generalPurposeRegister.parse('R15');
// → { success: true, value: { type: 'Register', value: 15 }, position: { index: 3, line: 1, column: 4 } }

And there it is — a working register parser. 🙌 Each grammar rule became one parser, and the structure of the code mirrors the structure of the grammar almost line for line. either handles the alternation, sequence handles the concatenation, regexp (one of our primary parsers, matching a sticky pattern at the current index) handles the range, and map lifts the matched text into a small AST node. This is the payoff of parser combinators: the grammar is the program.

This is also where ordered choice bites if you’re not careful — regexp(/[0-9]|1[0-5]/) would happily match just the 1 in 15 and leave the 5 behind. Listing 1[0-5] first fixes it.

One more building block: recursion

Real grammars are recursive — an expression can contain an expression. But a combinator that references a parser defined later (or itself) would blow up at module-load time. lazy defers construction until parse time.

import { Parser } from '../../parser';

export const lazy = <T = any>(fn: () => Parser<T>) =>
  new Parser<T>((input, state) => fn().parse(input, state));

By wrapping a parser in a thunk, we can refer to it before it exists. We’ll lean on this heavily once we start parsing nested expressions.

Wrapping up

And that’s the foundation of our assembler’s front end. We built a Parser class that threads position through every result, a set of primary parsers (char, string, regexp, whitespace, newline) that consume input, and combinators (sequence, either, many, map, optional, lazy, and more) that compose them into bigger parsers. Best of all, a formal grammar maps onto this style almost for free — each rule becomes a parser, and the combinators mirror the structure of the rules.

Here’s where the project stands after this part, with the new parser-combinators module sitting alongside everything we've built so far:

src
├── constants/ ...
├── instructions/ ...
├── modules
│   ├── cpu/ ...
│   ├── memory/ ...
│   ├── memory-controller/ ...
│   ├── parser-combinators
│   │   ├── parsers
│   │   │   ├── combinators
│   │   │   │   ├── and.ts
│   │   │   │   ├── chain.ts
│   │   │   │   ├── either.ts
│   │   │   │   ├── index.ts
│   │   │   │   ├── lazy.ts
│   │   │   │   ├── many-zero.ts
│   │   │   │   ├── many.ts
│   │   │   │   ├── map.ts
│   │   │   │   ├── optional.ts
│   │   │   │   ├── or.ts
│   │   │   │   ├── peek.ts
│   │   │   │   └── sequence.ts
│   │   │   ├── primary
│   │   │   │   ├── char.ts
│   │   │   │   ├── index.ts
│   │   │   │   ├── newline.ts
│   │   │   │   ├── regexp.ts
│   │   │   │   ├── string.ts
│   │   │   │   └── whitespace.ts
│   │   │   ├── utils
│   │   │   │   ├── index.ts
│   │   │   │   └── tap.ts
│   │   │   └── index.ts
│   │   ├── index.ts
│   │   ├── parser.ts
│   │   └── types.ts
│   └── index.ts
├── types/ ...
├── utils/ ...
└── index.ts

The branch can be found here.

That’s a lot for parsing single characters. But with this knowledge under our belt, we are ready to start parsing some actual assembly. See you in part 8!