Pratt Parsing : comment FLIN lit votre code

Le Pratt parsing est l'un des algorithmes les plus élégants de la conception de compilateurs. Il gère la précédence des opérateurs sans table de grammaire, il est extensible sans réécrire la boucle principale, et il tient en moins de 200 lignes de Rust. Quand nous avions besoin de construire le parser de FLIN -- un parser qui gère l'arithmétique, les comparaisons, les opérateurs logiques, l'accès aux membres, les appels de fonctions, les requêtes temporelles, les expressions d'intention IA et les constructions de vue de type HTML -- le Pratt parsing était le choix évident.

Cet article explique comment fonctionne le Pratt parsing, pourquoi nous l'avons choisi plutôt que les alternatives, et comment nous l'avons étendu pour gérer les fonctionnalités inhabituelles de FLIN comme la construction d'entités, l'opérateur temporel @ et les expressions d'intention ask/search.

Le problème : la précédence des opérateurs

Considérez l'expression 2 + 3 * 4. Tout programmeur sait que cela donne 14, pas 20, parce que la multiplication a une précédence supérieure à l'addition. Un parser doit encoder cette connaissance.

L'approche naïve -- la descente récursive avec une fonction par niveau de précédence -- fonctionne mais passe mal à l'échelle. Vous finissez avec une chaîne de fonctions : parse_assignment appelle parse_or, qui appelle parse_and, qui appelle parse_equality, qui appelle parse_comparison, qui appelle parse_term, qui appelle parse_factor, qui appelle parse_unary, qui appelle parse_primary. Chaque fonction n'existe que pour appliquer un seul niveau de précédence. Ajouter un nouvel opérateur signifie insérer une nouvelle fonction dans la chaîne et mettre à jour le graphe d'appels.

FLIN a 10 niveaux de précédence. Un parser naïf à descente récursive aurait besoin de 10 fonctions mutuellement récursives juste pour les expressions. Ce n'est pas terrible, mais c'est inutile. Le Pratt parsing condense toute la hiérarchie de précédence en une seule boucle.

L'algorithme Pratt

L'intuition de Vaughan Pratt, publiée en 1973, est que vous pouvez parser des expressions en utilisant une seule fonction qui prend un niveau de précédence minimum comme paramètre. L'algorithme :

1. Parser une expression préfixe (un littéral, un identifiant, un opérateur unaire ou une expression groupée).
2. Tant que le token suivant est un opérateur infixe avec une précédence supérieure ou égale au minimum, parser l'expression infixe en appelant récursivement la même fonction avec la précédence de l'opérateur comme nouveau minimum.
3. Retourner l'arbre d'expression résultant.

Les niveaux de précédence sont juste des nombres. Plus haut signifie liaison plus serrée. L'assignation est 1 (la plus lâche). Les opérateurs postfixes sont 9 (les plus serrés). Le parser consulte ces nombres au lieu d'une chaîne de fonctions.

Dans FLIN, nous avons défini 10 niveaux de précédence :

rust#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
#[repr(u8)]
pub enum Precedence {
    None       = 0,
    Assignment = 1,   // =         (associatif à droite)
    Or         = 2,   // ||
    And        = 3,   // &&
    Equality   = 4,   // == !=
    Comparison = 5,   // < > <= >=
    Term       = 6,   // + -
    Factor     = 7,   // * / %
    Unary      = 8,   // ! - ++ -- (préfixe)
    Postfix    = 9,   // ++ -- . [] () @
}

L'attribut #[repr(u8)] garantit que ceux-ci sont stockés comme des octets uniques, et le derive PartialOrd nous permet de comparer les niveaux de précédence avec < et >=. L'ordre est implicite dans l'ordre des variantes d'enum -- Rust dérive PartialOrd en se basant sur les valeurs des discriminants.

La boucle fondamentale

Le coeur du parser Pratt est une méthode que nous appelons parse_expression, qui délègue à parse_precedence :

rustfn parse_expression(&mut self) -> Result<Expr, ParseError> {
    self.parse_precedence(Precedence::Assignment)
}

fn parse_precedence(&mut self, min_prec: Precedence) -> Result<Expr, ParseError> {
    // Étape 1 : Parser le préfixe
    let mut left = self.parse_prefix()?;

    // Étape 2 : Parser les opérateurs infixes tant que la précédence le permet
    while let Some(prec) = self.infix_precedence() {
        if prec < min_prec {
            break;
        }
        left = self.parse_infix(left, prec)?;
    }

    Ok(left)
}

C'est toute la boucle Pratt. Quatorze lignes. La magie est dans parse_prefix, parse_infix et infix_precedence -- les trois méthodes qui disent à la boucle quoi faire avec chaque token.

