Théorie des Langages et Compilation

Cours 2 : Les Grammaires et la

Classification de Chomsky

Dr MAMBE
 Plan du cours

I. Grammaire
II. Langage engendré par une grammaire
III. Classification - Hiérarchie de Chomsky

2
 Introduction
Au sens littéraire du terme, les grammaires désignent
pour les langues naturelles, un ensemble de règles
syntaxiques conventionnelles qui déterminent un emploi
correct de la langue parlée et écrite. Le même concept
s’applique aussi pour la théorie des langages, en suivant
les règles de production d’une grammaire on peut
engendrer un langage.

3
 Grammaire
Définition

Définition

Une grammaire est un ensemble de règles de production qui sont utilisées pour
engendrer un langage.

Exemple

Dans la grammaire de la langue française on peut formuler une phrase en

respectant la séquence suivante : ‘Sujet’ ‘Verbe’ ‘COD’. On peut formuler un
nombre bien défini des phrases en respectant les règles de production suivantes :
PHRASE----------------SUJET VERBE CO
SUJET----------------je l il
VERBE----------------lis l conduit
COD---------------DETERMINANT NOM
DETERMINANT---------------un l la
NOM--------------- livre l voiture

4
 Grammaire
Définition

Exemple: A partir de ces règles syntaxiques on construit 24=16 phrases

syntaxiquement correct mais pas forcément sémantiquement correctes.

PHRASE----------------SUJET VERBE COD

SUJET----------------je l il
VERBE----------------lis l conduit
COD---------------DETERMINANT NOM
DETERMINANT---------------un l la
NOM--------------- livre l voiture

Parmi lesquelles, on cite les deux phrases suivantes :

SUJET----- Je SUJET---- il
PHRASE -- Je lis un livre
VERBE----lis VERBE---- conduit
et DETERMINANT---- la PHRASE --- Il conduit la voiture
DETERMINANT--- un
PHRASE ---Je conduit la livre
NOM----- livre NOM---- voiture

5
 Grammaire
Définition formelle

Définition formelle:
Une grammaire G est un quadruplet (N, T, P, S) tels que :

N : ensemble fini de symboles non terminaux.

T : ensemble fini de symboles terminaux.
N ∩ T=∅
S : symbole non terminal de départ (axiome).
P : ensemble fini de règles de production de la forme
𝛼𝛼 - 𝛽𝛽 tel que 𝛼𝛼 ∊ (N ∪ T)+ - T+ et 𝛽𝛽 ∊ (N ∪ T)*
Exemple:
Dans l’exemple précédant, la grammaire est définie comme suit :
• N= {PHRASE, SUJET, VERBE, COD, DETERMINANT}
• T= {je, il, lire, conduire, un, la, livre, voiture}
• S= {PHRASE}
• P= {PHRASE SUJET VERBE COD, CODDETERMINANT NOM, SUJETje l il,
VERBElis l conduit, DETERMINANTun l la, NOM  livre l voiture }

6
 Grammaire
Définition formelle

Notations:

Dans les règles formelles d’une grammaire :

 Les symboles de l’alphabet sont écrits en minuscule et appelés les symboles des
terminaux.
 Les autres symboles (sauf le mot vide) sont écrits en majuscule et appelés les
symboles non terminaux.
 La génération des mots commence toujours à partir d’un symbole non terminal
appelé l’axiome (dans notre exemple l’axiome = PHRASE).

7
 Grammaire
Dérivation

 Dérivation directe
Un mot w' dérive directement d’un mot w qu’on note w => w' si une règle de G est
appliquée une fois pour passer de w à w’. C’est-à-dire : il existe une règle 𝛼𝛼 ->𝛽𝛽
dans P telle que : w=u𝛼𝛼v et w’=u𝛽𝛽v avec avec u, v ∊ (N∪T)*.

 Exemple
Soit la grammaire: G = ({S},{a, b}, {S -> aSb, S->ε }, S) , nous avons :
1. aSb dérive directement de S et on écrit : S => aSb car il existe une règle
S->aSb ∊ P telle que : w = S et w' = aSb avec u=v=ε ∊ (N∪T)*

1. ab dérive directement de aSb et on écrit

aSb => ab car il existe une règle S->ε telle que :
w = aSb et w' = ab avec u=a et v=b

8
 Grammaire
Dérivation

 Dérivation au sens général

Un mot w' dérive directement d’un mot w qu’on note w -> w’, si on applique n fois
les règles de G pour passer de w vers w' tel que n ≥ 0 :

