Analyseurs syntaxiques

Ce module lit le fichier source, au moyen des API du système d'exploitation utilisé pour la compilation, et donne au module suivant la suite des caractères qui le composent.

En Delphi, on peut se servir simplement de la méthode LoadFromFile de la classe TStrings.

Ce deuxième module rassemble des suites de caractères, données par le module de lecture du texte source, en une suite, tout autant linéaire, de lexèmes. Un lexème est une entité composée de plusieurs caractères, qui a une signification dans le langage source. Il s'agit par exemple d'identificateurs, d'opérateurs, ou de mots-clefs. Les lexèmes peuvent être séparés par des espaces et, dans certains cas, ils doivent l'être.

Observons l'instruction Pascal suivante :

if Entier > 0 then
    ShowMessage('Le nombre est positif');

On peut y trouver 10 lexèmes, que l'on peut répartir en cinq catégories :

• identificateurs : Entier et ShowMessage ;
• mots-clefs : if et then ;
• opérateurs : plus grand (>), parenthèses () et point-virgule (;) ;
• nombres entiers : 0 ;
• chaînes de caractères : 'Le nombre est positif'.

Il ne faut pas confondre les constantes de types nombre entier ou chaîne de caractères, comme 0 et 'Le nombre est positif', avec les variables comme Entier. Dans le cas des constantes, c'est à l'analyseur lexical de déterminer le type et la valeur, à l'aide d'une classe de lexèmes différente selon le type. Dans le cas des variables, c'est à l'analyseur sémantique de découvrir le type, puisqu'elles sont toutes regroupées sous la classe de lexèmes Identificateur.

Vous pourrez trouver une introduction à l'analyse lexicale dans l'article sur les Lexers (autre nom des analyseurs lexicaux) d'Olivier Lance [LAN04].

Bien que nous n'étudierons pas l'analyse lexicale, nous aurons besoin d'un analyseur, dans la mesure où nous travaillerons sur des lexèmes dans l'analyse syntaxique. Vous trouverez une brève présentation de l'analyseur lexical utilisé dans l'annexe AAnnexe A - Analyseur lexical utilisé.

« Le module d'analyse syntaxique restructure le flot de lexèmes, donnés de façon linéaire par le module précédent, en un arbre abstrait. Chaque feuille de l'arbre correspond à un lexème… »

Chaque lexème est placé sur une feuille de l'arbre. Il fournit cet arbre abstrait non décoré au module d'analyse sémantique.

L'analyse sémantique collecte des informations dans l'arbre abstrait non décoré pour le décorer des résultats obtenus. Elle forme ainsi l'arbre abstrait décoré, abrégé en arbre abstrait.

Notre module d'analyse sémantique ne fera rien en réalité, puisque tout ce que nous voulons dans cette étude de l'analyse syntaxique, c'est récupérer l'arbre abstrait non décoré.

Ce dernier module de la partie avant produit un code intermédiaire à partir de l'arbre abstrait décoré. C'est une écriture de l'arbre abstrait que pourra comprendre la partie arrière.

Puisque nous ferons office nous-mêmes de partie arrière, avant de vérifier si l'analyseur syntaxique fait bien son travail, notre module de génération du code intermédiaire nous fournira une écriture XML de l'arbre abstrait(1).

Ce module effectue quelques optimisations directement sur le code intermédiaire. Une optimisation couramment implémentée ici est le pliage des constantes. C'est la compression d'une expression, dont on connaît la valeur de tous les opérandes à la compilation, en son résultat.

La génération de code réécrit le code intermédiaire en une liste linéaire d'instructions du système d'exploitation, de façon plus ou moins symbolique.

Ce troisième module de la partie arrière optimise à nouveau le code symbolique que lui donne la génération de code. Certaines de ces optimisations peuvent être placées dans le module d'optimisation du CI, et vice versa. Cependant, certaines ont plus leur place dans l'un ou l'autre module.

Le module de génération de langage machine convertit la liste des instructions symboliques en leur représentation- binaire supportée par le processeur de la machine cible. Il génère aussi des tables d'adresses, de constantes et de relocalisation.

