L14) La direction du parsing

LL, LR et le Dragon Book

Quand une grammaire génère une phrase, elle descend toujours de l’intention vers la surface — du symbole initial vers les mots. Mais quand elle analyse une phrase, elle peut choisir de monter, de descendre, ou de faire les deux à la fois. Cette liberté directionnelle, connue de tous les concepteurs de compilateurs, n’avait jamais été identifiée comme une dimension fondamentale de l’asymétrie entre génération et reconnaissance.

Où se situe cet article ?

Dans L13, nous avons exploré la dualité entre génération et reconnaissance — les deux usages fondamentaux de toute grammaire formelle. Nous avons identifié plusieurs dimensions de cette asymétrie : complexité computationnelle, déterminisme, information disponible, temporalité.

Mais une dimension était absente : la direction. C’est l’objet de cet article. Et c’est peut-être la dimension la plus surprenante, parce qu’elle se cache dans le livre de référence le plus utilisé en informatique — le Dragon Book — sans jamais être nommée.

Pourquoi c’est important ?

Imaginez un architecte qui dessine un bâtiment (génération) et un inspecteur qui examine un bâtiment existant (analyse). L’architecte part toujours de l’intention — le programme fonctionnel, les contraintes esthétiques, les normes — et descend vers les détails concrets : structure, matériaux, finitions. Il ne peut pas commencer par les poignées de portes et « remonter » vers le concept du bâtiment.

L’inspecteur, lui, a le choix. Il peut commencer par le toit et descendre. Il peut commencer par les fondations et monter. Il peut commencer par les issues de secours et raisonner dans les deux sens. La stratégie d’inspection est un paramètre — un choix de conception.

Cette asymétrie est exactement celle qui existe entre génération et parsing en théorie des langages formels. Et elle a des conséquences profondes.

L’idée en une phrase

La génération est intrinsèquement descendante (de l’axiome vers la surface), mais le parsing possède un degré de liberté directionnelle — le choix entre stratégie descendante, ascendante ou hybride — qui est absent de la génération.

Expliquons pas à pas

1. La génération descend toujours

Toute dérivation dans une grammaire syntagmatique (L2) procède du symbole initial $$S$$ vers les symboles terminaux :

$S \Rightarrow \alpha_1 \Rightarrow \alpha_2 \Rightarrow \cdots \Rightarrow w$

Ce processus est intrinsèquement descendant : il va du niveau le plus abstrait ( $$S$$ , l’intention : « je veux une phrase musicale ») au plus concret ( $$w$$ , la surface : les notes réelles).

Comme Chomsky l’a formulé : une grammaire génère « de haut en bas, pas de gauche à droite » (Chomsky, 1957). Quand une grammaire produit do ré mi fa, l’ordre temporel gauche-droite est un sous-produit de la décomposition hiérarchique :

$S \to AB,\quad A \to \text{do ré},\quad B \to \text{mi fa}$

La séquence temporelle do ré mi fa émerge de la structure verticale, pas l’inverse.

Encart : contre-exemple apparent

Kay (1996) a proposé un algorithme de génération par chart où l’assemblage syntactique peut procéder de bas en haut. Mais même dans ce cas, la direction sémantique reste descendante — ce qui pilote le processus est toujours intention → surface. La mécanique peut assembler les morceaux dans n’importe quel ordre ; la logique va toujours de l’abstrait au concret.

2. Le parsing a le choix

Pour le parsing, la direction est un paramètre de conception. Étant donné une grammaire $$G$$ et une chaîne $$w$$ , on cherche les arbres de dérivation $$t$$ tels que les feuilles de $$t$$ forment $$w$$ . Mais on peut chercher ces arbres de plusieurs façons :

