Analyse Syntaxique

Voici un algorithme pour générer les ensembles premiers associés aux symboles d’une

grammaire.

Algorithme premier (Données G=(VT,VN,S,P) : grammaire ; Résultat premier(S) : ensemble

de symboles terminaux)

début

pour tout X, X VT, faire

premier(X) :={X}

ffaire

// 1ère étape, symboles terminaux

pour tout X, (X → Y1Y2 … Yn)P, faire

// 2ème étape, symboles non terminaux

premier(X) := premier(Y1)\{ε}

pour j, j{2, 3, … , n}, faire

si  i, 1≤i≤j-1, on a εpremier(Yi) alors

premier(X) := premier(X)  premier(Yj)\{ε}

fsi

ffaire

si  i, 1≤i≤n, on a εpremier(Yi) alors

premier(X) := premier(X)  {ε}

fsi

si (X → ε) P alors premier(X) := premier(X)  {ε} fsi

ffaire

retourner(premier(S))

fin

(1)

(2)

(3)

(4)

Appliquons cet algorithme sur les exemples suivants.

Exemple : Soit la grammaire des expressions arithmétiques, représentée par les règles de

production suivantes :

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | nb

On a alors :

premier(E) = premier(T)

premier(E’) = {+, ε}

premier(T) = premier(F)

premier(T’) = {*, ε }

premier(F) = {(, nb}

Exemple :

S → ABC

A → aA | ε

B → bB | cB | ε

C → de | da | dA

On a alors :

Analyse Syntaxique

24

premier(S) = premier(A)  premier(B)  premier(C) \ {ε}

premier(A) = {a, ε}

premier(B) = {b, c, ε}

premier(C) = {d}

D’où premier(S) = {a, b, c, d}

2.1.2. Calcul de suivant

Commençons par définir l’ensemble suivant associé à un symbole non-terminal.

Définition : L’ensemble suivant associé à un symbole non-terminal X est l'ensemble de tous les

symboles terminaux x qui peuvent apparaître immédiatement à droite de X dans une dérivation.

Voici un algorithme pour générer les ensembles suivants associés aux symboles d’une

grammaire.

Algorithme suivant (Données G=(VT,VN,S,P) : grammaire ; Résultat suivant(S) : ensemble

de symboles terminaux)

début

pour tout X, XVN, faire suivant(X):= {$} ffaire // $ est un marqueur de fin de chaîne

pour toute règle R, RP, faire

si R est de la forme A → αBβ, BVN, alors

suivant(B) := suivant(B)  premier(β)\{ε}

fsi

si R est de la forme A → αB, BVN, alors

suivant(B) := suivant(B)  suivant(A)

fsi

si R est de la forme A → αBβ, BVN, avec εpremier(β) alors

suivant(B) := suivant(B)  suivant(A)

(1)

(2)

(3)

fsi

ffaire

retourner(suivant (S))

fin

Exemple :

S → Sc | Ba

B → Pa | bPb | P | ε

P → dS

a, b, c suivant(S) car on a les dérivations suivantes :

S

dSa et S

bdSba

Sc, S

Exemple: Soit la grammaire des expressions arithmétiques, représentée par les règles de

production suivantes :

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | nb

On a alors :

Analyse Syntaxique

25

suivant(E) = { $, ) }

suivant(E’) = { $, ) }

suivant(T) = { +, ), $ }

suivant(T’) = { +, ), $ }

suivant(F) = { *, ), +$ }

Exemple :

S → aSb | cd | Sae

A → aAdB | ε

B → bb

premier suivant

S

A

B

a c

$ b a

aε

b

d

d

2.1.3. Construction de la Table d'Analyse LL(1)

Donnons, d’abord, une définition d’une table d'analyse LL(1).

Définition : Une table d'analyse LL(1) est un tableau M à deux dimensions qui indique pour

chaque symbole non-terminal A et chaque symbole terminal a ou symbole $ la règle de production

à appliquer.

Algorithme table d'analyse (Données G=(VT,VN,S,P) : grammaire ; Résultat M : tableau à

deux dimensions)

Début

(i) pour chaque règle de production A → α faire

(i.i) pour tout apremier(α) et α≠ε faire

M[A,a] := M[A,a]  { A → α }

ffaire

(i.ii) si εpremier(α) alors

pour chaque bsuivant(A) faire

M[A,b] := M[A,b]  { A → α }

ffaire

fsi

ffaire

(ii) pour chaque case M[A,a] faire

si M[A,a] = Ø alors afficher(‘erreur syntaxique’) fsi

ffaire

Fin

Exemple : Pour la grammaire des expressions arithmétique, représentée par les règles de

production suivantes :

Analyse Syntaxique

26

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | nb

En appliquant l’algorithme précédent, on obtient la table d'analyse LL(1) suivante :

nb

+

*

(

)

$

E E → TE’

E → TE’

E'

E’ → +TE’

E’ → ε E’ → ε

T T → FT’

T'

F

F → nb

T → FT’

T’ → ε

T’ → *FT’

T’ → ε T’ → ε

F → (E)

