Chapitre 6    Analyse Syntaxique

6.1  Définitions et notations

6.1.1  Mots

Exemples

1. Mots sans carré
   
   Soit l'alphabet A = {a, b,c }. On construit la suite de mots suivante f₀ = a, pour n ³ 0, on obtient récursivement f_n+1 à partir de f_n en remplaçant a par abc, b par ac et c par b. Ainsi:
   
   
   f₁ = abc    f₂ = abcacb    f₃ = abcacbabcbac
   
   Il est assez facile de voir que f_n est un facteur gauche de f_n+1 pour n ³ 0, et que la longueur de f_n est 3 × 2^n-1 pour n ³ 1. On peut aussi montrer que pour tout n, aucun facteur de f_n n'est un carré, c'est à dire que si gg est un facteur de f_n alors g = e. On peut noter à ce propos que, si A est un alphabet composé des deux lettres a et b, les seuls mots sans carré sont a,b,ab,ba,aba,bab. La construction ci-dessus, montre l'existence de mots sans carré de longueur arbitrairement grande sur un alphabet de trois lettres.
   
   
2. Expressions préfixées
   
   Les expressions préfixées, considérées au chapitre 3 peuvent être transformées en des mots sur l'alphabet A = {+, *, (, ), a }, on remplace tous les nombres par la lettre a pour en simplifier l'écriture. En voici deux exemples,
   
   
   f = (* a a)     g = ( * ( + a (* a a)) (+ (* a a) (* a a)))
   
   
3. Un exemple proche de la compilation
   
   Considérons l'alphabet A suivant, où les ``lettres'' sont des mots sur un autre alphabet: A = {begin, end, if, then, else, while, do, ;, p, q, x, y, z }
   
   Alors f = while p do begin if q then x else y ; z end
   est un mot de longueur 13, qui peut se décomposer en
   
   
   f = while p do begin   g   ; z end
   
   où g = if q then x else y.

6.1.2  Grammaires

• L'alphabet A est dit alphabet terminal, tous les mots construits par la grammaire sont constitués de lettres de A.
  
  
• L'alphabet X est dit alphabet auxiliaire, ses lettres servent de variables intermédiaires servant à engendrer des mots. Une lettre S₀ de X, appelée axiome, joue un rôle particulier.
  
  
• Les règles sont toutes de la forme:
  S ® u
  où S est une lettre de X et u un mot comportant des lettres dans A È X.

Exemple

On part de l'axiome S₀ et on choisit une règle de la forme S₀ ® u. Si u ne contient aucune lettre auxiliaire, on a terminé. Sinon, on écrit u = u₁Tu₂. On choisit une règle de la forme T ® v. On remplace u par u' = u₁vu₂. On répète l'opération sur u' et ainsi de suite jusqu'à obtenir un mot qui ne contient que des lettres de A.

Exemple

Notations

6.2  Exemples de Grammaires

6.2.1  Les systèmes de parenthèses

6.2.2  Les expressions arithmétiques préfixées

6.2.3  Les expressions arithmétiques

6.2.4  Grammaires sous forme BNF

AdditiveExpression:
 MultiplicativeExpression
 AdditiveExpression + MultiplicativeExpression
 AdditiveExpression - MultiplicativeExpression

MultiplicativeExpression:
 UnaryExpression
 MultiplicativeExpression * UnaryExpression
 MultiplicativeExpression / UnaryExpression
 MultiplicativeExpression 
UnaryExpression:
 PreIncrementExpression
 PreDecrementExpression
 + UnaryExpression
 - UnaryExpression
 UnaryExpressionNotPlusMinus

UnaryExpressionNotPlusMinus:
 PostfixExpression
   UnaryExpression
 ! UnaryExpression
 CastExpression

PostfixExpression:
 Primary
 Name
 PostIncrementExpression
 PostDecrementExpression

Primary:
 PrimaryNoNewArray
 ArrayCreationExpression

PrimaryNoNewArray:
 Literal
 this
 ( Expression )
 ClassInstanceCreationExpression
 FieldAccess
 MethodInvocation
 ArrayAccess

6.3  Arbres de dérivation et arbres de syntaxe abstraite

---

Figure 6.1 : Arbre de dérivation de aabbabab

---

---

Figure 6.2 : Arbre de dérivation d'une expression arithmétique

---

---

Figure 6.3 : Arbre de syntaxe abstraite de l'expression

---

6.4  Analyse descendante récursive

class ASA {

  char op;
  ASA filsG, filsD;


  ASA (char x, ASA a, ASA b) {
    op = x;
    filsG = a;
    filsD = b;
  }

  static String f;
  static int i = 0;

