Td 2 analyse descendante ll1 Théorie des langages-téléc...

Théorie des langages : Td 2 analyse descendante ll1

Télécharger PDF

Exercice 1 : Analyse descendante LL(1)

a) Éliminer la récursivité à gauche de la grammaire suivante

Voici la grammaire initiale :

• S → (L) | a
• L → L, S | S

Solution

La grammaire sans récursivité à gauche est :

• S → (L') | a
• L' → L', S | S
• L → L',

b) Construire un analyseur syntaxique descendant pour la grammaire (a)

L’analyseur doit suivre ces règles :

• Si le premier symbole est (, alors on applique S → (L).
• Si le premier symbole est a, alors on applique S → a.
• Pour L, on vérifie si le symbole suivant est , ou ).
• Si , est présent, on applique L → L', S.
• Si ) est présent, on applique L → S.

c) Comportement de l’analyseur sur les phrases données

• (a,a) : L’analyseur commence par S → (L), puis L → L', S, et enfin S → a.
• (a,(a,a)) : L’analyseur suit S → (L), puis pour le premier L → S (car ) suit), puis S → a. Ensuite, il traite le sous-ensemble (a,a) comme dans l’exemple précédent.
• (a,((a,a),(a,a))) : L’analyseur commence par S → (L), puis pour le premier L → L', S (car , suit), S → a. Ensuite, il traite le sous-ensemble ((a,a),(a,a)) en appliquant L → L', S et S → (L) pour chaque paire imbriquée.

Exercice 2 : Analyseur descendant pour une grammaire booléenne

Voici la grammaire :

• Exprb → Exprb ou Termeb | Termeb
• Termeb → Termeb et Facteurb | Facteurb
• Facteurb → (Exprb) | vrai | faux

Solution

L’analyseur doit suivre ces règles :

• Si le symbole est vrai ou faux, appliquer Facteurb → vrai | faux.
• Si le symbole est (, alors appliquer Facteurb → (Exprb).
• Pour Termeb, si le symbole suivant est et, appliquer Termeb → Termeb et Facteurb.
• Si le symbole suivant est ou ou $ (fin de chaîne), appliquer Termeb → Facteurb.
• Pour Exprb, si le symbole suivant est ou, appliquer Exprb → Exprb ou Termeb.
• Si le symbole suivant est et, ($, appliquer Exprb → Termeb.

Exercice 3 : Montrer que la grammaire est LL(1)

Voici la grammaire :

• S → AaAb | BbBa
• A → ε
• B → ε

Solution

Pour montrer que cette grammaire est LL(1), on vérifie que chaque règle a un ensemble disjoint de premiers symboles (First) et de suivis (Follow).

• First(S) = {A, B} = {ε} (car A et B dérivent ε).
• First(A) = {ε}, Follow(A) = {a, b} (car A est suivi par a ou b dans les règles de S).
• First(B) = {ε}, Follow(B) = {a, b} (car B est suivi par a ou b dans les règles de S).
• Les règles de S sont distinguées par le premier symbole terminal : a pour AaAb et b pour BbBa.

Exercice 4 : Grammaire LL(1) sans ε-productions et alternatives distinctes

Pour montrer qu’une grammaire sans ε-productions où chaque alternative commence par un terminal différent est LL(1), on utilise les propriétés suivantes :

• Si chaque règle d’un symbole non-terminal commence par un terminal unique, alors les ensembles First pour ces règles sont disjoints.
• L’absence d’ε-productions garantit que les règles ne peuvent pas être ambiguës en raison d’un symbole vide.
• Les conflits de prédiction (predict) sont évités car aucun symbole non-terminal ne peut avoir deux règles commençant par le même terminal.

Exemple de grammaire LL(1)

Considérons la grammaire :

• S → aA | bB
• A → c
• B → d

Cette grammaire est LL(1) car :

• S a deux règles commençant par a et b respectivement.
• Les règles de A et B ne contiennent pas d’ε-productions.

FAQ

Qu’est-ce que la récursivité à gauche dans une grammaire ?

La récursivité à gauche survient lorsqu’une règle d’un symbole non-terminal commence par ce même symbole non-terminal. Par exemple, L → L, S est récursive à gauche.

Comment construire un analyseur descendant LL(1) ?

Un analyseur descendant LL(1) se construit en remplaçant chaque symbole non-terminal par des règles qui ne sont pas récursives à gauche, puis en créant une table de prédiction basée sur les premiers symboles des règles.

Qu’est-ce qu’une ε-production ?

Une ε-production est une règle qui permet à un symbole non-terminal de dériver le symbole vide (ε). Par exemple, A → ε est une ε-production.