Stratégie	Direction	Comment ça marche
LL (descente récursive)	Descendante ↓	On prédit quel non-terminal développer, puis on vérifie si les terminaux correspondent
LR (shift-reduce)	Ascendante ↑	On empile les terminaux lus, puis on réduit vers les non-terminaux quand un motif est reconnu
Earley (1970)	Hybride ↕	Prédiction descendante + complétion ascendante, combinées
CYK	Ascendante ↑	On construit un tableau par programmation dynamique, des sous-chaînes courtes vers les longues
Left-corner (1970)	Hybride ↕	On commence ascendant (le premier symbole), puis on prédit descendant

Cinq stratégies. Cinq directions. Et ce ne sont que les principales — il en existe d’autres (GLR, chart parsing, Packrat…).

Le point crucial : ce choix n’existe que pour le parser. Le générateur n’a pas de décision analogue. Il descend, point.

3. Le Dragon Book : une preuve involontaire

Le Dragon Book (Aho, Sethi & Ullman, 1986) est le livre de référence en conception de compilateurs. Son nom officiel est Compilers: Principles, Techniques, and Tools ; son surnom vient du dragon sur la couverture.

Ce livre fournit une étude de cas involontaire mais saisissante de l’asymétrie directionnelle :

Parsing : des centaines de pages. Chapitres entiers sur LL, LR, les tables de parsing, les conflits shift-reduce, la récupération d’erreurs, les grammaires d’opérateurs…
Génération de code : une discussion relativement contenue. Traversée linéaire de l’AST (L4), réécriture d’arbres, pattern matching.

Pourquoi cette disproportion ? Parce que la génération de code est une traversée descendante sans choix de direction — on parcourt l’AST du haut vers le bas, et le code machine sort au fur et à mesure. Le parsing, lui, nécessite tout un arsenal de stratégies, chacune avec ses forces, ses faiblesses, ses compromis.

Le Dragon Book ne nomme jamais cette asymétrie directionnelle. Il la démontre par son propre déséquilibre.

4. LL vs LR : l’observation frappante

Au sein du parsing, la distinction LL-versus-LR est particulièrement révélatrice.

LL (Left-to-right, Leftmost derivation) :

Le parser imite le processus génératif : il est descendant, il prédit quelle production appliquer
Il regarde un ou quelques symboles d’avance (le lookahead : les prochains symboles de l’entrée non encore lus) pour décider

LR (Left-to-right, Rightmost derivation) :

Le parser inverse le processus génératif : il est ascendant, il empile les symboles lus et les réduit quand il reconnaît le côté droit d’une règle
Il diffère ses décisions : il accumule des preuves avant de s’engager

Point crucial : LR est strictement plus puissant que LL. Pour tout $$k$$ (nombre de symboles d’avance), la classe des langages LR( $$k$$ ) inclut strictement la classe LL( $$k$$ ) (Knuth, 1965).

Autrement dit : la stratégie de parsing la plus différente de la génération est la plus puissante. Celle qui imite la génération est la plus faible.

Ce n’est pas un accident. Le parsing LR peut différer ses décisions — il attend d’avoir suffisamment de contexte pour s’engager. Cette capacité de report est quelque chose dont seul le parser a besoin. Le générateur s’engage immédiatement : il choisit une production et dérive. Le parser, lui, peut accumuler des preuves. Et plus il s’éloigne de la stratégie générative (descendante), plus il gagne en puissance.

Encart : l’analogie du détective

Un romancier (générateur LL) écrit l’histoire du début à la fin, chaque choix narratif découle du précédent. Un détective (parser LR) rassemble les indices (les terminaux), les empile, et ne conclut qu’une fois qu’un motif se dessine. Le détective est plus puissant justement parce qu’il ne suit pas la logique de l’auteur — il reconstruit en sens inverse.

5. Shieber : l’inversion qui ne marche pas

Stuart Shieber (1988) a tenté de concevoir une architecture unifiée pour le parsing et la génération — un seul moteur capable de faire les deux avec la même grammaire. Ce qu’il a découvert prouve l’asymétrie directionnelle de manière concrète.

