PandaCodeur · Examen 3 / 4

Examen de compilation : 3. Grammaires et analyse prédictive

Sujet original : 2 heures, niveau licence, 20 points.

Rappel avant le sujet

Barème : 4 + 6 + 6 + 4 = 20 points. Une branche ε se sélectionne avec SUIVANT. Une table sans conflits permet une analyse prédictive à un token de prévision.

1. Transformer une grammaire : 4 points

E → E + T | T
T → T * F | F
F → ( E ) | id

Supprimer la récursion gauche immédiate (2 points), expliquer les priorités et l’associativité à préserver dans l’arbre abstrait (2 points).

Afficher la correction expliquée

E → T E′
E′ → + T E′ | ε
T → F T′
T′ → * F T′ | ε
F → ( E ) | id

T regroupe les multiplications avant l’addition. La grammaire transformée reconnaît les mêmes expressions ; pour retrouver l’associativité à gauche de la grammaire initiale dans un AST, accumuler les opérations avec un repli gauche. La forme récursive droite des auxiliaires ne suffit pas à définir ce calcul sémantique.

2. Listes imbriquées : 6 points

S → ( L ) | a
L → S L′
L′ → , S L′ | ε

Calculer PREMIER et SUIVANT (3 points), construire la table LL(1) et conclure (3 points).

Afficher la correction expliquée

Non-terminal	PREMIER	SUIVANT
S	{(, a}	{$, ), ,}
L	{(, a}	{)}
L′	{,, ε}	{)}

M	(	)	a	,	$
S	S → ( L )	-	S → a	-	-
L	L → S L′	-	L → S L′	-	-
L′	-	L′ → ε	-	L′ → , S L′	-

Chaque cellule remplie contient une production. La grammaire est LL(1). L ne produit pas ε : la liste vide () n’est pas autorisée.

3. Reconnaître ou refuser : 6 points

Tracer (a,a) (4 points) puis expliquer le refus de (a,) et () (2 points).

Afficher la correction expliquée

Convention : sommet de pile à gauche ; $ marque la fin de l’entrée et le fond de pile.

Pile	Entrée restante	Action
S $	( a , a ) $	S → ( L )
( L ) $	( a , a ) $	Lire (
L ) $	a , a ) $	L → S L′
S L′ ) $	a , a ) $	S → a
a L′ ) $	a , a ) $	Lire a
L′ ) $	, a ) $	L′ → , S L′
, S L′ ) $	, a ) $	Lire ,
S L′ ) $	a ) $	S → a
a L′ ) $	a ) $	Lire a
L′ ) $	) $	L′ → ε
) $	) $	Lire )
$	$	Accepter

Dans (a,), après la virgule, le sommet S attend a ou (, alors que l’entrée présente ). M[S,)] est vide. Pour (), après (, le sommet L ne possède aucune règle sur ) : refus immédiat.

4. Branche annulable et conflit : 4 points

A → a B | ε
B → A a

A est l’axiome. Calculer SUIVANT(A) et décider LL(1).

Afficher la correction expliquée

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

SUIVANT(A) = {$,a} : $ vient de l’axiome, a de B → A a. Sur a, A → aB et A → ε entrent en conflit. La grammaire n’est pas LL(1), même si les deux branches de A commencent respectivement par a et ε.