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.
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.
| E | T | F |
|---|---|---|
| ) $ | ) $ + | ) $ + * |
La grammaire G est donc SLR(1).
| 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
|
(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.
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.