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

1. E→TE'
2. E'→ +TE' | e
3. T → FT'
4. T' → *FT' | e
5. F → (E) | id | cte

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

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) ??

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;
}

1. read_char() est une fonction booléenne qui consomme un caractère de yylex() et le compare à son argument.
2. 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.
3. 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.
4. nous n'avons pas abordé le typedef expr ni le fonctionnement de new Id(last_id) et new Cte(last_int).

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.

1. T → T' ';' T | e
2. T' → I | W | A
3. I → “if” C “then” T “endif” | “if” C “then” T “else” T “endif”
4. W → “while” C “do” T “endo”
5. A → Id ”=” E
6. I → “if” C “then” T [“else” T ] “endif” – hein?

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

De là nous construisons les First et Follow :