Analyse descendante des grammaires récursives à gauche


  1. Le problème et sa solution
    1. Principe
    2. Exemple : la notation polonaise postfixée

  2. La notation traditionnelle à précédences
    1. Traitons d'abord le cas simple à un seul niveau de priorité.
    2. La situation usuelle à deux niveaux de priorité

  3. Mise en œuvre effective
    1. Factorisation
    2. Programmation en C++, en application directe de la théorie

  1. Le problème et sa solution

  2. La notation traditionnelle à précédences

    La règle d'association à gauche de la syntaxe traditionnelle se traduit par des règles récursives à gauche.
    1. Traitons d'abord le cas simple à un seul niveau de priorité.

      La grammaire "naturelle" :
      1. E -> E Op T
      2. E -> T
      3. T -> ( E )
      4. T -> Var
      5. T -> Cte

      se transforme en
      1. E -> T S
      2. E -> T
      3. S -> Op T S
      4. S -> Op T
      5. T -> ( E )
      6. T -> Var
      7. T -> Cte
    2. La situation usuelle à deux niveaux de priorité

      La grammaire habituelle
      1. E -> E Opadd T
      2. E -> T
      3. T -> T Opmul F
      4. T -> F
      5. F -> ( E )
      6. F -> Var
      7. F -> Cte

      se transforme en
      1. E -> T S1
      2. E -> T
      3. S1 -> Opadd T S1
      4. S1 -> Opadd T
      5. T -> F S2
      6. T -> F
      7. S2 -> Opmul F S2   
      8. S2 -> Opmul F
      9. F -> ( E ) 
      10. F -> Var
      11. F -> Cte

  3. Mise en œuvre effective

    1. Factorisation

      La grammaire ci-dessus ne se prête pas à la programmation,
      car comment choisir entre les deux règles issues de chaque non-terminal
      autre que F ?

      On doit donc recourir à une seconde transformation (par factorisation) qui va nous ramener à des choix
      qui pourront être effectués sur la base du prochain caractère à lire (procédé dit du look-ahead).
      On pose X = S1 ∪ {ε}, Y = S2 ∪ {ε}, et on écrit :

      E -> T X
      X -> + T X
      X ->
      ε  ------ interprétation : si le prochain caractère à lire n'est pas '+', ôter 'X' de la pile
      T -> F Y
      Y -> * F Y
      Y ->
      ε  ------ interprétation : si le prochain caractère à lire n'est pas '*', ôter 'Y' de la pile
      F -> ( E )
      F -> Var
      F -> Cte


    2. Programmation en C++, en application directe de la théorie

      Le programme suit exactement le modèle exposé au cours 18.
      Sa rédaction est donc quasi-automatique !
      Voici une trace d'exécution :

      x+y*((z+3+x*y)+z)*2*z
      x -- E
      x -- T X
      x -- F Y X
      x -- x Y X
      + -- Y X
      + -- X
      + -- + T X
      y -- T X
      y -- F Y X
      y -- y Y X
      * -- Y X
      * -- * F Y X
      ( -- F Y X
      ( -- ( E ) Y X
      ( -- E ) Y X
      ( -- T X ) Y X
      ( -- F Y X ) Y X
      ( -- ( E ) Y X ) Y X
      z -- E ) Y X ) Y X
      z -- T X ) Y X ) Y X
      z -- F Y X ) Y X ) Y X
      z -- z Y X ) Y X ) Y X
      + -- Y X ) Y X ) Y X
      + -- X ) Y X ) Y X
      + -- + T X ) Y X ) Y X
      3 -- T X ) Y X ) Y X
      3 -- F Y X ) Y X ) Y X
      3 -- 3 Y X ) Y X ) Y X
      + -- Y X ) Y X ) Y X
      + -- X ) Y X ) Y X
      + -- + T X ) Y X ) Y X
      x -- T X ) Y X ) Y X
      x -- F Y X ) Y X ) Y X
      x -- x Y X ) Y X ) Y X
      * -- Y X ) Y X ) Y X
      * -- * F Y X ) Y X ) Y X
      y -- F Y X ) Y X ) Y X
      y -- y Y X ) Y X ) Y X
      ) -- Y X ) Y X ) Y X
      ) -- X ) Y X ) Y X
      ) -- ) Y X ) Y X
      + -- Y X ) Y X
      + -- X ) Y X
      + -- + T X ) Y X
      z -- T X ) Y X
      z -- F Y X ) Y X
      z -- z Y X ) Y X
      ) -- Y X ) Y X
      ) -- X ) Y X
      ) -- ) Y X
      * -- Y X
      * -- * F Y X
      2 -- F Y X
      2 -- 2 Y X
      * -- Y X
      * -- * F Y X
      z -- F Y X
      z -- z Y X
      OK



      On observe que
      1. la transformation de la boucle while en une boucle for n'est pas aussi évidente
        que pour les grammaires traitées au cours 18.
      2. l'adaptation du programme en vue de la génération de l'arbre d'expression
        est encore moins évidente !