===== TD 2 : Analyse Syntaxique Descendante =====

==== Grammaire récursive ====

^ Grammaire G0 ^
| E | -> | E+T %%|%% T |
| T | -> |T*F %%|%% F |
| F | -> | (E) %%|%% id %%|%% cte |

Cette grammaire est récursive à gauche. Pour la dérécursiver, nous observons que
  * E -> T ou T+T ou T+...+T
  * F -> F ou F*F ou F*...*F

Ainsi, on redéfinit 
  - E->TE' 
  - E'-> +TE' %%|%% e
  - T ->  FT'
  - T' -> *FT' %%|%% e
  - F -> (E) %%|%% id %%|%% cte



Pour mémoire, les conventions de la notation BNF incluent:

| { ... }  | 0 à n fois successives |
| [ ... ]  | 0 ou 1 fois |
| ( ... )  | groupe d'options |
|  %%|%% | ou  |

On écrira cette grammaire sous la forme BNF, qui est utilisé pour l'analyseur (yacc/bison) :

  *  E:: T {+T}
  *  T:: F {*F}
  *  F:: '('E')' %%|%% id %%|%% cte

Notre grammaire dérécursivée sera exprimée :  E:: T({+T} %%|%% e) ??

==== Analyseur pour cette grammaire ====

Dans l'analyseur, l'on écrit une fonction par règle : que faire pour prendre en compte chaque lecture d'UL.  Ainsi, nous aurons des fonctions read_E(), read_T(), read_F(), read_id(), read_cte(), qui détecte d'éventuelles erreurs et construisent 

  expr
  read_E(){
    expr result, other;
    result = read_T();
    if (result!=NULL){
      while (read_char('+') ){
      other = read_T();
      if (other==NULL) error(1);
      result = new Add(result,other);
      }
    }
    return result;
  }

  expr
  read_T(){
    expr result, other;
    result = read_F();
    if (result!=NULL) {
      while (read_char('*')){
        other = read_F();
        if (other==NULL) error(1);
        result = new Mult(result, other);
      }
    }
    return result;
  }
  
  expr
  read_F(){
    expr result;
    if (read_char('(')){
      result = read_E();
      if (result==NULL) error(1);
      if (!read_char(')')) error;
    }
    else if (read_id()) result = new Id(last_id);
    else if (read_cte()) result = new Cte(last_int);
    return result;
  }

  - ''read_char() '' est une fonction booléenne qui consomme un caractère de yylex() et le compare à son argument.
  - ''read_id()'' lit l'UL suivante et, s'il s'agit bien d'un identifiant, il l'ajout à une table de strings (var globale), augmente le compteur de strings last_id, et répond ''True''; répond ''False'' sinon.
  - ''read_cte()'' lit l'UL suivante et, s'il s'agit bien d'un integer, il l'ajout à une table (ou liste) de integers (var globale), augmente le compteur de integers last_integer, et répond ''True''; répond ''False'' sinon.
  - nous n'avons pas abordé le ''typedef expr'' ni le fonctionnement de ''new Id(last_id)'' et ''new Cte(last_int)''.




==== Grammaire des expressions rationnelles ====


==== Analyseur LL(1) pour des structures de contrôle ====

> Construire un analyseur LL(1) pour des structures de contrôle d'un pseudo Pascal de la forme ''if ... then ...endif'', ''if...then...else...endif'', ''while...do...endot'', et ''id = E'', dans lesquelles une liste d'instructions est composée d'instructions séparées par un point-virgule.  Pour ne pas surcharger la grammaire, on considère dans la suite que les symboles E pour les expressions arithmétiques et C pour les expressions conditionnelles sont des symboles terminaux.

| I -> "if"  C  "then"  B  "endif" |
| B -> id = E %%|%% I %%|%% J %%|%% W |
| J -> "if"  C  "then"  B  "else"  B  "endif"  |
| W -> "while"  C  "do"  B  "endo"  |

  - T -> T' ';' T  |  e
  - T' -> I  |  W  |  A
  - I -> "if" C  "then"  T  "endif" | "if"  C  "then"  T  "else"  T  "endif"
  - W -> "while"  C  "do"  T  "endo"
  - A -> Id  "="  E
  - I -> "if"  C  "then"  T  ["else" T ] "endif" -- hein?

==== Reprise  ====

  E -> E u T 
    |  T
  T -> TF
    | F
  F -> G'*'
    | G
  G -> (E)
    | 'a'
    | 'b'
    | 'c'

=== Dérécursivation ===

^Règle^ Production  ^
| 1 | E -> T E' |
| 2 | E' -> u T E' |
| 3 | E' -> e  |
| 4 | T -> F T' |
| 5 | T' -> F T' |
| 6 | T' -> e |
| 7 | F -> G F'  |
| 8 | F' -> '*' |
| 9 | F' -> e |
| 10 | G -> (E) |
| 11 | G -> a |
| 12 | G -> b |
| 13 | G -> c |

De là nous construisons les First et Follow : 

^  X  ^ First(X)  ^ Follow(X)  ^ Explication  ^
|  E  | { (, a, b, c }  | { $, ) } |  |
|  E'  | { u, e } | {$, ) } |  |
|  T  | { (, a, b, c }  | { u, $, ) } | First(E')+Follow(E) |
|  T'  | { (, a, b, c }  | { u, $, ) } | Follow(T)  |
|  F  | { (, a, b, c }  | { (, a, b, c, u, $ }  | First(T') & ? |
|  F'  | { *, e }  | { (, a, b, c, u, $, ) }  |  |
|  G  | { (, a, b, c }  |  { *, (, a, b, c, u, $ ) }  |  |
  

==== Analyseur LL(1) -- suite et fin ====