Combinateurs de parseurs de zéro en TypeScript

Combinateurs de Parseurs : Implémentation à Partir de Zéro en TypeScript

Un parseur est une fonction qui analyse le début d'une chaîne d'entrée et renvoie soit un fragment reconnu avec succès et le texte restant, soit une erreur. Le résultat de l'analyse est représenté par le type ParseResult<T> = [T, string] | null. Le succès signifie les données extraites et la partie restante de la chaîne ; l'échec signifie null.

Exemple de comportement d'un parseur de chiffres simple :

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

Le parseur ne vérifie pas tout le texte, seulement le début. Le reste est transmis au prochain parseur dans la chaîne.

Parseurs de Base : Chaînes et Plages de Caractères

Le premier parseur recherche une correspondance exacte de chaîne au début de l'entrée :

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

Exemples :

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

Parseur pour les séquences de caractères basé sur un prédicat :

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 pour les nombres naturels et les espaces :

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

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

Combinateur de Séquence

Le combinateur pSequence combine les parseurs en une chaîne, les appliquant séquentiellement au reste du précédent :

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

Exemple pour une commande de robot forward 45 :

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

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

Chaque parseur travaille avec le reste du précédent. Une erreur à n'importe quelle étape interrompt toute la séquence.

Combinateur de Choix

pOneOf essaie les parseurs dans l'ordre et renvoie le premier résultat réussi :

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

Extension de la grammaire de commande du 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")      // Succès
pCommand("rotate 30 right") // Succès

Points Clés

• Un parseur renvoie [resultat, reste] ou null, sans analyser tout le texte.
• Le combinateur pSequence applique les parseurs séquentiellement, en passant le reste.
• pOneOf teste les options dans l'ordre, renvoyant le premier succès.
• Les parseurs de base (pString, pSpanOf) couvrent la plupart des primitives.
• Les génériques TypeScript assurent la sécurité des types pour les résultats.

— Editorial Team