MASTER 1ère année

Travaux Pratiques de

Compilation

sujet n°1

(Familiarisation avec l'outil LEX)


Introduction.

Une rapide présentation de LEX

Exercice 1. Javanais ou Pig Latin

Le Javanais (en anglais Pig Latin) est un jeu d'enfants où l'on effectue des transformations simples sur les voyelles de mots. On vous demande d'écrire un traducteur Français - Javanais qui fait précéder chaque groupe de voyelles de av. Ainsi, Prise en main serait traduit par Pravisave aven mavain.

Exercice 2. Comptons les mots !

Exercice 3. Mon code sur Internet

On veut présenter proprement, sur le Web, des extraits de code C ou C++. Pour cela, il faut produire à partir d'un source C/C++ un fichier HTML respectant le formatage initial (retours ligne, indentation) et mettant en relief mots-clés, instructions du pré-processeur, chaînes de caractères et commentaires.

Voici un exemple de programme source : 

#include <fifo.h>
#define NVOISINS 8
for (x = 0; x < N; x++)
  {
  if (M[x] != 0)                   /* le pixel appartient a un maximum */
    {
    for (k = 0; k < NVOISINS; k += 1) /* parcourt les voisins */
      {                              /* si un voisin n'est pas dans la FIFO */
      y = voisin(x, k, rs, N);     /* et pas maximum, on le met en FIFO */
      if ((y != -1) && (! IsSet(y, EN_FIFO)) && (M[y] == 0))
        {
        FifoPush(FIFO, y);
        Set(y, EN_FIFO);
        if (trace) printf("empile point %d (%d,%d)\n", y, y%rs, y/rs);
        } /* if y ... */
      } /* for k */
    } /* if M */
  } /* for x */

Et voici le résultat désiré :

<html><pre><font size="+1"><font color="Blue">#include &lt;fifo.h&gt;</font>
<font color="Blue">#define NVOISINS 8</font>
<b>for</b> (x = 0; x &lt; N; x++)
  {
  <b>if</b> (M[x] != 0)                   <font color="Red">/* le pixel appartient a un maximum */</font>
    {
    <b>for</b> (k = 0; k &lt; NVOISINS; k += 1) <font color="Red">/* parcourt les voisins */</font>
      {                              <font color="Red">/* si un voisin n'est pas dans la FIFO */</font>
      y = voisin(x, k, rs, N);     <font color="Red">/* et pas maximum, on le met en FIFO */</font>
      <b>if</b> ((y != -1) &amp;&amp; (! IsSet(y, EN_FIFO)) &amp;&amp; (M[y] == 0))
        {
        FifoPush(FIFO, y);
        Set(y, EN_FIFO);
        <b>if</b> (trace) printf(<font color="#008000">"empile point %d (%d,%d)\n"</font>, y, y%rs, y/rs);
        } <font color="Red">/* if y ... */</font>
      } <font color="Red">/* for k */</font>
    } <font color="Red">/* if M */</font>
  } <font color="Red">/* for x */</font>
</font></pre></html>

#include <fifo.h>
#define NVOISINS 8
for (x = 0; x < N; x++)
  {
  if (M[x] != 0)                   /* le pixel appartient a un maximum */
    {
    for (k = 0; k < NVOISINS; k += 1) /* parcourt les voisins */
      {                              /* si un voisin n'est pas dans la FIFO */
      y = voisin(x, k, rs, N);     /* et pas maximum, on le met en FIFO */
      if ((y != -1) && (! IsSet(y, EN_FIFO)) && (M[y] == 0))
        {
        FifoPush(FIFO, y);
        Set(y, EN_FIFO);
        if (trace) printf("empile point %d (%d,%d)\n", y, y%rs, y/rs);
        } /* if y ... */
      } /* for k */
    } /* if M */
  } /* for x */

où les mots-clès sont en gras, les chaînes de caractères en vert et les commentaires en rouge. On remarquera que les caractères "if" dans "FifoPush" ne doivent pas constituer un mot-clé.

Voici quelques tags HTML pouvant servir :
debut, fin document                    <html>...</html>
respecte le formatage initial
 <pre>...</pre>
gras
 <b>...</b>
>
 &gt;
<
 &lt;
&
 &amp;
couleurs
 <font color="Green">...</font>


Et la liste des mots-clés de C++ :

asm        auto       break       catch       case        char
class      const      continue    default     delete      do
double     else       enum        extern      float       for
friend     goto       if          inline      int         long
new        operator   overload    private     protected   public
register   return     short       signed      sizeof      static
struct     switch     this        template    typedef     union
unsigned   virtual    void        volatile    while

Exercice 4. Table des symboles

Rôle de l'analyseur lexical dans un compilateur

Dans un compilateur, l'analyseur lexical transforme le flux d'entrée de caractères (provenant du fichier qui contient le programme source) en un flux de codes numériques qui représentent les unités lexicales (mots-clés, identificateurs, opérateurs, parenthèses, etc). Il produit également une table des symboles, qui est utile pour retrouver la forme originale des codes représentant les identificateurs (noms de variables, de fonctions...)

Le but de l'exercice est de réaliser, avec l'aide de Lex, un analyseur lexical pour un sous-ensemble du C++, le C-. Voici la description des unités lexicales de C- :

Ne sont pas des unités lexicales et doivent être ignorés : espace, retour à la ligne, commentaire (entre /* et */).

L'analyseur produit par Lex (la fonction yylex()) devra retourner le code du prochain token lu dans le flux d'entrée. Puisque le reste du compilateur n'est pas développé, on se contentera d'un programme principal de test appelant yylex() en boucle et affichant les résultats produits.

Codage des unités lexicales

Pour réaliser un analyseur lexical, il faut tout d'abord convenir d'un codage des unités lexicales. Celles-ci sont de plusieurs types:
Les unités lexicales simples

Les symboles non alphanumériques et les mots-clés peuvent être codés chacun par un entier différent. Par exemple:

symbole code symbole code symbole code
+ 1 { 23 << 45
- 2 } 24 >> 46
* 3 [ 25 || 47
/ 4 ] 26 && 48
if 100 for 112 while 124


Lorsque l'analyseur lexical reconnaît dans le flux d'entrée un de ces symboles, il émet dans le flux de sortie (ici : l'écran) le code correspondant.

Les valeurs constantes

Dans le flux de sortie de l'analyseur lexical, il faudra émettre dans ces cas:

Les identificateurs

On ne les connaît pas à l'avance. Il faut donc les enregistrer au fur et à mesure de leur apparition dans le programme source, et les stocker dans une table des symboles. La table des symboles établit la correspondance entre un symbole identificateur (nom de variable ou de fonction, par exemple) et un entier (l'index du symbole dans la table). Certains identificateurs (comme main, char, int, float) sont prédéfinis : ils font partie du langage et sont chargés dans la table des symboles lors de l'initialisation de l'analyseur lexical.

Dans le flux de sortie de l'analyseur lexical, il faudra émettre dans ce cas:

Important : L'apparition du même symbole plusieurs fois dans le programme source devra toujours donner lieu à l'émission dans le flux de sortie du même index.

La table des symboles

La table des symboles établit la correspondance entre un symbole identificateur (nom de variable ou de fonction, par exemple) et un entier (index du symbole dans la table). La structure de données la plus simple pour gérer cette table est un tableau de chaînes de caractères :

extrait de programme:

void segmente()
{
  int mesure;
  int increment = 1;
  int maximise = 0;

   mesure = 0;
...

extrait correspondant de la table des symboles:

index chaine
0 segmente
1 mesure
2 increment
3 maximise


Il sera bien entendu nécessaire de disposer d'une fonction de recherche d'une chaîne de caractères dans cette table, ainsi que d'une procédure d'ajout d'une chaîne de caractères dans la table. Vous pourrez utiliser une représentation de type tableau dans votre TP. Cependant, il existe des structures mieux adaptées à ce problème, notamment en ce qui concerne la complexité de l'opération de recherche d'une chaîne de caractères. C'est le cas notamment des tables de hachage, parfois appelées aussi tables à adressage dispersé, utilisées dans la plupart des compilateurs.