Universite Aix Marseille - L3 Informatique Compilation TD1

PRISE EN MAIN DES GRAMMAIRES

1. Grammaires et derivations

Exercice 1. Derivation.Soit la grammaire suivante :

S −→ ( L ) S | aL −→ L , S | S

(1) Quels sont les symboles non terminaux et les symboles terminaux ?

(2) Les mots � ( a ) a �, � ( a ) ( a ) � et � ( a , a ) a � sont-ils reconnus par la grammaire ?

(3) Donnez les derivations gauche et droite du mot � ( a , ( a , a ) a ) a �. Faites chez vousles derivations gauche et droite du mot � ( a , ( ( a , a ) a , ( a , a ) a ) a ) a �.

Exercice 2. Arbre de derivationSoit la grammaire d’expressions arithmetiques suivante :

E −→ E + T | TT −→ T × F | FF −→ ( E ) | a | b | c

(1) Donnez des arbres de derivation des deux expressions suivantes : � a + b × c � et� b + ( a × c + b ) �.

2. Manipulation / transformation de grammaires

Exercice 3. Factorisation.

Definition. Une grammaire G, avec N (resp. T ) l’ensemble de ses symboles non-terminaux (resp.terminaux), est non factorisee si elle admet deux regles, utiles et distinctes, de la forme suivante :

X −→ α βX −→ α γ,

ou α, β et γ appartiennent a (N ∪ T )∗ et ou α ne se derive pas en ε.

N.B. Des regles de la forme A −→ α β | α | γ, dont une partie droite est prefixe d’une autre,peuvent etre modifiees (factorisees) facilement en A −→ α A′ | γ, A′ −→ β | ε.Soit la grammaire suivante :

A −→ a B c | a C B dB −→ a A b c | c b | εC −→ b C a A b c | b C a B

(1) Cette grammaire est-elle factorisee ?

(2) Si la reponse est negative, quelles sont la(es) regle(s) qu’il conviendrait de factoriser pour lasimplifier ? Operez les operations de factorisation adequates.

Soit maintenant un grand classique, avec l’echantillon de grammaire suivant :Instruction −→ if Condition Instruction

| if Condition Instruction else Instruction| while Condition Instruction

(3) Que peut-on dire de ce morceau de grammaire ? Comment l’� arranger � ?

1

2 PRISE EN MAIN DES GRAMMAIRES

Exercice 4. Recursivite a gauche.

Definition. Une grammaire G, avec N (resp. T ) l’ensemble de ses symboles non-terminaux (resp.terminaux), est recursive gauche si elle admet une regle de la forme suivante :

X −→ X α,ou α appartient a (N ∪ T )∗.

N.B. On passe facilement d’un recursivite gauche directe a une recursivite droite directe (et

inversement). En effet, si on a A −→ A α | β, on voit que A+

=⇒ β α∗. Et cette derivationpeut etre produite par A −→ β A′, A′ −→ α A′ | ε.Soit la grammaire suivante, permettant d’ecrire des expressions arithmetiques du type id + id +. . .+ id :

E −→ E + T | TT −→ id

(1) Supprimez la recursivite gauche de cette grammaire.

Considerons a present une nouvelle grammaire, notee G1, definissant un langage d’expressionsarithmetiques plus complexes :

E −→ E + E | E × E | ( E ) | id

(2) Il est clair que G1 est aussi recursive gauche. Trouvez une grammaire G2 equivalente (i.e.definissant le meme langage) qui n’est pas recursive gauche.

Exercice 5. Ambiguite

Definition. Soit L un langage hors-contexte. Soit G une grammaire definissant L. G est diteambigue s’il existe un mot m de L tel que m admet deux arbres de derivation differents par G.

N.B. Le probleme de l’ambiguite en general d’une grammaire est indecidable, ce qui signifie qu’iln’est pas possible d’elaborer un algorithme qui soit capable de dire, apres un temps fini, si unegrammaire qu’on lui soumet est ambigue ou non.

Soit la grammaire :P −→ ε | ( P ) | P P

(1) Quel est le langage defini par cette grammaire ?

(2) Montrez qu’elle est ambigue.

(3) Proposez une grammaire equivalente qui ne l’est pas.

(4) La grammaire G1 de l’exercice precedent est-elle ambigue ?

(5) Meme question pour la grammaire G2 ?

(6) Reflechissez a une grammaire equivalente qui ne serait pas ambigue.

3. Construction de grammaires

Exercice 6. Langage L1 = {a∗b}Soit l’alphabet Σ = {a, b} et le langage L1 = {a∗b} sur Σ. Ecrivez une grammaire de L1.

Exercice 7. Langage L2 = {anbn | n ∈ N}Soit l’alphabet Σ = {a, b} et le langage L1 = {anbn | n ∈ N} sur Σ. Ecrivez une grammaire de L2.

Exercice 8. Langage L3 = {anbp | n > p ou (n, p) ∈ N× N}Soit l’alphabet Σ = {a, b} et le langage L3 = {anbp | n > p ou (n, p) ∈ N×N} sur Σ. Ecrivez unegrammaire de L3.