:: Enseignements :: ESIPE :: E4INFO :: 2008-2009 :: Compilation ::

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.

Exercice 1 - Analyses LR(0) et SLR(1)

Soit la grammaire :

G₁ :	(p₀) S ::= E '$'	(p₃) T ::= 'id'
	(p₁) E ::= E '+' T	(p₄) T ::= '(' E ')'
	(p₂) E ::= T	(p₅) T ::= 'id' '(' E ')'

Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1)?
Construire l'automate des items LR(0). Cette grammaire est-elle LR(0) ?
Construire la table d'analyse SLR(1) correspondante. Cette grammaire est-elle SLR(1) ?
Décrire l'analyse du mot id(id+id)$
Dessiner l'arbre de dérivation correspondant.

Exercice 2 - Plus d'analyses LR(0) et SLR(1)

Soit la grammaire G₂ :

(p₀) S ::= T '$'	(p₃) X ::= ε
(p₁) T ::= X B	(p₄) B ::= 'b' B
(p₂) X ::= 'a' X 'b'	(p₅) B ::= 'b'

Construire l'automate des items LR(0).
Construire la table d'analyse SLR(1). Cette grammaire est-elle SLR(1) ?
Quel est le langage engendré par la grammaire ?
Utiliser la table pour faire l'analyse du mot abb$.

Exercice 3 - Analyses LR(1) et LALR(1)

Soit la grammaire G₃ suivante :

G₃	(p₀) S ::= T '$'	(p₃) E ::= V
	(p₁) T ::= V '=' E	(p₄) V ::= 'id'
	(p₂) T ::= E	(p₅) V ::= '*' E

Calculer les ensembles annulable, premier et suivant. Sont-elles LL(1) ?
Construire l'automate des items LR(0). Cette grammaire est-elle LR(0) ?
Cette grammaire est-elle SLR(1) ?
Construire l'automate et la table LR(1) de la grammaire G₃. La grammaire est-elle LR(1) ?
Construire la table LALR(1). La grammaire G₃ est-elle LALR(1) ?