Ce dernier module assemble les suites de bits des instructions et les différentes tables, ainsi que d'éventuels prologues et épilogues, en un seul fichier qui respecte le format des fichiers exécutables du système d'exploitation.

Nous avons pu voir que la construction d'un analyseur par descente récursive est relativement simple. Mais tout n'est pas si rose.

En effet, il existe de nombreuses grammaires qui posent problème avec les analyseurs par descente récursive.

D'abord, vous aurez remarqué dans le graphe de contrôle du flux de la figure 3.3 qu'il faut plusieurs appels avant d'avancer sur un lexème. Cela représente une perte de temps qui peut être dérangeante. De plus, les tests qui renvoient la valeur False sont en quelque sorte un retour en arrière sur les lexèmes, ce qui signifie que l'analyse n'est pas réellement déterministe.

Ensuite, dans la majorité des grammaires usuelles, il est impossible de créer un analyseur correct. Par exemple, toute grammaire récursive à gauche produit inéluctablement un bouclage sans fin sur la procédure de traitement du non-terminal responsable.

Finalement, le traitement des erreurs est quasiment nul. Tout ce que nous sommes en mesure de faire, c'est de signaler qu'on s'attendait à voir un non-terminal particulier et qu'on a trouvé un lexème incorrect, avant de devoir purement et simplement abandonner la compilation. Ce n'est réellement pas pratique pour l'utilisateur.

Nous devons donc savoir comment déterminer quel choix devra être pris, sur la seule base du premier terminal en entrée.

Comment le savoir ? Tout simplement en connaissant l'ensemble des terminaux par lesquels peut commencer un choix donné. En effet, en connaissant cela, il nous suffit de retenir ce choix si le lexème en entrée appartient à cet ensemble. Nous appellerons désormais cet ensemble l'ensemble des premiers d'un choix kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp, et le noterons kitxmlcodeinlinelatexdvpPREM(\alpha)finkitxmlcodeinlinelatexdvp.

Cela paraît suffisant… Mais ne l'est malheureusement pas.

En effet, que se passe-t-il si un choix est nullifiable ? Il peut alors ne commencer par aucun terminal. Comment pourrions-nous alors déterminer qu'il faut sélectionner ce choix ?

On se base sur la considération suivante : il faut retenir un choix nullifiable si le lexème en entrée est un lexème qui peut suivre directement ce choix, cela revient à dire ceux qui peuvent suivre directement le non-terminal concerné. Cela nécessite de calculer une nouvelle information : l'ensemble des lexèmes qui peuvent suivre un non-terminal donné. Nous appellerons cet ensemble l'ensemble des suivants d'un non-terminal N, et le noterons kitxmlcodeinlinelatexdvpSUIV(N)finkitxmlcodeinlinelatexdvp.

Il restera à savoir si oui ou non un choix donné est nullifiable. Cette donnée peut être obtenue facilement en étendant la notion d'ensemble des premiers, pour lui faire comprendre la chaîne de symboles grammaticaux vide kitxmlcodeinlinelatexdvp\mathcal{E}finkitxmlcodeinlinelatexdvp si le choix correspondant est nullifiable.

Nous allons maintenant voir comment on peut calculer le contenu de ces deux ensembles.

Voyons tout d'abord comment calculer les kitxmlcodeinlinelatexdvpPREM(\alpha)finkitxmlcodeinlinelatexdvp.

Pour chaque choix, s'il commence par un terminal kitxmlcodeinlinelatexdvptfinkitxmlcodeinlinelatexdvp, c'est facile : kitxmlcodeinlinelatexdvpPREM(\alpha)finkitxmlcodeinlinelatexdvp est le singleton kitxmlcodeinlinelatexdvp\{t\}finkitxmlcodeinlinelatexdvp. Si c'est un non-terminal N, alors le choix kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp peut commencer par n'importe quel terminal par lequel N peut commencer. Cela nécessite donc d'obtenir un nouveau type d'information : l'ensemble des premiers d'un non-terminal N, que l'on notera bien entendu kitxmlcodeinlinelatexdvpPREM(N)finkitxmlcodeinlinelatexdvp.

