Précédent Remonter Suivant
Chapitre 2 Analyse Syntaxique

U n compilateur transforme un programme écrit en langage évolué en une suite d'instructions élémentaires exécutables par une machine. La construction de compilateurs a longtemps été considérée comme une des activités importantes en informatique, elle a suscité le développement de nombreuses techniques et théories maintenant classiques. La compilation d'un programme est réalisée en au moins trois phases, la première (analyse lexicale) consiste à découper le programme en petites entités: opérateurs, mots réservés, variables, constantes numériques, alphabétiques, etc. La deuxième phase (analyse syntaxique) consiste à expliciter la structure du programme sous forme d'un arbre, appelé arbre de syntaxe abstraite, chaque noeud de cet arbre correspond à un opérateur et ses fils aux opérandes sur lesquels il agit. La troisième phase (génération de code) construit la suite d'instructions du micro-processeur à partir de l'arbre de syntaxe abstraite; elle peut donner lieu à des développements sophistiqués, constituant toujours un domaine de recherche très actif.

Nous nous limiterons ici à une vision simple des deux premières étapes. Elle permettent d'illustrer l'utilisation des notions d'automates (analyse lexicale) et de grammaires (analyse syntaxique). En outre, l'analyse syntaxique fait partie des nombreuses situations où l'on transforme une entité, qui se présente sous une forme plate et difficile à manipuler, en une forme structurée adaptée à un traitement efficace. Le calcul symbolique ou formel, le traitement automatique du langage naturel constituent d'autres exemples. Notre but n'est pas de donner ici toutes les techniques permettant d'écrire un analyseur syntaxique, mais de suggérer à l'aide d'exemples comment il faudrait faire. L'ouvrage de base pour l'étude de la compilation est celui de A. Aho, R. Sethi et J. Ullman [21]. On peut aussi se référer aux premiers chapitres de [30] pour une présentation plus théorique.

2.1 Caractères

Les caractères constituent souvent dans un langage de programmation un type primitif. C'est bien le cas en Java. Les constantes de type caractère sont notées entre apostrophes 'a', 'b', 'c', etc. Les caractères spéciaux sont définis avec la barre renversée '\n' (line-feed), '\r' (retour charriot), '\t' (tabulation), '\\' (backslash), '\'' (apostrophe), '\"' (guillemet). La différence entre line-feed et retour-charriot est hélas subtile, car très dépendante du système d'exploitation. Dans le système Unix, le passage à la ligne suivante se fait avec le seul caractère line-feed. En MacOS, c'est retour-charriot. En Windows, c'est la séquence retour-charriot suivi de line-feed, une remarque à savoir pour le seul caractère figurant sur chaque ligne! Souvent, les éditeurs de texte lisent indifféremment les trois formats.

Selon les langages de programmation, la distinction entre caractères et entiers est plus ou moins stricte. En Java, les caractères forment un sous-ensemble des entiers. Ce sont des entiers courts non-signés. Ils occupent complètement un mot de 16 bits, et ne peuvent être convertis implicitement qu'à des entiers signés sur 32 bits de type int.

La fonction associant à chaque caractère un entier est la fonction de codage des caractères. Plusieurs codes ont successivement existé; ces codes deviennent plus complexes avec l'internationalisation des langages de programmation pour représenter les caractères par exemple en indi, en chinois, en coréen, ou en alphabet cyrillique, ainsi que les caractères accentués du français, de l'espagnol et des langages d'Europe centrale. Le consortium Unicode et l'ISO (International Organization for Standardization) ont défini un code universel, standard ISO 10646-1 utilisant 65534 valeurs.

