Grammaires

Sommaire du document

Symbole terminal et non terminal

Nous évoquerons souvent les notions de « terminal » et de « non terminal », qui se définissent de la manière suivante :

• symboles terminaux : chaînes de caractères issues du langage (les mots).
• symboles non terminaux : ce sont les noms que nous donnons aux règles de productions pour les reconnaître. Ces symboles n'appartiennent pas au langage défini par la grammaire.

Conventions d'écriture

Au long des exemples suivants, nous tenterons de respecter les convensions suivantes^[1] :

• les symboles non terminaux sont représentés par des lettres majuscules du début de l'alphabet (A, B, C, ...). Ils peuvent être représentés par des mots composés de minuscules, et dans ce cas nous les entourerons par les signes plus petit et plus grand de cette manière : <non-terminal>.
• les symboles terminaux sont représentés par des lettres minuscules de la fin de l'alphabet (... x, y, z).
• les suites de symboles grammaticaux sont représentés par des lettres du début de l'alphabet grec (α (alpha), β (beta), γ (gamma), ...).
• la chaîne vide est représentés par la lettre grecque ε (epsilon).

Grammaires récursive à gauche

Une grammaire est récursive à gauche si un symbole non terminal A se dérive strictement en une proto-phrase^[2] commençant par A ⇒⁺ Aα tel que α ne commence pas par A.

Structure des grammaires

Une grammaire est composée de quatre éléments :

• V_N : l'ensemble fini des symboles non-terminaux, que nous retrouvons parfois simplement sous la lettre N.
• V_T : l'ensemble fini des symboles terminaux (le vocabulaire terminal)^[3]. Cet ensemble V_T est disjoint de V_N.
• P : l'ensemble des productions. Il s'agit de l'ensemble des règles grammaticales.
• S : le symbole de départ (S ∈ V_N).

Classes de grammaires selon Chomsky^[5]

Grammaires libres^[6] (Type 0)

Les productions de la grammaire de type 0 sont de la forme : α → β avec α ∈ {V_N ∪ V_T}⁺ et β ∈ {V_N ∪ V_T}^*

Ces grammaires engendrent des « langages récursivement énumérables » (en anglais, “recursively enumerable languages”), acceptés par une machine de Turing^[8].

Grammaires contextuelles (Type 1)

Les productions de la grammaire contextuelle sont de la forme : αΑβ → αγβ avec Α ∈ N, α, β ∈ (N ∪ Σ)^* etγ ∈ (N ∪ Σ)⁺

Nous avons un élément non terminal (Α) qui dépend du contexte constitué par les mots qui l'encadrent (α et β).

Nous pouvons aussi accepter dans les grammaires de type 1 les productions de la forme : α → β avec α ∈ {V_N ∪ V_T}⁺ et β ∈ {V_N ∪ V_T}^* et |α| ≤ |β|, car ces grammaires produisent des langages contextuels.

Grammaires non contextuelles^[9] (Type 2)

Les productions de la grammaire non contextuelle sont de la forme : A → α avec A ∈ V_N et α ∈ {V_N ∪ V_T}^*

Chomsky^[5] a utilisé le terme “non contextuel” (en français, « context-free ») par opposition aux “contextuel” (en français, « context-sensitive ») pour lesquelles l'application d'une règle est soumise à des conditions.

Un langage « non contextuel »^[10] peut être représenté par un automate à pile non déterministe. Pour prouver qu'un langage n'est pas « non contextuel »^[10], nous devons donc prouver qu'il n'est pas possible de construire son automate à pile.

Grammaires régulières^[12] (Type 3)

Les productions de la grammaire de type régulière sont de la forme :
A → α | A → αB | A → ε (grammaire linéaire à droite^[13]) ou A → α | A → Bα | A → ε (grammaire linéaire à gauche^[14])
avec A ∈ V_N et α ∈ {V_N ∪ V_T}^*

