L16) Le paradoxe de la bidirectionnalité

50 ans de grammaires réversibles oubliées

Depuis les années 1970, des formalismes grammaticaux capables de fonctionner dans les deux directions — génération et analyse — existent en traitement automatique des langues. Pourtant, la plupart des systèmes formels dans d’autres domaines restent obstinément unidirectionnels. Ce paradoxe révèle que l’asymétrie entre génération et reconnaissance n’est pas un simple problème technique : c’est une fracture structurelle que même cinq décennies de solutions n’ont pas comblée.

Où se situe cet article ?

Dans L13, nous avons vu que certains systèmes — GF, les grammaires d’unification, le Bol Processor — sont conçus pour fonctionner dans les deux directions. Dans L14, nous avons exploré la dimension directionnelle de l’asymétrie. Dans L15, nous en avons posé les fondations mathématiques.

Cet article pose la question qui découle de tout cela : si la bidirectionnalité est possible et disponible depuis 50 ans, pourquoi n’est-elle pas partout ?

Pourquoi c’est important ?

Imaginez qu’un traducteur automatique ne puisse traduire que du français vers l’anglais, jamais l’inverse. Et qu’on vous dise : « la technologie pour faire l’inverse existe depuis 1972, mais personne ne l’utilise ».

C’est exactement la situation des grammaires formelles dans la plupart des domaines appliqués. En bio-informatique, les grammaires prédisent la structure de l’ARN (analyse) mais ne conçoivent pas de séquences (génération). En musicologie, les grammaires composent (génération) ou analysent, mais presque jamais les deux avec le même formalisme. En compilation, le parsing et la génération de code sont deux modules séparés.

Comprendre pourquoi cette situation persiste, c’est comprendre la nature profonde de l’asymétrie — et c’est identifier les leviers pour la surmonter.

L’idée en une phrase

Les formalismes bidirectionnels existent en TAL depuis les années 1970 mais n’ont pas été transférés aux autres domaines, parce que la bidirectionnalité exige la déclarativité — et la plupart des grammaires appliquées sont procédurales.

Expliquons pas à pas

1. La carte du paysage : qui fait quoi ?

Commençons par dresser l’inventaire. On peut classer les systèmes formels selon les directions qu’ils supportent :

Système	Domaine	Gen	Parse	Inférence	Bidirectionnel
Parsers LL/LR	Compilateurs	—	✓	—	—
Earley/CYK	Langages formels	—	✓	—	—
Pipeline NLG	TAL	✓	—	—	—
Templates NLG	TAL	✓	—	—	—
LLMs (GPT, etc.)	TAL	✓	(implicite)	—	—
DCG (Prolog)	TAL	✓	✓	—	✓*
FST (morphologie)	Linguistique	✓	✓	—	✓
GF (Ranta)	TAL multilingue	✓	✓	—	✓
KAMP (Appelt)	TAL	✓	✓	—	✓*
Strzalkowski	TAL	✓	✓	—	✓
L* (Angluin)	Langages formels	—	—	✓	—
Gold	Langages formels	—	—	✓	—
BP3	Musique	✓	✓	—	✓

\ Bidirectionnel en principe mais avec des pathologies asymétriques (DCG) ou un coût impraticable (KAMP).*

Trois constats sautent aux yeux :

La plupart des systèmes sont unidirectionnels. Ils font soit la génération, soit le parsing, rarement les deux.
Les systèmes bidirectionnels se concentrent en TAL (traitement automatique des langues), où le besoin pratique des deux directions (traduction, dialogue, ingénierie de grammaires) a stimulé le développement.
L’inférence grammaticale (la « troisième direction ») est presque toujours séparée des deux autres.

2. Les pionniers de la bidirectionnalité

DCG : la bidirectionnalité par Prolog (1972)

Les Definite Clause Grammars (DCG), intégrées à Prolog, sont intrinsèquement bidirectionnelles : la même grammaire peut être interrogée dans les deux directions grâce à l’unification et au backtracking.

