Corrigé de l’examen de compilation
Énsiie, semestre 3
18 janvier 2011
Exercice 1 : Analyse syntaxique (8 points)
w F irst(w)
aAa a w F ollow(w)
1. F irst(b)∩F ollow(A) 6= ∅ donc la gram-
bAba b A ab
b b
maire G1 n’est pas dans LL(1).
Automate déterministe LR(1)
A →b • [b]
O
S →b • Aba[$]
S → • aAa[$] b / A → • b[b] A / S →bA • ba[$]
S → • bAba[$]
A → • [b]
a b
S →a • Aa[$]
A → • b[a]
b / A →b • [a] S →bAb • a[$]
A → • [a]
A a
S →aA • a[$]
a / S →aAa • [$] S →bAba • [$]
S →b • Aba[$]
On voit un conflit shift/reduce dans l’état A → • b[b] : on peut décaler b ou
A → • [b]
1
réduire A → . La grammaire n’est donc pas LR(1). A fortiori, elle n’est pas LR(0),
ni LL(1).
2. On a L(G1 ) = {aa; aba; bba; bbba}. La grammaire
S →aA
S →bbA
A →a
A →ba
reconnaît le même langage et est LL(1) (le calcul des ensembles F irst est trivial)
et LR(0) : l’automate déterministe est
S → • aA b / S →b • bA
S → • bbA
a b
S →a • A S →bb • A
A→•a A→•a
A → • ba A → • ba
A
a b
A b
| { a $ #
S →aA• A →a• A →b • a S →bbA•
a
A →ba•
w F irst(w)
Dd f
Ee f
3. On voit que les ensembles F irst ne sont pas deux-à-deux dis-
f f
Cc f
C f
joint, la grammaire n’est pas LL(1).
2
Automate déterministe LR(0) :
C → •Dd
C → •Ee
f
C → •f / C → f•
D → •Cc
E → •Cc
D E
C
D →C •c '
C →D•d C →E•e
E →C •c
c d e
D → Cc•
C → Dd• C → Ee•
E → Cc•
D → Cc•
On voit un conflit reduce/reduce dans l’état où on peut réduire par
E → Cc•
D → Cc ou par E → Cc. Par conséquent la grammaire n’est pas LR(0).
Automate déterministe LR(1) :
C → •Dd[$ c]
C → •Ee[$ c]
f
C → •f [$ c] / C → f • [$ c]
D → •Cc[d]
E → •Cc[e]
D E
C
! (
D → C • c[d]
C → D • d[$ c] C → E • e[$ c]
E → C • c[e]
c d e
D → Cc • [d]
C → Dd • [$ c] C → Ee • [$ c]
E → Cc • [e]
Ici, il n’y a pas de conflit ; la grammaire est LR(1).
Pour rendre la grammaire LL(1), on applique les techniques habituelles :
3
– mise en forme récursive directe :
C →Ccd
C →Cce
C →f
– élimination de la récursivité à gauche :
C →f C 0
C 0 →cdC 0
C 0 →ceC 0
C 0 →
– factorisation à gauche :
C →f C 0
C 0 →cC”
C 0 →
C” →dC 0
C” →eC 0
On peut vérifier que la grammaire obtenue est bien LL(1).
Pour obtenir une grammaire LR(0), seule la mise en forme récursive directe est
nécessaire, on a alors l’automate
C → • Ccd
f
C → • Cce / C → f• C → Ccd•
=
C →•f
d
C
C →C • cd C →Cc • d
c / e / C → Cce•
C →C • ce C →Cc • e
Exercice 2 : Pile d’appel (8 points)
1. – f : il faut sauvegarder $ra en début d’appel car il est écrasé par les appels à i
et g ; il faut sauvegarder $a0 contenant x avant l’appel à g car il est utilisé par
la suite ; il n’est pas nécessaire de sauvegarder $a1, qui contient le lien statique,
car il n’est pas utilisé.
4
– g : il faut sauvegarder $ra en début d’appel car il est écrasé par les appels à h
et i ; il faut sauvegarder $a1 et $a2 contenant b et c avant l’appel à h car ils
sont utilisés par la suite ; il n’est pas nécessaire de sauvegarder $a0, qui contient
a, car il n’est pas utilisé après l’appel à h.
– h : il ne faut pas sauvegarder $ra car il n’y a pas d’appel qui l’écraserait ; de
même, les registres $a0–$a3 n’ont pas besoin d’être sauvegardés.
– i : idem.
2. f : g: h: i:
$ra e t n
$a0 = x lien statique lien statique
y $ra
$a1 = b
$a2 = c
u
On peut choisir de sauvegarder les registres dans un ordre différent.
3. ¬ $a0 1
$a1 indef (lien statique) r trame de f
$a2 indef indef 1
$a3 indef 4 ←$sp
$v0 indef
$ra r
$a0 1
$a1 4
r trame de f
$a2 1 1
$a3 4 5
$v0 indef 1 trame de i
$ra ® ←$sp
® $a0 1 (restauré)
$a1 4 r trame de f
$a2 1 1
$a3 4 5 ←$sp
$v0 -2
$ra ®
1. sauvegardé uniquement avant l’appel à g
5
¯ $a0 -2
$a1 -2
r trame de f
$a2 début de trame de g 1
$a3 1 -2
$v0 -2 -2 trame de g
$ra °
±
1
-2
0
-1 ←$sp trame de h
° $a0 -2
$a1 1 (restauré après appel) r trame de f
$a2 -2 (restauré après appel) 1
$a3 1 -2
$v0 -3 -2 trame de g
$ra °
±
1
-2
0 ←$sp
$a0 1
$a1 -2 r trame de f
$a2 -2 1
$a3 1 -1
$v0 -3 1 trame de i
$ra ± ←$sp
± $a0 1
$a1 -2 r trame de f
$a2 -2 1
$a3 1 -1 ←$sp
$v0 -2
$ra ±
4. addi $sp, $sp, -4 # création de la trame
lw %0, -4($a2) # debut de trame de f dans %0
lw %1, -4(%0) # valeur de x dans %1
add %2, %1, $a1 # calcul de la valeur de t
sw %2, 0($sp) # stockage de t sur la pile
6
add $v0, %2, $a0 # valeur de retour
addi $sp, $sp, 4 # destruction de la trame
jr $ra # retour à l’appelant
Exercice 3 : Allocation de registres (5 points)
1.
1 : neutre := 0;
2 : abs := neutre;
3 : opp := -x;
/ 4 : opp > x / 8 : abs := x;
5 : tmp := x;
6 : x := opp;
7 : opp := tmp;
2. instruction vivantes avant vivantes apres
1 x x neutre
2 x neutre x
3 x x opp
4 x opp x opp
5 x opp opp tmp
6 opp tmp x tmp
7 x tmp x opp
8 x
3.
tmp x abs
opp neutre
4. Quelque soit le critère choisi :
– fusionner abs et neutre
7
– simplifier abs/neutre
– spiller tmp
– simplifier x
– simplifier opp
Le seul choix possible concerne l’ordre des deux dernières étapes. On obtient le
coloriage :
tmp x abs
opp neutre
Exercice 4 : Reaching definitions (9 points)
1. i Reach((avant, i), x) Reach((après, i), x)
i1 i1
i2 i1 i2
i3 i1 i2 i1 i2
i4 i1 i2 i4
2. [
Reach((avant, i), x) = Reach((après, j), x)
j→i
3.
Reach((après, i), %v) = {i}
i redéfinit %v donc de tous les chemins qui arrivent après i, seul celui partant de
i ne redéfinit pas %v.
Reach((après, i), w) = Reach((avant, i), w) pour w 6= %v
i ne redéfinit pas w. Si on a un chemin d’une instruction j au point avant i qui ne
redéfinit pas w, alors en complétant ce chemin pour aller après i on ne redéfinit
toujours pas w.
4. On pose T = ({avant; après} × Instr) × Var → P(Instr). On a Reach ∈ T .
Comme ensemble des parties, (P(Instr), ⊆) est un treillis complet, donc (T , ⊆)˙
(ordre point-à-point) l’est aussi. On définit une fonction F : T → T telle que
[
F (f )((avant, i), w) = f ((après, j), w)
j→i
F (f )((après, i), w) ={i} si i définit w
F (f )((après, i), w) =f ((avant, i), w) si i ne définit pas w
8
˙ donc par le théorème de Knaster-
On peut vérifier que F est monotone dans (T , ⊆),
Tarski, elle admet des points fixes. On vérifie facilement que Reach est un point
fixe de F . Il s’agit du plus petit car on peut montrer que tout point fixe de F
surapproxime les ensembles Reach.
5. pour toute instruction i
pour toute variable v
Reach((avant,i),v) ← ∅
Reach((apres,i),v) ← ∅
W ← Instr
tant que W 6= ∅
retirer i de W, si possible sans prédécesseur dans W
pour tout v
pour tout j tel que j→i
Reach((avant,i),v) ← Reach((avant,i),v) ∪ Reach((apres,j),v)
si definit(i, v)
tmp ← i
sinon
tmp ← Reach((avant,i),v)
si tmp 6= Reach((apres,i),v)
ajouter à W les successeurs de i
Reach((apres,i),v) ← tmp
