Kombinátory parserů od nuly na TypeScript

Parser-kombinátory: implementace od nuly v TypeScriptu

Parser je funkce, která analyzuje začátek vstupního řetězce a vrací buď úspěšně rozpoznaný fragment se zbytkem textu, nebo chybu. Výsledek parsingu je reprezentován typem ParseResult<T> = [T, string] | null. Úspěch znamená extrahovaná data a zbylou část řetězce, neúspěch znamená null.

Příklad chování jednoduchého parseru číslic:

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

Parser nekontroluje celý text, ale pouze začátek. Zbytek je předán dalšímu parseru v řetězci.

Základní parsery: řetězce a sekvence znaků

První parser hledá přesnou shodu řetězce na začátku vstupu:

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

Příklady:

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

Parser sekvence znaků podle predikátu:

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

Použití pro přirozená čísla a mezery:

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

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

Kombinátor sekvence

Kombinátor pSequence spojuje parsery do řetězce a aplikuje je postupně na zbytek od předchozího:

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

Příklad pro příkaz robota forward 45:

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

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

Každý parser pracuje se zbytkem od předchozího. Chyba v kterékoli fázi přeruší celou sekvenci.

Kombinátor výběru

pOneOf zkouší parsery v pořadí a vrací první úspěšný výsledek:

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

Rozšíření gramatiky příkazů 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")      // Úspěch
pCommand("rotate 30 right") // Úspěch

Co je důležité

• Parser vrací [výsledek, zbytek] nebo null, neanalyzuje celý text.
• Kombinátor pSequence aplikuje parsery postupně a předává zbytek.
• pOneOf testuje varianty v pořadí a vrací první úspěšnou.
• Základní parsery (pString, pSpanOf) pokrývají většinu primitiv.
• TypeScript-generiky zajišťují typovou bezpečnost výsledků.

— Editorial Team