2.1.4. Analyse Syntaxique

Maintenant qu'on a la table d'analyse LL(1), comment l'utiliser pour déterminer si un mot m

donné appartient au langage, i.e., tel que S

m?

Pour répondre à cette question, on applique l’algorithme suivant Ceci se fait en utilisant une

pile.

Algorithme Analyse Syntaxique (Données m : mot, M : table d'analyse LL(1) ;

Résultat réponse : (accepter, refuser)

// initialisation de la pile. S étant la tête

// ps pointe sur la 1ère lettre de m

// autre≠accepter et autre≠refuser

Début

pile := [$, S]

ps :=adresse de la 1ère lettre de m

réponse=autre

répéter

Soit X le symbole en sommet de pile

Soit a la lettre pointée par ps

si X est un non terminal alors

si M[X,a] = X → Y1Y2 … Yn alors

dépiler(X)

Pour i=n bas 1 faire

empiler(Yi)

ffaire

retourner(X → Y1Y2 … Yn)

sinon

réponse=refuser

fsi

sinon

si X=$ alors

si a=$ alors réponse=accepter

sinon réponse=refuser

fsi

Analyse Syntaxique

27

sinon

si X=a alors

dépiler(X)

avancer(ps)

sinon

réponse=refuser

fsi

fsi

fsi

jusqu'à (réponse=accepter) ou (réponse=refuser)

Fin

Exemple : Soient le mot m=3+4*5 et la grammaire représentée par les règles de production

suivantes :

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | nb

En appliquant l’algorithme précédent, on obtient les traces suivantes :

pile

$ E

$ E'T

$ E'T'F

$ E'T'3

$ E'T'

$ E'

$ E'T+

$ E'T

$ E'T'F

$ E'T'4

$ E'T'

$ E'T'F*

$ E'T'F

$ E'T'5

$ E'T'

$ E'

$

Entrée

3+4*5$

3+4*5$

3+4*5$

3+4*5$

+4*5$

+4*5$

+4*5$

4*5$

4*5$

4*5$

*5$

*5$

5$

5$

$

$

Sortie

E → TE’

T → FT’

F → nb

T’ → ε

E’ → +TE’

T → FT’

F → nb

T’ → *FT’

F → nb

T’ → ε

E’ → ε

$ Le mot est accepté

Analyse Syntaxique

28

On obtient donc l'arbre syntaxique de la figure Fig. 1.

Fig. 1 Arbre syntaxique associé au mot m = 3+4*5

2.1.5. Les Grammaires LL(1)

Définissons, d’abord, une grammaire LL(1).

Définition : Une grammaire LL(1) est une grammaire pour laquelle la table d'analyse LL(1) n'a

aucune case ayant des entrées multiples, i.e., plusieurs règles de production associées à la même

case.

Le terme "LL(1)" signifie que l'on parcourt le mot à analyser de gauche à droite (L pour Left to

right scanning), que l'on utilise les dérivations gauches (L pour Leftmost derivation), et qu'un seul

(1) symbole de prévision est nécessaire à chaque étape nécessitant la prise d'une décision d'action

d'analyse.

L'algorithme d’analyse syntaxique, présenté dans le paragraphe suivant, ne peut être appliqué

qu’aux grammaires LL(1). En effet, si la table d'analyse LL(1) comporte des cases auxquelles

plusieurs règles de production sont associées, on ne pourra pas savoir quelle est règle de production

appliquer. Si la grammaire n’est pas LL(1), il faut essayer de la rendre LL(1).

Exemple : Nous avons déjà vu la grammaire représentée par les règles de production

suivantes :

S → aAb

A → cd | c

Nous avons premier(S)={a}, premier(A)={c}, suivant(S)={$} et suivant(A)={b}, ce qui donne

la table d'analyse LL(1) suivante :

Analyse Syntaxique

29

a

c

b d $

S →

aAb

S

A

A → cd

A → c

Il y a deux réductions pour la case M[A,c], donc ce n'est pas une grammaire LL(1). On ne peut

pas utiliser cette méthode d'analyse. En effet, on l'a déjà remarqué, pour pouvoir choisir entre la

production A → cd et la production A → c, il faut lire la lettre qui suit celle que l'on pointe (donc

deux symboles de prévision sont nécessaires).

Définition : Une grammaire est immédiatement récursive à gauche si elle contient un non-

terminal A tel qu'il existe une production A → Aα, où α est une séquence de symboles quelconques.

Définition : Une grammaire est récursive à gauche si elle contient un non-terminal A tel qu'il

existe une dérivation A

Aα, où α est une séquence de symboles quelconques.

Théorème : Une grammaire récursive à gauche n'est pas LL(1).

Exemple : Soit la grammaire représentée par les règles de production suivantes :

S → Aa | b

A → Ac | Sd | ε

Cette grammaire n’est pas LL(1), puisque, le symbole non-terminal S est récursif à gauche. En

effet, on a S → Aa → Sda . Mais il n'est pas immédiatement récursif à gauche.

Exemple : Soit la grammaire représentée par les règles de production suivantes :

