%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.