@fatbrain/nom

Parser combinators with precise types, inspired by nom

• results are plain tuples: [rest, error, value]
• output types are inferred, including tuples and unions
• parses any input with length, slice and at, strings and byte arrays alike
• no dependencies

Getting started

Install @fatbrain/nom using pnpm:

pnpm add @fatbrain/nom

Or npm:

npm install --save @fatbrain/nom

A parser is a function from an input to a result. Combinators build bigger parsers out of smaller ones.

First, create a app.js file:

import { regex, map } from '@fatbrain/nom'

const number = map(regex(/\d+/), ([n]) => +n)

const [rest, error, value] = number('42abc')

Then run the program:

node app.js
# => rest: 'abc'
#    error: null
#    value: 42

Results

Every parser returns a three element tuple. The middle element is null when nothing went wrong, and otherwise names the kind of failure, the same way a verify or satisfy predicate returns null or an error:

tag('hello')('hello world')
// => [' world', null, 'hello']
tag('hello')('goodbye')
// => ['goodbye', 'error', 'tag-not-found']

The third kind is 'fatal', a failure that must not be backtracked over. Both failures are truthy, so if (error) covers them together, and error === 'fatal' tells them apart.

The two are tracked separately in the type, as Parse<I, O, E, F>. Writing Parse<I, O, E> leaves F as never, which reads correctly: a parser that cannot fail fatally.

On success the first element is the unconsumed remainder, to continue parsing from. On failure it is where the failure was detected, for diagnostics only. Never resume from it, backtrack and retry from the input you already hold.

tuple(tag('a'), tag('z'))('abc')
// => ['bc', 'error', 'tag-not-found']   <- element two failed at offset 1

Because the tag is a literal, destructuring narrows on it:

const [rest, error, value] = number('42abc')
if (error) {
  // value is the error type
} else {
  // value is a number
}

Building parsers

Let's parse a CSS color like rgb(255, 0, 127).

Create a color.js file:

import { tag, regex, map, delimited, separated } from '@fatbrain/nom'

const number = map(regex(/\d+/), ([n]) => +n)
const rgb = delimited(tag('rgb('), separated(tag(', '), number), tag(')'))

Then run the program:

node color.js
# => rgb('rgb(255, 0, 127)')
#    ['', null, [255, 0, 127]]
#
#    rgb('rgb(255, 0')
#    ['', 'error', 'tag-not-found']

Errors

Every parser declares exactly what it can fail with, and combinators union the error types of their parts. Nothing widens to string, so a parse failure stays exhaustively matchable however deeply it composes:

tuple(tag('a'), take(4))
// fails with: 'tag-not-found' | 'end-of-input'

separated(tag(','), number)
// fails with: 'tag-not-found' | 'no-match' | 'not-a-string' | Stall

Use mapErr to replace an error with one that means something to your caller:

const port = mapErr(number, () => 'expected-port' as const)
port('http')
// => ['http', 'error', 'expected-port']

verify adds its predicate's error to the union rather than replacing it:

verify(number, n => (n > 255 ? 'too-big' : null))
// fails with: 'no-match' | 'not-a-string' | 'too-big'

Note that string absorbs string literals in a union, so mapping an error to plain string anywhere collapses the whole union back to string.

Stalls

many, fold and separated loop until the inner parser fails. A parser that succeeds without consuming anything would loop forever, so they stop and return the stall sentinel instead:

many(opt(tag('a')))('aab')
// => ['b', 'fatal', { type: 'stall' }]

A stall means the grammar cannot terminate, not that the input is bad. It is reported at the position where progress stopped, and it is fatal, so it propagates outwards instead of being mistaken for a successful empty match. Test for it with isStall:

const [rest, error, value] = many(opt(tag('a')))('aab')
error && isStall(value)
// => true

Commitment

When every branch of an alt fails, all it can tell you is that none of them matched. It cannot pick one branch's error to report, because none of them is more right than the others:

const rgb = delimited(tag('rgb('), separated(tag(', '), number), tag(')'))

alt(rgb, tag('red'))('rgb(oops)')
// => ['rgb(oops)', 'error', 'no-alternative']   <- true, but not helpful

cut(parser) commits. Once the parser inside it has been entered, its failure is final, and no enclosing alt, opt, many, separated or orElse may try something else instead:

const rgb = preceded(tag('rgb('), cut(separated(tag(', '), number)))

alt(rgb, tag('red'))('rgb(oops)')
// => ['oops)', 'fatal', 'no-match']   <- the real problem, at the real position