Parsing préfixe

Le parser préfixe gère les tokens qui apparaissent au début d'une expression : littéraux, identifiants, opérateurs unaires, expressions groupées et constructions spécifiques à FLIN comme ask et search.

Les littéraux sont le cas le plus simple. Quand le parser voit un token Integer, Float, String ou Bool, il enveloppe la valeur dans un noeud Expr::Literal et retourne.

Les opérateurs unaires (!, -, ++, --) consomment le token opérateur, parsent récursivement l'opérande à la précédence Unary et retournent un noeud Expr::Unary. L'appel récursif avec la précédence Unary garantit que -x <em> 3 se parse comme (-x) </em> 3 plutôt que -(x * 3), parce que la précédence unaire (8) est supérieure à la précédence facteur (7).

Les expressions groupées ((expr)) consomment la parenthèse ouvrante, parsent l'expression interne à la précédence la plus basse (pour permettre n'importe quel opérateur à l'intérieur), consomment la parenthèse fermante et retournent l'expression interne sans l'envelopper dans un noeud supplémentaire. Les parenthèses sont de la pure syntaxe -- elles affectent l'ordre de parsing mais ne laissent aucune trace dans l'AST.

L'expression ask est spécifique à FLIN : ask "Quelles sont les factures en retard ?" compile vers une requête d'intention IA. Le parser préfixe reconnaît le mot-clé ask, parse l'expression chaîne suivante et retourne un noeud Expr::Ask. De même, search "requête" in Entity by field limit 5 est parsé comme une expression structurée avec plusieurs clauses.

Parsing infixe

Le parser infixe gère les tokens qui apparaissent entre deux expressions : opérateurs binaires, accès aux membres, appels de fonctions, accès par index et l'opérateur temporel @.

