LOG3210 - Élément de langages et compilateur

Questionnaire : Final
Ettore Merlo – Professeur
Doriane Olewicki – Chargée de cours

ON
Hiver 2021

1 Grammaire
Supposons une grammaire telle que décrite ci-dessous (n.b. “” est le symbole epsilon, le symbole vide):

S →[L] (1)
L →ET (2)

TI E →S
E →id
E →
T →, L
(3)
(4)
(5)
(6)
T → (7)

1.1. (3pts) Décrivez le vocabulaire produit par cette grammaire. Quelles sont les phrases “limites” si elles
LU
existent (la/les plus petite(s) phrase(s) et la/les plus grande(s) phrase(s)) acceptées par cette grammaire
?
Une liste de liste ou d’élément ’id’ ou de caractère vide, séparé par des virgules.
La plus petite phrase est “[]”
Il y a plusieurs grande phrase possible qui sont infiniments grandes vu que chaque element peut être une
liste. Par exemple: [[[...id, id, ....]], [[...id, id, ....]], ...]
SO

1.2. (3pts) En utilisant la dérivation par la droite, montrez que la phrase [id, id] est acceptée par la gram-
maire.
S ⇒ [L] ⇒ [ET ] ⇒ [E, L] ⇒ [E, ET ] ⇒ [E, E] ⇒ [E, id] ⇒ [id, id]

1
1.3. (3pts) Est-ce que la grammaire présente de la récursivité (direct et/ou indirecte) par la gauche ?
OUI/NON (entourez la réponse). NON
Si OUI, transformez la grammaire pour éliminer la récursivité. Si NON, expliquez pourquoi. Dans
les deux cas, utilisez l’algorithme pour éliminer la récursivité à gauche vu en cours! (Pour
éliminer la récursivité à gauche ou pour prouver qu’il n’y en a pas.)
NON, et on applique l’algorithme pour le prouver:
On définit un ordre de parcourt des symboles non-terminaux: [S, L, E, T ]
n.b. d’sautre ordres sont possibles.
On commence:

ON
• Step (S):
– for e before S: /
– Récursivité directe (S → S...) ? /
• Step (L):
– for e before L:
∗ F → S... ? /
– Récursivité directe (F → F...) ? /
• Step (E):
TI
– for e before L:
∗ E → S... ? (3) becomes E → [L] (8)
∗ E → L... ? /
– Récursivité directe (E → E...) ? /
• Step (T):
– for e before T:
LU
∗ T → S... ? /
∗ T → L... ? /
∗ T → E... ? /
– Récursivité directe (T → T...) ? /
Une règle est transformée mais pas de récursivité n’est détectée.
SO

2
1.4. (8pts) Calculez les ensembles FIRST and FOLLOW de cette grammaire. Utilisez le tableau ci-joint
pour indiquer vos réponses.
FIRST [ ] id , 
S (1) S → [L]

L (2) L → ET (2) L → ET (2) L → ET (2) L → ET

E (3) E → S (4) E → id (5) E → 

ON
T (6) T →, E (7) T →, E

FOLLOW [ ] id , $
S (3) E → S (3) E → S X

L (1) S → [L]

T
TI (2) L → ET

(2) L → ET
(2) L → ET

1.5. (6pts) Dans les cases suivantes, expliquez pourquoi vous avez indiqué ou non quelque chose:
LU
 
