Universit de Genve

Facult des Sciences Juridiques, Economiques et de Gestion de Genve

Classes : 3LFIAG

TD2 : ANALYSE SYNTAXIQUE

MTHODE DANALYSE DESCENDANTE

Exercice 1:

1- La grammaire est non ambigu, en effet pour n'importe quel mot w L(G) il y a un unique arbre
syntaxique, ceci est d au fait qu'on a tabli une certaine rgle de priorit et de prcdence pour garantir
l'unicit de l'arbre syntaxique de chaque mot et par consquence la non ambigut de la grammaire.

Priorit * est plus associatif gauche

()

2- Principe de l'algorithme: partir de G (V, , R, S) on obtient M= (K, , , , s, F):

Les 3 rgles du cours:

I. (s, , ) (p, S)
II. (p, , A) (p, ) avec A R cd si A est au sommet de la pile on peut le remplacer par .
III. (p, , ) (p, ) cd si le sommet de la pile concide avec le symbole lire de la chaine, on
le

Consomme et on le dpile.

Application des 3 rgles sur l'exemple de l'exercice:

I. 1-(s, , ) (p, E) III. 9-(p, +, +) (p, )

II. 2-(p, , E) (p, E+T) 10-(p, (, ( ) (p, )
3-(p, , E) (p, T) 11-(p,),)) (p, )
4-(p, , T) (p, T*F) 12-(p, *, *) (p, )
5-(p, , T) (p, F) 13-(p, x, x) (p, )
6-(p, , F) (p, (E)) 14-(p, 1, 1) (p, )
7-(p, , F) (p, x1) 15-(p, 2, 2) (p, )
8-(p, , F) (p, x2)

1
 K={s, p} ; = V ; s=tat initial ; F= {p}

3- le sommet de la pile

Etat Pile Restant de la chaine Transition Rgle de

lire utilise grammaire
S $ x1+x2*x1$ 1
P $E x1+x2*x1$ 2 E E+T
P $T+E x1+x2*x1$ 3 E T
P $T+T x1+x2*x1$ 5 T F
P $T+F x1+x2*x1$ 7 F x1
P $T+1x x1+x2*x1$ 13 Dpiler
P $T+1 1+x2*x1$ 14 Dpiler
P $T+ +x2*x1$ 9 Dpiler
P $T x2*x1$ 4 T T*F
P $F * T x2*x1$ 5 T F
P $F * F x2*x1$ 8 F x2
P $F * 2x x2*x1$ 13 Dpiler
P $F * 2 2*x1$ 15 Dpiler
P $F * *x1$ 12 Dpiler
P $F x1$ 7 F x1
P $1x x1$ 13 Dpiler
P $1 1$ 14 Dpiler
P $ $

4- M1 est non dterministe ( trouver une configuration ou on peut appliquer plus qu'une transition):
*A la configuration de l'tape 2 il ya deux transitions applicables (tx 2 et tx3)
*De mme l'tape 4 (tx 4 et tx 5 applicables).

5-
{ E E+T sont deux rgles rcursives gauche ( A*A / un ensemble de
terminaux)

T T*F

6- G'(V', ', R', E) 7- 1. (s, , ) (p, E)

V'={+,*,(,),x,1,2,,T,T',E,E',F,A} 2. (p, , E) (p, TE')

'={+,*,(,),x,1,2, } 3. (p, , E') (p, +TE')

R': 4. (p, , E') (p, )

1. E TE' limination de la 5. (p, , T) (p, FT')

2
 2. E' +TE' rcursivit gauche 6. (p, , T') (p,*FT')
3. E'
4. T FT' limination de la 7. (p, , T') (p, )
5. T' *FT' rcursivit gauche
6. T' 8. (p, , F) (p, (E))
7. F( E)
8. F xA 9. (p, , F) (p, xA)
9. A 1 factorisation
10. A 2 10. (p, , A) (p, 1)

11. (p, , A) (p, 2)

12. (p, +, +) (p, )

13. (p, *, *) (p, )

14. (p, , ) (p, )

15. (p, (, () (p, )

16. (p, ), )) (p, )

17. (p, x, x) (p, )

18. (p, 1, 1) (p, )

19. (p, 2, 2) (p, )

8-

Etat Pile Restant de la chaine Transition Rgle de

lire utilise grammaire
S $ x1+x2*x1$ 1
P $E x1+x2*x1$ 2 E TE'
P $E'T x1+x2*x1$ 5 T FT'
P $E'T'F x1+x2*x1$ 9 F xA
P $E'T'Ax x1+x2*x1$ 17 dpiler
P $E'T'A 1+x2*x1$ 10 A 1
P $E'T'1 1+x2*x1$ 18 dpiler
P $E'T' +x2*x1$ 7 T'
P $E' +x2*x1$ 3 E' +TE'
P $E'T+ +x2*x1$ 12 Dpiler
P $E'T x2*x1$ 5 T FT'
P $E'T'F x2*x1$ 9 F xA
P $E'T'Ax x2*x1$ 17 Dpiler
P $E'T'A 2*x1$ 11 A 2
P $E'T'2 2*x1$ 19 Dpiler
P $E'T' *x1$ 6 T'*FT'
P $E'T'F* *x1$ 13 Dpiler

