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.
  1. 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. (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.

  3. (4 points / 30) L'examen des règles montre que : On en déduit la table Suivant :
    E T F
    ) $ ) $ + ) $ + *
    qui permet de résoudre les conflits :

    La grammaire G est donc SLR(1).

  4. (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.

  5. (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.