Parser-Kombinatoren von Grund auf in TypeScript

Parser-Kombinatoren: Implementierung von Grund auf in TypeScript

Ein Parser ist eine Funktion, die den Anfang eines Eingabestrings analysiert und entweder ein erfolgreich erkanntes Fragment mit dem verbleibenden Text oder einen Fehler zurückgibt. Das Parsergebnis wird durch den Typ ParseResult<T> = [T, string] | null dargestellt. Erfolg bedeutet extrahierte Daten und den verbleibenden Teil des Strings; Misserfolg bedeutet null.

Beispielverhalten eines einfachen Ziffern-Parsers:

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

Der Parser überprüft nicht den gesamten Text, sondern nur den Anfang. Der Rest wird an den nächsten Parser in der Kette übergeben.

Basis-Parser: Strings und Zeichenbereiche

Der erste Parser sucht nach einer exakten String-Übereinstimmung am Anfang der Eingabe:

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

Beispiele:

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

Parser für Zeichensequenzen basierend auf einem Prädikat:

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

Anwendung für natürliche Zahlen und Leerzeichen:

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

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

Sequenz-Kombinator

Der pSequence-Kombinator verbindet Parser zu einer Kette und wendet sie sequenziell auf den Rest des vorherigen an:

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

Beispiel für einen Roboter-Befehl forward 45:

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

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

Jeder Parser arbeitet mit dem Rest des vorherigen. Ein Fehler in jeder Phase unterbricht die gesamte Sequenz.

Auswahl-Kombinator

pOneOf versucht Parser in der Reihenfolge und gibt das erste erfolgreiche Ergebnis zurück:

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

Erweiterung der Roboter-Befehlsgrammatik:

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")      // Erfolg
pCommand("rotate 30 right") // Erfolg

Die wichtigsten Punkte

• Ein Parser gibt [result, remainder] oder null zurück, ohne den gesamten Text zu analysieren.
• Der pSequence-Kombinator wendet Parser sequenziell an und übergibt den Rest.
• pOneOf testet Optionen in der Reihenfolge und gibt den ersten Erfolg zurück.
• Basis-Parser (pString, pSpanOf) decken die meisten Primitive ab.
• TypeScript Generics stellen Typsicherheit für Ergebnisse sicher.

— Editorial Team