En parsing, l’algorithme est piloté par la chaîne de surface : on consomme les tokens de gauche à droite, et la chart (la table de parsing) est indexée par les positions dans la chaîne — « du caractère 3 au caractère 7, on a reconnu un syntagme nominal ».

En génération, la chaîne n’existe pas encore — c’est elle qu’on cherche à produire. Il est donc impossible d’indexer la chart par des positions de chaîne. Shieber a dû restructurer l’algorithme pour qu’il soit piloté par la structure sémantique : la génération suit les têtes sémantiques (les nœuds de sens), pas les têtes syntaxiques (les mots). C’est la semantic head-driven generation (Shieber et al., 1990).

Cette restructuration n’est pas un simple changement de paramètre — c’est une réorganisation du flux de données. Le parsing va de la surface vers le sens : $w \to t$ . La génération va du sens vers la surface : $\phi \to w$ . Ce qui sert d’entrée à l’un n’existe pas encore pour l’autre. La même information déclarative (les règles grammaticales) exige deux interprétations procédurales distinctes.

L’observation de Shieber confirme que l’asymétrie directionnelle est structurelle : on ne peut pas « faire tourner le parsing à l’envers » pour obtenir la génération. Même dans un cadre unifié, la direction impose des choix architecturaux irréductibles.

6. Knuth et les attributs : descendant vs ascendant

Les grammaires d’attributs de Knuth (1968) formalisent la même asymétrie dans le domaine sémantique (pas seulement syntaxique).

Dans ces grammaires, les nœuds de l’arbre de dérivation portent des attributs — des informations calculées. Ces attributs circulent dans deux directions :

Attributs hérités ( $\downarrow$ ) : ils descendent du parent vers l’enfant. Exemple : le type attendu d’une expression, imposé par le contexte.
Attributs synthétisés ( $\uparrow$ ) : ils montent de l’enfant vers le parent. Exemple : la valeur calculée d’une expression, remontée depuis les feuilles.

La génération est essentiellement un flux d’attributs hérités (l’intention descend). L’analyse est un flux bidirectionnel (les informations montent et descendent). Grune et Jacobs observent que les grammaires d’attributs « devraient plutôt être classées comme des systèmes de reconnaissance » — le flux bidirectionnel des attributs est une propriété analytique.

Ce qu’il faut retenir

La génération est intrinsèquement descendante : de l’axiome vers les terminaux, de l’intention vers la surface. C’est une constante.
Le parsing possède un degré de liberté directionnelle : LL (descendant), LR (ascendant), Earley (hybride), CYK (ascendant), left-corner (hybride). C’est un paramètre.
Le Dragon Book illustre involontairement cette asymétrie : des centaines de pages sur les stratégies de parsing, la génération tenue pour acquise.
LR est plus puissant que LL : la stratégie la plus différente de la génération est la plus performante, parce qu’elle peut différer ses décisions.
Cette asymétrie directionnelle est connue de tous les concepteurs de compilateurs mais n’avait jamais été nommée comme dimension indépendante de l’asymétrie génération-reconnaissance.
En musique, c’est la même chose : composer (descendre de l’intention vers les notes) n’a qu’une direction ; analyser une pièce existante peut procéder de multiples façons (harmonique, motivique, schenkérienne, statistique…).

Pour aller plus loin

Références fondamentales

Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools (le Dragon Book). Addison-Wesley — le traitement le plus complet des stratégies LL et LR.
Chomsky, N. (1957). Syntactic Structures. Mouton — la formulation originale de la direction descendante de la génération.
Knuth, D.E. (1965). « On the Translation of Languages from Left to Right. » Information and Control — preuve que LR( $$k$$ ) ⊃ LL( $$k$$ ).
Knuth, D.E. (1968). « Semantics of Context-Free Languages. » Mathematical Systems Theory — les grammaires d’attributs (hérités ↓ et synthétisés ↑).

