Grammaires

Grammaires libres6 (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⁸.

Table des matières Haut

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.

Table des matières Haut

Grammaires non contextuelles9 (Type 2)

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

Chomsky⁵ 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 »¹⁰ peut être représenté par un automate à pile non déterministe. Pour prouver qu'un langage n'est pas « non contextuel »¹⁰, nous devons donc prouver qu'il n'est pas possible de construire son automate à pile.

Table des matières Haut

Grammaires régulières12 (Type 3)

Les productions de la grammaire de type régulière sont de la forme :
A → α | A → αB | A → ε (grammaire linéaire à droite¹³) ou A → α | A → Bα | A → ε (grammaire linéaire à gauche¹⁴)
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¹⁷.

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 »¹⁰.

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

Table des matières Haut

Grammaires LL(1)

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(1) ?

• 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.

Table des matières Haut

Lemme de pompage des langages réguliers12

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 »¹⁰ 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

Table des matières Haut