3615 Alex, site d'Alexandre Brianceau

Il est demandé de réaliser un compilateur à l’aide des outils Lex et Yacc pour un sous ensemble du langage C, le spC et de générer un code à trois adresses proche du langage assembleur, le 3aC. Afin de nous aider à cette tâche, des fichiers squelettes des descriptions Lex et Yacc nous sont fournis.

Vous trouverez plus d’information à propos du sujet sur la feuille d’énoncé distribuée aux étudiants.

Vous avez tout d’abord pu observer la table des matières puis cette introduction, vous pourrez ensuite aborder notre vision du sujet, puis ce que nous avons produit et nous finirons par nos observations sur notre travail.
Bonne lecture.

Pour commencer nous avions besoin du makefile. La source complète se trouve jointe avec le rapport. Expliquons un peu les cibles principales.

Compil

Cette partie est en faîte la fonction par défaut, ce qui veut dire que lorsque l’on tape make dans un terminal, cela exécute la suite des commandes de cette partie.
Pour compiler le compilateur, il faut d’abord utiliser Yacc pour générer la table des symboles, puis Lex pour l’analyseur syntaxique et enfin compiler les deux afin d’obtenir notre exécutable.

All

Exécute la cible compil mais créer les fichiers de bases, à savoir les fichiers de Lex et de Yacc, si ceux-ci sont non-existant. Cela rendra une erreur bien sûr de toute façon s’il n’existait pas avant.

Clean

Supprime l’ensemble des fichiers intermédiaires et finaux produits par un précédent make. Au final, votre dossier ressemble à sa jeunesse lorsqu’il était tout juste décompressé de l’archive ;-)

Tar

Cette cible permet de compresser les fichiers dans une archive *.tar afin de pouvoir l’envoyer/recevoir facilement.

Debug

Exécute les mêmes commande que par défaut, mais permet de passer Yacc en mode debug ce qui a pour effet de savoir tout ce que fait notre compilateur, ce qui peut être pratique si une la source soumise n’est pas acceptée par le compilateur.

Graphique

Exécute les mêmes commandes que compil mais rajoute des effets graphiques inutiles.

Le fichier Lex était le premier des deux fichiers à créer et modifier après le makefile car c’est lui qui lira notre flux d’entrée, à savoir un fichier source en spC.

Après avoir recopié le fichier fournis (ANSI.l), nous avons supprimé tous les motifs qui ne nous sommes pas utiles du fait que l’on va lire du spC (Simplified C). Toutes les descriptions de ce que l’on peut lire se trouve sur l’énoncé. Celui-ci est classique, avec une première partie permettant d’utiliser des alias d’ Pour commencer, il ne faut pas oublier de mettre la ligne #include « y.tab.h » afin d’utiliser la table des symboles qui sera générée par Yacc.

Par la suite nous avons alors assigné des actions à ces motifs afin de pouvoir faire quelque chose de notre analyse avec Yacc. Pour que Yacc puisse utiliser la lecture de Lex, il faut lui retourner les terminaux qu’il vient de reconnaître. Ainsi, il faut retourner le TOKEN lui étant attribué par le code suivant : return(TOKEN) ;

Si jamais Yacc devra utiliser le texte en entrée (comme par exemple une variable ou le nom d’une fonction), alors nous devons affecter ce texte (qui correspond à yytext) à la variable yylval qui est une structure ayant comme attribut str, qui lui permet de gérer le texte. Nous verrons cette structure dans le fichier Yacc. Pour effectuer cette affectation, il ne faut pas oublier d’utiliser strdup afin d’allouer l’espace mémoire correcte à yylval.str en fonction de la chaîne de caractère lue.

Finalement, un exemple typique serait :

{L}({L}|{D})* { yylval.str=strdup(yytext); return(IDENTIFIER); }

Dans cet exemple on voit bien toutes les opérations décrites juste avant.

Le fichier Yacc s’appuie sur le fichier spC.y car le langage que l’on veut reconnaître est ce dernier. Dès le début, il a tout d’abord fallu inclure la bibliothèque string.h (#include ) afin d’utiliser les fonctions spécifiques sur les chaînes de caractères comme strdup() ou strchr() par exemple.

Ensuite nous devions définir une structure à yylval afin de pouvoir traiter des chaînes de caractères au lieu des entiers par défaut. Pour cela nous avons rajouté la ligne suivante :

%union { char* str; }

A partir de là, nous pouvions compiler nos fichiers et obtenions déjà un compilateur capable de traiter une source en spC et si il ne nous disait pas qu’il y avait une erreur, alors c’est que notre chaîne avait été reconnue.

Cependant ce n’était pas suffisant, il fallait maintenant associer des actions à l’ensemble de la grammaire pour permettre de transformer la source spC en 3aC (code à 3 adresses). Notre politique dans ce cas a été de d’abord permettre le réaffichage complet du code en entrée, sans aucune transformation puis nous avons modifié le code afin de le passer en 3aC.

Pour cela, nous avons utilisé trois types principaux d’actions. Avant d’aller plus loin, voyons les variables que l’on peut utiliser. Nous avons tout d’abord la variable $$ qui correspond à la variable qui sera « remontée » par la suite dans la grammaire et ensuite les variables $i (pour tout i appartenant à R) qui correspondent aux ième valeurs de la règle qui elles-mêmes proviennent soit de la règle fille (si c’est un non-terminal) donc remontée par un $$, soit par Lex (si c’est un terminal).

Voici les trois actions principales :

1. La remontée simple :
   C’est le type le plus simple car il suffit de placer dans $$ la valeur du TOKEN sans y toucher. On utilise ici, comme dans le fichier de Lex la fonction strdup() car elle nous permet de ne pas nous soucier de l’allocation mémoire de $$ lors de la simple copie de chaîne de caractères. L’instruction est du type :

   $$=strdup($1);

2. La remontée avec concaténation :
   Le but est le même, remonter dans la variable $$ une chaîne de caractères cependant cette fois des actions vont être effectuées. Pour cela, on concatène les différentes chaînes et on agit sur cette chaîne comme on le souhaite pour la faire remonter. Pour cela, le plus simple est d’utiliser la fonction sprintf() qui permet d’utiliser la même syntaxe que le classique printf() mais en mettant le résultat ensuite dans $$.Il ne faut bien sûr pas oublier d’allouer une place en mémoire suffisante pour $$ car ici, on n’utilise pas strdup() comme précédemment. Voici des instructions typiques :

   int len = strlen($2);
   $$ = malloc((len + 10) * sizeof(char));
   sprintf($$, « (%s) », $2);

3. L’affichage des chaînes :
   Ici on utilise tout simple le printf afin d’afficher sur la sortie standard toutes les diverses concaténations produites par les règles précédentes.

Rajoutons simplement que nous avons rajouté les entiers label_i et var_i afin de convenir respectivement à la génération des labels et variables temporaires pour la transformation en 3aC. Pour finir, il faut définir le type des tokens et des non-terminaux qui sont donc des <str>.