alt(rgb, tag('red'))('red')
// => ['', null, 'red']   <- uncommitted branches still work normally

A fatal error keeps its own type, cut only changes how far it travels. Combinators that merely pass an error along keep it fatal, so it surfaces at the top with the position and the error of whatever actually went wrong.

Because the two are separate type parameters, commitment is visible in the signature. cut empties E into F, and the combinators that recover empty E on their own, which leaves the parsers that cannot fail saying so:

opt(tag('a'))            // Parse<I, 'a' | undefined, never, never>
opt(cut(tag('a')))       // Parse<I, 'a' | undefined, never, 'tag-not-found'>
many(tag('a'))           // Parse<I, 'a'[], never, Stall>

mapErr renames recoverable errors and leaves fatal ones alone. Use mapFatal for the other half.

Basic parsers

tag(string) matches a literal:

tag('hello')('hello world')
// => [' world', null, 'hello']

regex(pattern) matches at the current position only, and yields the match array:

regex(/\d+/)('123abc')
// => ['abc', null, ['123']]
regex(/\d+/)('abc123')
// => ['abc123', 'error', 'no-match']

take(count) takes a fixed number of units:

take(3)('abcdef')
// => ['def', null, 'abc']
take(3)('ab')
// => ['ab', 'error', 'end-of-input']

satisfy(predicate), oneOf(set) and noneOf(set) each take a single element. They report an empty input as 'end-of-input', separately from a rejected element:

satisfy(c => (c >= '0' && c <= '9' ? null : 'not-a-digit'))('42')
// => ['2', null, '4']
oneOf('abc')('bx')
// => ['x', null, 'b']
noneOf('abc')('zx')
// => ['x', null, 'z']

satisfy takes the same kind of predicate as verify, returning the error or null to accept, so the failure is named by the caller:

satisfy(c => (c >= '0' && c <= '9' ? null : 'not-a-digit'))('x')
// => ['x', 'error', 'not-a-digit']

The set is a sequence of the elements to accept, so oneOf('abc') for a string and oneOf(new Uint8Array([1, 2])) for bytes, where the element is a number. satisfy cannot infer its element from a bare arrow, so annotate it, satisfy((c: string) => …).

Combinators

tuple(...parsers) runs each in order and collects the outputs:

tuple(tag('a'), number)('a42!')
// => ['!', null, ['a', 42]]

alt(...parsers) takes the first that succeeds. If none do it fails with 'no-alternative' at its own position, rather than reporting whichever branch happened to be last, so reordering the branches never changes the result. Use cut inside a branch when you want its failure to be the one that surfaces:

alt(tag('yes'), tag('no'))('no!')
// => ['!', null, 'no']
alt(tag('yes'), tag('no'))('maybe')
// => ['maybe', 'error', 'no-alternative']

opt(parser) never fails, and consumes nothing when it does not match:

opt(tag('-'))('42')
// => ['42', null, undefined]

preceded(before, parser), terminated(parser, after) and delimited(before, parser, after) drop the surrounding matches:

preceded(tag('#'), number)('#42')
// => ['', null, 42]
terminated(number, tag(';'))('42;')
// => ['', null, 42]
delimited(tag('('), number, tag(')'))('(42)')
// => ['', null, 42]

separated(delimiter, parser) collects one or more, and stops as soon as the delimiter no longer matches. The failed delimiter is not consumed:

separated(tag(','), number)('1,2,3!')
// => ['!', null, [1, 2, 3]]

A trailing delimiter ends the list rather than failing it. The delimiter is rewound, so it is left for whatever parses next:

separated(tag(','), number)('1,2,')
// => [',', null, [1, 2]]

Only the first element is required:

separated(tag(','), number)('x')
// => ['x', 'error', 'no-match']

many(parser, until?) collects zero or more:

many(tag('a'))('aab')
// => ['b', null, ['a', 'a']]
many(tag('a'))('bbb')
// => ['bbb', null, []]

until ends the loop early, and is inclusive. The element it stops on is collected and consumed, so it reads as "stop after this one":

many(tag('a'), (value, index) => index === 2)('aaaa')
// => ['a', null, ['a', 'a', 'a']]

That is what you want for a terminator, where the last element is part of what you matched:

const line = many(satisfy(() => null), c => c === '\n')

line('hi\nthere')
// => ['there', null, ['h', 'i', '\n']]
line('hi')
// => ['', null, ['h', 'i']]

count(parser, n) collects exactly n:

