Ensimag APP 1ère année — GC Examen 1ère session — mars 2020
Grammaires et compilation
Durée : 2h Tous documents autorisés Barème indicatif sur 21 points
Les 3 exercices sont indépendants. Dans les BNFs, les symboles sont des mots séparés par des
espaces : les (resp. non-)terminaux sont dans la police “machine-à-écrire” (resp. en “GRAS”).
. Exercice 1 (5 points) :
Soit L le sous-ensemble des mots de {b, c}∗ dont le nombre de b et le nombre de c ont même
parité : autrement dit, c’est le langage régulier
L = { w ∈ {b, c}∗ | |w|b mod 2 = |w|c mod 2 }
1) Donner une BNF sur le vocabulaire terminal {a, b, c} qui reconnaît le langage
{an c w bn | n ∈ N et w ∈ L}
2) Calculer les directeurs LL(1) de la BNF de la question 1). Est-elle LL(1) ? Justifier.
. Exercice 2 (10 points) :
On étudie deux BNFs définissant un langage inspiré de ce- (1) E ::= id
lui des expressions du langage C sur le vocabulaire terminal (2) | E[E]
{id, [, ], ., *, (, )}. Ici, id est un terminal qui représente l’ensemble (3) | E . id
des identificateurs du langage. On considère tout d’abord la BNF G1 (4) | *E
ci-contre (5) | (E)
1) Pour chacun des 4 mots suivants, donner l’ensemble (vide si le mot n’est pas reconnu) de
tous ses arbres d’analyses : “id . * id” “id [ id ] . id” “* id . id” “( * id ) . id”
2) La BNF G1 est-elle ambiguë ? Est-elle LL(1) ? Justifier.
3) On considère maintenant la BNF G2 donnée par
(1) E1 ::= * E1 (3) E0 ::= id (5) X ::= . id X
(2) | E0 X (4) | ( E1 ) (6) | [ E1 ] X
(7) |
Donner l’ensemble des arbres d’analyses sur G2 de chacun des 4 mots de la question 1).
4) Calculer les directeurs LL(1) de G2 . La BNF est-elle ambiguë ? Justifier.
5) On considère l’opérateur -> du C qui définit “e->x” comme un raccourci de “(*e).x”.
Étendre la BNF G2 en une BNF LL(1) qui fournit aussi cet opérateur, de sorte que les
opérateurs -> et . aient la même précédence. Justifier son caractère LL(1).
2019-2020 page 1/2
Ensimag APP 1ère année — GC Examen 1ère session — mars 2020
. Exercice 3 (6 points) :
On cherche ici à compiler des propositions en notation préfixe sous forme d’expressions C
formées d’une cascade de si-alors-sinon (avec l’opérateur ternaire du C). Le langage d’entrée
du compilateur est décrit par l’équation P ci-dessous. Le langage de sortie est décrit par
l’équation E. Dans ces deux langages, le terminal id ↑ x correspond à un identificateur C,
appelé x, distinct de “t” et “f”, et reconnu par l’analyseur lexical. Dans P, les opérateurs
logiques ont la même syntaxe que dans le TP.
P ::= t E ::= 1 // valeur “vrai”
| f | 0 // valeur “faux”
| id↑x | ( id↑x ? E : E )
| -P Expressions C générées
| &PP
| |PP
| >PP
Propositions en entrée
On décrit ce compilateur à l’aide d’un système d’attributs sur le symbole P ci-dessous, dont le
cas des opérateurs “|” et “>” reste à faire à la question 2. Pour une proposition p de P, étant
donné en entrée e1 et e2 deux expressions de E, le système d’attributs calcule une expression r
de E logiquement équivalente à “si p alors e1 sinon e2 ”. Le compilateur exécute cet algorithme
avec e1 valant initialement 1 et e2 valant 0.
P↓e1↓e2↑r ::= t r := e1
| f r := e2
| id↑x r := (x?e1 :e2 )
| - P↓e2↓e1↑r
| & P↓r0↓e2↑r P↓e1↓e2↑r0
...
1) Pour e1 = 1 et e2 = 0, représenter la propagation d’attributs de la proposition suivante, où x
et y sont les identificateurs associés au terminal id par l’analyseur lexical : “& - & f x & y t”.
2) Compléter le système d’attributs ci-dessus avec les cas qui manquent.
Indication : on peut justifier le cas du & ci-dessus avec le fait que comme “& p1 p2 ” est
logiquement équivalent à “si p1 alors p2 sinon faux”, alors “si & p1 p2 alors e1 sinon e2 ” est
équivalent à “si p1 alors (si p2 alors e1 sinon e2 ) sinon e2 ”.
De même, on peut utiliser que “| p1 p2 ” est équivalent à “si p1 alors vrai sinon p2 ” et que
“> p1 p2 ” est équivalent à “si p1 alors p2 sinon vrai”.
3) Avec votre système d’attributs quel est le résultat du compilateur sur “| f > x f” ?
2019-2020 page 2/2