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

Analyse LL

Dans ce TD, nous allons voir comment construire une table d'analyse LL(1). Pour cela, nous commencerons par construire les ensembles annulable, premier et suivant des grammaires.

Exercice 1 - Analyse LL

Considérons la grammaire suivante:

G₀:	(0) S ::= E '$'	(2) E ::= '*'EE
	(1) E ::= '+'EE	(3) E ::= 'a'

Calculer les ensembles annulable, premier et suivant.
Construire la table d'analyse LL de cette grammaire.
Vérifier si les mots a+a*a$ et +a*aa$ sont reconnus.
Construire les arbres de dérivation correspondants.
Implémenter l'analyseur LL de la grammaire en Java.

Exercice 2 - Plus d'analyse LL

Considérons la grammaire suivante:

G₁:	(0) S ::= E '$'	(3) E ::= '(' E ')'
	(1) E ::= E '+' E	(4) E ::= 'a'
	(2) E ::= E '*' E

Calculer les ensembles annulable, premier et suivant.
Construire la table d'analyse LL de cette grammaire.
Pourquoi la grammaire n'est-elle pas LL ?
Cette grammaire est-elle ambigüe ?

Exercice 3 - Encore plus d'analyse LL

G₂:	(0) S ::= E '$'	(3) E' ::= ε	(6) T' ::= ε
	(1) E ::= T E'	(4) T ::= F T'	(7) F ::= '(' E ')'
	(2) E' ::= '+' T E'	(5) T' ::= '*' F T'	(8) F ::= 'a'

Calculer les ensembles annulable, premier et suivant.
Construire la table d'analyse LL de cette grammaire.
Vérifier si les mots "a + a $" et "+ ( * a ( a ) )" sont reconnus.
Construire les arbres de dérivation correspondants.