  static ASA expression() throws ErreurDeSyntaxe {

    ASA a = terme();
    if (f.charAt(i) == '+') {
        ++i;
        return new ASA('+', a, expression());
    }
    else return a;
  }

  static ASA terme() throws ErreurDeSyntaxe {

    ASA a = facteur();
    if (f.charAt(i) == '*') {
        ++i;
        return new ASA ('*', a, terme());
    }
    else return a;
  }

  static ASA facteur() throws ErreurDeSyntaxe {

    if (f.charAt(i) == '(') {
        ++i;
        ASA a = expression();
        if (f.charAt(i) == ')') {
            ++i;
            return a;
            }
        else throw new ErreurDeSyntaxe(i);
    }
    else if (f.charAt(i) == 'a') {
            ++i;
            return new ASA ('a', null, null);
         }
         else throw new ErreurDeSyntaxe(i);
  }
}

class ErreurDeSyntaxe extends Exception {
  int position;

  public ErreurDeSyntaxe (int i) {
    position = i;
  }
}

static boolean Analyse (String u, f) {

  if (f.equals(u))
      return true;
  else {
      Mettre f et u sous la forme f= gxh, u=gyv où x ¹ y
      if (y Ï A)
          Pour toute règle y ® w faire
               if (Analyse(g + w + v, f))
                   return true;
      return false;
  }
}

static int pos = 1;

static boolean analyseDescendante (String u, String f) {

  while (f.charAt(pos) == u.charAt(pos))
      ++pos;
  if (f.charAt(pos) == '$' && u.charAt(pos) == '#')
      return true;
  else {
      char y = u[pos];
      if (estAuxiliaire(y))
          for (int i = 0; i < nbRegles[y]; ++i) {
              String v = u.substring(0, pos) + regle[y][i] 
                       + u.substring(pos+1);
              if (Analyse (v, f))
                  return true;
          }
      return false;
  }
}

Remarques

1. Cette procédure ne donne pas de résultat lorsque la grammaire est ce qu'on appelle récursive à gauche (le mot récursif n'a pas ici tout à fait le même sens que dans les procédures récursives), c'est à dire lorsqu'il existe une suite de dérivations partant d'un S de X et conduisant à un mot u qui commence par S. Tel est le cas pour la première forme de la grammaire des expressions arithmétiques infixes qui ne peut donc être analysée par l'algorithme ci dessus.
   
   
2. Les transformations que l'on applique au mot u s'expriment bien à l'aide d'une pile dans laquelle on place le mot à analyser, sa première lettre en sommet de pile.
3. Cette procédure est très coûteuse en temps lors de l'analyse d'un mot assez long car on effectue tous les essais successifs des règles et on peut parfois se rendre compte, après avoir pratiquement terminé l'analyse, que la première règle appliquée n'est pas la bonne. Il faut alors tout recommencer avec une autre règle et éventuellement répéter plusieurs fois. La complexité de l'algorithme est ainsi une fonction exponentielle de la longueur du mot à analyser.
   
   
4. Si on suppose qu'aucune règle ne contient un membre droit égal au mot vide, on peut diminuer la quantité de calculs effectués en débutant la procédure d'analyse par un test vérifiant si la longueur de u est supérieure à celle de f. Dans ce cas, la procédure d'analyse doit avoir pour résultat false. Noter que dans ces conditions la procédure d'analyse donne un résultat même dans le cas de grammaires récursives à gauche.

6.5  Analyse LL

Expressions préfixées