C’est-à-dire : il existe une séquence de chaînes w1, w2,…, wn telle que :

w= w1 , w'= wn et wi => wi+1 pour ∀ 1≤ i < n

 Exemple
Soit la grammaire: G = ({S},{a, b}, {S -> aSb, S->ε }, S) , nous avons :
S=> aSb => ab, c’est une dérivation de longueur 2

9
 Grammaire
Dérivation
 Définition

Un langage engendré par une grammaire G= (N, T, P, S) est l’ensemble des mots obtenus
en appliquant des séquences de dérivations à partir de l’axiome S. on note :
L(G)= w ∊ T* / S ⇒*G w
 Exemples
1. Pour la grammaire G = ({A},{a, b}, {A -> aSb, A->ε }, A) , nous avons :
- Mot minimal: ε
- La forme générale : L(G)={ an bn / n ≥ 0 }
S=>aSb=>aaSbb => aaaSbbb…….=> an ε bn => an bn
 Remarque
Une grammaire définit un seul langage par contre un même langage peut être
engendré par plusieurs grammaires différentes.

10
 Langage engendré par une grammaire
Grammaires équivalentes

 Définition
Deux grammaires sont équivalentes si elles engendrent le même langage.
G équivalente à G’ ⇔ L(G) = L(G’)
 Exemple

1. G = ({S, A, B},{a, b},{S ->aS/ABb, A ->Aa/a, B ->b}, S)

S->aS->aABb->aabb ,
S->ABb->AaBb->Aabb->aabb
S->ABb->AaBb->Aabb->Aaabb->Aaaabb>aaaabb
2. G’ = ({S, A, B},{a, b},{S ->aS/aA, A ->aA/bB, B->b}, S)
S->aS->aaS->aaaS->aaaaA->aaaabB-> aaaabb
S->aS->aaA->aabB->aabb
On trouve que L(G)=L(G’) = {akb2 / k ≥1}

11
Langage engendré par une grammaire
Grammaires équivalentes

 Définition
Deux grammaires sont équivalentes si elles engendrent le même langage.
G équivalente à G’ ⇔ L(G) = L(G’)
 Exemple

1. G = ({S, A, B},{a, b},{S ->aS/ABb, A ->Aa/a, B ->b}, S)

S->aS->aABb->aabb ,
S->ABb->AaBb->Aabb->aabb
S->ABb->AaBb->Aabb->Aaabb->Aaaabb>aaaabb
2. G’ = ({S, A, B},{a, b},{S ->aS/aA, A ->aA/bB, B->b}, S)
S->aS->aaS->aaaS->aaaaA->aaaabB-> aaaabb
S->aS->aaA->aabB->aabb
On trouve que L(G)=L(G’) = {akb2 / k ≥1}

12
 Classification - Hiérarchie de Chomsky
Classification des grammaires

Hiérarchie de Chomsky

Selon la classification de Chomsky, les grammaires sont regroupées en quatre

types en fonction de la forme de leurs règles de production.

Soit une grammaire G = (N, T, P, S)

 Grammaire Syntagmatique – Type 0

 Grammaire Monotone- Type 1
 Grammaire Algébrique (hors contexte)- Type 2
 Grammaire Régulière- Type 3

13
 Classification - Hiérarchie de Chomsky
Grammaires Type 0

Grammaire Syntagmatique – Type 0

G est dite grammaire de type 0 dite aussi grammaire sans restriction
(grammaire générale) : si toute ses règles sont de la forme générale suivante :

14
 Classification - Hiérarchie de Chomsky
Grammaires Type 1

Grammaire Monotone – Type 1

G est dite grammaire de type 1 dite aussi grammaire monotone : si toutes ses
règles sont de la forme :

15
 Classification - Hiérarchie de Chomsky
Grammaires Type 2

Grammaire algébrique (hors contexte)– Type 2

G est dite grammaire de type 2 dite aussi grammaire algébrique (hors contexte) :
si toutes ses règles sont de la forme.

16
 Classification - Hiérarchie de Chomsky
Grammaires Type 2
Arbre de dérivation - Arbre Syntaxique
 Définition

Dans le cas d’une grammaire hors-contexte G, on peut représenter la

dérivation d’une phrase de L(G) à partir de l’axiome à l’aide d’un arbre
syntaxique (ou arbre d’analyse ou arbre de dérivation). Cette représentation
fait abstraction de l’ordre d’application des règles de la grammaire et aide à
la compréhension de la syntaxe de la phrase considérée. On appelle arbre
de dérivation (ou arbre syntaxique), tout arbre tel que :

