Site d’Emmanuel Saint-James
Philologie de la programmation
Désambiguez et Décontextualisez, sinon je craque

Il existe toute une série de questions sur les grammaires formelles, certaines irrésolues :

• il n’existe pas d’algorithme universel déterminant si deux grammaires produisent le même langage ;
• il n’existe pas d’algorithme universel déterminant si une grammaire est ambigüe ou non ;
• il existe des langages inhéremment ambigus, c’est-à-dire qui ne sont définissables que par des grammaires ambigües (exemple : les mots formés de deux palindromes) ;
• les grammaires dont les parties gauches des règles peuvent contenir des non terminaux, appelées grammaires contextuelles n’ont aucune propriété algébrique intéressante, d’où le recours à la statistique pour les langues naturelles (un aveu d’échec déguisé en réussite) ;
• l’ensemble des grammaires acontextuelles, dites aussi algébriques, est fermé par union et concaténation, mais pas par intersection (a^* bⁿ cⁿ et aⁿ bⁿ c^* sont définissables par des grammaires acontextuelles, mais pas aⁿ bⁿ cⁿ) ;
• l’ensemble des grammaires acontextuelles comporte un sous-ensemble, les grammaires dites rationnelles, caractérisées par des parties droites de règles n’ayant qu’un seul non terminal et en fin de règle ;
• les langages définis par ces grammaires sont analysables par automate fini c’est-à-dire sans consommation de mémoire ;
• pour les autres grammaires acontextuelles , il faut une pile dont la longueur dépend de la donnée d’entrée, autrement dit il faut procéder à une allocation dynamique de mémoire ;
• théorème fondamental : toute grammaire acontextuelle est l’intersection, à un codage près, d’un langage de Dyck et d’une grammaire rationnelle.