%token ID
%%
expr : ID '=' expr
| expr '+' terme
| terme
;
terme : terme '*' facteur
| facteur
;
facteur : '(' expr ')'
| ID
;
et en annexe,
le fichier produit par l'option -v de yacc
(en fait, bison).
Attention : la lecture de cette annexe est indispensable
à la résolution des questions de cette partie.
State 10 contains 1 shift/reduce conflict.
Grammar
rule 1 expr -> ID '=' expr
rule 2 expr -> expr '+' terme
rule 3 expr -> terme
rule 4 terme -> terme '*' facteur
rule 5 terme -> facteur
rule 6 facteur -> '(' expr ')'
rule 7 facteur -> ID
state 0
ID shift, and go to state 1
'(' shift, and go to state 2
expr go to state 3
terme go to state 4
facteur go to state 5
state 1
expr -> ID . '=' expr (rule 1)
facteur -> ID . (rule 7)
'=' shift, and go to state 6
$default reduce using rule 7 (facteur)
state 2
facteur -> '(' . expr ')' (rule 6)
ID shift, and go to state 1
'(' shift, and go to state 2
expr go to state 7
terme go to state 4
facteur go to state 5
state 3
expr -> expr . '+' terme (rule 2)
$ go to state 15
'+' shift, and go to state 8
state 4
expr -> terme . (rule 3)
terme -> terme . '*' facteur (rule 4)
'*' shift, and go to state 9
$default reduce using rule 3 (expr)
state 5
terme -> facteur . (rule 5)
$default reduce using rule 5 (terme)
state 6
expr -> ID '=' . expr (rule 1)
ID shift, and go to state 1
'(' shift, and go to state 2
expr go to state 10
terme go to state 4
facteur go to state 5
state 7
expr -> expr . '+' terme (rule 2)
facteur -> '(' expr . ')' (rule 6)
'+' shift, and go to state 8
')' shift, and go to state 11
state 8
expr -> expr '+' . terme (rule 2)
ID shift, and go to state 12
'(' shift, and go to state 2
terme go to state 13
facteur go to state 5
state 9
terme -> terme '*' . facteur (rule 4)
ID shift, and go to state 12
'(' shift, and go to state 2
facteur go to state 14
state 10
expr -> ID '=' expr . (rule 1)
expr -> expr . '+' terme (rule 2)
'+' shift, and go to state 8
'+' [reduce using rule 1 (expr)]
$default reduce using rule 1 (expr)
state 11
facteur -> '(' expr ')' . (rule 6)
$default reduce using rule 6 (facteur)
state 12
facteur -> ID . (rule 7)
$default reduce using rule 7 (facteur)
state 13
expr -> expr '+' terme . (rule 2)
terme -> terme . '*' facteur (rule 4)
'*' shift, and go to state 9
$default reduce using rule 2 (expr)
state 14
terme -> terme '*' facteur . (rule 4)
$default reduce using rule 4 (terme)
state 15
$ go to state 16
state 16
$default accept
E E
/|\ / | \
/ | \ / | \
a = E E + T
/|\ /|\ |
/ | \ / | \ |
E + T a = E F
| | | |
T F T c
| | |
F c F
| |
b b
| Action | Etat | Pile |
| 0 | 0 | |
| empiler | 1 | 0 ID 1 |
| empiler | 6 | 0 ID 1 = 6 |
| empiler | 1 | 0 ID 1 = 6 ID 1 |
| réduire par la règle 7 | 5 | 0 ID 1 = 6 facteur 5 |
| réduire par la règle 5 | 4 | 0 ID 1 = 6 terme 4 |
| réduire par la règle 3 | 10 | 0 ID 1 = 6 expression 10 |
| empiler | 8 | 0 ID 1 = 6 expression 10 + 8 |
| empiler | 12 | 0 ID 1 = 6 expression 10 + 8 ID 12 |
| réduire par la règle 7 | 5 | 0 ID 1 = 6 expression 10 + 8 facteur 5 |
| réduire par la règle 5 | 13 | 0 ID 1 = 6 expression 10 + 8 terme 13 |
| réduire par la règle 2 | 10 | 0 ID 1 = 6 expression 10 |
| réduire par la règle 1 | 3 | 0 expression 3 |
| 15 | ||
| succès | 16 |
La seconde colonne est redondante, puisque l'état de l'automate est en sommet de pile ; mais cette colonne accélère la correction !
Plus précisément, l'algorithme de calcul de Suivant donne, comme dans le cas de la grammaire ETF :
Lorsqu'aucune règle de priorité n'est spécifiée, yacc choisit d'empiler plutôt que de réduire : c'est ce qui permet de traiter correctement l'ambiguïté de la construction "if ... then ... else". Ici, c'est aussi le bon choix, qui donne priorité à l'addition sur l'affectation.
affect : ID '=' affect
| expr
;
expr :expr '+' terme
| terme
;
terme : terme '*' facteur
| facteur
;
facteur : '(' affect ')'
| ID
;
Ne pas oublier de modifier la règle pour les parenthèses,
qui encadrent le nouvel axiome. Noter que G' reconnaît ainsi
l'instruction : a = b = c.