td5 correction .pdf



Nom original: td5-correction.pdfTitre: td-correction.dvi

Ce document au format PDF 1.3 a été généré par dvips(k) 5.95a Copyright 2005 Radical Eye Software / ESP Ghostscript 815.02, et a été envoyé sur fichier-pdf.fr le 27/12/2015 à 16:52, depuis l'adresse IP 80.249.x.x. La présente page de téléchargement du fichier a été vue 1079 fois.
Taille du document: 265 Ko (13 pages).
Confidentialité: fichier public


Aperçu du document


Correction TD de Compilation no5
Ing´
enieurs 2000 - IR2
——

Analyse LR
Dans ce TD, nous allons voir comment construire l’automate des items LR
d’une grammaire, ainsi que la table d’analyse correspondante qui permet de
tester si un mot appartient ou non au langage reconnu par la grammaire.

x Exercice

1. Soit les grammaires suivantes :
G0 (p0 ) S ::= E ’$’
(p1 ) E ::= E ’a’
(p2 ) E ::= ’a’
G′0 (p0 ) S ::= E ’$’
(p1 ) E ::= ’a’ E
(p2 ) E ::= ’a’

Pour ces deux grammaires :
1. Quels sont les langages reconnus ?


Le langage reconnu est le mˆeme pour les deux grammaires : a+


2. Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1) ?


Pour G0 :
premier(S)=premier(E)
premier(E)={a}

premier(S)=premier(E)
premier(E)={a}
suivant(S)=∅
suivant(E)={$}

suivant(S)=∅
suivant(E)={$, a} Pour G′0 :

1

Ces deux grammaires ne sont pas LL(1) car G0 est r´ecursive `a gauche et dans G′0 ,
premier(p1 ) = premier(p2 ).


3. Construire les automates des items LR(0). Ces grammaires sont-elles LR(0) ?


Pour G0 :

Pour G′0 :

La grammaire G0 est LR(0) alors que la grammaire G′0 ne l’est pas car il y a un confilit
d´ecalage/r´eduction dans l’´etat 2.


4. Construire les tables d’analyse SLR(1) correspondantes. Ces grammaires sontelles SLR(1) ?


Pour G0 :
a
0
d2
1
d3
2 r(p2 )
3 r(p1 )

$

Pour G′0 :
a
0
d2
1
2
d2
3 r(p1 )

E
g1

ACCEPT
r(p2 )
r(p1 )

2

$
ACCEPT
r(p2 )
r(p1 )

E
g1
g3

Ces deux grammaires sont SLR(1).


5. D´ecrire l’analyse du mot aaaa. Que remarquez-vous ? Qu’en d´eduisez-vous ?


Pour G0 :
Entr´ee
aaaa$
aaa$
aaa$
aa$
aa$
a$
a$
$
$
ACCEPT

Pile
0
0 (a,2)
0 (E,1)
0 (E,1) (a,3)
0 (E,1)
0 (E,1) (a,3)
0 (E,1)
0 (E,1) (a,3)
0 (E,1)

E ::= ’a’
E ::= E ’a’
E ::= E ’a’
E ::= E ’a’
S ::= E ’$’

Pour G0 :
Entr´ee
Pile
aaaa$
0
aaa$
0 (a,2)
aa$
0 (a,2) (a,2)
a$
0 (a,2) (a,2) (a,2)
$
0 (a,2) (a,2) (a,2) (a,2)
$
0 (a,2) (a,2) (a,2) (E,3)
E ::= ’a’
$
0 (a,2) (a,2) (E,3)
E ::= ’a’ E
$
0 (a,2) (E,3)
E ::= ’a’ E
$
0 (E,1)
E ::= ’a’ E
ACCEPT
S ::= E ’$’

Dans le cas de la grammaire G0 la taille de la pile augmente de fa¸con lin´eaire par
rapport `
a la taille de l’entr´ee reconnue. La reconnaissance avec la grammaire G′0 est
donc plus coˆ
uteuse en terme de m´emoire, il faut donc privil´egier les r´ecursivit´e gauche
plutˆot que les r´ecursivit´e droite avec les analyseur LR.


6. Dessiner les arbres de d´erivation correspondants.



3

Pour G′0 :

Pour G0 :


x Exercice

2.
Soit la grammaire suivante :
G1 (p0 ) S ::= E ’$’
(p3 ) T ::= ’id’
(p1 ) E ::= E ’+’ T (p4 ) T ::= ’(’ E ’)’
(p2 ) E ::= T
(p5 ) T ::= ’id’ ’(’ E ’)’

