Pratt parsing remplace l'algorithme Shunting Yard pour les expressions C

Contexte et motivation

Le développeur a souhaité créer un analyseur d'expressions C en s'appuyant sur le Pratt parsing, technique peu citée dans les manuels classiques comme le Dragon Book. L'article rappelle que les cours universitaires privilégient généralement le parsing LR ou la descente récursive, alors que le modèle de Pratt, décrit dans le papier original de 1973, se retrouve surtout dans les projets de compilation et les communautés PLT. L'objectif était de comparer ce modèle à l'algorithme de Dijkstra, le Shunting Yard, déjà implémenté sous forme de calculatrice.

Comparaison avec l'algorithme Shunting Yard

Le Shunting Yard utilise une pile d'opérateurs et un flux de sortie. Chaque opérateur possède une binding power (BP) : « + » et « - » ont BP = 1, « * » et « / » BP = 2. Le code C suivant montre la logique de poussée et de dépilage selon le BP :

#include 
#include 
typedef struct { char ops[32]; int idx; } Stk;
void push(Stk *s, char op) { s->idx += 1; s->ops[s->idx] = op; }
void pop(Stk *s)   { s->idx -= 1; }
char peek(Stk *s)  { return s->ops[s->idx]; }
char empty(Stk *s) { return s->idx == -1; }
int get_bindpower(char op) { static const int bps[] = { ['+']=1, ['-']=1, ['*']=2, ['/']=2 }; return bps[op]; }
int main(int argc, char **argv) {
    char *str = argv[1];
    Stk _opstk = (Stk){ .idx = -1 }; Stk *opstk = &_opstk;
    while (*str) {
        if (isdigit(*str)) printf("EMIT '%c'\n", *str);
        else {
            while (!empty(opstk) && get_bindpower(peek(opstk)) >= get_bindpower(*str)) {
                printf("EMIT '%c'\n", peek(opstk)); pop(opstk);
            }
            push(opstk, *str);
        }
        str++;
    }
    while (!empty(opstk)) { printf("EMIT '%c'\n", peek(opstk)); pop(opstk); }
    return 0;
}

Cette implémentation montre la difficulté d'étendre le modèle : les parenthèses, les opérateurs unaire ou les fonctions nécessitent des traitements spéciaux, ce qui alourdit le code.

Mécanisme du parser Pratt

Le Pratt parser remplace la pile explicite par la pile d'appels du langage. Chaque appel reçoit un left binding power (LBP) qui détermine jusqu'où la récursion doit s'étendre. Le fragment suivant illustre la fonction expr qui consomme d'abord un préfixe (un chiffre) puis, tant que le LBP est inférieur au BP de l'opérateur suivant, consomme le sous‑expression de droite :

#include 
#include 
#include 
int get_bindpower(char op) { static const int bps[] = { ['\0']=0, ['+']=1, ['-']=1, ['*']=2, ['/']=2 }; return bps[op]; }

typedef struct { char *str; } Parser;
char cur(Parser *p) { return *p->str; }
void bump(Parser *p) { p->str++; }

void expr(Parser *parser, int left_bindpower) {
    if (isdigit(cur(parser))) printf("EMIT '%c'\n", cur(parser));
    else { fprintf(stderr, "expression doesn't start with a number\n"); abort(); }
    bump(parser);
    while (left_bindpower < get_bindpower(cur(parser))) {
        int new_left = get_bindpower(cur(parser));
        char op = cur(parser);
        bump(parser);
        expr(parser, new_left);
        printf("EMIT '%c'\n", op);
    }
}

int main(int argc, char **argv) {
    Parser parser = { .str = argv[1] };
    expr(&parser, 0);
    return 0;
}

Le test left_bindpower < get_bindpower(cur(parser)) reproduit le « pop » du Shunting Yard : dès qu'un opérateur de moindre puissance apparaît, la fonction retourne, laissant le contrôle à l'appelant.

Analyse des avantages et limites

Le modèle Pratt évite la duplication de piles et ne crée des appels récursifs qu'à chaque sous‑expression réelle, ce qui réduit la profondeur de récursion comparée à une descente récursive stricte où chaque niveau de priorité serait une fonction distincte. Cette approche simplifie l'ajout de nouveaux opérateurs : il suffit de définir leur BP et d'implémenter éventuellement un nud ou led dédié. En revanche, le code présenté ne gère pas les parenthèses, les opérateurs unaire ni les fonctions à arguments variables ; ces extensions requièrent des nud supplémentaires qui reconnaissent « ( » et retournent après avoir consommé la sous‑expression jusqu'à « ) ». Le papier de Pratt décrit ces cas, mais l'exemple minimal reste limité à des opérateurs binaires et à des nombres à un caractère.