• Si f_i commence par a, alors u_i+1 = g_iav_i
• Si f_i commence par (+, alors u_i+1 = g_i(+SS)v_i
• Si f_i commence par (*, alors u_i+1 = g_i(*SS)v_i
• Un autre début pour f_i signifie que f n'est pas une expression préfixée correcte, il y a une erreur de syntaxe.

static Arbre ArbSyntPref() {
  Arbre a;
  char x;

  if (f.charAt(pos) == 'a') {
      a = NouvelArbre('a', null, null);
      ++pos;
  } else if (f.charAt(pos) == '(' && 
            (f.charAt(pos+1) == '+' || f.charAt(pos+1) == '*')) {
      x = f.charAt(pos + 1);
      pos = pos + 2;
      a = NouvelArbre(x, ArbSyntPref(), ArbSyntPref());
      if (f.charAt(pos) == ')')
           ++pos;
      else 
           erreur(pos);
  } else 
      erreur(pos);
  return a;
}

 
static boolean Analyse(String f, int pos) {
    int i;

    pos = 1;
    while (Pile.valeur(p) == f.charAt(pos)) {
        Pile.supprimer(p);
        ++pos;
    }
    if (Pile.vide(p) && f.charAt(pos) == '$')
        return true;
    else {
        y = Pile.valeur(p);
        if (! estAuxiliaire(y))
           return false;
        else {
           i = Predicteur (y, pos, pos+k-1);
           if (i != Omega) {
                System.out.println (y, '->', regle[y][i]);
                Pile.inserer(regle[y,i], p);
                return Analyse (f, pos);
            } else
                return false;
        }
    }
}

6.6  Analyse ascendante

• Réduire aSb en S s'il est suivi de b ou s'il est situé en fin de mot.
  
  
• Réduire ab en S s'il est suivi de b ou s'il est situé en fin de mot.
  
  
• Réduire abS en S quelle que soit sa position.
  
  
• Réduire aSbS en S quelle que soit sa position.

• Réduire a en F quelle que soit sa position.
  
  
• Réduire (E) en F quelle que soit sa position.
  
  
• Réduire F en T s'il n'est pas précédé de *.
  
  
• Réduire T*F en T quelle que soit sa position.
  
  
• Réduire T en E s'il n'est pas précédé de + et s'il n'est pas suivi de *.
  
  
• Réduire E + T en E s'il n'est pas suivi de *.
  
  
• Réduire E - T en E s'il n'est pas suivi de *.

6.7  Evaluation

static int evaluer(Arbre x) {

    if (x.valeur == 'a')
        return x.valeur;
    else if (x.valeur == '+')
        return evaluer(x.filsG) + evaluer(x.filsD);
    else if (x.valeur == '-')
        return evaluer(x.filsG) - evaluer(x.filsD);
    else if (x.valeur == '*')
        return evaluer(x.filsG) * evaluer (x.filsD);
}

6.8  Programmes en C

type asa =
  Feuille of char 
| Noeud of char * asa * asa;;

exception erreur_de_syntaxe of int;;

let f = " (a + a * a ) ";;
let i = ref 0;;

let rec expression () =
  let a = terme () in
  if f.[!i] = `+` then begin
    incr i;
    Noeud (`+`, a, expression ()) end
  else a

and terme () =
  let a = facteur () in
  if f.[!i] = `*` then begin
    incr i;
    Noeud (`*`, a, terme ()) end
  else a

and facteur () =
  if f.[!i] = `(` then begin
    incr i;
    let a = expression () in
    if f.[!i] = `)` then begin
      incr i;
      a end
    else raise (erreur_de_syntaxe !i) end
  else
  if f.[!i] = `a`
  then begin
    incr i;
    Feuille `a` end 
  else raise (erreur_de_syntaxe !i);;

(* Prédicat définissant les non-terminaux *)
let est_auxiliaire y = ... ;;

(* règle.(s).(i) est la ième règle
 dont le membre gauche est s *)
let règle =
  [|  [| s00; s01; ... |];
      [| s10; s11; ... |];
      [| si0; si1; ... |];
  ... |];;

(* nbrègle.(s) est le nombre de règles
 dont le membre gauche est s *)
let nbrègle = [| s0; ...; sn |];;

(* Fonction auxiliaire sur les chaînes
 de caractères: remplacer s pos char
 renvoit une copie de la chaîne s
 avec char en position pos *)
let remplacer s pos char =
  let s1 = make_string (string_length s) ` ` in
  blit_string s 0 s1 0 (string_length s);
  s1.[pos] <- char;
  s1;;

let analyse_descendante f u =
  let b = ref false in
  let pos = ref 0 in
  while f.[!pos] = u.[!pos] do incr pos done;
  if f[!pos] = `$` && u.[!pos] = `#`
  then 
    true
  else
    let y = u.[!pos] in
    if est_auxiliaire y
    then begin
      let i = ref 0 in
      let ynum = int_of_char y - int_of_char `A` in
      while not !b && !i <= nbrègle.(ynum) do
        b := analyse_récursive
              (remplacer (u, !pos, règle.(ynum).(!i)), f);
       else incr i
     done;
     !b end
    else false;;

(* Analyse LL(1), voir page X *)
let rec arbre_synt_pref () =
  if f.[!pos] = `a`
  then begin
    incr pos;
    Feuille `a` end
  else
  if f.[!pos] = `(`
  && f.[!pos + 1] = `+`
  || f.[!pos + 1] = `*`
  then begin
    let x = f.[!pos + 1] in
    pos := !pos + 2;
    let a = arbre_synt_pref () in
    let b = arbre_synt_pref () in
    if f.[!pos] = `)`
    then Noeud (x, a, b)
    else erreur (!pos) end
  else erreur(!pos);;

(* Évaluation, voir page X *)
type expression =
| Constante of int
| Opération of char * expression * expression;;

let rec évaluer = function
| Constante i -> i
| Opération ('+', e1, e2) -> évaluer e1 + évaluer e2
| Opération ('*', e1, e2) -> évaluer e1 * évaluer e2;;