Afin de travailler de façon plus générique et plus abstraite - et donc plus simple -, nous adopterons également un ensemble des premiers pour les terminaux. Ainsi, il existera aussi l'ensemble des premiers d'un terminal kitxmlcodeinlinelatexdvptfinkitxmlcodeinlinelatexdvp - noté kitxmlcodeinlinelatexdvpPREM(t)finkitxmlcodeinlinelatexdvp pour changer - qui sera équivalent au singleton kitxmlcodeinlinelatexdvp\{t\}finkitxmlcodeinlinelatexdvp.

Ainsi, kitxmlcodeinlinelatexdvpPREM(\alpha)finkitxmlcodeinlinelatexdvp est tout simplement égal à l'ensemble des premiers de son premier symbole grammatical.

Nous connaissons donc les ensembles des premiers des terminaux et nous savons que pour calculer ceux des choix nous avons encore besoin de ceux des non-terminaux. Voyons donc comment les calculer.

Pour un non-terminal N de la forme :

kitxmlcodeinlinelatexdvpPREM(N)finkitxmlcodeinlinelatexdvp est naturellement l'union des ensembles des terminaux par lesquels peuvent commencer les choix kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvp\betafinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\gammafinkitxmlcodeinlinelatexdvp de N. Nous avons donc besoin des PREM des non-terminaux pour calculer ceux des choix, mais aussi ceux des choix pour calculer les PREM des non-terminaux.

Cela peut sembler être un cercle vicieux. En fait, beaucoup d'algorithmes dans le domaine de la compilation paraissent être insolvables à cause de cela. Pourtant, ils sont bel et bien réalisables. On appelle ce type d'algorithme des algorithmes de fermeture transitive, ou plus simplement algorithmes de fermeture.

Ce type d'algorithme possède trois parties : la définition des données, l'initialisation et les règles de déduction. La définition des données peut être assimilée à la déclaration var d'une routine Pascal. Durant l'initialisation, on définit les données de départ, et les règles de déduction sont les directives qui indiquent comment faire progresser l'ensemble des données vers la solution finale.

Les algorithmes de fermeture ont besoin de données initiales, à partir desquelles calculer des informations supplémentaires. Mais que sont donc nos données initiales dans ce cas ? Il s'agit des ensembles des premiers des terminaux. Nous savons en effet que pour tout terminal kitxmlcodeinlinelatexdvptfinkitxmlcodeinlinelatexdvp, kitxmlcodeinlinelatexdvpPREM(t) = \{t\}finkitxmlcodeinlinelatexdvp.

Vous trouverez en figure 3.4 l'algorithme de fermeture qui calcule les ensembles PREM d'une grammaire. Appliqué sur la grammaire de la figure 3.2, les ensembles PREM calculés seront tels que montrés sur la figure 3.5.

Vous aurez remarqué qu'une quatrième variante de l'ensemble des PREM a été ajoutée. Il s'agit des PREM des fins de choix. Nous aurons en effet besoin de ces informations pour le calcul de l'ensemble des suivants.

Le calcul de l'ensemble des suivants d'un non-terminal est plus simple. Par ailleurs, on ne doit pas étendre la notion aux terminaux et choix/fins de choix dans ce cas. Entrons donc directement dans le vif du sujet.

Pour calculer les SUIV, nous aurons à nouveau recours à un algorithme de fermeture. Vous trouverez cet algorithme sur la figure 3.6, et le résultat de son application à la grammaire de la figure 3.2 à la figure 3.7.

Nous disposons maintenant de toutes les informations nécessaires à la conception d'un analyseur LL(1). Toutefois, nous nous devons d'abord d'étudier certains cas qui rendent impossible l'écriture d'un tel analyseur. Ce sont ce qu'on appelle des conflits LL(1).