3
 P $E'T'F x1$ 9 F xA
P $E'T'Ax x1$ 17 Dpiler
P $E'T'A 1$ 10 A 1
P $E'T'1 1$ 18 Dpiler
P $E'T' $ 7 T'
P $E' $ 4 E'
P $ $

Exercice 3:

S Ab | a |AA

A Sa | Ac | B

BSd

1. On choisit un ordre : S, A, B : S peut contenir les symboles A, B mais, B ne doit pas contenir ni A, ni S.

Algo : (voir cours) ; on procde par remplacement, puis limination de la rcursivit immdiate pour
chaque symbole,

Pour le symbole A :

A Sa est transforme en : AAba

Aaa

AAAa

limination de la rcursivit immdiate de A:

AAba AaaA|BA

Aaa AbaA|AaA|cA

AAAa A

AAc

AB

4
Pour le symbole B :

Remplacement de S

BSd BAbd Remplacement de A

BAAd BaaAbd|BAbd

Bad BaaAAd|BAAd

Bad

Elimination de la

recursivit immdiate

de B

BaaAbdB|aaAAdB|adB

BAbdB|AAdB

La grammaire G' aprs limination de la rcursivit:

S Ab | a |AA

AaaA|BA

AbaA|AaA|cA

BaaAbdB|aaAAdB|adB

BAbdB|AAdB

2. Factorisation :

S Ab |AA S AD

S a D b|A

5
 S a

AaaA|BA

AbaA|AaA|cA|

BaaAbdB|aaAAdB|adB B aE B aE

E aAbdB|aAAdB|dB E aA'F | dB'

F bdB|AdB

BAbdB|AAdB| B'A'F |

On obtient:

G' : S AD | a

Db|A

AaaA|BA

AbaA|AaA|cA|

B aE

E aA'F | dB'

F bdB|AdB

B'A'F |

3. Oui, la grammaire G' est LL(1) car elle n'est pas recursive gauche.

Exercice 4:

1) Si on considre la somme de 2 et 3, on peut crire sous trois formes:

-notation infixe: 2+3

-notation prfixe: + 2 3

Notation postfixe: 2 3 +

La grammaire donne dfinit la notation postfixe des expressions arithmtiques.

2) E E E op la grammaire est rcursive gauche donc elle n'est pas LL(1).

6
 3) Elimination de la rcursivit:

G1:

E nb E'

E' E op E'

E'

Pas de factorisation ncessaire.

Premier(E)={nb} suivant(E)={op, $}
Premier(E') ={nb,} suivant(E') ={op,$ }

Table d'analyse:

nb op $
E E nb E'
E' E' E op E' E' E'

G1 est LL(1):puisque chaque case de la table d'analyse contient une seule rgle.

w= nb nb op nb op

pile Restant lire de w action

$E nb nb op nb op $ E nb E' 1
$ E'nb nb nb op nb op $ dpiler
$ E' nb op nb op $ E' E op E' 2
$ E' op E nb op nb op $ E nb E' 3
$ E' op E' nb nb op nb op $ Dpiler
$ E' op E' op nb op $ E' 4
$ E' op op nb op $ dpiler
$ E' nb op $ E' E op E' 5
$ E' op E nb op $ E nb E' 6
$ E' op E' nb nb op $ dpiler
$ E' op E' op $ E' 7
$ E' op op $ dpiler
$ E' $ E' 8
$ $ Le mot est accept

7
 4) Construction de l'arbre syntaxique du mot w en ralisant la squence de sortie "action" de l'analyse
syntaxique. Selon la table d'analyse on obtient la squence 1,2,3.8.

nb E'

E op E'

nb E' E op E'

nb E'

Exercice 2:

B BB |BB| BB| B | (B) | id | vrai | faux

1. Pour montrer que G est ambigu, il suffit d'exhiber un mot de L(G) ayant deux arbres de
drivation, exemple w= id id vrai

B B

B B

B B

8
 B B vrai

Id B B id B

B vrai id

id

2. Pour liminer l'ambigut il faut tenir compte de la priorit des oprateurs et de l'associativit gauche:

Priorit descendante: () , , , ,

Soit G' (V', ' , R', B) tel que :

V={B, E, T, R, id, vrai, faux}

R': B BE | E

E ET | T

T TR | R

R R | (B) | id | vrai | faux

Rq:

Pour obtenir une grammaire qui n'est pas ambigu, on doit effectuer des choix de priorits et
d'associativits.

Choix de priorit: () est plus prioritaire que , est plus prioritaire que ,etc

Choix de l'associativit: L'oprateur est associatif gauche : a b c = (a b) c. On dcide que

les oprateurs et sont galement associatifs gauche (on pourrait les choisir associatifs droite).