Architecture unifiée

Shieber, S. (1988). « A Uniform Architecture for Parsing and Generation. » COLING — première tentative d’architecture unifiée parsing/génération.
Shieber, S., van Noord, G., Pereira, F.C.N. & Moore, R.C. (1990). « Semantic-Head-Driven Generation. » Computational Linguistics, 16(1), 30–42 — la génération pilotée par les têtes sémantiques, preuve que le parsing ne s’inverse pas trivialement.
Kay, M. (1996). « Chart Generation. » ACL — génération par chart (assemblage ascendant, mais logique sémantique descendante).

Stratégies de parsing

Earley, J. (1970). « An Efficient Context-Free Parsing Algorithm. » Communications of the ACM — l’algorithme hybride descendant-ascendant.
Rosenkrantz, D.J. & Lewis, P.M. (1970). « Deterministic Left Corner Parsing. » IEEE Symposium on Switching and Automata Theory — la stratégie left-corner.
Grune, D. & Jacobs, C. (2008). Parsing Techniques: A Practical Guide. Springer — panorama complet des techniques de parsing.

Dans le corpus

L1 — Les niveaux de la hiérarchie
L2 — Comment les grammaires produisent des phrases
L4 — L’arbre de syntaxe abstraite
L13 — Vue d’ensemble de l’asymétrie (6 dimensions)
L15 — Les formalisations mathématiques de l’asymétrie
L16 — Pourquoi la bidirectionnalité n’a pas été transférée

Glossaire

Ascendant (bottom-up) : Stratégie de parsing qui part des symboles terminaux (les feuilles de l’arbre) et remonte vers l’axiome (la racine). Exemples : LR, CYK.
Attribut hérité ( $\downarrow$ ) : Information qui descend du parent vers l’enfant dans une grammaire d’attributs. Flux descendant.
Attribut synthétisé ( $\uparrow$ ) : Information qui monte de l’enfant vers le parent dans une grammaire d’attributs. Flux ascendant.
Chart (table de parsing) : Structure de données tabulaire utilisée par les algorithmes de parsing (Earley, CYK, chart parsing) pour stocker les résultats intermédiaires. En parsing, indexée par les positions dans la chaîne d’entrée. En génération, cette indexation est impossible (la chaîne n’existe pas encore), d’où la nécessité de piloter par les têtes sémantiques.
CYK (Cocke-Younger-Kasami) : Algorithme de parsing ascendant par programmation dynamique. Fonctionne en $\mathcal{O}(n^3)$ pour toute CFG.
Descendant (top-down) : Stratégie qui part de l’axiome (la racine) et descend vers les terminaux (les feuilles). C’est la direction naturelle de la génération. En parsing, c’est la stratégie LL.
Dragon Book : Surnom de Compilers: Principles, Techniques, and Tools (Aho, Sethi & Ullman, 1986), le livre de référence en conception de compilateurs.
Earley : Algorithme de parsing hybride (descendant-ascendant) capable de traiter toute CFG en $\mathcal{O}(n^3)$ .
Left-corner : Stratégie de parsing hybride qui commence ascendante (le premier symbole) puis poursuit descendante (prédiction).
LL (Left-to-right, Leftmost derivation) : Parsing descendant prédictif. Imite la direction de la génération. Moins puissant que LR.
Lookahead : Nombre de symboles d’avance qu’un parser consulte pour décider quelle règle appliquer. Noté $$k$$ dans LL( $$k$$ ) et LR( $$k$$ ).
LR (Left-to-right, Rightmost derivation) : Parsing ascendant par décalage-réduction. Inverse la direction de la génération. Strictement plus puissant que LL (Knuth, 1965).

Prérequis : L1, L2, L13
Temps de lecture : 12 min
Tags : #parsing #direction #LL #LR #dragon-book #asymétrie #compilateurs

← Retour à l’index