Nous avons vu comment on pouvait décider quel choix devait être sélectionné. Il faut prendre celui qui contient dans son ensemble PREM le lexème kitxmlcodeinlinelatexdvptfinkitxmlcodeinlinelatexdvp en entrée, ou kitxmlcodeinlinelatexdvp\mathcal{E}finkitxmlcodeinlinelatexdvp si le lexème kitxmlcodeinlinelatexdvptfinkitxmlcodeinlinelatexdvp est dans l'ensemble SUIV du non-terminal en cours.

Mais que se passe-t-il si plusieurs choix remplissent les conditions ? Dans ce cas il y a conflit LL(1]).

Il y aura conflit LL(1) si les choix kitxmlcodeinlinelatexdvp\alphafinkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\betafinkitxmlcodeinlinelatexdvp d'un non-terminal N sont tels que :

• kitxmlcodeinlinelatexdvpPREM(\alpha)\ \cap\ PREM(\beta) \neq \emptysetfinkitxmlcodeinlinelatexdvp (conflit PREM-PREM) ;
• kitxmlcodeinlinelatexdvp\mathcal{E}\in PREM(\alpha)finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvpPREM(\beta)\ \cap\ SUIV(N) \neq \emptysetfinkitxmlcodeinlinelatexdvp (conflit PREM-SUIV) ;
• kitxmlcodeinlinelatexdvp\mathcal{E}\in PREM(\alpha)finkitxmlcodeinlinelatexdvp et kitxmlcodeinlinelatexdvp\mathcal{E}\in PREM(\beta)finkitxmlcodeinlinelatexdvp (conflit SUIV-SUIV).

Une grammaire qui ne contient aucun conflit est une grammaire LL(1). On ne peut écrire d'analyseurs LL(1) que pour les grammaires qui sont LL(1).

L'ennui, c'est que la plupart des grammaires ne sont pas LL(1). Il convient, pour créer un analyseur syntaxique LL(1), de supprimer ces conflits en modifiant la grammaire du langage.

Cela dépassant le cadre de ce travail, je vous renvoie une fois de plus au livre Compilateurs [GBJLO2, section 2.2.4.3].

Voilà, nous disposons enfin de toutes les informations nécessaires à la construction d'un analyseur LL(1). Afin de vous permettre d'avancer progressivement, et donc de vous faciliter la compréhension, nous étudierons d'abord l'analyse prédictive par descente récursive. Elle est très proche de l'analyse non prédictive tant par son fonctionnement que par son nom.

En fait, elle fonctionne exactement de la même façon, si ce n'est qu'on n'effectue plus un test de type if sur le résultat des fonctions récursives, mais bien une instruction de type case of sur le lexème en entrée.

Du point de vue de l'exécution, c'est évidemment beaucoup plus rapide. Et du point de vue de la maintenance et de la compréhension du code, c'est également beaucoup plus clair. On aura donc toujours avantage à utiliser une méthode LL(1) par rapport à la méthode entièrement manuelle.

Vous trouverez le code d'un analyseur prédictif par descente récursive pour la grammaire de la figure 3.2 dans le fichier Predictif.pas.