Mais la symétrie est algorithmique, pas computationnelle. Les règles récursives à gauche causent des boucles infinies en parsing descendant — mais pas en génération. Inversement, les règles récursives à droite peuvent faire diverger la génération. La même grammaire, dans deux directions, rencontre des pathologies différentes. C’est une illustration concrète de l’asymétrie directionnelle (L14).

FST : l’inversion mathématique (1983)

Les transducteurs à états finis (FST), utilisés en morphologie computationnelle, ont une propriété élégante : l’inverse d’un FST est aussi un FST. Si $$T$$ transforme les formes sous-jacentes en formes de surface (génération), alors $T^{-1}$ fait l’inverse (analyse).

La morphologie à deux niveaux de Koskenniemi (1983) exploite ceci directement. Mais cette propriété d’inversion ne vaut que pour les machines à états finis — elle ne se généralise pas aux grammaires context-free, où l’inversion est indécidable en général.

Q-systèmes : le calcul réversible (1970)

Les Q-systèmes de Colmerauer (1970), précurseurs de Prolog, ont été conçus dès l’origine pour le calcul réversible. Leur influence persiste dans la programmation logique, où la séparation entre logique et contrôle (Kowalski, 1979) fait de la direction un paramètre plutôt qu’un choix architectural.

3. Grammatical Framework : la bidirectionnalité à grande échelle

GF (Grammatical Framework, Ranta, 2004) est le système bidirectionnel moderne le plus abouti. Son architecture sépare deux niveaux :

Syntaxe abstraite : la représentation du sens, indépendante de la langue
Syntaxe concrète : la réalisation de surface, spécifique à chaque langue

Le même arbre abstrait peut être linéarisé (génération : arbre → phrase) ou parsé (reconnaissance : phrase → arbre) dans n’importe laquelle des 40+ langues supportées.

GF démontre que la bidirectionnalité est réalisable à grande échelle. Mais il nécessite un engagement architectural : la grammaire doit être écrite de façon déclarative, avec sens et forme proprement séparés.

4. Le coût de la bidirectionnalité

KAMP : computationnellement impraticable

Appelt (1985, 1987) a tenté une architecture unifiée pour la planification et la réalisation en génération de texte. Il a formulé ce qui est peut-être l’observation la plus importante :

« L’exigence la plus fondamentale de toute grammaire bidirectionnelle est qu’elle soit représentée déclarativement. Si elle est procédurale, l’asymétrie est inévitable. »

Son système KAMP fonctionnait — mais était « computationnellement impraticable ». Le coût de l’unification de la planification et de la réalisation dans un seul cadre s’est avéré prohibitif.

C’est un résultat d’avertissement : la bidirectionnalité est possible en principe mais coûteuse en pratique.

L’inversion de grammaires : Strzalkowski

Plutôt que de concevoir une grammaire bidirectionnelle dès le départ, Strzalkowski (1993) a développé des techniques pour transformer automatiquement une grammaire de parsing en grammaire de génération — en inversant la structure de contrôle tout en préservant le contenu déclaratif.

Les résultats : l’inversion fonctionne, mais la grammaire inversée est moins efficace, et certaines constructions résistent entièrement à l’inversion. Le fait même qu’un processus d’inversion soit nécessaire prouve l’asymétrie opérationnelle.

Le test bidirectionnel de Goodman et Bond

Goodman et Bond (2009) ont fourni la preuve empirique la plus convaincante de la valeur de la bidirectionnalité : tester une grammaire HPSG à la fois en parsing et en génération a révélé des erreurs invisibles en usage unidirectionnel, augmentant la couverture de 18 %.

Morale : utiliser une grammaire dans une seule direction, c’est ne tester que la moitié de ses propriétés.

5. Pourquoi la bidirectionnalité n’a pas été transférée

