Analyse syntaxique, examen de compilation, janvier 1997

Annexe
Corrigé

Sujet

Soit G la grammaire ETF, à laquelle on a ajouté une règle d'affectation, où, comme en C, une affectation peut être considérée à son tour comme une expression. Voici le fichier, dans le format reconnu par yacc, qui décrit cette grammaire :
%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.
  1. G est-elle ambiguë ? On demande une réponse argumentée brièvement, mais précisément.

  2. G est-elle SLR(1) ? On demande une réponse argumentée brièvement, mais précisément.

  3. Détailler le fonctionnement de l'analyseur syntaxique pendant l'analyse de a=b+c en utilisant une table à trois colonnes : action (décalage ou réduction), état de l'automate, contenu de la pile. Utiliser évidemment les numéros d'états et de règles fournis en annexe.

  4. Pourquoi yacc ne signale-t-il pas de conflit dans l'état 1 ?

  5. Expliquer le conflit de l'état 10, et sa résolution par yacc. Expliquer la raison du choix de yacc ; ce choix est-il le bon ?

  6. Comment transformer la grammaire G pour éviter le conflit de l'état 10 ?

Annexe

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

Corrigé

  1. G est ambiguë ; par exemple l'expression a = b + c possède deux arbres de dérivation :
           E                     E
          /|\                  / | \
         / | \                /  |  \
        a  =  E              E   +   T
             /|\            /|\      |
            / | \          / | \     |
           E  +  T        a  =  E    F
           |     |              |    |
           T     F              T    c
           |     |              |
           F     c              F
           |                    |
           b                    b
         
    

  2. G n'est pas SLR(1), puisqu'elle est ambiguë. Indépendamment de la question précédente, yacc signale un conflit, donc G n'est pas LALR(1), et encore moins SLR(1).

  3. 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 !

  4. Yacc ne signale pas de conflit dans l'état 1, car le conflit entre "empiler '='" et "réduire par la règle 7" peut être résolu en calculant Suivant (facteur), qui ne contient pas le symbole terminal '='.

    Plus précisément, l'algorithme de calcul de Suivant donne, comme dans le cas de la grammaire ETF :

  5. Le conflit de l'état 10, entre "empiler '+'" et "réduire par la règle 1" ne peut pas être résolu comme précédemment, puisque Suivant (expression) contient le symbole terminal '+'. G n'est donc pas SLR(1) ; en fait G est ambiguë, puisque les deux actions en conflit conduisent à des arbres de dérivation corrects et distincts (voir question 1).

    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.

  6. Pour transformer G en une grammaire G' non ambiguë, il faut ajouter un niveau de priorité, et donc un symbole non terminal :
      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.