Parser Combinators from Scratch in TypeScript

Parser Combinators: Implementation from Scratch in TypeScript

A parser is a function that analyzes the beginning of an input string and returns either a successfully recognized fragment with the remaining text, or an error. The parsing result is represented by the type ParseResult<T> = [T, string] | null. Success means extracted data and the remaining part of the string; failure means null.

Example behavior of a simple digit parser:

parseDigit("1")     // ["1", ""] 
parseDigit("1cm")   // ["1", "cm"]
parseDigit("123")   // ["1", "23"]
parseDigit("hello") // null

The parser does not check the entire text, only the beginning. The remainder is passed to the next parser in the chain.

Basic Parsers: Strings and Character Spans

The first parser looks for an exact string match at the beginning of the input:

type ParseResult<T> = [T, string] | null;
type Parser<T> = (input: string) => ParseResult<T>;

function pString(str: string): Parser<string> {
    return (input: string) => {
        if (input.startsWith(str))
            return [str, input.substring(str.length)]
        else
            return null
    }
}

Examples:

• pString("hello")("hello") → ["hello", ""]
• pString("hello")("hello, world!") → ["hello", ", world!"]
• pString("hello")("hi!") → null

Parser for character sequences based on a predicate:

function pSpanOf(predicate: (char: string) => boolean): Parser<string> {
    return (input: string) => {
        let i = 0;
        while (i < input.length) {
            if (!predicate(input[i])) break
            i++
        }
        return [input.substring(0, i), input.substring(i)]
    }
}

function pNonEmptySpanOf(predicate: (char: string) => boolean): Parser<string> { 
    return (input: string) => {
        const result = pSpanOf(predicate)(input)
        if (result == null || result[0].length == 0) return null;
        return result
    }
}

Application for natural numbers and spaces:

const pNatural = pNonEmptySpanOf(char => "0123456789".includes(char));
const pSpace = pSpanOf(char => char == " ");

pNatural("123")     // ["123", ""]
pNatural("123cm")   // ["123", "cm"]
pSpace("   123")    // ["   ", "123"]

Sequence Combinator

The pSequence combinator combines parsers into a chain, applying them sequentially to the remainder from the previous one:

function pSequence<T>(...parsers: Parser<T>[]): Parser<T[]> {
    return (input: string) => {
        const results: T[] = []
        let current = input
        for (const parser of parsers) {
            const result = parser(current)
            if (result == null) return null
            results.push(result[0])
            current = result[1]
        }
        return [results, current]
    }
}

Example for a robot command forward 45:

const pForward = pSequence(
    pString("forward"),
    pSpace,
    pNatural
);

pForward("forward 45")    // [["forward", " ", "45"], ""]
pForward("forward")       // null
pForward("forward45")     // [["forward", "", "45"], ""]

Each parser works with the remainder from the previous one. An error at any stage interrupts the entire sequence.

Choice Combinator

pOneOf tries parsers in order and returns the first successful result:

function pOneOf<T>(...parsers: Parser<T>[]): Parser<T> {
    return (input: string) => {
        for (const parser of parsers) {
            const result = parser(input)
            if (result != null) return result;
        }
        return null;
    }
}

Extending the robot command grammar:

const pCommand = pOneOf(
    pSequence(pString("forward"), pSpace, pNatural),
    pSequence(pString("backward"), pSpace, pNatural),
    pSequence(
        pString("rotate"),
        pSpace, pNatural,
        pSpace,
        pOneOf(pString("left"), pString("right"))
    )
);

pCommand("forward 45")      // Success
pCommand("rotate 30 right") // Success

Key Takeaways

• A parser returns [result, remainder] or null, without analyzing the entire text.
• The pSequence combinator applies parsers sequentially, passing the remainder.
• pOneOf tests options in order, returning the first success.
• Basic parsers (pString, pSpanOf) cover most primitives.
• TypeScript generics ensure type safety for results.

— Editorial Team