Combinadores de parsers desde cero en TypeScript

Combinadores de Parsers: Implementación desde Cero en TypeScript

Un parser es una función que analiza el comienzo de una cadena de entrada y devuelve ya sea un fragmento reconocido exitosamente con el texto restante, o un error. El resultado del parsing se representa mediante el tipo ParseResult<T> = [T, string] | null. El éxito significa datos extraídos y la parte restante de la cadena; el fallo significa null.

Comportamiento de ejemplo de un parser de dígitos simple:

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

El parser no verifica todo el texto, solo el comienzo. El resto se pasa al siguiente parser en la cadena.

Parsers Básicos: Cadenas y Rangos de Caracteres

El primer parser busca una coincidencia exacta de cadena al comienzo de la entrada:

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

Ejemplos:

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

Parser para secuencias de caracteres basado en un predicado:

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

Aplicación para números naturales y espacios:

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

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

Combinador de Secuencia

El combinador pSequence combina parsers en una cadena, aplicándolos secuencialmente al resto del anterior:

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

Ejemplo para un comando de robot forward 45:

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

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

Cada parser trabaja con el resto del anterior. Un error en cualquier etapa interrumpe toda la secuencia.

Combinador de Elección

pOneOf prueba los parsers en orden y devuelve el primer resultado exitoso:

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

Extendiendo la gramática de comandos del robot:

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

Conclusiones Clave

• Un parser devuelve [result, remainder] o null, sin analizar todo el texto.
• El combinador pSequence aplica parsers secuencialmente, pasando el resto.
• pOneOf prueba opciones en orden, devolviendo el primer éxito.
• Los parsers básicos (pString, pSpanOf) cubren la mayoría de primitivas.
• Los genéricos de TypeScript garantizan seguridad de tipos para los resultados.

— Editorial Team