Un langage est régulier ssi un programme peut le lire (de gauche à droite) en ne mémorisant qu'une information finie.

Nous pouvons définir un langage régulier de la manière suivante :

• Soit Σ l'alphabet (fini) du langage L
  • ∅ est un langage régulier;
  • {ε} est un langage régulier;
  • ∀ a ∈ Σ, {a} est un langage régulier (langages de mots à une seule lettre);
• si L₁ et L₂ sont réguliers, alors
  • L₁L₂ = {W₁W₂ | W₁ ∈ L₁, W₂ ∈ L₂} est régulier
  • L₁ ∪ L₂ est régulier
• L* = {ε} ∪ {wwww...w | W ∈ L} est régulier

Pour prouver qu'un langage est régulier, nous pouvons soit donner l'expression rationelle qui correspond, soit donner son AFN [automate fini non déterministe].

Pour prouver qu'un langage n'est pas régulier, nous pouvons soit montrer que nous ne pouvons construire son AFN, soit utiliser le lemme de pompage^[17].

Tout langage fini est un langage régulier. Un langage non fini peut toutefois être un langage régulier si son automate est fini et contient un cycle.

Tout langage régulier est un langage « non contextuel »^[10].

Certaines grammaires non régulières peuvent tout de même engendrer des langages réguliers.

Grammaires LL_(k)

• Le premier L signifie “Left to right scanning” (en français, « parcours de la gauche vers la droite »)
• Le second L signifie “Leftmost derivation” (en français, « dérivation gauche »)
• La lettre k est remplacé par un nombre qui signifie que le choix de la bonne expansion doit pouvoir se faire sur la base des k prochains symboles à lire.

Une grammaire récursive à gauche n'est jamais une grammaire LL_(k).

Grammaires LL₍₁₎

Les grammaires LL(1) sont généralement suffisantes pour la construction de langages de programmation, pour peu qu'ils respectent les conditions qui suivent.

Une grammaire G est LL(1) ssi pour toute paire de productions distinctes Α → α | β de G :

• Il n'existe aucun symbole terminal a tel que α et β dérivent tous deux des chaînes commençant par a.
• Les chaînes α et β ne peuvent dériver toutes deux la chaîne vide.
• Si β ⇒* ε, alors α ne dérive aucune chaîne commençant par un terminal qui est dans SUIVANT(A).
  De même, si α ⇒* ε, alors β ne dérive aucune chaîne commençant par un terminal qui est dans SUIVANT(A).

Comment rendre une grammaire LL₍₁₎ ?

• Eliminer la récursivité gauche.
  Par exemple, A ::= Aα | β devient A ::= βA', A' ::= αA' | ε (nous avons alors une récursivité droite)
• Factoriser les parties communes (nous postposons le choix en groupant les parties communes).
  Par exemple, I ::= if E then I | if E then I else I devient I ::= if E then I C et C ::= ε | else I.

Grammaires ambiguës

Si nous pouvons générer plus d'un arbre syntaxique pour une même chaîne du langage, nous pouvons dire que la grammaire est ambiguë.

Nous pouvons être confrontés à des grammaires ambiguës quand par exemple α et β sont ε-productifs.

Nous pouvons généralement résoudre engendrés par une grammaire ambiguë en définissant des règles de précédence ou d'associativité.

Grammaires LR_(k)

• Le premier L signifie “Left to right scanning” (en français, « parcours de la gauche vers la droite »)
• Le second R signifie “Rightmost derivation” (en français, « dérivation droite »)
• La lettre k est remplacé par un nombre qui signifie que le choix de la bonne expansion doit pouvoir se faire sur la base des k symboles anticipés et non consommés.

Un analyseur LR_(k) effecute une analyse ascendante sur les grammaires non contextuelles.

Nous retrouvons souvent simplement le terme LR, pour lequel LR₍₁₎ est sous-entendu.

Grammaires LR₍₀₎

