corrigé exercice03 compilation

Corrigé de l'exercice 3
Le barème indiqué (total pour l'exercice : 19 points) est sur 30 points, et la note finale (sur 20) est obtenue par une règle de trois.
Automate (6 points sur 30)
règle 1 expr -> terme '+' expr
règle 2 expr -> terme
règle 3 terme -> facteur '*' terme
règle 4 terme -> facteur
règle 5 facteur -> '(' expr ')'
règle 6 facteur -> ident

état 0

expr -> . terme '+' expr
expr -> . terme
terme -> . facteur '*' terme
terme -> . facteur
facteur -> . '(' expr ')'
facteur -> . ident

ident décaler et aller en 1
'(' décaler et aller en 2

terme aller en 3
facteur aller en 4

état 1

facteur -> ident . (règle 6)

réduire par la règle 6

état 2

facteur -> '(' . expr ')'
expr -> . terme '+' expr
expr -> . terme
terme -> . facteur '*' terme
terme -> . facteur
facteur -> . '(' expr ')'
facteur -> . ident

ident décaler et aller en 1
'(' décaler et aller en 2

expr aller en 5
terme aller en 3
facteur aller en 4

état 3

expr -> terme . '+' expr
expr -> terme . (règle 2)

'+' décaler et aller en 6

autres cas : réduire par la règle 2

état 4

terme -> facteur . '*' terme
terme -> facteur . (règle 4)

'*' décaler et aller en 7

autres cas : réduire par la règle 4

état 5

facteur -> '(' expr . ')'

')' décaler et aller en 8

état 6

expr -> terme '+' . expr
expr -> . terme '+' expr
expr -> . terme
terme -> . facteur '*' terme
terme -> . facteur
facteur -> . '(' expr ')'
facteur -> . ident

ident décaler et aller en 1
'(' décaler et aller en 2

expr aller en 9
terme aller en 3
facteur aller en 4

état 7

terme -> facteur '*' . terme
terme -> . facteur '*' terme
terme -> . facteur
facteur -> . '(' expr ')'
facteur -> . ident

ident décaler et aller en 1
'(' décaler et aller en 2

terme aller en 10
facteur aller en 4

état 8

facteur -> '(' expr ')' . (règle 5)

réduire par la règle 5

état 9

expr -> terme '+' expr . (règle 1)

réduire par la règle 1

état 10

terme -> facteur '*' terme . (règle 3)

réduire par la règle 3




Pour résoudre le problème de la terminaison de l'analyse on peut ajouter :

état 0
expr aller en 11

état 11
$ accepter

mais cette précision est tout à fait facultative dans le cadre de l'examen.

(2 points / 30) L'état 3 présente un conflit lorsque le caractère courant est '+' : décaler ou réduire T en E. L'état 4 présente un conflit lorsque le caractère courant est '*' : décaler ou réduire F en T.

(4 points / 30) L'examen des règles montre que :
'+' appartient à Suivant (T)
Suivant (E) est inclus dans Suivant (T)
'*' appartient à Suivant (F)
Suivant (T) est inclus dans Suivant (F)
')' appartient à Suivant (E)
On en déduit la table Suivant :
E T F
) $ ) $ + ) $ + *

qui permet de résoudre les conflits :

dans l'état 3, lorsque le caractère courant est '+', il est impossible de réduire T en E, car '+' n'appartient pas à Suivant (E).

dans l'état 4, lorsque le caractère courant est '*', il est impossible de réduire F en T, car '*' n'appartient pas à Suivant (T).
La grammaire G est donc SLR(1).


(2 points / 30) Arbres de dérivation :
Grammaire ETF
Grammaire G

E
/ | \
/ | \
E + T
/ | \ |
/ | \ ...
E + T tn
/ | \ |
... ...
E + T tn-1
| |
| ...
T t2
|
...
t1

E
/ | \
/ | \
T + E
| / | \
... / | \
t1 T + E
| / | \
... ...
t2 T + E
| |
... |
tn-1 T
|
...
tn




L'addition est donc associative à gauche pour ETF, et associative à droite pour G. Certain(e)s parlent de dérivation gauche (resp. droite), ce qui n'a rien à voir. Il est inutile (et absurde) de détailler les dérivations de T en ti dont on ignore tout.
(3 points / 30) Piles des analyseurs ascendants :


Grammaire ETF Grammaire G
Après lecture de t1 0 E 3 0 T 3
Après lecture de + t2 0 E 3 0 T 3 + 6 T 3
Après lecture de + t3 0 E 3 0 T 3 + 6 T 3 + 6 T 3

Dans le cas de la grammaire ETF, T est réduit en E après lecture de t1, car le caractère courant est '+' ; de même E + T est réduit en E après lecture de t2, car le caractère courant est '+', etc. Dans le cas de la grammaire G c'est seulement après lecture de tn, lorsque le caractère courant est '$' (symbole de fin de texte), que T est réduit en E, puis T + E en E, et ainsi de suite de droite à gauche.

La pile de l'analyseur ascendant pour G a donc tendance à croître beaucoup plus que dans le cas de la grammaire ETF.


(2 points / 30) Le comportement de la pile étudié précédemment est valable pour toute comparaison d'une règle récursive gauche et d'une règle récursive droite. Dans le cas de la grammaire C transformée, on peut craindre un débordement de pile dès qu'on compile une suite d'instructions un peu longue.
Note : prétendre que les instructions seront lues (ou analysées) en ordre inverse de leur écriture, est absurde, car la modification proposée ne porte pas sur l'analyse des instructions individuelles.