Les 127 premières valeurs constituent le code ASCII (American Standard Codes for Information Interchange) des caractères américains (c'est-à-dire les caractères latins non-accentués) donné en hexadecimal par la table 2.1. On remarque que les codes des chiffres sont des valeurs consécutives, ainsi que pour les lettres minuscules et majuscules. Les 20 premières valeurs, non imprimables, peuvent être obtenues en appuyant simultanément sur la touche CTRL (contrôle) du clavier et sur celle du caractère correspondant quatre lignes plus bas dans le tableau. Ainsi nul, soh, \t, \n s'obtiennent en effectuant CTRL-@, CTRL-A, CTRL-I, CTRL-J.

    0   1   2   3   4   5   6   7   8   9   a   b   c   d   e   f  
00   nul   soh   stx   etx   eot   enq   ack   bel   \\   \t   \n   vt   np   \r   so   si  
10   dle   dc1   dc2   dc3   dc4   nak   syn   etb   can   em   sub   esc   fs   gs   rs   us  
20       !   "   #   $   %   &   '   (   )   *   +   ,   -   .   /  
30   0   1   2   3   4   5   6   7   8   9   :   ;   <   =   >   ?  
40   @   A   B   C   D   E   F   G   H   I   J   K   L   M   N   O  
50   P   Q   R   S   T   U   V   W   X   Y   Z   [   \   ]     _  
60   `   a   b   c   d   e   f   g   h   i   j   k   l   m   n   o  
70   p   q   r   s   t   u   v   w   x   y   z   {   &   }   ~   del  

Figure 2.1 : Le code ASCII en hexadécimal


Les 256 premières valeurs de l'Unicode constituent le code ISO 8859-1 (Latin-1) avec les lettres accentuées ou les caractères particuliers latins.

En fait, l'Unicode a maintenant dépassé les 16 bits, sa nouvelle norme (codage ISO 10646-2) demande 31 bits pour inclure encore plus de langues. Malheureusement, beaucoup de programmes utilitaires des vieux systèmes d'exploitation tels que le système Unix, conçu en 1970, (ou son incarnation publique Linux), utilisent la représentation ASCII; par exemple, les caractères des noms de fichiers ne peuvent dépasser les 7 bits de l'ASCII. Pour rester compatible (compatibilité ascendante), une représentation en longueur variable, l'UTF-8, a été définie, comme indiqué sur la table 2.2. En UTF-8, les codes ASCII sont inchangés et tiennent toujours sur un octet; les codes ISO-Latin tiennent sur deux octets (le premier commençant par les 3 bits 110; le deuxième par les 2 bits 10; la valeur significative tenant facilement sur les 11 bits restants); les autres codes tiennent sur trois octets (le premier commençant par 1110; les deux autres par 10; la valeur significative tenant aussi facilement sur les 16 bits restants). Le nombre des premiers bits valant 1 donnent le nombre d'octets utilisés pour le cas non-ASCII; la garde 10 en tête de chacun des autres octets permet la synchronisation en cas de perte d'octets.

    Unicode         Code UTF-8
                           
    0000 -- 007f         0xxxxxxx            
    0080 -- 07ff         110xxxxx     10xxxxxx      
    0800 -- ffff         1110xxxx     10xxxxxx     10xxxxxx

Figure 2.2 : Le code de longueur variable UTF-8 en binaire


En Java, quelques fonctions permettent de caractériser les caractères sans avoir à considérer leur code. Par exemple isLetter, isDigit, isLetterOrDigit donnent un résultat booléen signifiant que leur argument est une lettre, un chiffre ou l'un des deux. On pourrait les définir ainsi (dans le cas ASCII);
static boolean isDigit (char c) {
  return '0' <= c && c <= '9';
}
static boolean isLetter (char c) {
  return 'a' <= c && c <= 'z' && 'A' <= c && c <= 'Z';
}
static boolean isLetterOrDigit (char c) {
  return isLetter(c) || isDigit(c);
}

La fonction inverse du codage prend une valeur entière et essaie de la traduire en caractère. Il faut faire attention à ne pas confondre les deux valeurs. Ainsi le caractère correspondant au chiffre x sera donné par la formule '0' + x, c'est à dire les valeurs hexadécimales c0 pour 0, c1 pour 1, c2 pour 2, etc.

2.2 Chaînes de caractères

Les chaînes de caractères sont en première approximation des tableaux de caractères. Mais, souvent leur représentation est plus compacte. En Java, les chaînes de caractères sont représentés par des objets de la classe String. La longueur de la chaîne s est donnée par x.length(). Attention, c'est un appel à la méthode length (avec des parenthèses) et non un champ de donnée comme dans le cas des tableaux. Quelques autres méthodes utiles permettent d'écrire s.equals(t) pour tester l'égalité de s et t, ou s.indexOf(c) pour donner la première occurence de c dans s, ou s.charAt(i) pour rendre le caractère à la position i dans s. L'opérateur + produit la concaténation de deux chaînes. Ainsi s+t est la chaîne constituée de s puis de t. Si l'une des deux opérandes n'est pas une chaîne, l'autre est transformée en chaîne de caractère en lui appliquant la méthode toString (de sa classe). Enfin, les chaînes de caractères sont immuables, c'est-à-dire des constantes non modifiables. Ceci simplifie le partage des chaînes de caractères, par exemple, entre plusieurs processus concurrents (cf. le chapitre sur la concurrence).

L'expression Integer.parseInt(s) associe à la chaîne de caractères s l'entier qu'elle dénote en décimal. Symétriquement, x+"" produit la chaîne de caractères correspondant à la représentation décimale de x. La fonction parseInt peut être définie par:
static int parseInt (String s) throws NumberFormatException {
  int r = 0;
  for (int i = 0; i < s.length(); ++i) {
    if (!Character.isDigit (s.charAt(i)))
      throw new NumberFormatException();
    r = 10 * r + s.charAt(i) - '0';
  }
  return r;
}

La fonction parseInt ne fait que calculer, pour la chaîne s constituée des caractères s0, s1, ...sp, le polynôme Si=0p si 10p-i par la méthode de Horner. Réciproquement, la fonction symétrique, appelons-la integerToString, s'écrit:
static String integerToString (int x) {
  String s = "";
  while (x != 0) {
    s = s + ('0' + x % 10);
    x = x / 10;
  }
  return s;
}

Cette dernière fonction existe aussi en standard en Java. On l'obtient en calculant l'expression new Integer(x).toString() ou plus simplement x+"" comme déjà mentionné.
Exercice 7   Ecrire un programme pour la méthode toString de la classe Integer.

Exercice 8   Ecrire une fonction integerToString avec deux arguments x et b retournant la chaîne de caractères représentant l'entier x dans la base b.

Toutefois, la fonction integerToString n'est pas très efficace, puisqu'à chaque itération une nouvelle chaîne de caractères s est construite avec seulement un caractère de plus. Au total, elle prend un espace-mémoire en O(l 2) si on pose l = log10 x. Il est impossible de faire autrement avec les variables de la classe String dont les valeurs sont imuables. Fort heureusement, la classe StringBuffer permet de manipuler des chaînes de caractères modifiables en réservant un espace mémoire paramétrable à leur création. Le programme précédent qui s'écrit comme suit prend maintenant un espace-mémoire en O(l):
static String integerToString (int x) {
  StringBuffer s = new StringBuffer();
  while (x != 0) {
    s = s.append ('0' + x % 10);
    x = x / 10;
  }
  return new String(s);
}

2.3 Alphabets, mots, langages

D'un point de vue théorique, une chaîne de caractères est appelé un mot; les caractères sont des lettres; l'ensemble des lettres constitue un alphabet. Autrement dit, si A est un alphabet, un mot construit sur A est une suite finie f = a1 a2 ... an de lettres prises dans A (n ³ 0); l'entier n est la longueur de f. On note par e le mot vide, c'est le mot de longueur 0. Le produit de deux mots f et g est obtenu en écrivant f puis g à la suite, on le note fg. Donc la longueur de fg est égale à la somme des longueurs de f et de g. Un mot f est un facteur de g s'il existe deux mots g' et g'' tels que g = g' f g''; f est facteur gauche de g si g = fg''; c'est un facteur droit si g = g'f. L'ensemble des mots sur l'alphabet A est noté A*. On remarque qu'on a trivialement e f = f e = f et que (fg)h = f(gh) (lois d'un monoïde).
Exemple 1  Mots sans carré. Soit l'alphabet A = { a, b, c }. On construit la suite de mots suivante f0 = a, et, pour n ³ 0, on obtient fn+1 à partir de fn en remplaçant a par abc, b par ac et c par b. Ainsi:
f0 = a      f1 = abc      f2 = abcacb      f3 = abcacbabcbac
Il est assez facile de voir que fn est un facteur gauche de fn+1 pour n ³ 0, et que la longueur de fn est 3 × 2n-1 pour n ³ 1. On peut aussi montrer que, pour tout n, aucun facteur de fn n'est un carré, c'est à dire que, si gg est un facteur de fn, alors g = e. Remarquons à 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.

Exemple 2  Expressions préfixées. Les expressions arithmétiques en notation (polonaise) préfixe peuvent être considérées comme 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

Exemple 3  Un mini-langage de programmation. 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 ; zend
est un mot de longueur 13, qui peut se décomposer en
f = while p dobegin   g   ; zend      g = if q then x elsey

Un langage est un ensemble de mots. Par exemple, si A= {a, b}, le langage L = {an bn | n ³ 0} des mots contenant n fois la lettre a suivis d'autant de fois de b. On peut aussi considérer le langage des L' des mots contenant autant de fois a que de fois b. Bien sûr, on a L Ì L'. Si A' = { (, ) }, on peut considérer le langage D des mots sur A' bien parenthésés, c'est-à-dire avec exactement une parenthèse fermante pour chaque parenthèse ouvrante. Par exemple, ()(()()) Î D. Si on remplace la parenthèse ouvrante par la lettre a et la parenthèse fermante par la lettre b, on obtient un langage L'' bien parenthésé sur A, et on a L Ì L'' Ì L' Ì A*.

Le produit de mots peut être étendu au produit de langages. Si L et L' sont deux langages sur l'alphabet A, le produit LL' désignera l'ensemble des mots obtenus par produit d'un mot de L et de L'.
LL' = { fg | fÎ L,   g Î L'}
On notera aussi Ln pour le produit LL... L itéré n fois. Par convention L0 = { e }. Enfin l'opération étoile qui désigne les mots formés par produits de mots de L est définie par:
L* = L0 È L È L2 ... È Ln ...
Remarquons que cette notation est bien cohérente avec l'écriture utilisée, A*, pour désigner tous les mots sur l'alphabet A.

2.4 Expressions régulières

Les expressions régulières permettent de dénoter simplement un ensemble de mots. Par exemple pour désigner tous les mots du langage {an b | n ³ 0 }, on écrit a*b, c'est-à-dire les mots contenant un nombre quelconque (éventuellement nul) de a suivi d'un b. De même b*a représente l'ensemble des mots commençant par un nombre quelconque de b suivi d'un seul a. Pour représenter l'union de ces deux ensembles, on écrit a*b + b*a.


Définition 1   Soit A un alphabet. Une expression régulière est toute expression formée à partir du mot vide e, des lettres de A avec les opérations produit, somme et étoile. Le langage [[ e ]] dénoté par l'expression régulière e est défini récursivement par:
[[ e ]] = { e }     [[ a ]] = { a }     [[ (e) ]] = [[ e ]]
[[ e e' ]] = [[ e ]] [[ e' ]]     [[ e* ]] = [[ e ]]*     [[ e + e' ]] = [[ e ]] È [[ e' ]]

Parfois l'opération somme e+e' est aussi écrite avec une barre verticale, donnant e | e'. La première notation est plus utilisée en informatique théorique, la deuxième dans les manuels de description des langages de programmation. Nous utilisererons indistinctement les deux notations. Une autre notation fréquente est e+ pour désigner e* sans la chaîne vide e. Ainsi e* = e + e+.
Exemple 4  Mots contenant un facteur donné. Soit A = {a, b} et u Î A*. L'ensemble des mots ayant u en facteur s'écrit (a+b)*u(a+b)*. Par exemple, si u = aab, on obtient (a+b)*aab(a+b)*.

Exemple 5  Mots contenant un nombre pair de lettres. Sur l'alphabet A = {a, b}. L'expression régulière (b* a b* a)* désigne les mots contenant un nombre pair de a. On peut aussi utiliser (b + a b* a)* pour ce même ensemble. Maintenant, si on exige un nombre pair de a et de b, on arrive à l'expression pas si évidente ((a+ba(aa)* b)(b(aa)* b)*(a+ba(aa)* b) + b(aa)* b)*.

Exemple 6  Noms de fichiers. Dans les systèmes de fichiers, on opère souvent sur tous les fichiers dont le nom comporte un suffixe donné, par exemple.html. On les désigne par une expression régulière de la forme *.html. Le symbole ? est aussi parfois utilisé. Formellement ? est un joker dénotant l'alphabet de toutes les lettres de code ASCII, et * est une abbréviation pour (?)*. Ainsi a*.java désigne tous les fichiers dont le nom commence par un a et de suffixe .java; de même, .???* dénote tous les fichiers dont le nom a au moins 3 lettres commençant par un point.

Exemple 7  Identificateurs et nombres. Soit A = {a, b, ... z } et C = {0, 1, 2, ... 9 }. Ecrivons [a-z] pour dénoter A et [0-9] pour C. Un nom de variable ou de fonction (un identificateur) est représenté par l'expression régulière [a-z]([a-z]+[0-9])*. Une constante entière est dénotée par [0-9]+. Donc un identificateur est une suite de chiffres ou de lettres commençant toujours par une lettre; un nombre est une suite non vide de chiffres.

Exemple 8  Motifs de filtrage. Dans les systèmes informatiques, les expressions régulières sont aussi utilisées pour retrouver des motifs dans des fichiers, par exemple pour imprimer les lignes contenant le motif (comme le fait la commande grep du système Unix -- get regular expression). On utilise des caractères fictifs ^ et $ pour dénoter le début et la fin de ligne. Alors les lignes vides sont obtenues par le motif "^$"; les lignes blanches par "^_*$"; une suite non vide de caractères blancs est "__*"; etc. Ici le sens de * n'est pas le même que pour les noms de fichiers; a* a le sens normal a* des expressions régulières.

Les expressions régulières ont fait l'objet d'études intensives, leur structure est bien plus riche qu'on ne pourrait le penser a priori. Elles n'ont pas vraiment de représentations canoniques. Mais, si on rajoute 0 pour Ø et si on pose 1 = e et e £ e' pour e + e' = e', on obtient un certains nombres de lois définissant ce qu'on appelle une algèbre de Kleene:
(1) e + f = f + e     
(2) e + (f + g) = (e + f) + g     
(3) e + 0 = e     
(4) e + e = e     
(5) e(fg) = (e f) g     
(6) e = e  1 = e     
(7) e (f + g) = e f + e g     
(8) (e + f) g = e g + f g     
(9) eE  0 = 0     
(10) 1 + e e * = e *     
(11) 1 + e * e = e *     
(12) f + e g £ g  Þ  e*f £ g      (12') e g £ g  Þ  e*g £ g
(13) f + g e £ g  Þ  fe* £ g      (13') g e £ g  Þ  ge* £ g

En fait, toutes les égalités entre expressions régulières peuvent être obtenues à partir de ces 13 équations (Les équations 12-12' et 13-13' sont équivalentes). Par exemple, pour montrer que a* a* = a *, on note que 1 + a a* = a* par (10). D'où a a* £ a* par définition de £. Donc a* a* £ a* par (12'). Réciproquement, a* a* = (1 + a a*) a* par (10). D'où a* a* = a* + a a* a* par (8) et (6). Donc a* £ a* a*.
Exercice 9   Montrer qu'on a dans les algèbres de Kleene: e £ e' £ e   Û   e = e'.

Exercice 10   Montrer en utilisant les lois des algèbres de Kleene que (a*)* = a *, (a *b)* a * = (a + b)*, a (ba)* = (ab)* a, et a * = (aa)* + a (aa)*.

Exercice 11   Montrer les équations précédentes par des raisonnements directs sans utiliser les algèbres de Kleene.

Exercice 12   Montrer que e = f + ge implique que e = g*f.

2.5 Analyse lexicale

On veut donc extraire un flot de lexèmes dans la très longue chaîne de caractères constituant le texte d'un programme. On élimine tous les caractères inutiles ou redondants. Par exemple, les caractères blancs (espace, tabulation, retour-charriot, line-feed) sont souvent inutiles; un seul suffit plutôt qu'une bonne dizaine consécutifs. De la même manière, les commentaires sont inutiles (pour compiler un programme). Un lexème est une entité importante pour la compilation telle qu'un identificateur, une constante numérique, un opérateur, une chaîne de caractères, une contante caractère, etc.

Comme vu dans l'exemple 7, un identificateur ou une constante entière peuvent être définis par des expressions régulières. Il en va de même pour tous les autres lexèmes. Un nombre flottant est une suite de chiffres suivis éventuellement d'un point (.) et d'une suite de chiffres. Pour la notation de l'ingénieur, c'est un peu plus compliqué puisqu'il faut expliquer les formats de la partie significative et de la partie exposant. Une chaîne de caractères commence et finit par un guillemet ("); à l'intérieur c'est une suite quelconque de caractères différent de guillemet. Toutefois après une barre renversée (\) on peut aussi mettre un guillemet à l'intérieur de la chaîne.

Les définitions de lexèmes sous forme d'expressions régulières sont données par:
lettre = a|b|... z|A|B|... Z|_
chiffre = 0|1|2|3|4|5|6|7|8|9
identificateur = lettre (lettre | chiffre)*
nombre = chiffre+
nombre_flottant = nombre (e | . nombre)
chaine = " ((~")+ \")* "

en adoptant la notation ~c pour désigner les caractères différents de c. Avec de telles définitions, nous pouvons enfin penser à écrire un programme pour rechercher des lexèmes dans une très longue chaîne de caractères. Nous définissons d'abord la représentation des lexèmes dans notre langage de programmation favori. Dans une deuxième phase, on produira le programme correspondant à la description par expressions régulières.

Les lexèmes sont représentés par des objets de la classe Lexeme suivante avec trois champs de données: le champ nature indique si le lexème est un nombre, un identificateur, un opérateur ou un délimiteur comme parenthèse ou crochet ou la fin de fichier; le champ valeur stocke la valeur d'un entier dans le cas où le lexème est un nombre; le champ nom est la chaîne de caractères représentant le nom d'un identificateur dans le cas où le lexème est un identificateur. Ces trois champs ne sont pas utiles simultanément, mais, pour simplifier, nous considérons ces trois champs pour chaque lexème.
class Lexeme {
  final static int L_Nombre = 0, L_Id = 1, L_Plus = '+', L_Moins = '-',
        L_Mul = '*', L_Div = '/', L_ParG = '(', L_ParD = ')',
        L_CroG = '[', L_CroD = ']', L_EOF = -1;
  int nature;
  int valeur;
  String nom;

  Lexeme (int i) { nature = L_Nombre; valeur = i; }
  Lexeme (String s) { nature = L_Id; nom = s; }
  Lexeme (char op) { nature = op; }
}

La fonction Lexeme.suivant retourne le prochain lexème dans le flot d'entrée de l'analyseur lexical. Elle saute les caractères blancs (espace, tabulation, line-feed, retour-chariot) et retourne, selon le premier caractère non-blanc rencontré, un lexème identificateur, nombre entier ou symbole opérateur-délimiteur. La définition des fonctions ident ou nombre suit exactement la valeur de l'expression régulière définissant les lexèmes identificateur ou nombre. La fonction avancer passe au caractère suivant dans le flot d'entrée et le stocke dans la variable globale c.
  static char c;    // caractère courant

  static Lexeme suivant() {
    sauterLesBlancs();
    if (Character.isLetter(c)) return new Lexeme (ident());
    else if (Character.isDigit(c)) return new Lexeme (nombre());
    else switch (c) {
    case '+'case '-'case '*'case '/':
    case '('case ')': avancer(); return new Lexeme (c);
    defaultthrow new Error ("Caractère illégal");
   }
  }

  static void avancer() { c = in.readChar(); }

  static void sauterLesBlancs() {
    while ( Character.isWhitespace (c) )
      avancer();
  }

  static String ident() {
    StringBuffer r;
    while (Character.isLetterOrDigit (c)) {
      r = r.append (c);
      avancer();
    }
    return new String(r);
  }

  static int nombre() {
    int r = 0;
    while (Character.isDigit (c)) {
      r = r * 10 + c - '0';
      avancer();
    }
    return r;
  }

Exercice 13   Compléter le programme pour chercher des lexèmes pour les nombres flottants et les chaînes de caractères de telle manière que sur le texte suivant
class PremierProg {
  public static void main (String[ ] args){
    System.out.println ("Bonjour tout le monde!");
    System.out.println ("fib(20) = " + fib(20));
  }
}

les résultats successifs produits par appel à la fonction Lexeme.suivant seront:
L_Id(class) L_Id(PremierProg) L_AccG L_Id(public) L_Id(static)
L_Id(void) L_Id(main) L_ParG L_Id(String) L_CroG L_CroD L_Id(args)
L_ParD L_AccG L_Id(System) L_Point L_Id(out) L_Point L_Id(println)
L_ParG L_Chaine(Bonjour tout le monde!) L_ParD L_PointVirgule
L_Id(System) L_Point L_Id(out) L_Point L_Id(println) L_ParG
L_Chaine(fib(20) = ) L_Plus L_Id(fib) L_ParG L_Nombre(20) L_ParD
L_ParD L_PointVirgule L_AccD L_AccD L_EOF

Exercice 14   Modifier l'analyseur lexical pour sauter les commentaires comme en Java. (Il va y avoir un problème pour la fin de ligne).

Exercice 15   En se servant d'une pile, simuler une calculette HP, utilisant la notation polonaise suffixe, pour évaluer des expressions arithmétiques.

Notre présentation simplifiée de l'analyse lexicale ne doit pas faire oublier qu'il existe des outils très sophistiqués (comme lex de M. Lesk) permettant d'obtenir automatiquement de très bons analyseurs lexicaux à partir d'une description de haut niveau avec des expressions régulières. Cela simplifie grandement l'écriture de compilateurs, car souvent l'analyse lexicale est délicate à réaliser. En outre, ces outils sont très efficaces pour générer rapidement des automates finis de taille quasi minimale. (La notion d'expression régulière est reliée à la notion d'automate fini que nous verrons plus tard).
2.6 Arbres de syntaxe abstraite

Un compilateur produit un arbre de syntaxe abstraite à partir du texte du programme. En effet, un compilateur teste si le programme est syntaxiquement correct (grâce à la phase d'analyse syntaxique que nous verrons plus loin), mais il en produit aussi une représentation structurée sous forme arborescente, un arbre de syntaxe abstraite. Prenons le simple exemple des expressions arithmétiques construites à partir des nombres et de noms de variables avec les opérateurs +, -, × et /. Un arbre de syntaxe abstraite pour l'expression (x+1)× (3 × y+2) est représenté sur la figure 2.3.


Figure 2.3 : Arbre de syntaxe abstraite


La représentation de ces arbres de syntaxe abstraite, ou ASA, ou termes va se faire grâce à une classe Terme qui définit ce qu'on appelle un type disjonctif dans d'autres langages de programmation (ML): l'ensemble des termes est l'union d'arbres binaires dont les noeuds sont des opérateurs pris parmi +, -, × et /, et les feuilles sont des variables ou des constantes entières. Ce qui nous donne:
class Terme {
  final static int ADD = 0, SUB = 1, MUL = 2, DIV = 3, MINUS = 4,
                   VAR = 5, CON = 6;
  int nature;
  int valeur;
  String nom;
  Terme a1, a2;

  Terme (int t, Terme a) {nature = t; a1 = a; }
  Terme (int t, Terme a, Terme b) {nature = t; a1 = a; a2 = b; }
  Terme (String s) {nature = VAR; nom = s; }
  Terme (int v) {nature = CON; valeur = v; }
}

Comme pour la représentation précédente des lexèmes, les champs de données utilisés correspondent à tous les cas possibles. Le champ nature indique si le noeud correspond à une addition, soustraction, multiplication, un moins unaire, ou s'il s'agit d'une feuille pour les variables et les constantes; le champ nom donne l'identificateur pour les feuilles qui sont des variables; le champ valeur donne la constante entière pour les feuilles qui sont des constantes. Dans le cas de l'exemple de la figure 2.3, l'arbre de syntaxe abstraite est implanté comme indiqué sur la figure 2.4. On peut le construire par les instructions suivantes:


Figure 2.4 : Représentation d'un arbre de syntaxe abstraite



Terme t = new Terme (MUL,
             new Terme (ADD, new Terme ("x"), new Terme (1)),
             new Terme (ADD,
                new Terme (MUL, new Terme (3), new Terme ("y")),
                new Terme (2)));

Les arbres de syntaxe abstraite (ASA) constituent une des structures les plus abstraites associées à un programme. Dans l'exemple précédent, les textes de programme (x+1)× (3 × y+2), ou (x+1)× ((3 × y) +2) ou ((x+1)× (3 × y +(2))) correspondent au même ASA. Les détails de la ``syntaxe concrète ``, avec leurs excès de parenthèses, ont été oubliés. Mais cette expression est, bien sûr, différente de l'expression de la figure 2.5 dont l'ASA est différent. Il correspond à l'expression (x+1)× (3 × (y + 2)).


Figure 2.5 : Un autre arbre de syntaxe abstraite


2.7 Grammaires

Pour construire des ensembles de mots, on utilise la notion de grammaire. Une grammaire G comporte deux alphabets A et VN, un axiome S qui est une lettre appartenant à VN et un ensemble R de règles.
Exemple 9   A = { a, b }, VN = { S, T, U }, l'axiome est S. Les règles sont données par :
S ® aT bS          T ® aT bT          U ® bU aU
S ® bU aS          T ® e          U ® e
S ® e                    

Pour engendrer des mots à l'aide d'une grammaire, on applique le procédé suivant:
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 = u1Tu2. On choisit une règle de la forme T ® v. On remplace u par u' = u1vu2. 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.
Dans la mesure où il y a plusieurs choix possibles à chaque étape, on voit que le nombre de mots engendrés par une grammaire est souvent infini. Mais certaines grammaires peuvent n'engendrer aucun mot. C'est le cas par exemple des grammaires dans lesquelles tous les membres droits des règles contiennent un lettre de VN. On peut formaliser le procédé qui engendre les mots d'une grammaire de façon un peu plus précise en définissant la notion de dérivation. Etant donnés deux mots u et v contenant des lettres de A È VN, on dit que u dérive directement de v pour la grammaire G, et on note v ® u, s'il existe deux mots w1 et w2 et une règle de grammaire S ® w de G tels que v = w1S w2 et u = w1ww2. On dit aussi que v se dérive directement en u. On dit que u dérive de v, ou que v se dérive en u, si u s'obtient à partir de v par une suite finie de dérivations directes. On note alors: v ®* u, ce qui signifie l'existence de w0, w1, ... wn (n ³ 0) tels que w0 = v, wn = u et, pour tout i (0 £ i < n), on a wi® wi+1.

Un mot est engendré par une grammaire G, s'il dérive de l'axiome et ne contient que des lettres de A, l'ensemble de tous les mots engendrés par la grammaire G, est le langage engendré par G; il est noté L( G).

Reprenons la grammaire G de l'exemple 9 et effectuons quelques dérivations en partant de S. Choisissons S ® aTbS, puis appliquons la règle T ® e. On obtient:
S ® aTbS ® abS
On choisit alors d'appliquer S ® b UaS . Puis, en poursuivant, on construit la suite
S ® aTbS ® abS ® abbUaS ® abbbUaUaS ® abbbaUaS ® abbbaaS ® abbbaa
D'autres exemples de mots L ( G) sont bbaa et abbaba obtenus à l'aide de calculs similaires:
S ® bU aS ® bbU aU aS ® bbaU aS ® bbaaS ® bbaa
S ® aT bS ® abS ® abbUaS ® abbaS ® abbabU aS ® abbabaS ® abbaba
Plus généralement, on peut montrer que, pour cet exemple, L ( G) est constitué de tous les mots qui contiennent autant de lettres a que de lettres b.

2.8 Exemples de Grammaires

2.8.1 Les systèmes de parenthèses

Le langage des systèmes de parenthèses joue un rôle important tant du point de vue de la théorie des langages que de la programmation. Dans les langages à structure de blocs, les begin end ou les | \prog| se comportent comme des parenthèses ouvrantes et fermantes. Dans des langages comme Lisp, le décompte correct des parenthèses fait partie de l'habileté du programmeur. Dans ce qui suit, pour simplifier l'écriture, on note a une parenthèse ouvrante et b une parenthèse fermante. Un mot de {a, b}* est un système de parenthèses s'il contient autant de a que de b et si tous ses facteurs gauches contiennent un nombre de a supérieur ou égal au nombre de b. Une autre définition possible est récursive, un système de parenthèses f est ou bien le mot vide (f = e) ou bien formé par deux systèmes de parenthèses f1 et f2 encadrés par a et b (f = af1bf2).

Cette nouvelle définition se traduit sous la forme de la grammaire suivante:

A = { a, b }, VN = { S }, l'axiome est S, les règles sont données par:
S ® aS bS         S ® e
On notera la simplicité de cette grammaire, la définition récursive rappelle celle des arbres binaires, un tel arbre est construit à partir de deux autres comme un système de parenthèses f l'est à partir de f1 et f2. La grammaire précédente a la particularité, qui est parfois un inconvénient, de contenir une règle dont le membre droit est le mot vide. On peut alors utiliser une autre grammaire déduite de la première qui engendre l'ensemble des systèmes de parenthèses non réduits au mot vide, dont les règles sont:
S ® aSbS          S ® aSb          S ® abS          S ® ab
Cette transformation peut se généraliser et on peut ainsi pour toute grammaire G trouver une grammaire qui engendre le même langage, au mot vide près, et qui ne contient pas de règle de la forme S ® e.

2.8.2 Les expressions arithmétiques préfixées

Ce sont grosso modo les expressions que l'on trouve dans le langage Lisp. Dans une expression arithmétique préfixée, les opérateurs figurent avant leurs opérandes. Le nombre de leurs opérandes est délimité par un système de parenthèses. Pour simplifier, les opérandes atomiques (constantes entières ou variables) sont représentées par la lettre a. Leur définition récursive se traduit immédiatement par la grammaire suivante:




A = { +, × , ( , ) , a }, VN = { S }, l'axiome est S, les règles sont données par:

S ® ( + S S )     S ® ( × S S)     S ® a


Deux exemples d'expressions arithmétiques préfixées sont engendrés comme suit:
S   ®  
( T   S   S )
*
®
 
( ×   a   a)
   
S   ®   ( T S S )
   
*
®
 
  ( T ( T S S ) ( T S S ) )
   
*
®
 
  ( T ( T   S ( T   S   S ) ) ( T ( T   S   S ) ( T   S   S ) ) )
   
*
®
 
  ( × ( +   a ( ×   a   a) ) ( + ( ×   a  a) ( ×   a  a) ) )
Cette grammaire peut être généralisée pour traiter des expressions faisant intervenir d'autres opérateurs d'arité quelconque. Ainsi, pour ajouter les symboles Ö , - et /, il suffit de considérer deux nouveaux éléments T1 et T2 dans VN et prendre comme nouvelles règles:




S ® (T1 S )       S ® (T2 S S )       S ® a                        
T1 ® Ö        T1 ® -       T2 ® +       T2 ® ×       T2 ® -       T2 ® /



2.8.3 Les expressions arithmétiques

Il s'agit maintenant de donner une grammaire pour les expressions arithmétiques infixes, c'est-à-dire notées comme en mathématiques. Pour simplifier, on ne considère que les deux opérateurs × et +. Les parenthèses permettent de regrouper les opérations, elles ne sont pas nécessaires pour délimiter un produit dans une somme$ puiwqUe que × est plus prioritaire que +. Dans un premier temps, nous supposons que les opérandes atomiques sont représentées par le symbole a. Les expressions arithmétiques sont donc engendrées par la grammaire suivante:

A = { +, × , ( , ) , a } , VN = { E, P, F}, l'axiome est E, les règles sont données par:
E ® P          P ® F          F ® a
E ® P + E          P ® F × P          F ® ( E )
Un mot engendré par cette grammaire est par exemple:
( a + a ) × ( a × a + a )
Il représente l'expression
(x+1)× (3 × y +2)
dans laquelle les opérandes atomiques sont remplacées par le symbole a.

On peut se convaincre que cette expression est engendrée par la grammaire en commençant la dérivation qui l'engendre à partir de l'axiome:
E   ®   P ® F × P ® ( E ) × P ® ( P+E ) × P
    ®   ( F+E ) × P ® ( a+E ) × P ® ( a+P) × P
    ®   ( a+F) × P ® ( a+a) × P ® ( a+a) × F
    ®   ( a+a) × ( E ) ® ··· ® ( a + a ) × ( a × a + a )

Les lettres de l'alphabet auxiliaire ont été choisies pour rappeler la signification sémantique des mots qu'elles engendrent. Ainsi E, P et F représentent respectivement les expressions, produits et facteurs. Dans cette terminologie, on constate que toute expression est somme de termes et que tout produit est produit de facteurs. Chaque facteur est ou bien réduit à la variable a ou bien formé d'une expression entourée de parenthèses. Ceci traduit les dérivations suivantes de la grammaire.
E ® P + E ® P + P + E ...
*
®
 
P+P+P ... +P
P ® F × P ® F × F × P ...
*
®
 
F× F× F ... × F

La convention usuelle de priorité de l'opération × sur l'opération + explique que l'on commence par engendrer des sommes de termes avant de décomposer les termes en produits de facteurs, en règle générale pour des opérateurs de priorités quelconques on commence par engendrer les symboles d'opérations ayant la plus faible priorité pour terminer par ceux correspondant aux plus fortes.

On peut généraliser la grammaire pour faire intervenir beaucoup plus d'opérateurs. Il suffit d'introduire de nouvelles règles comme par exemple
E ® E - P        P ® P /  F
si l'on souhaite introduire des soustractions et des divisions. Comme ces deux opérateurs ont la même priorité que l'addition et la multiplication respectivement, il n'a pas été nécessaire d'introduire de nouveaux éléments dans VN. Il faudrait faire intervenir de nouvelles variables auxiliaires si l'on introduit de nouvelles priorités.

Nous avons abusivement considéré le symbole a comme représentant unique des facteurs les plus simples. En fait, les expressions arithmétiques sont aussi formées avec des constantes numériques et des noms de variables. En fait, l'alphabet terminal est l'ensemble des lexèmes définis par un analyseur lexical. Dans notre cas, une syntaxe plus réaliste sera définie comme suit:

A = { +, × , ( , ) , id, nombre } , VN = { E, P, F}, l'axiome est E, les règles sont données par:
E ® P          P ® F          F ® id
E ® P + E          P ® F × P          F ® nombre
                      F ® ( E )

2.8.4 Notations abrégées

Plusieurs abréviations existent pour raccourcir la longueur d'une grammaire. Par exemple, on peut factoriser les parties gauche en utilisant la barre verticale ( | ) pour séparer les parties droites possibles. Ainsi la grammaire précédente s'écrirait:
E ® P | P + E                  P ® F | F × P
F ® id | nombre | ( E )                 
Souvent aussi le symbole (:=) tend à remplacer la flèche (®), donnant ainsi pour l'exemple précédent:
E := P | P + E                  P := F | F × P
F := id | nombre | ( E )                 

Mais la forme la plus usuelle de notation abrégée est la BNF, sous laquelle on représente les grammaires des langages de programmation La BNF (Backus Naur Form) tient son nom de John Backus, le concepteur de FORTRAN, et de Peter Naur qui l'ont utilisé pour donner une définition formelle du langage Algol 60.

Dans la convention d'écriture adoptée pour la BNF, les éléments de VN sont des suites de lettres et symboles comme MultiplicativeExpression, UnaryExpression. Les règles ayant le même élément dans leur partie gauche sont regroupées et cet élément n'est pas répété pour chacune d'entre elles. Le symbole ® est remplacé par : suivi d'un passage à la ligne. Quelques conventions particulières permettent de raccourcir l'écriture: one of permet d'écrire plusieurs règles sur la même ligne; les éléments de l'alphabet terminal A sont les mots-clé, comme class, if, then, else, for, ..., et les opérateurs ou séparateurs comme + * / - ; , ( ) [ ] = == < >.

Dans les grammaires données en annexe, on compte dans la grammaire de Java 131 lettres pour l'alphabet auxiliaire et 251 règles. Il est hors de question de traiter ici ce trop long exemple. Nous nous limitons aux exemples donnés plus haut dans lesquels figurent déjà toutes les difficultés que l'on peut trouver par ailleurs.

Notons toutefois que l'on trouve la grammaire des expressions arithmétiques sous forme BNF dans l'exemple de la grammaire de Java donnée en annexe. On trouve en effet à l'intérieur de cette grammaire:
AdditiveExpression:
        MultiplicativeExpression
        AdditiveExpression + MultiplicativeExpression
        AdditiveExpression - MultiplicativeExpression

MultiplicativeExpression:
        UnaryExpression
        MultiplicativeExpression * UnaryExpression
        MultiplicativeExpression / UnaryExpression
        MultiplicativeExpression % UnaryExpression

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

2.9 Analyse syntaxique

Le but de l'analyse syntaxique est de déterminer si un mot appartient ou non au langage engendré par une grammaire. Il s'agit donc, étant donné un mot f de construire la suite des dérivations qui a permis de l'engendrer. Si l'on pratique ceci à la main pour de petits exemples, on peut utiliser la technique classique dite ``essais-erreurs`` consistant à tenter de deviner à partir d'un mot la suite des dérivations qui ont permis de l'engendrer. Cette suite se présente plus clairement sous forme d'un arbre, dit arbre de dérivation ou arbre syntaxique, dont des exemples sont donnés figures 2.6 et 2.7. Il s'agit de ceux obtenus pour les mots aabbabab et (x+1)× (3× y+2) engendrés respectivement par la grammaire des systèmes de parenthèses et par celle des expressions arithmétiques. L'arbre de dérivation de la figure 2.6 est construit progressivement comme suit:
L'étiquette S de la racine de l'arbre est l'axiome de la grammaire. Chaque noeud interne est étiqueté par une variable X non-terminale (appartenant à VN); en outre, le mot u obtenu en lisant de gauche à droite les étiquettes de ses fils est tel que X ® u est une règle de la grammaire. Enfin, le mot f dont on fait l'analyse est constitué des étiquettes des feuilles lues de gauche à droite.


Figure 2.6 : Arbre de dérivation de aabbabab




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


Plusieurs dérivations peuvent correspondre à un même arbre syntaxique. Mais, en général, il n'existe qu'un seul arbre de dérivation pour un mot donné du langage engendré. L'existence de plusieurs arbres de dérivations pour un même mot signifie souvent qu'il existe plusieurs interprétations possibles pour celui-ci. On dit qu'alors la grammaire est ambiguë. Toutes les grammaires données plus haut sont non-ambiguës. En revanche, la grammaire suivante pour les expressions arithmétiques est ambiguë.

A = { +, × , ( , ) , id, nombre } , VN = { E }, l'axiome est E, les règles sont données par:
E ® E + E          E ® id          E ® ( E )
E ® E × E          E ® nombre         
En effet, le mot 4 + 3 × 2 a deux arbres de dérivation distincts comme indiqué sur la figure 2.8. Ils correspondent aux expressions (4+3)× 2 = 14 et 4+(3 × 2) = 10.


Figure 2.8 : Grammaire ambiguë


L'arbre de dérivation est parfois appelé arbre de syntaxe concrète pour le distinguer de l'arbre de syntaxe abstraite. L'arbre de syntaxe abstraite est bien plus compact que le précédent. Il s'obtient par des transformations simples à partir de l'arbre de dérivation. C'est bien ce que fait un analyseur syntaxique.

2.10 Analyse descendante récursive

Deux principales techniques sont utilisées pour effectuer l'analyse syntaxique. Etant donnés une grammaire G et un mot f, il s'agit de construire la suite des dérivations de G conduisant de l'axiome au mot f,
S ® u1 ® u2 ... un-1 ® un = f
La première technique consiste à démarrer de l'axiome S et à tenter de retrouver u1, puis u2 jusqu'à obtenir un = f, c'est l'analyse descendante. La seconde, l'analyse ascendante procède en sens inverse, il s'agit de commencer par deviner un-1 à partir de f puis de remonter à un-2 et successivement jusqu'à l'axiome S. Nous décrivons ici sur des exemples les techniques d'analyse descendante, l'analyse ascendante sera traitée dans un paragraphe suivant.

La première méthode que nous considérons s'applique à des grammaires très particulières, mais que l'on rencontre très souvent. Dans ces cas, l'algorithme d'analyse syntaxique devient une traduction fidèle de l'écriture de la grammaire. On utilise pour cela autant de fonctions qu'il y a d'éléments dans VN, chacune d'entre elles est destinée à reconnaître un mot dérivant de l'élément correspondant de VN. Prenons le cas des expressions arithmétiques de la section 2.8.3, l'analyseur récursif descendant s'écrit:

static Lexeme lc;  // lexème courant
static void avancer() {lc = Lexeme.suivant(); }

static Terme expression() {
  Terme t = produit(); switch (lc.nature) {
  case Lexeme.L_Plus: avancer(); return new Terme (ADD, t, expression());
  case Lexeme.L_Moins: avancer(); return new Terme (MINUS, t, expression());
  defaultreturn t;
 }
}

static Terme produit() {
  Terme t = facteur(); switch (lc.nature) {
  case Lexeme.L_Mul: avancer(); return new Terme (MUL, t, produit());
  case Lexeme.L_Div: avancer(); return new Terme (DIV, t, produit());
  defaultreturn t;
 }
}

static Terme facteur() {
  Terme t; switch (lc.nature) {
  case Lexeme.L_ParG: avancer(); t = expression();
    if (lc.nature != Lexeme.L_ParD) throw new Error ("Il manque ')'");
    break;
  case Lexeme.L_Nombre: t = new Terme (lc.val); break;
  case Lexeme.L_Id: t = new Terme (lc.nom); break;
  defaultthrow new Error ("Erreur de syntaxe");
  }
  avancer();
  return t;
}

Ce programme réutilise les constantes et les fonctions définies pour l'analyseur lexical présenté plus haut. Les fonctions expression, produit et facteur correspondent aux variables auxiliaires E, P et F. Le corps de chaque fonction consiste à considérer les différentes parties droites possibles pour les règles de grammaires associées à ces variables. Ainsi, pour E, on choisit entre les trois cas P+E, P-E et P selon le lexème courant rencontré après avoir lu un produit. Si c'est l'opérateur + ou -, on est dans le cas où la partie droite est P+E, ou P-E. On fait de même pour choisir entre F × P, F /P et F dans le cas d'un produit en décidant sur les lexèmes × ou /. Pour un facteur, la décision entre (E), id ou nombre se fait en considérant le lexème courant qui alors ne peut être que (, L_Id ou L_Nombre.

Cette technique fonctionne bien ici car les membres droits des règles de grammaire ont une forme particulière. Pour chaque élément X de VN, l'ensemble des membres droits {u1, u2... up} de règles, dont le membre gauche est X, satisfait les conditions suivantes: les premières lettres des ui qui sont dans A, sont toutes distinctes et les ui qui commencent par une lettre de VN sont factorisables à gauche. Beaucoup de grammaires de langages de programmation satisfont ces conditions: Pascal, Java.

Remarquons que notre grammaire des expressions arithmétiques ne contient pas de récursivité à gauche, c'est-à-dire que VN ne contient aucun X pouvant se dériver vers un mot Xu. Mais, si nous avions plutôt pris les règles de grammaire suivantes:
E ® P          P ® F          F ® id
E ® E + P          P ® P × F          F ® nombre
                      F ® ( E )
la grammaire possède maintenant des récursivités à gauche, puisqu'on a E ®* Eu et P ®* Pv. Alors l'analyseur récursif descendant associé à cette nouvelle grammaire se mettrait à boucler en commençant par chercher une expression dans une expression, ou un produit dans un produit. La méthode d'analyse récursive descendante ne marche donc pas si la grammaire est récursive à gauche.

La valeur retournée par notre analyseur syntaxique est un arbre de syntaxe abstraite. C'est bien ce que l'on cherche à construire. Comme annoncé, l'analyseur syntaxique vérifie la conformité syntaxique de l'expression sur le flot d'entrée et construit l'objet de la classe Terme correspondant, dans le cas où l'entrée est un texte de programme syntaxiquement correct.

La grammaire ne peut donc être récursive à gauche; on reprend donc la grammaire de la section 2.8.3. Cette grammaire aboutit à la construction d'arbres de syntaxe abstraite qui privilégient l'association à droite pour les opérateurs de même précédence. Ainsi P+P+P est interprété comme P+(P+P); de même F × F × F correspond à F × (F × F). Malheureusement, ce choix n'est pas le bon pour les opérateurs - ou /, puisque P-P-P correspond d'habitude à (P-P)-P et non à P-(P-P) comme généré par notre grammaire. Pour y remédier, tout en respectant l'absence de récursivité à gauche, on change l'analyseur pour générer les arbres de syntaxe abstraites avec un accumuleur. On modifie donc les fonctions expression et produit comme suit:
static Terme expression() {
  Terme t = produit();
  while (lc.nature == Lexeme.L_Plus) || (lc.nature == Lexeme.L_Moins) {
    avancer();
    switch (lc.nature) {
      case Lexeme.L_Plus: t = new Terme (ADD, t, produit()); break;
      case Lexeme.L_Moins: t = new Terme (MINUS, t, produit()); break;
    }
   return t;
  }
}

static Terme produit() {
  Terme t = facteur();
  while (lc.nature == Lexeme.L_Mul) || (lc.nature == Lexeme.L_Div) {
    avancer();
    switch (lc.nature) {
      case Lexeme.L_Mul: t = new Terme (MUL, t, facteur()); break;
      case Lexeme.L_Div: t = new Terme (DIV, t, facteur()); break;
    }
   return t;
  }
}

Notre analyseur syntaxique récursif descendant s'arrête dès qu'il a lu une expression arithmétique. Pourtant il se peut que le résultat ne correspond pas à tout le flot d'entrée. Par exemple 3_2 sera considéré comme correct et reconnu comme la constante 3; de même ( x+1) (y+2 ) est reconnu comme l'expression x+1. Il faut donc vérifier si, après la lecture de l'expression, le lexème courant arithmétique est bien la fin de fichier L_EOF. La grammaire correspondante est alors:

A = { +, × , ( , ) , id, nombre, eof}, VN = { S, E, P, F}, l'axiome est S, les règles sont données par:
E ® P          P ® F          F ® id
E ® P + E          P ® F × P          F ® nombre
S ® E  eof                     F ® ( E  )

2.11 Autres méthodes d'analyse syntaxique

2.11.1 Méthode récursive descendante avec retours en arrière

Une technique plus générale d'analyse syntaxique consiste à procéder comme suit. On construit itérativement des mots u dont on espère qu'ils vont se dériver en f. Au départ on a u = S (l'axiome de la grammaire). A chaque étape de l'itération, on cherche la première lettre de u qui n'est pas égale à son homologue dans f. On a ainsi
u = gyv    f = gxh    x¹ y
Si y Î A (alphabet terminal), on ne peut dériver f de u, et il faut faire repartir l'analyse du mot qui a donné u. Sinon y Î VN et on recherche toutes les règles dont y est le membre gauche.
y ® u1    y ® u2    ···   y ® uk
On applique à u successivement chacune de ces règles, on obtient ainsi des mots v1, v2, ... vk. On poursuit l'analyse, chacun des mots v1, v2, ... vk jouant le rôle de u. L'analyse est terminée lorsque u = f. La technique est celle de l'exploration arborescente qui sera développée au chapitre 4. On peut la représenter par la fonction suivante donnée sous une forme informelle.
static boolean analyse (String u, String f) {
  if (f.equals(u))
    return true;
  else {
    Mettre f et u sous la forme f= gxh, u=gyvx ¹ y
    if ( y ÏA )
      Pour toute règle y ® w faire
         if (analyse (g + w + v, f))
           return true;
    return false;
  }
}

Remarquons que cette fonction ne marche toujours pas lorsque la grammaire est récursive à gauche, comme dans la grammaire des expressions arithmétiques de la page ??. En outre, cette technique d'analyse engendre une détection d'erreur imprécise, car les erreurs de syntaxe ne sont trouvées qu'après avoir fait tous les choix de règle. Elle est aussi coûteuse en temps 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'était pas la bonne. Il faut alors tout recommencer avec une autre règle et éventuellement répéter plusieurs fois ce mécanisme. La complexité de l'algorithme est ainsi une fonction exponentielle de la longueur du mot f à analyser.

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. Dans ces conditions, la fonction analyse donne un résultat même dans le cas de grammaires récursives à gauche.

2.11.2 Analyse LL

Une technique pour éviter les retours en arrière de l'analyse descendante récursive consiste à deviner la règle à appliquer en examinant les premières lettres du mot f à analyser. Plus généralement, lorsque l'analyse a déjà donné le mot u et que l'on cherche à obtenir f, on écrit comme ci-dessus
u = gSv    f = gh
et les premières lettres de h doivent permettre de retrouver la règle qu'il faut appliquer à S. Cette technique n'est pas systématiquement possible pour toutes les grammaires, mais c'est le cas sur un grand nombre de grammaires utiles, comme par exemple celle des expressions préfixées ou une grammaire modifiée (par factorisation à gauche) des expressions infixes. On dit alors que la grammaire est LL.
Exemple 10  Expressions préfixées. Nous considérons la grammaire de ces expressions: A = { +, *, (, ), a }, VN = { S }, l'axiome est S, les règles sont données par:
S ® ( + S S )      S ® ( * S S)      S ® a

Pour un mot f de A*, il est immédiat de déterminer u1 tel que
S ® u1
*
®
 
f

En effet, si f est de longueur 1, ou bien f= a et le résultat de l'analyse syntaxique se limite à S ® a, ou bien f n'appartient pas au langage engendré par la grammaire.

Si f est de longueur supérieure à 1, il suffit de connaître les deux premières lettres de f pour pouvoir retrouver u1. Si ces deux premières lettres sont ( +, c'est la règle S ® (+S S) qui a été appliquée. Si ces deux lettres sont ( * alors c'est la règle S ® (* S S ). Tout autre début de règle conduit à un message d'erreur.

Ce qui vient d'être dit pour retrouver u1 en utilisant les deux premières lettres de f se généralise sans difficulté à la détermination du (i+1)ème mot ui+1 de la dérivation à partir de ui. On décompose d'abord ui et f en:
ui = gi S vi     f = gi fi
et on procède en fonction des deux premières lettres de fi. On en déduit une fonction de construction d'un arbre de syntaxe abstraite pour les expressions préfixées en reprenant les définitions antérieures des classes pour les lexèmes et les termes:

static Terme expressionPrefixe() {
  Terme t; switch (lc.nature) {
    case Lexeme.L_Id: t = new Terme (lc.nom); break;
    case Lexeme.L_ParG: avancer();
      switch (lc.nature) {
        case Lexeme.L_Plus: avancer(); t = expressionPrefixe();
          t = new Terme (ADD, t, expressionPrefixe()); break;
        case Lexeme.L_Mul: avancer(); t = expressionPrefixe();
          t = new Terme (MUL, t, expressionPrefixe()); break;
        defaultthrow new Error ("Erreur de syntaxe");
      }
      if (lc.nature != Lexeme.L_ParD) throw new Error ("Il manque ')'");
    defaultthrow new Error ("Erreur de syntaxe");
  }
  avancer();
  return t;
}

Cette fonction ne fait donc aucun retour en arrière. Cette technique d'analyse syntaxique donné s'étend à toute grammaire LL. Ici on détermine la règle à appliquer en regardant deux lexèmes à l'avance dans le flot de lexèmes d'entrée. La grammaire est dite LL(k) si on peut détermier la règle à appliquer dans l'analyse descendante en regardant k lexèmes à l'avance. Alors on peut énoncer le résultat suivant:
Théorème 2   Si G est une grammaire LL(k), il existe un algorithme en O(n) qui effectue l'analyse syntaxique descendante d'un mot f de longueur n.

En fait, cet algorithme sert principalement pour k £ 2. On peut le contruire en prenant la grammaire en paramètre. C'est ce que font des méta-analyseurs syntaxiques comme javacc. En outre, une définition formelle des analyseurs LL peut être donnée en considérant la théorie des automates à pile.

Pour finir, reconsidérons le cas des expressions arithmétiques infixées. La grammaire suivante n'est pas LL, car il est difficile de distinguer les applications des règles E ® P et E ® P + E en regardant k lettres à l'avance.
E ® P          P ® F          F ® a
E ® P + E          P ® F × P          F ® ( E )
Cependant, par factorisation à gauche, on construit la grammaire LL(1) équivalente suivante, sur laquelle on retrouve la fonction d'analyse syntaxique considérée en 2.10.
E ® P E'          P ® F P'           
E' ® e          P' ® e          F ® a
E' ® + P E'          P' ® × F P'          F ® ( E )

2.11.3 Analyse ascendante

Les algorithmes d'analyse ascendante sont légèrement plus compliqués que ceux de l'analyse descendante. Ils s'appliquent à un plus grand nombre de grammaires. C'est pour cette raison qu'on les utilise souvent. Ils sont ainsi à la base du système yacc de S. Johnson qui sert à écrire des compilateurs sous le système Unix. Rappelons que l'analyse ascendante consiste à retrouver la dérivation
S0 ® u1 ® u2 ... un-1 ® un = f
en commençant par un-1 puis un - 2 et ainsi de suite jusqu'à remonter à l'axiome S0. On effectue ainsi ce que l'on appelle des réductions car il s'agit de remplacer un membre droit d'une règle par le membre gauche correspondant, celui-ci est en général plus court.

Un exemple de langage qui n'admet pas d'analyse syntaxique descendante simple, mais sur lequel on peut effectuer une analyse ascendante est le langage des systèmes de parenthèses. Rappelons sa grammaire:
S ® aS bS          S ® aS b          S ® abS          S ® ab
On voit que les règles S ® aSbS et S ® aSb peuvent engendrer des mots ayant un facteur gauche commun arbitrairement long, ce qui interdit tout algorithme de type LL(k). Cependant, nous allons donner un algorithme simple d'analyse ascendante d'un mot f.

Partons de f et commençons par tenter de retrouver la dernière dérivation, celle qui a donné f = un à partir d'un mot un-1. Nécessairement un-1 contenait un S qui a été remplacé par ab pour donner f. L'opération inverse consiste donc à remplacer un ab par S, mais ceci ne peut pas être effectué n'importe où dans le mot, ainsi si on a
f= ababab
il y a trois remplacements possibles donnant
Sabab      abSab      ababS
Les deux premiers ne permettent pas de poursuivre l'analyse. En revanche, à partir du troisième, on retrouve abS et finalement S. D'une manière générale, on remplace ab par S chaque fois qu'il est suivi de b ou qu'il est situé en fin de mot. Les autres règles de grammaires s'inversent aussi pour donner des règles d'analyse syntaxique. Ainsi: On a un algorithme du même type pour l'analyse des expressions arithmétiques infixes engendrées par la grammaire:
E ® P          P ® F          F ® a
E ® E + P          P ® P × F          F ® (E)
E ® E - P         

Pour effectuer une réduction, cet algorithme tient compte de la première lettre qui suit le facteur que l'on envisage de réduire (et de ce qui se trouve à gauche de ce facteur). On dit que la grammaire est LR(1). La théorie complète de ces grammaires mériterait un plus long développement; elle correspond à la notion de langages générés par des automates déterministes. Nous nous contentons de donner ici ce qu'on appelle l'automate LR(1) qui effectue l'analyse syntaxique de la grammaire, récursive à gauche, des expressions infixes.

On lit le mot à analyser de gauche à droite et on effectue les réductions suivantes dès qu'elles sont possibles: On peut gérer le mot réduit à l'aide d'une pile. Les opérations de réduction consistent à supprimer des éléments dans celle-ci, les tests sur ce qui précède ou ce qui suit se font très simplement en consultant les premiers symboles de la pile. L'analyse se fait en une seule passe sur le mot à analyser, donc sans retours en arrière. Comme pour le cas LL(k), on a le théorème suivant pour les grammaires LR(k).
Théorème 3   Si G est une grammaire LR(k), il existe un algorithme en O(n) qui effectue l'analyse syntaxique descendante d'un mot f de longueur n.

2.12 Programmes sur les arbres de syntaxe abstraite

L'analyse syntaxique consiste à construire des arbres de syntaxe abstraite. Dans cette section, nous donnons quelques exemples d'utilisation de cette structure.

2.12.1 Evaluation

Pour évaluer la valeur d'un terme correspondant à une expression arithmétique, il faut se donner une valuation des variables, c'est-à-dire une fonction associant une valeur à chacune des variables contenues dans ce terme. Le graphe de cette fonction est appelé un environnement. Le programme pour évaluer une expression correspond au morphisme suivant sur les arbres de syntaxe abstraite:

static int evaluer (Terme t, Environnement e) {
  switch (t.nature) {
  case ADD: return evaluer (t.a1, e) + evaluer (t.a2, e);
  case SUB: return evaluer (t.a1, e) - evaluer (t.a2, e);
  case MUL: return evaluer (t.a1, e) * evaluer (t.a2, e);
  case DIV: return evaluer (t.a1, e) / evaluer (t.a2, e);
  case CONST: return t.val;
  case VAR: return Environnement.assoc (t.nom, e);
  defaultthrow new Error ("Erreur dans evaluation");
  }
}

où la classe Environnement définit la liste d'association suivante:
class Environnement {
  String nom;
  int val;
  Environnement suivant;

  static int assoc (String s, Environnement e) {
    if (e == nullthrow new Error ("Variable non définie");
    if (e.nom.equals(s)) return e.val;
    else return assoc (s, e.suivant);
  }
}

Parfois, on dit aussi que la fonction evaluer est définie par induction structurelle sur la classe des termes.

2.12.2 Impression

Un autre programme classique sur les arbres de syntaxe abstraite consiste à les imprimer. C'est la fonction inverse de l'analyse syntaxique, puisqu'il s'agit de générer une chaîne de caractères, dont l'analyse syntaxique produirait le même arbre. Dans le cas des expressions arithmétiques, plusieurs programmes d'impression sont possibles. Le plus simple est de produire les expressions complètement parenthésées. Par exemple, avec l'ASA de la figure 2.3, on obtiendrait ((x+1)×((3× y)+2)). L'idéal est plutôt de produire une impression avec le minimum de parenthèses, comme (x+1)×(3× y +2). Notre programme sera le symétrique de l'analyseur syntaxique:
static void impExp (Terme t) {
  switch (t.nature) {
  case ADD: impProd(t.a1); System.out.print ("+"); impExp(t.a2); break;
  case SUB: impProd(t.a1); System.out.print ("-"); impExp(t.a2); break;
  default: impProd(t); break;
  }
}

static void impProd (Terme t) {
  switch (t.nature) {
  case MUL: impFact(t.a1); System.out.print ("*"); impProd(t.a2); break;
  case DIV: impFact(t.a1); System.out.print ("/"); impProd(t.a2); break;
  default: impFact(t); break;
  }
}

static void impFact (Terme t) {
  switch (t.nature) {
  case CON: System.out.print (t.valeur); break;
  case VAR: System.out.print (t.nom); break;
  default: System.out.print ("("); impExp(t); System.out.print (")"); break;
  }
}

Exercice 16   Faire le programme d'impression avec la règle d'association à gauche pour les opérateurs de même précédence.

2.12.3 Génération de code

Il s'agit de générer du code machine pour calculer des expressions arithmétiques sur un processeur simplifié. Notre machine a des registres Ri dans lesquels s'effectuent les opérations arithmétiques. Les registres peuvent recevoir une constante n (entière) ou être chargés à partir d'une mémoire x. Le jeu complet des instructions de notre processeur est le suivant:
Ri ¬ n        Ri ¬ Ri + Rj        Ri ¬ Ri × Rj
Ri ¬ x        Ri ¬ Ri - Rj        Ri ¬ Ri  /  Rj

Ainsi pour évaluer l'expression (x+1)× (3 × (y+2)) (dont l'arbre de syntaxe abstraite est sur la figure 2.4), on peut générer par exemple un des deux codes suivants:
R0 ¬ x           R0 ¬ x
R1 ¬ 1           R1 ¬ 1
R0 ¬ R0 + R1           R0 ¬ R0 + R1
R1 ¬ 3           R1 ¬ y
R2 ¬ y           R2 ¬ 2
R3 ¬ 2           R1 ¬ R1 + R2
R2 ¬ R2 + R3           R2 ¬ 3
R1 ¬ R1 × R2           R2 ¬ R2 × R1
R0 ¬ R0 × R1           R0 ¬ R0 × R2
On constate que le premier code utilise 4 registres (R0, R1, R2 et R3), alors que le deuxième n'en utilise que 3 (R0, R1 et R2). Si les registres constituent une ressource rare, il vaut mieux utiliser la deuxième solution. Pour connaître le nombre de registres minimum à utiliser, une vieille remarque due à Ershov consiste à dire que pour évaluer une constante ou une variable, il suffit d'un seul registre, et que, pour évaluer une expression de la forme e Å e', il faut un registre supplémentaire pour stocker le résultat de e ou de e', si e et e' ont besoin d'un même nombre de registres, et que sinon il suffit d'évaluer d'abord l'expression qui demande le plus grand nombre de registres, et de stocker son résultat dans un registre non nécessaire pour le calcul de la deuxième expression. Ainsi, le nombre de registres minimal reg(e) pour évaluer e est défini récursivement par:
reg(x) = reg(n) = 1
reg(e Å e')= ì
í
î
1 + reg(e) si   reg(e) = reg(e')
max(reg(e), reg(e')) sinon
D'où le programme suivant pour générer un code utilisant un nombre optimal de registres:
static int reg (Terme t) {
  switch (t.nature) {
  case ADD: case SUB: case MUL: case DIV:
    int n1 = reg(t.a1), n2 = reg(t.a2);
    if (n1 == n2) return 1 + n1;
    else return Math.max(n1,n2);
  case CONST: case VAR: return 1;
  defaultthrow new Error ("Erreur dans evaluation");
  }
}

static int genCode (Terme t, int r0) {
  switch (t.nature) {
  case ADD: case SUB: case MUL: case DIV:
    int n1 = reg(t.a1), n2 = reg(t.a2);
    if (n1 >= n2) {
      int r1 = genCode(t.a1, r0), r2 = genCode(t.a2, r1);
      System.out.println ("R" + r1 + " <- R" + r1 + " + R" + r2);
      return r1;
    } else {
      int r2 = genCode(t.a2, r0), r1 = genCode(t.a1, r2);
      System.out.println ("R" + r2 + " <- R" + r2 + " + R" + r1);
      return r2;
    }
  case CONST:
    System.out.println ("R" + r0 " <- " + t.val);
    return r0;
  case VAR:
    System.out.println ("R" + r0 " <- " + t.nom);
    return r0;
  defaultthrow new Error ("Erreur dans evaluation");
  }
}

A nouveau, la fonction genCode est définie par induction structurelle sur la classe des termes. On comprend bien sur cette exemple la nécessité de la phase d'analyse syntaxique, qui a permis de bien isoler la structure sur laquelle s'effectue la génération de code, à savoir la structure de syntaxe abstraite. Bien sûr, il existe des techniques beaucoup plus sophistiquées pour générer du code. C'est l'objet de tout le domaine de la compilation. Par exemple, on peut tenir compte du partage, et ne pas recalculer des expressions déjà calculées; ainsi, dans (x+1)× (3 × (x+1)), ce n'est pas la peine de générer deux fois le code de x+1. Un autre exemple est de tenir compte de la non banalisation des registres, certaines opérations ne pouvant se faire que dans des registres pairs. Un troisième exemple consiste à tenir compte de la durée de vie des variables, en supposant que les déclarations de variables ont une certaine portée. Tout cela nous entrainerait trop loin, mais fait partie de la problématique standard de la compilation.

Une autre curiosité a trait aux nombres reg(e) exprimant le nombre de registres minimaux pour le calcul de e. Ce sont des entités que l'on peut définir sur tout arbre binaire, même ceux qui ne correspondent pas à des arbres de syntaxe abstraite. Ces nombres de Horton-Strahler ont un correspondant en hydrologie et en botanique. Ils donnent l'épaisseur d'une rivière en fonction de l'épaisseur de ses affluents, ou d'une branche en fonction de sa structure de branchement.

2.13 Programmes en OCaml

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 = String.make (String.length s) ' ' in
  String.blit 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 ?? *)
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 ?? *)
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;;


Précédent Remonter Suivant