1. Calculer les ensembles annulable, premier et suivant pour cette grammaire. Estelle LL(1) ?


premier(S)=premier(E)
premier(E)=premier(T)
premier(T)={id, (}

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

La grammaire G1 n’est pas LL(1) car les ensembles premier des productions (p1 ) et
(p2 ) sont ´egaux et leurs non-terminal en partie gauche (E) sont ´egaux. Ceci dˆ
u `a la
r´ecursivit´e gauche de la production (p1 ).


2. Construire l’automate des items LR(0). Cette grammaire est-elle LR(0) ?

4



5

La grammaire n’est pas LR(0) car il y a un conflit d´ecalage/r´eduction dans l’´etat 3.


3. Construire la table d’analyse SLR(1) correspondante. Cette grammaire est-elle
SLR(1) ?


Les lignes de la table d’analyse correspondent aux ´etats de l’automate des items et les
colonnes correspondent aux symboles. Il est inutile de faire apparaˆıtre l’axiome A. dx
correspond `
a un d´ecalage (d) dans l’entr´ee, et un saut `a l’´etat x. gx corrrespond `a un
empilement non-terminal (goto), et `a un saut `a l’´etat x. r(y) correspond `a une r´eduction
par la production (y). Les r(y) correspondent `a des ´etats finaux dans l’automate des
items, et apparaissent pour chacun des suivants du membre gauche de la r`egle.
Exemple : dans l’´etat 10, on a une r´eduction par la r`egle 4 (T ::= (E)). Sur la ligne 10,
on a donc r(p4 ) dans les colonnes qui correspondent aux suivants de T.

0
1
2
3
4
5
6
7
8
9
10
11

id
d3

d3
d3
d3

(
d4

d6
d4
d4
d4

)

+

$

r(p2 )
r(p3 )

d5
r(p2 )
r(p3 )

ACCEPT
r(p2 )
r(p3 )

E
g1

T
g2

g7

g2
g8
g2

g9
d10
r(p1 )
d11
r(p4 )
r(p5 )

d5
r(p1 )
d5
r(p4 )
r(p5 )

r(p1 )
r(p4 )
r(p5 )


4. D´ecrire l’analyse du mot id(id+id)$


Entr´ee
id(id+id)$
(id+id)$

id+id)$
+id)$

Pile
0
on initialise la pile ave l’´etat 0
0 id 3
quand il y a d´ecalage, on met le symbole lu dans la
pile, suivi par le num´ero de l’´etat atteint
0 id 3 ( 6
0 id 3 ( 6 id 3

6

+id)$

+id)$
id)$
)$
)$
)$
$
$
$
ACCEPT