Si la bidirectionnalité existe depuis 50 ans en TAL, pourquoi n’est-elle pas partout ?

Hypothèse 1 : le prérequis de déclarativité. Appelt l’a dit : la bidirectionnalité exige des grammaires déclaratives — qui disent quoi sans dire comment. Or la plupart des grammaires appliquées sont procédurales : elles intègrent la direction de traitement dans la grammaire elle-même. Une grammaire de formes en architecture spécifie comment produire des formes, pas comment les reconnaître. Les grammaires procédurales résistent à l’inversion parce que le contenu linguistique et la structure de contrôle sont inséparables.

Hypothèse 2 : le coût caché. La bidirectionnalité a des coûts qui ne sont pas visibles au moment de la conception : KAMP impraticable, Strzalkowski moins efficace, GF nécessitant un engagement architectural. Le bénéfice (+18 % de couverture) ne justifie pas toujours l’effort quand une seule direction suffit.

6. L’asymétrie est structurelle, pas accidentelle

La thèse centrale : les six dimensions de l’asymétrie (L15) ne sont pas des problèmes techniques résolubles. Chacune est indépendante des autres et irréductible :

D1 (complexité) est une conséquence de la hiérarchie de Chomsky — elle ne changera pas avec du matériel plus rapide
D2 (ambiguïté) découle des propriétés mathématiques des langages — aucun algorithme ne rend non ambigu un langage intrinsèquement ambigu (déterminisme, non-injectivité et cardinalité sont un seul phénomène)
D3 (direction) reflète l’ordre logique de la dérivation — l’axiome précède les terminaux
D4 (information) découle de l’architecture de Shannon — l’encodeur connaît la source, le décodeur non
D5 (inférence) est bornée par Gold
D6 (temporalité) est formalisée par Hale/Levy

Encart : les LLMs ne résolvent pas l’asymétrie

Les grands modèles de langage semblent générer sans effort — du texte fluide, en temps linéaire. Mais ils déplacent le coût analytique plutôt que de l’éliminer. L’entraînement d’un LLM EST un acte massif d’analyse : compresser un corpus entier en paramètres de modèle. Le coût de génération O(n) par token est payé en amont par un coût d’entraînement colossal. La génération intelligente présuppose toujours une analyse préalable.

7. Au-delà du TAL : bio-informatique, décompilation et musique

L’asymétrie se manifeste partout où les grammaires formelles sont utilisées :

Bio-informatique. Les grammaires stochastiques context-free (SCFG) prédisent la structure secondaire de l’ARN — un problème de reconnaissance. La direction inverse — concevoir des séquences d’ARN avec une structure cible — est le repliement inverse (inverse folding), connu pour être NP-difficile. L’asymétrie : repliement (reconnaissance, polynomial) vs. conception (génération contrainte, NP-difficile).

Décompilation. En compilation, le parsing (code source → AST) et la génération de code (AST → binaire) sont asymétriques. La décompilation (binaire → code source) est possible mais produit du code structurellement différent de l’original — une manifestation de la non-injectivité (D5) : de multiples programmes sources compilent vers le même binaire.

Musique. C’est le « laboratoire idéal » : la composition (génération) et l’analyse musicale sont des pratiques établies depuis des siècles. Pourtant, la plupart des systèmes musicaux sont unidirectionnels. La taxonomie ci-dessous classe les principaux systèmes selon les directions qu’ils supportent :

→ Voir la taxonomie chronologique dans L13 Figure 1.