Ainsi que vous pouvez le constater, la structure générale est totalement conservée : on utilise toujours une routine par non-terminal et une générique pour les terminaux. La différence est qu'elles ne renvoient plus un booléen témoin de leur succès ou de leur échec. En effet, on sait, dès lors qu'on entre dans une routine de non-terminal (ou même d'un terminal) que ce non-terminal est le bon - sauf s'il y a erreur syntaxique.

D'autre part, cela nous permet d'apporter une amélioration notoire. Puisque l'on sait qu'on étudie le bon non-terminal, on peut déjà construire le nœud correspondant et le transmettre aux routines appelées récursivement en tant que parent du nœud qu'elles devront construire. Cela permet non seulement de simplifier la libération propre des objets en cas d'erreur syntaxique (remarquez que les blocs try...except...end sont plus élégants); mais cela permet aussi de posséder directement des informations de contexte qui pourront être utiles à une analyse sémantique combinée à l'analyse syntaxique. C'est un avantage indéniable pour les compilateurs étroits.

Finalement, on peut maintenant utiliser la valeur de retour des fonctions pour une information bien plus intéressante qu'un code de réussite, à savoir le nœud construit. Cela permet de simplifier également l'écriture des blocs de choix.

Vous voyez donc que l'analyse prédictive par descente récursive ne possède que des atouts par rapport à l'analyse non prédictive. Aussi, je vous déconseille de ne jamais construire un analyseur non prédictif professionnel.

Courage… Il ne nous en reste plus qu'un ! L'analyseur prédictif non récursif.

Quelles différences avec l'analyseur récursif ? D'abord, c'est que ce petit dernier range tous les résultats calculés précédemment dans une table constante, plutôt que de les exploiter au travers d'un case of. Cette table est à deux dimensions : l'une indexée par des non-terminaux, l'autre par des lexèmes. L'autre différence majeure réside dans le fait que nous n'avons plus une routine par non-terminal, mais bien une seule routine concentrant tout l'algorithme en elle-même.

Afin de mieux vous repérer, vous trouverez en figure 3.8(5) ce que l'on appelle la table de transition de la grammaire de la figure 3.2.

Cette table indique, pour chaque non-terminal actif et chaque terminal en entrée, le choix du non-terminal à sélectionner. Lorsqu'une case est vide, cela signifie qu'il y a erreur syntaxique.

On peut se représenter les non-terminaux comme les états d'un automate d'états, et les terminaux en entrée comme les événements extérieurs de cet automate. Par exemple, lorsqu'on est dans l'état Entree, et qu'un terminal '(' se présente dans l'entrée, on passe dans l'état Expression.

Cependant, ce n'est pas aussi évident qu'un automate d'états fini. En effet, lorsqu'on se trouve dans l'état ResteExpression et qu'on reçoit un lexème '+' en entrée, on transite vers une suite d'états ! Mieux encore, si l'on reçoit un lexème ')' on va à une chaîne vide d'états…

C'est pourquoi nous aurons besoin de ce que l'on appelle un automate à pile. Un tel automate est constitué d'une pile d'états. Lors d'un cycle de l'automate, on dépile le sommet de la pile (qui est un état) et, selon son type et le contenu de la table de transition, on empile les composantes du choix sélectionné dans l'ordre inverse (pour les dépiler ensuite dans le bon ordre). Lorsqu'on termine un choix, on effectue une sorte de mouvement-kitxmlcodeinlinelatexdvp\mathcal{E}finkitxmlcodeinlinelatexdvp pour remonter au non-terminal parent.

Tout cela doit vous sembler bien abstrait et peu compréhensible… Ne vous en faites pas, je suis de votre avis. Aussi je vous propose de découvrir sans plus tarder le code de cet automate, que nous allons expliquer ensuite. Vous pourrez trouver ce code dans le fichier PredictifNonRecursif.pas (voir annexe BAnnexe B - Référentiel des fichiers sources).

La routine maîtresse de ce source est bien entendu la routine AnalyseSyntaxique. Nous la reproduisons sur la figure 3.9. Voyons son comportement pas à pas.

Tout d'abord, à l'instar de nos deux premiers analyseurs syntaxiques, celui-ci démarre l'analyse lexicale (ligne 122).

Ensuite, on crée la pile prédictive (ligne 126). On transmet en paramètre du constructeur le symbole de départ de la grammaire : il sera empilé originellement.

De la ligne 128 à la ligne 156, on trouve la boucle principale de l'algorithme. Cette boucle remplace en réalité les appels récursifs des analyseurs précédents. Elle ne s'arrête que sur erreur syntaxique ou lorsque la pile prédictive est vide. Cette dernière situation signifie que l'entrée est complètement analysée.

L'algorithme répétitif effectue la tâche suivante : il dépile le sommet de la pile prédictive et, selon son type, effectue une des trois actions suivantes.

Si le sommet de la pile est un code de retour au parent (ligne 133), alors on redéfinit le nœud courant comme étant le parent de l'ancien. Il s'agit du mouvement-kitxmlcodeinlinelatexdvp\mathcal{E}finkitxmlcodeinlinelatexdvp dont nous avons parlé plus haut. D'autres implémentations de ce mouvement peuvent être faites. Par exemple, si l'on code de manière à ce qu'un nœud de non-terminal puisse indiquer lorsque son choix est complet, on peut se baser sur cette information pour remonter au parent.

Si le sommet de la pile est un terminal (ligne 137), il faut simplement reconnaître ce terminal et l'ajouter aux fils du nœud courant.

Si le sommet de la pile est un non-terminal (ligne 145), on effectue un mouvement de prédiction. Voici les différentes instructions qui sont effectuées.

1. On commence par consulter la table de transition pour déterminer le choix à sélectionner, en fonction du non-terminal récupéré en pile et du lexème en entrée (ligne 146).
2. On crée ensuite le non-terminal indiqué en pile et on signale son choix (ligne 147). Remarquez au passage que nous utilisons désormais un type générique pour les non-terminaux. Il serait en effet impensable d'utiliser ici un case of pour déterminer son type. Si l'on construit un analyseur étroit, ce peut être gênant. On recourra alors à des tables de correspondance entre un non-terminal et sa classe et on utilisera un constructeur polymorphique.
3. La ligne 149 constitue une action un peu barbare : on assigne à Result le premier non-terminal rencontré. Cela marche effectivement, mais c'est peu joli. Une programmation propre requerrait ici un code plus lourd et donc plus lent. On préfère ainsi conserver cette impureté informatique…
4. L'instruction suivante relie le nouveau nœud au nœud courant, qui est son parent (ligne 151).
5. Après cela, on définit le nouveau nœud comme le nœud courant (ligne 153).
6. Finalement, on empile les différents symboles du choix sélectionné sur la pile (ligne 154). Notez que les procédures EmpileChoixi empilent d'abord un code de retour au parent, qui est la fin du choix, puis tous les symboles dans l'ordre inverse sur la pile. Et ce pour les dépiler plus tard dans le bon ordre.

function AnalyseSyntaxique(Entree : string) : TNoeudEntree;
var Courant , Nouveau : TNoeudNonTerminal;
    NouveauLexeme : TNoeudLexeme;
    Symbole : Char;
    Choix : integer;
begin
  DemarrerAnalyseurLexical(Entree);
  Result := nil;
  try
    Courant := nil;
    Pile := TPilePredictive.Create(ntEntree);
    try
      while not Pile.Empty do
      begin
        Symbole := Pile.Pop;

        if Symbole = codeRetourneAuParent then
        begin // le choiz courant est terminé
          Courant := Courant.Parent;
        end else
        if Symbole < ntEntree then
        begin // la prédiction est un terminal -> reconnaissance
          if CurLex.Classe <> Symbole then
          ErreurSyntaxique;
          NouveauLexeme := TNoeudLexeme.Create;
          NouveauLexeme.Lexeme := CurLex;
          Courant.AjouteFils(NouveauLexeme);
          LexemeSuivant;
        end else
        begin // la prédiction est un non-terminal -> prédiction
          Choix := TableTransition[Symbole, CurLex.Classe] ;
          Nouveau := TnoeudNonTerminal.Create(
            Courant, Symbole, ChoixDuNonTerminal[Symbolel(Choix));
          if not Assigned (Result) then
            Result := Nouveau;
          if Assigned(Courant) then
            Courant.AjouteFils(Nouveau);
          Courant := Nouveau;
          EmpileChoix[Choix];
        end;
      end;
    finally
      Pile.Free;
    end;
  except
    if Assigned(Result) then
      Result.Free;
    raise;
  end;
end;

Notez enfin la clause except (ligne 160) qui doit libérer les nœuds construits en cas d'erreur. La seule libération du nœud Result suffit à libérer tous les nœuds construits. En effet, dans cet algorithme, le nœud Result est le premier construit et dès qu'un nouveau nœud est créé, il est directement relié à son parent et son parent à lui. Ainsi, comme chaque parent détruit les enfants qui lui sont reliés à sa libération, une seule libération entraîne toutes les autres. Rien de plus simple…