• FIRST S, ”id” :
Rien ici
SO

 
• FIRST E, ”[” :
From rule (1) First(S) contient First(S). First(S) contient ”[” grâce à la règle (1)

3
  
• FOLLOW S, ”, ” :
Par la règle (3), Follow(S) contient le Follow(E). Par la règle (2), Follow(E) contient le First(T) et
First(T) contient ”,” par la règle (6).

ON
1.6. (3pts) Cette grammaire est-elle LL(1) ? Justifiez d’après la définition donnée au cours.
OUI par définition de LL(1)
Pour deux productions A → α|β distinctes:
• FIRST(α) et FIRST(β) sont deux ensembles disjoints.
• Au plus un de α et β peut dériver la chaı̂ne vide  (déjà spécifié en 1).
• Si β peut éventuellement dériver  ( est dans FIRST(β) ), alors FIRST(α) et FOLLOW(A) sont
disjoints. De même, si α peut éventuellement dériver  ( est dans FIRST(α) ), alors FIRST(β) et
FOLLOW(A) sont disjoints.

TI
Toutes ces conditions sont remplies vue les FIRST and FOLLOW remplis ci dessus.
LU
SO

4
2 Analyse syntaxique ascendante
2.1. Supposons la même grammaire qu’à la question précédente (ci-dessous, les règles 1 à 7). La grammaire
augmentée de cette grammaire est la suivante (ci-dessous, les règles 0 à 7, la règle 0 est ajoutée) (n.b.
“” est le symbole epsilon, le symbole vide):

S 0 →S (0)
S →[L] (1)
L →ET (2)

ON
E →S (3)
E →id (4)
E → (5)
T →, L (6)
T → (7)

Voici une partie des ensembles et GOTOs pour cette grammaire augmentée. (l’ensemble I0 et I1 et le
GOTO suivant GOT O(I0 , S)).

I0 ={S 0 → •S ; S → •[L]}

TI I1 = GOT O(I0 , S) = {S 0 → S•}

[...]

calculez les GOTOs suivants et indiquez le numéro de l’ensemble d’après la table de parsage ascendante
fournie:
(a) (1.5pts) GOT O(I0 , ”[”) = {S → [•L] ; L → •ET ; E → •S ; E → •id ; E → • ; S → •[L]}
LU

Ensemble = I2
SO

(b) (1.5pts) GOT O(I2 , S) = {E → S•}

Ensemble = I5

5
2.2. (8pts) La table de parsage ascendante associée à cette grammaire est la suivante:

ACTION GOTO
Etats
[ ] id , $ S L E T
0 s2 1
1 acc
2 s2 r5 s6 r5 5 3 4
3 s7
4 r7 s9 8

ON
5 r3 r3
6 r4 r4
7 r1 r1 r1
8 r2
9 s2 r5 s6 r5 5 10 4
10 r6

Est-ce que la phrase “[id, ]” est reconnue par la grammaire donnée ? Prouvez-le en appliquant le parcours
ascendant. (Tableau à la page suivante)

Pile Symboles Entrée Action

0
02
026
024
024 9
TI $
$[
$[id
$[E
$[E,
[id,]$
id,]$
, ]$
, ]$
]$
s2
s6
r4
s9
r5
024 94 $[E,E ]$ r7
024 948 $[E,ET ]$ r2
024 9 10 $[E,L ]$ r6
LU
024 8 $[ET ]$ r2
023 $[L ]$ s7
023 7 $[L] $ r1
01 $S $ acc
SO

6
3 Définition dirigée par la syntaxe (SDD)
Supposons la gramaire suivante:
S →[L] (1)
L →E, L (2)
L →E (3)
E →id (4)

ON
Cette grammaire permet de construite une liste d’id, de longueur 1 à l’infinie. Nous voulons définir une SDD
pour cette grammaire telle que:
• S contient le nombre de id dans la liste. (un attribut [Link])
• chaque E contient l’index de l’id dans la liste. (un attribut [Link])
Un exemple de cette SDD appliqué à l’exemple “[id, id, id]” donnerait l’arbre suivant: (attention, d’autres
attributs pourraient être nécessaires et ne sont pas indiqués dans cet arbre.)

TI
LU
SO

7
3.1. (8pts) Dans le tableau ci-après, définissez les règles sémantiques de cette SDD.
On suppose que:
• Il n’y a pas de variable globale accessible à tout point de l’arbre.
• Vous pouvez définir tous autres attributs nécessaires pour votre SDD.

3.2. (3pts) Pour chaque règle, indiquez d’une croix dans le tableau si la règle est synthétisée (SYN) ou héritée
(HER).
3.3. (3pts) Complétez l’arbre de parsage fourni ci-dessus pour la phrase [id, id, id] si y a d’autres attributs

ON
que vous avez définis dans votre SDD.
Vous avez la place de refaire le dessin à la page suivant le tableau si nécessaire. Veuillez indiquer sous
cette question où vous avez répondu.

Règle de production Règle sémantique SYN HER

(1) S → [L] [Link] = 10 X

[Link] = [Link] X

(2) L → E, L1
TI [Link] = [Link] X

L1 .index = [Link]+1 X

[Link] = L1 .taille X
LU
(3) L→E [Link] = [Link] X

[Link] = [Link] + 1 X
SO

(4) E → id

8
(Espace pour refaire l’arbre de parsage si nécessaire)

ON
TI
LU
SO

9
4 Code machine et gestion des registres
Supposons le bloc de code simple suivant, avec les ensembles variables vives et next-use fournis:

# CODE Variables Vives Next-Use

intermédiaire IN OUT IN OUT
1 a=b+c b,c,e,f a,e,f b:[1], c:[1], e:[2], f:[2,4] a:[3,4], e:[2], f:[2,4]
2 d =e * f a,e,f a,d,f a:[3,4], e:[2], f:[2,4] a:[3,4], d:[3], f:[4]
3 e=a-d a,d,f a,f a:[3,4], d:[3], f:[4] a:[4], f:[4]

ON
4 f=a+f a,f f a:[4], f:[4] /
stop return f
4.1. (10pts) Dans le tableau à la page suivante, écrivez le code machine associé au code du bloc simple. Ce
code machine doit respecter une contrainte de 3 registres. Les registres doivent être assignés lors de
l’écriture du code (assignation simple).
4.2. (5pts) Pour chaque ligne de code machine, indiquez (dans la partie droite du tableau) l’état des registres
après l’application de la ligne de code machine.
(a) Dans la colonne correspondant à chaque registre, indiquez la variable contenue dans le registre.
(b) Entourez à chaque ligne les registres modifiés (les registres contenant de la ou les variable(s) dont

1
Code

a=b+c
TI
la valeur diffère de sa valeur en mémoire).

intermédiaire
Code machine

LD R0, b
R0
b
Registres
R1 R2

LD R1, c b c

ADD R2, R0,R1 b c (a)

LU
2 d =e * f LD R0,e e c (a)

LD R1, c e f (a)

MUL R0, R0, R1 (d) f (a)

3 e=a-d SUB R0, R2, R0 (e) f (a)

SO

4 f=a+f ADD R1, R2, R1 (e) (f) (a)

stop return f ST f, R1 (e) f (a)

4.3. Supposons le même code intermédiaire:

10
 # CODE
intermédiaire
1 a=b+c
2 d =e * f
3 e=a-d
4 f=a+f
stop return f

(a) (3pts) Construisez le graphe dirigé acyclique (DAG) de ce bloc.

ON
TI
LU

(b) (3pts) D’après le DAG que vous avez construit et le “return” de ce bloc, pouvez-vous proposer une
réduction de code ? Si OUI, donnez la réduction de code et justifiez. Si NON, justifiez pourquoi.
Les opérations pour créer e et d ne sont pas nécessaire. Le nouveau code est donc
SO

# CODE
intermédiaire
1 a=b+c
4 f=a+f
stop return f

11
5 Arbre d’activation
Supposons les fonctions suivantes, servant à calculer un nombre de Fibonacci:
A( int i ) {
i f ( i >2) {
A( i −1);
B( i ) ;
}
else {

ON
C( ) ;
}
}
B( i ) {
i f ( i >1)
B( i −2);
}
C( ) {
return ;
}

Enter(A(i))
TI
5.1. (5pts) Indiquez les séquences d’activations pour la fonction A(i) avec pour paramètre i=3.

Enter(A(2))
Enter(C())
Leave(C())
Leave(A(2))
LU
Enter(B(3))
Enter(B(1))
Leave(B(1))
Leave(B(3))
Leave(A(3))

5.2. (2pts) Indiquez l’état de la pile pendant l’exécution du deuxième appel à B rencontré dans l’ordre des
séquences d’activation pour l’exemple précédent (question 5.1).
SO

ATTENTION: Il y a peut-être plus de cases que nécessaires dans ce tableau.

A(3) - B(3)- B(1)

12
6 Gestion de la mémoire et ramasse-miettes
Pendant le cours, nous avons vu plusieurs stratégies d’allocation de mémoire. Supposons la fragmentation
de mémoire suivante: Les blocs sont numérotés de 1 à 5, et leur taille et état (libre ou occupé) sont indiqués

ON
pour chacun. Supposons que le dernier bloc mémoire ayant été alloué soit le bloc 2.
6.1. Vous voulez allouer un espace mémoire pour un bloc de taille= 1.
Pour chaque sous-question, une représentation de cette même mémoire est fournie. Veuillez compléter le
dessin en coloriant l’espace alloué selon la stratégie d’allocation. On suppose que les espaces non coloriés
sont libres et les espaces coloriés sont alloués/occupés.
(a) (2pts) Quel est l’état de la mémoire après une allocation utilisant la stratégie “first fit”?

TI
LU

(b) (2pts) Quel est l’état de la mémoire après une allocation utilisant la stratégie “best fit”?
SO

13
 (c) (2pts) Quel est l’état de la mémoire après une allocation utilisant la stratégie “next fit”?

ON
6.2. (5pts) En général, parmi ces trois stratégies (“first fit”, “best fit”, “next fit”):

TI
(a) quelle stratégie préféreriez-vous utiliser?
(b) Quels sont ses avantages?
(c) Quels sont ses inconvénients?
Deux réponses possibles ici:
Soit Best fit:
(+) moins de fragmentation
LU
(−) il faut parcourir toute la mémoire/lent
(−) ne tire pas profit de la localité spatiale
Soit next-fit:
(+) profite de la localité spatiale
(+) rapide
(−) peut créer pas mal de fragmentation, potentiellement moins que first fit (donc un (+))

Si les étudiants mettent les deux, ils faut mettre tous les arguments.
SO

14