Un analyseur LR_(k) n'effectue aucune anticipation pour décider quelle réduction il doit entreprendre. Si nous constatons que la table des actions contient plus d'une action dans une même cellule, nous avons la certitude que lq grammaire n'est pas LR₍₀₎, et nous devons alors augmenter le nombre de symboles de prévision.

Grammaires SLR

Les analyseurs SLR₍₀₎ est utilise un autre algorithme d'analyse descendante, version renforcée de LR₍₀₎.

Afin de résoudre les conflits LR₍₀₎, nous devons alors consulter SUIVANT(A), où A est le côté gauche de la règle à réduire.

Grammaires LALR

Un automate à pile permet d'analyser une grammaire LALR [“Look-Ahead Left Recursive”^[21]]. Un exemple célèbre d'analyseur syntaxique LALR est YACC.

Grammaires attribuées

Les grammaires attribuées sont des grammaires non contextuelles étendues avec des attributs (typage, table des symboles, etc.) associés à des valeurs, et définis par des règles d'attribution associées aux productions (les règles de la grammaire).

Lemme de pompage

Si le nombre d'états de l'automate est plus petit que la chaîne, la chaîne contient une boucle qui peut être répetée. Nous pouvons alors dire que la partie de la boucle est « pompée ».

Lemme de pompage des langages réguliers^[12]

Nous utiliserons par la suite la décomposition que nous permet le lemme de pompage pour prouver par l'absurde qu'un langage n'est pas régulier.

Si le langage est régulier, nous pouvons le décomposer selon la formule qui suit.

• Soit L un langage sur un alphabet Σ.
  Si L est régulier alors
  ∃ p ∈ N : ∀ w ∈ L, |w| ≥ p ⇒ ∃ x,y,z Σ* :

  1. w = xyz
  2. |y| ≥ 1
  3. |xy| ≤ p
  4. ∀ n ∈ N, x yⁿ z ∈ L

Le lemme de pompage indique que nous pouvons répéter une partie centrale du mot, et que le mot ainsi produit appartient toujours au langage décrit : ∀ n ≥ 0, xyⁿz ∈ L

Notre automate est dans son état initial (Sinit). Nous pouvons accepter une séquence de caractères (partie x) qui nous fait passer d'état en état jusqu'au moment où l'acceptation du caractère lu nous placera dans le premier état de la boucle (partie y). Ensuite nous pouvons passer par un certain nombre d'états (partie z).

Exemple : le langage qui comprend les nombres pairs en binaire (0, 10, 100, 110, etc.).

Nous représentons donc les nombres pairs en binaire par un 0, ou un 1 suivi d'un certain nombre de 0 ou de 1, et enfin un 0 pour terminer.

L'expression rationnelle qui correspond à ce langage est 0|1(0|1)*0, ce qui correspond parfaitement au lemme de pompage (x y* z) avec :

• x = 1
• y = (0|1)*
• z = 0

Lemme de pompage des langages non contextuels

• Soit L un langage sur un alphabet Σ.
  Si L est « non contextuel »^[10] alors
  ∃ p ∈ N : ∀ s ∈ L, |s| ≥ p ⇒ ∃ x,y,z,v,w Σ* :

  1. s = xvywz
  2. |vw| ≥ 1
  3. |vyw| ≤ p
  4. ∀ n ∈ N, x vⁿ y wⁿ z ∈ L

ε-productif

Nous pouvons parler de symbole non terminal ε-productif si ce non terminal A ∈ V_N et que A ⇒ *ε

Table des analyseurs et des langages

Notes

