PandaCodeur · Exercices 2 / 2

Exercices de compilation : 2. Grammaires et analyse

Six problèmes de syntaxe, du calcul des ensembles aux conflits SLR.

Mode d’emploi et rappel

Prévoyez 90 minutes. Écrivez systématiquement l’axiome et les terminaux. Vérifiez ε dans PREMIER mais jamais dans SUIVANT. Une conclusion « non LL(1) » doit désigner un conflit précis.

1. Dérivation et langage : découverte

S → a S b | ε

Dériver aaabbb et caractériser le langage. Indice : compter simultanément les a et les b.

Afficher la correction expliquée

S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb

Chaque production non vide ajoute un a devant et un b derrière. Le langage est {aⁿbⁿ | n≥0}, dont ε. Le mot abab n’en fait pas partie car tous les a précèdent les b.

2. Réduire une grammaire : application

S → a | A
A → A B
B → b
C → c

Supprimer les symboles inutiles. Indice : productivité avant accessibilité.

Afficher la correction expliquée

Au point fixe, S, B et C sont productifs. A ne peut jamais éliminer sa propre occurrence : il est improductif. Supprimer A et les productions qui l’utilisent laisse S → a, B → b, C → c. Depuis S, B et C sont inaccessibles. La grammaire réduite est S → a.

3. Factoriser et décider : application

S → a b | a c

Factoriser puis donner la table LL(1). Indice : isoler le préfixe commun a.

Afficher la correction expliquée

S → a R
R → b | c

M	a	b	c	$
S	S → a R	-	-	-
R	-	R → b	R → c	-

La grammaire initiale présente deux règles en M[S,a]. La version factorisée ne possède plus de conflit.

4. Propagation de SUIVANT : consolidation

S → A B
A → a | ε
B → b | ε

Calculer les ensembles, construire la table et décider si ε est accepté.

Afficher la correction expliquée

Non-terminal	PREMIER	SUIVANT
S	{a, b, ε}	{$}
A	{a, ε}	{$, b}
B	{b, ε}	{$}

M	a	b	$
S	S → A B	S → A B	S → A B
A	A → a	A → ε	A → ε
B	-	B → b	B → ε

La grammaire est LL(1). ε est accepté par S ⇒ AB ⇒ B ⇒ ε. Le langage vaut {ε,a,b,ab}. $ se propage à A car B est annulable.

5. Programmer une descente récursive : consolidation

Écrire un parseur pour les listes S → (L) | a ; L → S L′ ; L′ → , S L′ | ε. Indice : remplacer L′ par une boucle.

Afficher la correction expliquée

S():
  si courant == a : accepter(a)
  sinon si courant == ( :
    accepter(() ; L() ; accepter())
  sinon : erreur

L():
  S()
  tant que courant == , : accepter(,) ; S()
  si courant != ) : erreur

programme():
  S()
  accepter(fin)

accepter(t) vérifie le token t puis avance. La première invocation de S dans L interdit une liste vide. Le contrôle final empêche d’accepter seulement un préfixe comme a suivi de caractères inattendus.

6. Conflit SLR et attributs : approfondissement

E → B = F | F ; F → B ; B → + F | a

Un état contient E → B · = F et F → B ·. Pourquoi le lookahead = pose-t-il problème ? Donner aussi une règle synthétisée pour l’évaluation de E → E1 + T.

Afficher la correction expliquée

= appartient à SUIVANT(F), car il suit B dans E → B=F, se propage de B à F dans B → +F, et les relations F → B ferment la propagation. L’item achevé F → B · autorise donc une réduction sur = ; l’autre item exige un décalage. Conflit SLR. Une règle synthétisée possible est E.val = E1.val + T.val. Le premier examen fournit la collection complète d’items.