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

Analyse LL - Correction

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.

Rappel sur les ensembles annulable, premier et suivant:
a) L'ensemble annulable contient les variables annulables, c'est-à-dire celles qui peuvent se dériver en ε , éventuellement en appliquant plusieurs productions.
annulable = {}
b) L'ensemble premier associe à une variable l'ensemble des terminaux qui peuvent apparaître comme lexème d'une dérivation partant de cette variable, éventuellement en appliquant plusieurs productions.
premier(E) = {'+','*','a'}
c) L'ensemble suivant associe une variable à l'ensemble des terminaux qui peuvent apparaître juste après cette variable dans un arbre de dérivation partant de S.
suivant(E) = {'$'} + premier(E) = {'$','+','*','a'}
On construit la table d'analyse LL selon le principe suivant :

	...	a	...
...
X		X ::= α si a appartient à premier(α) X ::= ε si a appartient à suivant(X)
...

Il n'y a pas de conflit, la grammaire est LL(1).

L'analyse s'effectue selon le principe suivant :

si le sommet de la pile d'analyse est un non-terminal, on cherche dans la table la règle à appliquer en regardant le symbole d'entrée :
- si une règle existe, on remplace le non-terminal par le membre droit de la règle trouvée ;
- si pas de règle, il y a échec ;
si le sommet de la pile d'analyse est un terminal
- s'il est différent du symbole d'entrée, il y a échec ;
- s'il est identique au symbole d'entrée
  - si c'est '$', la chaîne d'entrée est reconnue ;
  - on l'efface de la pile d'analyse et on avance dans l'entrée.

Entrée	Pile d'analyse	Action
a+a*a	S	(0)
a+a*a	E$	(3)
a+a*a	a$	shift
+a*a	$	reject

La séquence "a+a*a" n'est pas reconnue!

Entrée	Pile d'analyse	Action
+a*aa$	S	(0)
+a*aa$	E$	(1)
+a*aa$	+EE$	shift
a*aa$	EE$	(3)
a*aa$	aE$	shift
*aa$	E	(2)
*aa$	*EE$	shift
aa$	EE$	(3)
aa$	aE$	shift
a$	E$	(3)
a$	a$	shift
$	$	accept

Le mot "+a*aa" est reconnu!

Implémentation de l'analyseur LL en Java:
cf cours.

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 ?

annulable = {}
premier(E) = {(,a}
suivant(E) = {$,+,*,)}

	+	*	(	)	a	$
E			1,2,3		1,2,4

Il y a conflit, la grammaire G₁ n'est donc pas LL(1).
Elle est ambigüe car, par exemple, il y a deux arbres de dérivations possibles pour "a + a + a".

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.

annulable = {E',T'}

premier(E) = premier(T) = {a,(}
premier(E') = {+}
premier(T) = premier(F) = {a,(}
premier(T') = {*}
premier(F) = {a,(}

suivant(E) = {$,)}
suivant(E') = suivant(E)
suivant(T) = premier(E')+suivant(E)+suivant(E') [car E' est annulable]
suivant(T') = suivant(T)
suivant(F) = premier(T')+suivant(T') + suivant(T) [car T' est annulable]

suivant(E') = suivant(E) = {$,)}
suivant(T') = suivant(T) = {+,$,)}
suivant(F) = {*,+,$,)}

table d'analyse LL

	+	*	(	)	a	$
E			1		1
E'	2			3		3
T			4		4
T'	6	5		6		6
F			7		8

Entrée	Pile d'analyse	Action
a + a$	S	(0)
a + a$	E$	(1)
a + a$	TE'$	(4)
a + a$	FT'E'$	(8)
a + a$	aT'E'$	shift
+ a$	T'E'$	(6)
+ a$	E'$	(2)
+ a$	+TE'$	shift
a$	TT'E'$	(4)
a$	FT'E'$	(8)
a$	aT'E'$	shift
$	T'E'$	(6)
$	E'$	(3)
$	$	accept

Le mot "+ ( * a ( a ) ) $" ne peut pas être analysé, car il n'y a aucune règle pour '+' lorsque E est au sommet de la pile d'analyse.