1. ↑ Conventions d'écriture : Ce sont les convensions utilisées dans les ouvrages qui ont servi de référence à la rédaction de ce document, mais nous pouvons trouver d'autres notations dans la litérature.
   
   
2. ↑ proto-phrase : Nous parlons de « proto-phrase » pour indiquer que sa construction n'est pas achevée.
   
   
3. ↑ V_T : Nous utiliserons V_T et non Σ, car nous sommes dans le cas d'une analyse syntaxique, et l'analyse syntaxique se base sur le résultat de l'analyse lexicale de Σ, Σ représentant l'ensemble fini qui correspond à « l'alphabet » du langage analysé.
   
   
4. ↑^a,b MIT : Massachusetts Institute of Technology
   
   
5. ↑^a,b Noam Chomsky : Linguiste et philosophe américain, professeur au MIT [Massachusetts Institute of Technology]
   
   
6. ↑ Grammaires libres : Nous pouvons aussi retrouver les grammaires libres sous l'appellation « grammaires générales », ou “unrestricted grammars” et “phrase structure grammar” en anglais..
   
   
7. ↑ langages récursivement énumérables : correspond à “recursively enumerable languages » en anglais
   
   
8. ↑ Alan Mathison Turing : Mathématicien britanique, inventeur des concepts de programmation et de programme.
   
   
9. ↑ Grammaires non contextuelles : Nous pouvons aussi retrouver les grammaires non contextuelles sous l'appellation « grammaires algébriques », ou “context-free grammar” et “phrase structure grammar” en anglais..
   
   
10. ↑^a,b,c,d,e non contextuel : correspond à « context-free” en français
    
    
11. ↑ contextuel : correspond à « context-sensitive” en français
    
    
12. ↑^a,b Régulier : Le qualificatif « régulier » est souvent employé comme traduction textuelle de l'anglais “regular”, mais nous devrions bien employer « rationnel ». Cependant, nous utiliserons pour l'instant le terme « régulier » car c'est de cette manière qu'il figure dans les ouvrages de référence.
    
    
13. ↑ Grammaire linéaire à droite : grammaire dont chaque membre à droite de la flèche finit par un non terminal.
    
    
14. ↑ Grammaire linéaire à gauche : grammaire dont chaque membre à droite de la flèche commence par un non terminal.
    
    
15. ↑^a,b ssi : si et seulement si
    
    
16. ↑^a,b AFN : automate fini non déterministe
    
    
17. ↑ Non régulier & lemme de pompage : Nous utiliserons le lemme de pompage pour prouver que notre langage n'est pas régulier, mais nous ne pouvons pas utiliser le lemme de pompage pour prouver qu'un langage est régulier.
    
    
18. ↑^a,b,c,d Left to right scanning : correspond à « parcours de la gauche vers la droite” en français
    
    
19. ↑ Simple Left to right scanning with Rightmost derivation : correspond à « simple parcours de la gauche vers la droite avec dérivation droite” en français
    
    
20. ↑ SLR₍₀₎ : “Simple Left to right scanning with Rightmost derivation” (en français, « simple parcours de la gauche vers la droite avec dérivation droite »)
    
    
21. ↑^a,b Look-Ahead Left Recursive : correspond à « analyseurs syntaxiques LR avec anticipation” en français
    
    
22. ↑ LALR : “Look-Ahead Left Recursive” (en français, « analyseurs syntaxiques LR avec anticipation »)
    
    
23. ↑ Yet Another Compiler Compiler : correspond à « Encore un autre compilateur de compilateur” en français
    
    
24. ↑ YACC : “Yet Another Compiler Compiler” (en français, « Encore un autre compilateur de compilateur »)
    
    

Références

1. Compilateurs : Dick Grune, Henry E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen, Cours et exercices corrigés
2. Compilateurs : A. Aho, M. Lam, R. Sethi, J. Ulman, Principes; techniques et outils
3. IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (Janvier 2010)
4. Structures syntaxiques : Noam Chomsky
5. Three models for the description of language : Noam Chomsky, IRE Transactions on Information Theory (Septembre 1956)
6. Automata theory : Wikipedia, formal languages and formal grammars (version 06/05/10)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Liste des images

1. Hiérarchie des grammaires selon Chomsky _{(Référence : infobrol)}
2. Lemme de pompage _{(Référence : infobrol)}

Structure du document