Pour les opérateurs binaires standard (+, -, *, /, ==, !=, <, >, &&, ||), le parser infixe consomme l'opérateur, appelle récursivement parse_precedence avec la précédence de l'opérateur (pour les opérateurs associatifs à gauche) ou la précédence moins un (pour les opérateurs associatifs à droite comme l'assignation), et retourne un noeud Expr::Binary.

La distinction entre associativité gauche et droite est une seule ligne de code :

rustfn parse_infix(&mut self, left: Expr, prec: Precedence) -> Result<Expr, ParseError> {
    let op = self.advance(); // consommer l'opérateur

    match op.kind {
        // Associatif à droite : assignation
        TokenKind::Equal => {
            let right = self.parse_precedence(Precedence::Assignment)?;
            Ok(Expr::Assign { target: Box::new(left), value: Box::new(right) })
        }

        // Associatif à gauche : tout le reste
        TokenKind::Plus | TokenKind::Minus |
        TokenKind::Star | TokenKind::Slash | TokenKind::Percent => {
            let right = self.parse_precedence(next_precedence(prec))?;
            Ok(Expr::Binary {
                left: Box::new(left),
                op: token_to_binop(&op),
                right: Box::new(right),
            })
        }

        // Accès aux membres : expr.field
        TokenKind::Dot => {
            let field = self.expect_identifier()?;
            // Vérifier un appel de méthode : expr.method(args)
            if self.check(TokenKind::LeftParen) {
                let args = self.parse_call_args()?;
                Ok(Expr::MethodCall {
                    object: Box::new(left),
                    method: field,
                    args,
                })
            } else {
                Ok(Expr::Member {
                    object: Box::new(left),
                    field,
                })
            }
        }

        // Accès temporel : expr @ time
        TokenKind::At => {
            let time_expr = self.parse_precedence(Precedence::Postfix)?;
            Ok(Expr::Temporal {
                expr: Box::new(left),
                time: Box::new(time_expr),
            })
        }

        // ... autres opérateurs infixes
    }
}

L'accès aux membres (.) et l'accès par index ([]) sont des opérateurs infixes à la précédence Postfix, qui est la plus haute. Cela garantit que a.b + c se parse comme (a.b) + c, pas a.(b + c). L'opérateur temporel @ se situe aussi à la précédence Postfix, donc user.name @ yesterday se parse comme (user.name) @ yesterday -- accéder au champ name, puis interroger sa valeur à l'horodatage d'hier.

Le problème de désambiguïsation

FLIN a une ambiguïté syntaxique qui a nécessité un traitement soigné. Considérez :

flinUser { name: "Juste" }

Est-ce une construction d'entité (créer un User avec name réglé à "Juste") ou un identifiant suivi d'un bloc de code ? Le parser ne peut pas le dire à partir du token courant seul -- il a besoin de regarder en avant.

Nous avons résolu cela avec une méthode looks_like_entity_construct qui regarde les tokens après l'accolade ouvrante :

rustfn looks_like_entity_construct(&self) -> bool {
    // Pattern : Identifier { Identifier : ...
    // Si nous voyons identifiant-deux-points après l'accolade, c'est une construction d'entité.
    // Si nous voyons un mot-clé d'instruction ou pas de deux-points, c'est un bloc.
    if let Some(TokenKind::Identifier(_)) = self.peek_kind() {
        if let Some(TokenKind::Colon) = self.peek_nth_kind(1) {
            return true;
        }
    }
    false
}

L'heuristique est simple : si la première chose à l'intérieur des accolades est identifiant: ..., c'est une construction d'entité. Sinon, c'est un bloc de code. Cela fonctionne parce que les blocs de code commencent par des instructions (mots-clés, assignations, expressions) et les constructions d'entités commencent par des paires champ-valeur. Les deux patterns sont syntaxiquement distincts après deux tokens de lookahead.

C'est un lookahead borné -- nous ne regardons jamais plus de deux tokens en avant. Le parser reste O(n) dans le nombre de tokens.

Évaluation court-circuit

Les opérateurs logiques && et || nécessitent un traitement spécial parce qu'ils sont en court-circuit : l'opérande droit ne devrait pas être évalué si l'opérande gauche détermine le résultat. Au niveau du parsing, cela ne change pas l'algorithme -- les deux sont des opérateurs binaires associatifs à gauche à leurs niveaux de précédence respectifs. Le comportement de court-circuit est encodé plus tard, dans le générateur de code, en utilisant des sauts conditionnels.

Mais le parser fait quelque chose d'important : il étiquette && et || comme BinOp::And et BinOp::Or dans l'AST, distincts de BinOp::BitwiseAnd ou BinOp::BitwiseOr (que FLIN ne supporte pas actuellement, mais la distinction est architecturalement saine). Cet étiquetage garantit que le générateur de code sait quels opérateurs nécessitent une émission de court-circuit sans avoir à ré-analyser le token opérateur.

Parsing des instructions

Tandis que le parser Pratt gère les expressions, le parser de FLIN doit aussi gérer les instructions : déclarations de variables, déclarations d'entités, flux de contrôle, opérations save/delete et définitions de routes. Celles-ci sont parsées par une méthode de dispatch séparée :

rustfn parse_statement(&mut self) -> Result<Stmt, ParseError> {
    match self.peek_kind() {
        Some(TokenKind::Keyword(Keyword::Entity)) => self.parse_entity_decl(),
        Some(TokenKind::Keyword(Keyword::Save))   => self.parse_save_stmt(),
        Some(TokenKind::Keyword(Keyword::Delete)) => self.parse_delete_stmt(),
        Some(TokenKind::Keyword(Keyword::If))     => self.parse_if_stmt(),
        Some(TokenKind::Keyword(Keyword::For))    => self.parse_for_stmt(),
        Some(TokenKind::Keyword(Keyword::Route))  => self.parse_route_stmt(),
        Some(TokenKind::Identifier(_))            => self.parse_var_or_expr_stmt(),
        _                                          => self.parse_expr_stmt(),
    }
}

Chaque type d'instruction a sa propre méthode de parsing. parse_entity_decl consomme le mot-clé entity, un identifiant (le nom de l'entité), une accolade ouvrante, une séquence de déclarations de champs et une accolade fermante. parse_if_stmt consomme le mot-clé if, une expression de condition, un corps délimité par des accolades et une clause else optionnelle.

La méthode parse_var_or_expr_stmt gère une autre ambiguïté : quand le parser voit un identifiant, cela pourrait être le début d'une déclaration de variable (name = "Juste") ou une instruction expression (print("hello")). Le parser regarde en avant pour = ou : pour distinguer les deux cas.

Flux de contrôle : if et for

L'instruction if de FLIN supporte les chaînes if, else if et else :

flinif count > 10 {
    status = "high"
} else if count > 5 {
    status = "medium"
} else {
    status = "low"
}

Le parser gère cela récursivement : après avoir parsé le corps du if, il vérifie la présence d'un mot-clé else. S'il le trouve, il vérifie si le token suivant est un autre if (en faisant une chaîne else if) ou une accolade ouvrante (en faisant un simple else). Cette structure récursive signifie que les chaînes if/else if/else sont représentées dans l'AST comme des noeuds If imbriqués, pas comme une liste plate. Le générateur de code gère cela naturellement avec des sauts conditionnels imbriqués.

La boucle for de FLIN supporte l'itération sur des collections avec une variable d'index optionnelle :

flinfor item in items {
    save item
}

for item, index in items {
    // index est disponible
}