Analytiques : GTTM (1983), analyse schenkérienne computationnelle (2004), IDyOM (2018), grammaire de graphe mélodique (Finkensiep, 2019), compression grammaticale (2021)
Génératifs formels : Holtzman (1981), Max (1988), SuperCollider (1996), OpenMusic (1999), Euterpea (2013), TidalCycles (2014), L-systems (2021), CFG+Markov (2025)
Génératifs neuronaux : Jukebox (2020), MusicLM (2023), MusicGen (2023), Suno (2025) — pas de grammaire explicite, uniquement du deep learning
Bidirectionnels — avec des degrés d’intégration très variables : CCG jazz (Steedman, 1984 → 2014, 30 ans entre les deux directions), EMI (Cope, 1989, séquentiel), OMax (2006), Antescofo (2008), modèle unifié voice-leading (Harrison & Pearce, 2019), et BP3 (I2) = le cas le plus intégré (modes PROD, ANAL, TEMP avec la même grammaire)

Pour le détail de chaque système, voir L13 §8.

8. L’inférence : la troisième direction oubliée

Au-delà de la dualité génération-reconnaissance, l’inférence grammaticale (L13 §9) constitue une troisième direction encore plus fondamentale — et encore plus négligée.

Gold (1967) a prouvé que toute classe de langages « superfinie » (contenant tous les langages finis et au moins un infini) n’est pas identifiable à partir de données positives seules. C’est un mur théorique.

Horning (1969) a trouvé la première issue : les PCFG (Probabilistic Context-Free Grammars) sont apprenables dans un cadre bayésien — en utilisant des connaissances a priori (un « prior ») pour discriminer entre grammaires candidates. Le prior probabiliste brise la symétrie qu’exploite le théorème de Gold.

L’algorithme L d’Angluin (1987) a montré que les langages réguliers sont apprenables efficacement — mais avec un oracle d’appartenance*, c’est-à-dire une capacité de reconnaissance intégrée au processus d’inférence. L’inférence présuppose la reconnaissance, tout comme la génération intelligente présuppose l’analyse.

Les trois opérations forment une hiérarchie (L15) :

$\underbrace{\text{Génération}}_{\mathcal{O}(n)} \;<\; \underbrace{\text{Reconnaissance}}_{\mathcal{O}(n^3)} \;<\; \underbrace{\text{Inférence}}_{2^{\mathcal{O}(n)}}$

Ce qu’il faut retenir

Les systèmes formels sont majoritairement unidirectionnels : ils font soit la génération, soit l’analyse, rarement les deux.
Les systèmes bidirectionnels (DCG, FST, GF, inversion de grammaires) existent en TAL depuis les années 1970, mais n’ont pas été transférés aux autres domaines.
Deux raisons principales : la bidirectionnalité exige la déclarativité (séparer le quoi du comment), et elle a un coût caché (KAMP impraticable, grammaires inversées moins efficaces).
L’asymétrie est structurelle, pas accidentelle : elle découle de la hiérarchie de Chomsky, du théorème de Parikh, de l’architecture de Shannon — pas d’un manque de progrès technique.
Les LLMs déplacent le coût analytique (vers l’entraînement) mais ne l’éliminent pas.
L’inférence grammaticale est la troisième direction, la plus difficile, et elle présuppose la reconnaissance (Angluin).
La musique est le laboratoire idéal pour étudier cette asymétrie — BP3 étant l’un des rares systèmes explicitement bidirectionnels.

Pour aller plus loin

Systèmes bidirectionnels

Ranta, A. (2004). « Grammatical Framework: A Type-Theoretical Grammar Formalism. » Journal of Functional Programming, 14(2), 145–189 — GF, le système bidirectionnel le plus complet.
Appelt, D.E. (1987). « Bidirectional Grammars and the Design of Natural Language Generation Systems. » TINLAP-3 — la thèse de la déclarativité.
Strzalkowski, T. (1993). Reversible Grammar in Natural Language Processing. Springer — l’inversion de grammaires.
Goodman, M.W. & Bond, F. (2009). « Using Generation for Grammar Analysis and Error Detection. » ACL Workshop — la preuve empirique (+18 %).
Colmerauer, A. (1970). « Les systèmes-Q. » Université de Montréal — les précurseurs de Prolog.
Koskenniemi, K. (1983). Two-Level Morphology. University of Helsinki — morphologie bidirectionnelle par FST.