const digit = map(regex(/\d/), ([n]) => +n)

count(digit, 2)('12')
// => ['', null, [1, 2]]

fold(parser, init, fold) accumulates instead of allocating an array:

fold(digit, 0, (acc, n) => acc + n)('123')
// => ['', null, 6]

permutation(...parsers) matches all of them, in any order:

permutation(tag('a'), number)('42a')
// => ['', null, ['a', 42]]

verify(parser, predicate) rejects a value the parser accepted. The predicate returns an error, or null to keep it:

verify(number, n => (n > 255 ? 'too-big' : null))('999')
// => ['999', 'error', 'too-big']

value(constant, parser) replaces the output:

value(true, tag('yes'))('yes')
// => ['', null, true]

recognize(parser) yields the consumed input instead of the output:

recognize(tuple(tag('a'), number))('a42!')
// => ['!', null, 'a42']

peek(parser) matches without consuming:

peek(tag('a'))('abc')
// => ['abc', null, 'a']

map(parser, fn) and mapErr(parser, fn) transform the output and the error:

map(regex(/\d+/), ([n]) => +n)('123abc')
// => ['abc', null, 123]
mapErr(tag('a'), () => 'want-a')('b')
// => ['b', 'error', 'want-a']

andThen(parser, fn) feeds an output back in, for input that describes itself:

const prefixed = andThen(number, (input, n) => take(n)(input))
prefixed('3abcdef')
// => ['def', null, 'abc']

It can also reject a value the parser accepted, by returning an err. The new error joins the union rather than replacing it:

andThen(number, (input, n) => (n > 255 ? err(input, 'too-big') : ok(input, n)))
// fails with: 'no-match' | 'not-a-string' | 'too-big'

orElse(parser, fn) is the mirror image, and recovers from a failure. The callback receives the input the parser was called with, so it can resume from there:

orElse(number, (input, error) => ok(input, error === 'no-match' ? 0 : -1))('abc')
// => ['abc', null, 0]

Recovering with an ok clears the error from the type entirely, so orElse(number, input => ok(input, 0)) cannot fail at all. Returning an err replaces the error instead:

orElse(number, input => err(input, 'want-number'))
// fails with: 'want-number'

opt is just orElse with a discarded error:

const opt = parser => orElse(parser, input => ok(input, undefined))

ok(input, value) and err(input, error) build results, for writing your own parsers:

const eof = input => (input.length === 0 ? ok(input, null) : err(input, 'expected-eof'))

Other inputs

Parsers are not limited to strings. Any sequence that slices into itself works:

export interface Input<E> {
  length: number
  slice(start?: number, end?: number): this
  at(index: number): E | undefined
}

The parameter is one element of the sequence, not the sequence itself, which slice already carries through this. A string is an Input<string> because indexing one gives a string back, and a Uint8Array is an Input<number>. Both satisfy it as they are, with no wrapper:

const magic = tag(new Uint8Array([0x89, 0x50]))

preceded(magic, take(2))(new Uint8Array([0x89, 0x50, 1, 2, 3]))
// => [Uint8Array([3]), null, Uint8Array([1, 2])]

Item<I> names the element type, for parsers that work one element at a time:

type A = Item<string> // string
type B = Item<Uint8Array> // number

There is nothing to declare. tag, regex, take, satisfy, oneOf and noneOf fix their input type where the parser is finally applied, not where it is built, so the remainder you get back is the sequence you passed in:

const [rest] = take(1)('abc')
// rest is a string

const [bytes] = take(1)(new Uint8Array([1, 2, 3]))
// bytes is a Uint8Array

Two parsers hand back whatever they were given, take and recognize, so their output is not known until they are applied. That is too late for verify, andThen or orElse, which have to type a callback against it up front. over pins the input type for them, and leaves everything else inferred:

verify(over<string>()(take(1)), x => (x === 'a' ? null : 'not-a'))('abc')
// => ['bc', null, 'a']       x is a string

It reaches into composites too, and is the identity at runtime:

over<string>()(tuple(take(1), take(2)))('abcd')
// => ['d', null, ['a', 'bc']]

Annotate with Parse when you want to fix the whole type ahead of use, for instance to reject a parser built for the wrong sequence:

const byte: Parse<Uint8Array, Uint8Array, 'end-of-input'> = take(1)

Parse<I, O, E, F> and Result<I, O, E, F> are both exported, for writing your own parsers and combinators.

Note that regex only works on strings, and fails with 'not-a-string' otherwise.

License

MIT