Pratt parsing simplifie la construction d'analyseurs grâce aux nud et led

Contexte et motivation

Le paradigme Pratt, décrit pour la première fois en 1973, se résume à neuf lignes de code dans un langage de haut niveau tel que Rhombus. Cette concision explique pourquoi de nombreux tutoriels se contentent de reproduire l’implémentation sans détailler les propriétés sous‑jacentes. L’auteur souligne que la maîtrise de l’algorithme n’est pas indispensable pour l’utiliser : il suffit de copier‑coller le bloc de neuf lignes et d’appeler la fonction de parsing, évitant ainsi l’ajout d’une dépendance complexe.

Mécanisme de Pratt : nud, led et puissance de liaison

Le cœur de la méthode repose sur deux catégories d’actions sémantiques : les nud (null denotation) et les led (left denotation). Un nud traite un token qui n’attend rien à sa gauche, alors qu’un led reçoit en argument l’expression déjà reconnue à gauche du token. Cette distinction inverse le modèle traditionnel où les actions sont attachées aux règles de production non‑terminales.

Chaque token possède également une binding power (puissance de liaison) exprimée par un entier positif. Cette valeur détermine la priorité d’associativité : un token avec une puissance supérieure empêche le parser de réduire l’expression à droite tant que la puissance de liaison n’est pas dépassée. Les tables de l’auteur contiennent trois colonnes : les codes lexicales des terminaux, les fonctions nud ou led (signatures ExprPtr(Context&,reader,reader&) et ExprPtr(Context&,reader,reader&,ExprPtr)), et les puissances de liaison.

Comparaison avec les techniques traditionnelles

Les générateurs de compilateurs classiques, comme GNU Bison, associent les actions sémantiques aux productions BNF. Cette approche nécessite la définition explicite d’une grammaire non‑terminale pour chaque règle, augmentant la complexité du fichier de description. En revanche, Pratt place les actions directement sur les terminaux, ce qui réduit le nombre de règles et rend le code plus lisible lorsqu’on manipule des expressions arithmétiques ou des opérateurs unaires.

Le gain de concision se traduit également par une meilleure modularité : chaque token implémente son propre comportement, facilitant l’ajout ou la modification d’opérateurs sans toucher à l’ensemble de la grammaire. Cette modularité explique pourquoi l’auteur a pu intégrer un moteur de parsing « heavily Pratt‑based » dans son compilateur sans analyser en profondeur le fragment de neuf lignes.

Limites et bonnes pratiques

Malgré sa simplicité, la méthode Pratt ne convient pas à toutes les grammaires. Les langages avec des constructions contextuelles complexes (par exemple, les déclarations de type dépendant du contexte) peuvent nécessiter des mécanismes de look‑ahead que le modèle de puissance de liaison ne gère pas naturellement. De plus, l’absence de séparation explicite entre syntaxe et sémantique peut rendre le débogage plus difficile, car les erreurs d’interprétation sont souvent liées à une mauvaise configuration des fonctions nud/led ou à une puissance de liaison incohérente.

Pour atténuer ces risques, il est recommandé de documenter chaque fonction terminale, de choisir des puissances de liaison strictement croissantes pour les opérateurs binaires, et de valider le comportement du parser avec une suite de tests couvrant les cas d’associativité et de priorité.