Inférence grammaticale

Gold, E.M. (1967). « Language Identification in the Limit. » Information and Control — le résultat d’impossibilité.
Horning, J.J. (1969). A Study of Grammatical Inference. PhD thesis, Stanford — l’issue bayésienne.
Angluin, D. (1987). « Learning Regular Sets from Queries and Counterexamples. » Information and Computation — L* et l’oracle d’appartenance.
de la Higuera, C. (2010). Grammatical Inference. Cambridge University Press — référence complète.

Applications domaine-spécifiques

Bonnet, É., Rzążewski, P. & Sikora, F. (2020). « Designing RNA Secondary Structures Is Hard. » Journal of Computational Biology — repliement inverse NP-difficile.
Su, S.-Y., Huang, C.-W. & Chen, Y.-N. (2019). « Dual Supervised Learning for Natural Language Understanding and Generation. » ACL — NLU/NLG comme paire duale.
Reiter, E. & Dale, R. (2000). Building Natural Language Generation Systems. Cambridge University Press — le pipeline NLG.

Dans le corpus

L9 — TAG, CCG, MCFG : les formalismes mildly context-sensitive
L13 — Vue d’ensemble de l’asymétrie (6 dimensions)
L14 — La direction du parsing : LL, LR et le Dragon Book
L15 — Les formalisations mathématiques de l’asymétrie
M6 — GTTM : le paradigme analytique appliqué
M10 — L’inférence grammaticale en musique (à venir)
I2 — Le Bol Processor : un système bidirectionnel

Glossaire

Bidirectionnalité : Propriété d’un formalisme grammatical qui peut être utilisé à la fois pour la génération (produire des chaînes) et la reconnaissance (analyser des chaînes) avec la même grammaire.
DCG (Definite Clause Grammar) : Extension grammaticale de Prolog, intrinsèquement bidirectionnelle grâce à l’unification, mais avec des pathologies asymétriques (récursions infinies différentes dans chaque direction).
Déclarativité : Propriété d’une grammaire qui sépare ce qu’elle dit (le contenu linguistique) de comment elle est traitée (la direction, la stratégie de parcours). Prérequis de la bidirectionnalité selon Appelt.
FST (Finite-State Transducer) : Automate à états finis avec entrée et sortie. L’inverse d’un FST est aussi un FST — propriété qui ne se généralise pas aux grammaires context-free.
GF (Grammatical Framework) : Formalisme grammatical multilingue de Ranta (2004, 2019) avec séparation syntaxe abstraite/concrète, permettant parsing et génération dans 40+ langues.
Inversion de grammaires : Technique de Strzalkowski pour transformer automatiquement une grammaire de parsing en grammaire de génération en inversant la structure de contrôle. Prouve que la direction est intégrée dans les grammaires procédurales.
KAMP : Système d’Appelt unifiant planification et réalisation en NLG. Bidirectionnel mais « computationnellement impraticable ».
NLG (Natural Language Generation) : Sous-domaine du TAL qui concerne la génération de texte. Le pipeline de Reiter & Dale décompose le processus en planification du document → microplanification → réalisation de surface.
Pipeline NLG : Architecture en trois étapes (Reiter & Dale, 2000) : 1) planification du document (quoi dire), 2) microplanification (comment le dire), 3) réalisation de surface (la phrase). Structurellement descendant.
Repliement inverse (inverse folding) : En bio-informatique, le problème de concevoir une séquence d’ARN qui se replie en une structure cible. NP-difficile (Bonnet et al., 2020).
TAL (Traitement Automatique des Langues) : Le domaine de l’informatique qui traite du langage naturel. En anglais : NLP (Natural Language Processing).

Prérequis : L9, L13
Temps de lecture : 14 min
Tags : #bidirectionnalité #grammaires-réversibles #TAL #GF #DCG #inférence #Gold

← Retour à l’index