Forme normale de Chomsky

En informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme :

  1.  ;
  2. ou  ;
  3. ou

sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et est le mot vide.

Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.

Historique

modifier

La forme normale de Chomsky tient son nom du linguiste américain Noam Chomsky, qui a conçu également la hiérarchie qui porte son nom, et qui a décrit cette forme normale à cette occasion dans un article publié en 1959[1].

Variantes de définition

modifier

Une variante de la définition consiste à ne pas permettre le mot vide : seules des règles de la forme

ou ,

sont permises où , et sont des symboles non terminaux et est un symbole terminal. C'est la définition adoptée par exemple par Carton[2] ou Hopcroft et. al. [3]. Bien entendu, ces grammaires n'engendrent pas le mot vide.

Une autre variante[4],[5] demande que les membres droits de règles soient de longueur au plus 2, mais n'impose pas que les membres droits de longueur 2 soient formés exclusivement de symboles non terminaux. Un telle grammaire est appelé 2-forme normale ou « 2NF ».

Propriétés et utilisations

modifier

Toute grammaire écrite en forme normale de Chomsky est une grammaire non contextuelle. Inversement, toute grammaire hors contexte peut être transformée en une grammaire équivalente (c'est-à-dire engendrant le même langage) en forme normale de Chomsky.

À l'exception de la règle (3), toutes les règles d'une grammaire sous forme normale de Chomsky sont croissantes ; par conséquent, tout au long d'une dérivation, les longueurs des mots croissent. Ils croissent de 1 avec une règle de type (1), et restent de même longueur avec une règle de type (2). La dérivation d'un mot de longueur se fait donc toujours en étapes : il y a étapes de type (1) et étapes de type (2). De plus, dans la mesure où toutes les règles de dérivation de non-terminaux transforment un non-terminal en deux non-terminaux, un arbre de dérivation fondé sur une grammaire en forme normale de Chomsky est un arbre binaire avec nœuds internes et feuilles, et sa hauteur est au maximum la longueur de la chaîne de caractères.

Grâce à ces propriétés, de nombreuses preuves dans le domaine des langages formels deviennent plus simples en utilisant la forme normale de Chomsky (par exemple le fait que l'appartenance d'un mot au langage engendré est décidable). Plusieurs algorithmes généraux d'analyse syntaxique, comme l'algorithme de Cocke-Younger-Kasami, emploient cette forme normale.

Conversion d'une grammaire en forme normale de Chomsky

modifier

La conversion d'une grammaire en forme normale de Chomsky se fait par une suite de transformations simples, appliquées dans un certain ordre. La plupart des manuels de théorie des automates décrivent cette conversion[6],[7],[8],[9], [10],[11] ,[12]. Dans un article pédagogique, Lange et Leiß[13] décrivent soigneusement ces opérations, et ils donnent des noms aux étapes de la transformation ce qui facilite l'exposition. De plus, ils indiquent l'ordre à utiliser qui permet de garantir une complexité linéaire.

En général, la transformation est précédée d'une opération — appelée « réduction » chez Carton 2008, (Section 2.1.2 : Grammaires réduites, p. 79) ou « eliminating useless symbols » chez Hopcroft, Motwani et Ullman 2007, (Section 7.1.1 : Eliminating useless symbols, p. 262) — qui sert à supprimer les variables inutiles. Une variable X est utile si elle figure dans une dérivation de l'axiome en un mot terminal; pour cela, elle doit être accessible à partir de l’axiome par une suite de dérivations, et être « coaccessible », au sens qu'elle doit pouvoir être dérivée en un mot terminal.

Chacune des cinq transformation suivantes (START, TERM, BIN, DEL, UNIT) établit une des propriétés requise par la forme normale de Chomsky. On les présente, en suivant Lange et Leiß, comme si elles s'appliquaient à une grammaire générale ; on verra plus loin que l'ordre d'application est important si on veut minimiser la complexité en temps. Dans ces ordres particuliers, certaines opérations sont plus simples, comme l'opération UNIT qui sert à éliminer les règles unité.

La complexité des opérations se mesure par rapport à la taille de la grammaire G donnée. Elle est définie simplement[13] comme la place que prend l'écriture des règles, sont

où la sommation porte sur toutes les règles de la grammaire. En particulier, une ε-règle contribue pour 1 dans la somme.

START : Suppression de l’axiome dans les membres droits de règles

modifier

Pour cela, on introduit un nouveau symbole qui devient l'axiome, et la règle

,

est l’ancien axiome. Ceci ne modifie pas le langage engendré, et la variable ne figure pas dans un membre droit de règle.

TERM : Suppression des lettres terminales dans les membres droits de règles de longueur au moins 2

modifier

Si une lettre terminale figure dans un membre droit de règle de longueur au moins 2, on la remplace par une nouvelle et on ajoute la nouvelle règle

et on remplace la règle ci-dessus par

En fait, on fait ce remplacement simultanément pour toutes les occurrences de lettres terminales dans les membres droits de règles. Cela ne modifie pas le langage engendré, et augmente le nombre de règles d'au plus le nombre de lettres terminales. L'opération est donc linéaire en fonction de |G|.

BIN : Suppression des membres droits avec plus de deux symboles

modifier

On remplace une règle

,

par les règles

,

où les sont des nouveaux symboles non terminaux[14],[15]. Cette opération au plus triple la taille de la grammaire.

DEL : Élimination des ε-règles

modifier

Une ε-règle est une règle de la forme

,

n'est pas l’axiome de la grammaire. On commence par déterminer les variables qui dérivent en ε ; ces variables, appelées annulables (« nullable » en anglais), se calculent par récurrence : X est annulable s'il existe une règle

telle que sont tous annulables.

Pour toute variable , annulable ou non, toute règle

est remplacée par toutes les règles obtenues en supprimant une ou plusieurs, voire toutes les variables annulables dans le membre droit de règle, puis on supprime toutes les ε-règles (à l'exception de celle de l'axiome si elle est présente)[16].

Par exemple, dans la grammaire suivante avec axiome S0,

S0AbB | C
BAA | AC
Cb | c
Aa | ε

La variable A, et par conséquent B, sont annulables, et ni C ni S0 ne le sont. Dans la version intermédiaire suivante, on a coloré les variables à supprimer :

S0AbB | AbB | AbB | AbB | C
BAA | AA| AA | AεA | AC | AC
Cb | c
Aa | ε

Après suppression des variables en vert, et des règles A → ε (d'origine) et B → ε (produite), on obtient la grammaire

S0AbB | Ab | bB | b | C
BAA | A | AC | C
Cb | c
Aa

Cette grammaire engendre le même langage, sans ε-règles.

UNIT : Suppression des règles unité

modifier

Une règle unité est une règle de la forme

et sont des variables, et plus généralement une règle

,

où toutes les variable de sont annulables. Pour éliminer ce type de règles, on la remplace par la règle

pour chaque règle

sauf si c'est une règle unité précédemment enlevée[17]. Cette technique est complétée dans le cas de cycles (comme l'existence de trois règles ) par l'identification des variables d'un cycle : elles sont toutes remplacées par l'une d'entre elles. La transformation UNIT peut faire passer la taille de la grammaire de |G| à |G|2.

Ordre des transformations

modifier
Préservation
des propriétés des transformations
la transformation X préserve le résultat de Y
la transformation X peut altérer le résultat de Y.
X\Y START TERM BIN DEL UNIT
START
TERM
BIN
DEL
UNIT ()*
*UNIT conserve le résultat de DEL
si START a été effectué au préalable.

L'ordre dans lequel les opérations sont appliquées est important pour deux raisons : d'abord, il est possible qu'une transformation puisse annuler l'effet d'une opération précédente ; par exemple, si on utilise START après UNIT, on réintroduit une règle unité. Sur la table, les ordres convenables sont indiqués.

Une autre raison pour choisir l'ordre des opérations avec soin est l'augmentation possible de la taille de la grammaire, et par là même la complexité des opérations. La taille de la grammaire résultat peut aller de |G|2 à 22|G| pour une grammaire de taille |G|[18]. L'augmentation dépend de l'ordre entre DEL et BIN. Il peut être exponentiel si DEL est opéré en premier, puisqu'une règle dont le membre droit est de longueur n peut produire 22n règles, et sinon est linéaire. UNIT peut provoquer une augmentation quadratique de la taille[4].

La plus petite augmentation de taille se produit pour les ordres (START,TERM,BIN,DEL,UNIT) et (START,BIN,DEL,UNIT,TERM).

Preuve de correction

modifier

Les divers manuels et cours de théorie des langages contiennent en général, en plus de l'exposé des procédures, des démonstrations de la correction des algorithmes. Une formalisation de ces opérations de réduction, à savoir la suppression de variables inutiles, l’élimination des règles unité et des epsilon-règles dans l’assistant de preuve Coq a été entreprise par Marcus V. M. Ramos et Ruy J. G. B. de Queiroz[19]. Dans ce formalisme, Coq prouve que les opérations sont correctes en ce sens qu’ils préservent le langage engendré par la grammaire.

Références

modifier
  1. (en) Noam Chomsky, « On Certain Formal Properties of Grammars », Information and Control, vol. 2,‎ , p. 137–167 (DOI 10.1016/s0019-9958(59)90362-6, lire en ligne [PDF]).
  2. Carton 2008
  3. Hopcroft, Motwani et Ullman 2007
  4. a et b Lange et Leiß 2009, p. 5.
  5. Romain Legendre et François Schwarzentruber, Compilation : analyse lexicale et syntaxique : Du texte à sa structure en informatique, Paris, Ellipse, , 312 p. (ISBN 978-2-340-00366-8)
  6. Hopcroft et Ullman 1979, p. 87-94.
  7. Hopcroft, Motwani et Ullman 2007, Section 7.1 : Normal Forms for Context-Free Grammars, p. 261-275.
  8. Wegener 1993, Section 6.2 Die Chomsky-Normalform für kontextfreie Grammatiken, p. 149-152.
  9. Carton 2008, Section 2.1.4 : Forme normale quadratique, p. 80-82.
  10. Sipser 2013, Section 2.1: Context-free grammars. Chomsky normal form p. 108.
  11. Martin 2003, Section 6.6 : Simplified forms and normal forms, p. 237-240.
  12. Linz 2001, Chapter 6 : Simplification of context-free grammars, p. 149-164
  13. a et b Lange et Leiß 2009.
  14. Hopcroft et Ullman 1979, p. 93.
  15. Hopcroft, Motwani et Ullman 2007, p. 272
  16. Hopcroft, Motwani et Ullman 2007, p. 265.
  17. Hopcroft, Motwani et Ullman 2007, p. 268.
  18. Lange et Leiß 2009, p. 7.
  19. Marcus V. M. Ramos et Ruy J. G. B. de Queiroz, « Formalization of simplification for context-free grammars », préprint arXiv,‎ (arXiv 1509.02032v2).

Bibliographie

modifier
Article d'exposition
Manuels
Cours en ligne

Lien externe

modifier

Outil pédagogique pour la conversion d'une grammaire en forme normale de Chomsky

Voir aussi

modifier