0 id 3 ( 6 T 2
T ::= id
quand il y a une r´eduction, on retire de la pile ce qui
correspond au membre droit de la r`egle, et on empile
a la place le membre gauche de la r`egle. Ici la r`egle
`
est T ::= id, on retire donc id 3, et on empile T.
Pour savoir dans quel ´etat aller, on regarde l’´etat qui
pr´ec`ede T dans la pile, ici 6. Comme dans l’´etat 6, la
transition par T nous am`ene en 2, on empile 2.
0 id 3 ( 6 E 9
E ::= T
0 id 3 ( 6 E 9 + 5
0 id 3 ( 6 E 9 + 5 id 3
0 id 3 ( 6 E 9 + 5 T 8
T ::= id
0 id 3 ( 6 E 9
E ::= E + T
0 id 3 ( 6 E 9 ) 11
0 T 2
T ::= id(E)
0 E 1
E ::= T
S ::= E$


5. Dessiner l’arbre de d´erivation correspondant.




x Exercice

3.
Soit G2 la grammaire suivante :
(p0 ) S ::= T ’$’
(p3 ) X ::= ε
(p1 ) T ::= X B
(p4 ) B ::= ’b’ B
(p2 ) X ::= ’a’ X ’b’ (p5 ) B ::= ’b’

7

1. Construire l’automate des items LR(0).




2. Construire la table d’analyse SLR(1). Cette grammaire est-elle SLR(1) ?


annulable={X}
premier(S)=premier(T)
premier(T)=premier(X)+premier(B)
premier(X)={a}
premier(B)={b}
premier(S)=premier(T)={a, b}
suivant(T)={$}
suivant(X)=premier(B)+{b}={b}
suivant(B)=suivant(T)={$}
Note : les transitions par ε doivent apparaˆıtre dans la table.

8

0
1
2
3
5
6
7
8
9

a
d3

b
r(p3 )∗

d3

d6
r(p3 )∗

$

T
g1

X
g2

B

ACCEPT
g5
g7
r(p1 )
r(p5 )

d6
d9

g8

r(p4 )
r(p2 )



Dans les ´etats 0 et 3 de l’automate des items, on a une r´eduction par la production
(p3 ) (X ::= ε). On met donc r(p3 ) pour tous les suivants du membre gauche (ici X).

La grammaire est SLR(1), car il n’y a pas de conflit.


3. Quel est le langage engendr´e par la grammaire ?


an bn+m , n ≥ 0 et m > 1


4. Utiliser la table pour faire l’analyse du mot abb$.


Pile
0
0 a
0 a
0 a
0 a
0 X
0 X
0 X
0 T

3
3
3
3
2
2
2
1

ε4
X 7
X 7 b 9

X ::= ε
X ::= aXb

b 6
B 5

B ::= b
T ::= XB
S ::= T



Entr´ee
abb$
bb$
bb$
bb$
b$
b$
$
$
$
ACCEPT

9

x Exercice

4.
Soit la grammaire G3 suivante :
G3 (p0 ) S ::= T ’$’
(p3 ) E ::= V
(p1 ) T ::= V ’=’ E (p4 ) V ::= ’id’
(p2 ) T ::= E
(p5 ) V ::= ’*’ E

– Calculer les ensembles annulable, premier et suivant pour cette grammaire. Estelle LL(1) ?


premier(S) = premier(T)
premier(T) = premier(V) + premier(E)
premier(E) = premier(V)
premier(V) = {id,*}
premier(V) = premier(E) = premier(T) = premier(S) = {id,*}
suivant(T) = {$}
suivant(V) = {=} + suivant(E)
suivant(E) = suivant(T) + suivant(V)
suivant(E) = suivant(V) = {=, $}
La grammaire G3 n’est LL(1) car les ensembles premier des production (p1 ) et (p2 )
sont ´egaux et ces productions ont le mˆeme non-terminal (T ) en partie gauche.


– Construire l’automate des items LR(0). Cette grammaire est-elle LR(0) ?



10

La grammaire n’est pas LR(0) car il y a un conflit d´ecalage/r´eduction dans l’´etat 2.


– Cette grammaire est-elle SLR(1) ?


La grammaire G3 n’est pas SLR car dans l’´etat 2 il y a un conflit d´ecalage/r´eduction
qui ne peut pas ˆetre r´esolu via l’ensemble suivant car = fait partie de suivant(E).


– Construire l’automate et la table LR(1) de la grammaire G3 . La grammaire estelle LR(1) ?



11

12

0
1
2
3
4
5
6
7
8
9
10
11
12
13

id
d4

*
d5

=

d6
r(p4 )
d4
d11

E
g3

V
g2

g7
g9

g8
g10

g13

g10

ACCEPT
r(p3 )
r(p2 )
r(p4 )

d5
d12
r(p5 )
r(p3 )

d11

T
g1

$

r(p5 )
r(p3 )
r(p1 )
r(p3 )
r(p4 )

d12
r(p5 )

Il n’y a pas de conflit dans la table, la grammaire G3 est donc LR(1).


– Construire la table LALR(1). La grammaire G3 est-elle LALR(1) ?


Il est possible de confondre les ´etats 5 et 12, 8 et 10, 4 et 11 ainsi que 7 et 13.

0
1
2
3
4
5
6
7
8
9

id
d4

*
d5

=

d6
r(p4 )
d4
d4

$

E
g3

V
g2

g7
g9

g8
g8

ACCEPT
r(p3 )
r(p2 )
r(p4 )

d5
d5
r(p5 )
r(p3 )

T
g1

r(p5 )
r(p3 )
r(p1 )

Il n’y a pas de conflit dans le table, la grammaire G3 est donc LALR(1).


13


td5-correction.pdf - page 1/13
 
td5-correction.pdf - page 2/13
td5-correction.pdf - page 3/13
td5-correction.pdf - page 4/13
td5-correction.pdf - page 5/13
td5-correction.pdf - page 6/13
 




Télécharger le fichier (PDF)


td5-correction.pdf (PDF, 265 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


td5 correction
corrige sujet thl
td2
serie thl 3 2017 2018
correction td2
chap 3 compilation version finale ult

Sur le même sujet..