S → aTbbbb

T → Tb | ε

Cette grammaire n’est pas LL(1), puisque, le symbole non-terminal T est immédiatement

récursif à gauche. Donc, il est récursif.

Exemple : Cette grammaire contient des récursivités à gauche immédiates donc elle n’est pas

LL(1).

S → ScA | B

A → Aa | ε

B → Bb | d | ε

2.2. Analyse Ascendante

Définissons, d’abord, une analyse ascendante.

Définition : Une analyse ascendante construire consiste à construire l'AD du bas vers le haut.

Le haut étant la racine, i.e., l'axiome de la grammaire du langage. Le bas étant les feuilles, i.e., les

unités lexicales.

Une technique d’analyse ascendante consiste à suivre un processus de décalage-réduction. En

suivant ce processus, on ne peut réaliser que deux types opérations :

Analyse Syntaxique

30

(i) L’opération de décalage, en anglais shift : Décaler d'une lettre le pointeur sur le mot à

analyser

(ii) L’opération de réduction, en anglais reduce : Réduire une séquence de symboles

quelconques par un symbole non-terminal en utilisant une des règles de production.

Exemple : Soient grammaire représentée par la rège S → aSbS

le mot

m=aacbaacbcbcbcbacbc. Est-ce que m est un mot du langage défini par cette grammaire?

Répondons à cette question en faisant une analyse ascendante :

| c et

1.

on ne peut rien réduire, donc on décale

2.

on ne peut rien réduire, donc on décale

3.

on ne peut rien réduire, donc on décale

4.

on peut réduire par S → c

5.

on ne peut rien réduire, donc on décale

...

6.

on peut utiliser S → c

7.

on ne peut rien réduire, donc on décale

Analyse Syntaxique

31

8.

on ne peut rien réduire, donc on décale

9.

On peut utiliser S → c

10.

On peut utiliser S → aSbS

11.

décalage

12.

décalage

13.

réduction par S → c

14.

réduction par S → aSbS

15.

réduction par S → aSbS

Analyse Syntaxique

32

16.

décalage

17.

décalage

18.

réduction par S → c

19.

réduction par S → aSbS

20.

décalage

21.

décalage

22.

décalage

23.

réduction par S → c

Analyse Syntaxique

33

24.

décalage

25.

décalage

26.

réduction par S → c

27.

réduction par S → aSbS

28.

réduction par S → aSbS

29.

Terminé : Le mot a été réduit à l’axiome de la grammaire. Donc, c’est un mot du langage.

Les opérations réalisées ci-dessus peuvent être résumées par l'arbre suivant :

Analyse Syntaxique

34

Fig. 2 Analyse ascendante du mot m=aacbaacbcbcbcbacbc

Le processus de décalage-réduction peut être réalisé en utilisant une table, appelée table

d'analyse LR. Cette table nous indique, pour chaque symbole de séquence de symboles courantes,

si on doit faire un décalage ou bien si on doit faire une réduction.

Dans ce cours, nous ne n’aborderons pas le problème de construction de cette table.

Définition : Une table d'analyse LR, notée M, associée à une grammaire G = (VT,VN,S,P), est

une table qui représente une espèce d'automate, appelé automate à pile. Cette table est définie

comme suit :

(i) Une ligne i représente l’état i de l’automate,

(ii) Une colonne a représente un élément de VTVN,

(iii) Une case M[i,a] est définie comme suit :

dj. Dans ce cas, on fait une opération de décalage : On empile le symbole a

dans une pile associée à l'automate et on passe de l’état i l’état j.

M[i,a] =

rp. Dans ce cas, on fait une opération de réduction : On remplace la

séquence de symboles en sommet de pile associée à l'automate, qui

correspond à la partie droite de la règle numéro p, par le symbole non-

terminal de la partie gauche de cette règle. Puis, on passe de l’état i

l’état j.

Exemple : Avec la grammaire des expressions arithmétiques, représentée par les règles de

production suivantes :

E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | nb

Analyse Syntaxique

35

on obtient la table d'analyse LR suivante :

nb

d5

d5

d5

d5

0

1

2

3

4

5

6

7

8

9

10

11

+ *

(

d

)

$

E

T F

1

2

3

4

d

r

4

r

4

4

d

r

r

d

r

7

r

4

6

2

4

r

6

6

d

r

7

r

3

r

5

6

1

3

5

8

2

3

9

3

1

0

A

CC

r

r

r

r

2

4

2

4

d

r

r

6

6

d

d

d

r

r

r

11

1

3

5

r

r

r

1

3

5

Exemple : Faisons analyse ascendante du mot m = 3 + *4 en utilisant la table d'analyse LR

précédente.

Analyse Syntaxique

36

Fig. 3 Analyse LR du mot m = 3 + *4$

Exemple : Faisons analyse ascendante du mot m = 3+4*2 en utilisant la table d'analyse LR

précédente.

²²

Fig. 4 Analyse LR du mot m = 3+4*2

Analyse Syntaxique

37

Fig. 5 Arbre de dérivation du mot m = 3+4*2

*