• La racine est le symbole de départ.

• Les feuilles sont des symboles terminaux ou ε.
• Les nœuds sont des non-terminaux.

Pour déterminer si une chaîne terminale appartient au langage

engendré par une grammaire, on établit un arbre de dérivation dont la
racine est l’axiome, les feuilles sont des terminaux formant la chaîne
donnée et les nœuds sont des variables décrivant les régles utilisées.
17
 Classification - Hiérarchie de Chomsky
Grammaires Type 2
Arbre de dérivation - Arbre Syntaxique
 Exemple
Soit la grammaire suivante : T={a, b, 0, 1, +, *, ( , )}, N={E, I} avec E est
l’axiome, et les règles de production suivantes :
E → I / E∗E / E+E / (E)
I → a / b / Ia / Ib / I0 / I1

La figure ci-coté représente l’arbre de dérivation de

l’expression : a ∗ (a + b00). La dérivation la plus à gauche et
la plus à droite fournissent le même arbre.

E→E∗E
→ I ∗E → a ∗E
→ a ∗ (E)
→ a ∗ (E+E)
→ a ∗ (I+E)
→ a ∗ (a+E) → a ∗ (a+I) → a ∗ (a+I0) → a ∗ (a+I00) → a ∗ (a+b00)
18
 Classification - Hiérarchie de Chomsky
Grammaires Type 2
Arbre de dérivation - Arbre Syntaxique
 Exemple

Soit la grammaire suivante : T={a, b, 0, 1, +, *, ( , )}, N={E, I} avec E est

l’axiome, et les règles de production suivantes :
E → I / E∗E / E+E / (E)
I → a / b / Ia / Ib / I0 / I1

 Dérivation la plus à gauche de : a*(b+a0)

E ⇒ E∗E ⇒ I∗E ⇒ a∗E ⇒ a∗(E) ⇒ a∗(E+E) ⇒ a∗(I+E) ⇒ a∗(b+E) ⇒ a∗(b+I)

⇒a∗(b+I0) ⇒ a∗(b+a0)

 Dérivation la plus à droite de : a*(b+a0)

E ⇒ E∗E ⇒ E∗(E) ⇒ E∗(E+E) ⇒ E∗(E+I) ⇒ E∗(E+I0) ⇒ E∗(E+a0) ⇒E ∗(I +a0) ⇒ E

∗(b+a0) ⇒ I ∗(b+a0) ⇒ a∗(b+a0)
19
 Classification - Hiérarchie de Chomsky
Grammaires Type 3

 Grammaire régulière- Type 3

G est dite grammaire de type 3 dite aussi grammaire régulière :si

elle est régulière à gauche ou bien à droite.

20
 Classification - Hiérarchie de Chomsky
Grammaires Type 3
 Grammaire Régulière - Type 3

21
Classification - Hiérarchie de Chomsky
Classification des grammaires

22
 Classification - Hiérarchie de Chomsky
Classification des langages

La classification des grammaires va permettre de classer les langages selon le

type maximum de la grammaire qui l’engendre (puisqu’un langage peut être
engendré par plusieurs grammaires de types différents). Il y a une relation
d’inclusion stricte entre les 4 types des langages.

On dit qu’un langage est de type i s’il est engendré par une grammaire de type i et
pas par une grammaire d’un type supérieur.

23
 Classification - Hiérarchie de Chomsky
Classification des langages

 Exemples

• Langage de Type 0
L={ac, acb, ca…}
G = ⟨{S}, {a, b, c}, {S → aS | Sb | c, aSb → Sa | bS}, S⟩

• Langages Contextuel - Type 1 :

L={anbncn | n≥0}
G = ⟨{S,B,W,X},{a, b, c},{ S → abc, S → aSBc, cB → WB,WB → WX,
WX → BX, BX → BC, bB→ bb}, S⟩

24
Classification - Hiérarchie de Chomsky
Classification des langages

 Exemples

• Langages hors Contexte- Type 2:

L = {anbn | n ≥ 0}
G = ⟨{S}, {a, b}, {S → aSb|ε}, S⟩

• Langages Rationnel ( Régulier)- Type 3

L ={m ∈ {a, b}∗}
G = {{S}, {a, b}, {S → aS | bS | ε}, S }

25
 Exercice

Exercice 1:

On considère la grammaire G = (T, N, S, R) où

T = { b, c }
N={S}
R = { S → bS | cc }

1. Quel est le type de G.

2. Déterminer L(G).

Exercice 2:

Construire une grammaire pour le langage L = {abna/n ∈ N}.

26