Le parser consomme le mot-clé for, un ou deux identifiants (séparés par une virgule), le mot-clé in, une expression de collection et un corps délimité par des accolades. La variable d'index optionnelle est une petite commodité syntaxique qui élimine le besoin d'une variable compteur séparée.

Les chiffres

À la fin des sessions 5 et 6, le parser était fonctionnellement complet pour les programmes FLIN de base. Les statistiques racontent l'histoire :

La session 5 a construit le coeur du parser -- le struct Parser, les méthodes advance/check/expect, le parsing des déclarations de variables et d'entités. La session 6 a ajouté le parser Pratt pour les expressions et les instructions de flux de contrôle. Ensemble, elles ont pris environ 75 minutes.

Récupération d'erreur

Un parser qui s'arrête à la première erreur est inutile en pratique. Les vrais fichiers source ont des erreurs multiples, et les développeurs veulent les voir toutes, pas seulement la première. Le parser de FLIN implémente la récupération d'erreur à travers une méthode synchronize :

rustfn synchronize(&mut self) {
    while !self.is_at_end() {
        // S'arrêter aux limites d'instructions
        if self.previous_kind() == Some(TokenKind::Newline) {
            return;
        }
        match self.peek_kind() {
            Some(TokenKind::Keyword(Keyword::Entity)) |
            Some(TokenKind::Keyword(Keyword::Save))   |
            Some(TokenKind::Keyword(Keyword::Delete)) |
            Some(TokenKind::Keyword(Keyword::If))     |
            Some(TokenKind::Keyword(Keyword::For))    |
            Some(TokenKind::Keyword(Keyword::Route))  => return,
            _ => { self.advance(); }
        }
    }
}

Quand le parser rencontre une erreur, il appelle synchronize(), qui avance à travers les tokens jusqu'à atteindre une limite d'instruction probable -- un retour à la ligne ou un mot-clé qui commence une nouvelle instruction. Puis le parser reprend le parsing normal. L'erreur est enregistrée mais n'interrompt pas la compilation.

Cette approche est imparfaite -- parfois la synchronisation saute trop ou trop peu de tokens, produisant des erreurs en cascade. Mais c'est largement mieux que de s'arrêter à la première erreur, et c'est une pratique standard dans les compilateurs de production.

Pourquoi pas un générateur de parser ?

Nous aurions pu utiliser un générateur de parser comme LALR, PEG ou tree-sitter pour définir la grammaire de FLIN et auto-générer le parser. Nous avons choisi de ne pas le faire, pour trois raisons.

Premièrement, la syntaxe modale de FLIN (du code entrelacé avec des vues de type HTML) ne s'inscrit pas proprement dans un formalisme de grammaire standard. Un générateur de parser aurait nécessité des contournements maladroits pour les transitions de mode que le lexer écrit à la main gère naturellement.

Deuxièmement, les messages d'erreur des parsers générés sont typiquement médiocres. "Token X attendu, token Y trouvé" est le mieux que vous obtenez. Un parser écrit à la main peut produire des messages comme "l'accolade ouvrante manque dans la déclaration d'entité -- avez-vous oublié { après le nom de l'entité ?" Ce niveau de spécificité est important pour un langage ciblant des développeurs qui peuvent être nouveaux en programmation.

Troisièmement, un parser Pratt écrit à la main est assez simple pour qu'il ne bénéficie pas de l'automatisation. Le parser d'expressions entier fait moins de 200 lignes. Le parser d'instructions en ajoute 400 de plus. Un générateur de parser nous économiserait peut-être 200 lignes de code tout en nous enlevant notre capacité à personnaliser la gestion d'erreurs, le comportement de lookahead et les transitions de mode.

Ce qui a suivi

Le parser produit un AST -- un arbre syntaxique abstrait qui représente la structure du programme sans aucun bruit syntaxique (parenthèses, accolades, points-virgules) du code source. Le prochain article examine cet AST en détail : quels noeuds il contient, comment il représente les fonctionnalités uniques de FLIN (entités, vues, accès temporel, requêtes d'intention), et les décisions de conception qui le rendent adapté à la fois à la vérification de types et à la génération de code.

Ceci est la partie 13 de la série "Comment nous avons construit FLIN", qui documente comment un CEO à Abidjan et une IA CTO ont construit un langage de programmation en partant de zéro.

Navigation de la série : - [11] Session 1 : mise en place du projet et 42 mots-clés - [12] Construire un lexer en partant de zéro en Rust - [13] Pratt Parsing : comment FLIN lit votre code (vous êtes ici) - [14] L'arbre syntaxique abstrait : la représentation interne de FLIN - [15] L'inférence de types Hindley-Milner dans un langage personnalisé