:: Enseignements :: ESIPE :: E4INFO :: 2010-2011 :: Analyse syntaxique ::

Analyses LR(0) et SLR(1)

Dans ce TD, nous allons voir comment construire l'automate des items LR(0) 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$.