Parser-kombinatory od zera w TypeScript

Parser-kombinatory: implementacja od zera w TypeScript

Parser to funkcja, która analizuje początek wejściowego ciągu znaków i zwraca albo pomyślnie rozpoznany fragment z pozostałym tekstem, albo błąd. Wynik parsowania reprezentowany jest typem ParseResult<T> = [T, string] | null. Sukces oznacza wydobyte dane i pozostałą część ciągu, niepowodzenie — null.

Przykład zachowania prostego parsera cyfr:

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

Parser nie sprawdza całego tekstu, a jedynie początek. Pozostała część jest przekazywana do następnego parsera w łańcuchu.

Bazowe parsery: ciągi znaków i sekwencje znaków

Pierwszy parser szuka dokładnego dopasowania ciągu na początku wejścia:

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

Przykłady:

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

Parser sekwencji znaków według predykatu:

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

Zastosowanie dla liczb naturalnych i spacji:

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

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

Kombinator sekwencji

Kombinator pSequence łączy parsery w łańcuch, stosując je sekwencyjnie do pozostałej części po poprzednim:

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

Przykład dla komendy robota forward 45:

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

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

Każdy parser pracuje na pozostałej części po poprzednim. Błąd na dowolnym etapie przerywa całą sekwencję.

Kombinator wyboru

pOneOf próbuje parserów po kolei i zwraca pierwszy pomyślny wynik:

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

Rozszerzenie gramatyki komend robota:

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

Co ważne

• Parser zwraca [wynik, pozostała część] lub null, nie analizując całego tekstu.
• Kombinator pSequence stosuje parsery sekwencyjnie, przekazując pozostałą część.
• pOneOf testuje warianty po kolei, zwracając pierwszy pomyślny.
• Bazowe parsery (pString, pSpanOf) pokrywają większość prymitywów.
• Generyki TypeScript zapewniają bezpieczeństwo typów wyników.

— Editorial Team