1.Présentation *

Faire un compilateur est une étape importante de notre cursus. Ce projet nous a été proposé pour nous permettre de mettre en application les connaissances acquises dans le domaine de la compilation, de la théorie des langages et de la programmation orientée objets.

Le sujet était de réaliser un compilateur de langage Pascal générant un code exécutable sur une machine à pile de notre choix. Notre première orientation a été la Java Virtual Machine qui utilise ce concept, mais des problèmes liés à la protection du P-code Java nous a fait changer d’orientation. Notre choix définitif a donc été d’utiliser une machine réelle, l’assembleur Mips. Lors d’un précédent projet nous avions utilisé un simulateur pour ce type d’architecture. Cette optique nous a permis d’entrevoir une phase de compilation plus proche de la réalité.

Après une analyse précise du sujet, nous avons défini, les différentes phases de l’élaboration de notre compilateur. Nous pouvons différencier quatre grandes étapes :

La seconde partie de notre analyse nous a permis de définir une répartition des taches dans le temps, adéquate et efficace. Le planning de la page suivante modélise cette idée.

La première étape d’un compilateur est l’analyse lexicale. En effet il faut traduire et analyser le programme pour vérifier l’emploie exclusif du vocabulaire de la grammaire. Nous avons dans notre cas utilisé un outils intéressant pour cette étape, lex.

Lex est un analyseur syntaxique fourni en standard sous UNIX, sous la forme d’une bibliothèque C. Il permet de transformer un flux d’entrée, de l’analyser et d’effectuer les opérations désirées sur le vocabulaire. Nous avons utilisé cette bibliothèque pour simplifier la tâche des analyses suivantes.

Nous avons transformé tous les éléments du vocabulaire, en code, ce qui permet à des fonctions d’analyser simplement les termes employés. Le code utilise deux concepts, les chaînes prédéfinies et les autres. La première catégorie peut être simplement codée par un numéro. En effet si nous codons le mot clé if par le numéro 021, on aura bien un code efficace. Par contre coder une chaîne de caractère ne peut être effectué de la sorte. Nous avons donc introduit un second code. Nous utilisons pour les chaînes, les identificateurs, les entiers et les réels, un autre code ; un code numérique suivi de la chaîne correspondant à l’objet. D’autre part pour des questions de commodité nous avons utilisé des séparateurs, le symbole $.

En résumé nous avons transformé un fichier Pascal en fichier code :

Cette transformation assure de plus, que tous les éléments du fichier Pascal, correspondent bien à un mot du vocabulaire. Si ce n’est pas le cas, l’analyse lexicale interrompt la compilation.

Pour faciliter l’utilisation d’un tel code pendant la phase de développement, nous avons créé un ENUM qui convertit les codes numériques en codes littéraux.

Ce format de codage a été défini pour faciliter la lecture du code lors des analyses suivantes. Ceci a été réalisé à l’aide de fonctions que nous avons implantées dans la classe Utilitaire.

La classe utilitaire regroupe toutes les fonctions de gestions de flux, la macro Assert, la fonction de débuggage, la numérotation de la ligne courante et le numéro du dernier objet créé.

Elles sont au nombre de six divisées en deux groupes de trois, celles qui prennent des informations dans le flux standard et celles qui se contentent de lire le flux. Il existe trois sortes de données sur le flux : les " code " les " var " les " chaîne ".

Nous avons sur le flux des codes $xxx représentant la conversion de symbole par LEX, les données var et chaînes sont précédées d’un code particulier.

Soit i le flux d’entrée standard : $090 pipo$ $084

code=global.PrendreCode(i) ; Le flux devient : pipo$ $084 et code=90

global.PrendreVar(i,variable); Le flux devient : $084 et variable=pipo

Soit i le flux d’entrée standard : 'l''essai est probant'$ $084

global.PrendreChaine(i,chaine); Le flux devient $084 et chaine=l’essai est probant

Les fonctions de lecture sont identiques le pointeur de début de flux est sauvegardé puis restitué à la fin de l’opération de lecture. Nous utilisons pour cela les fonctions seekg et tellg.

Deux autres fonctions de flux sont implantées : l’une convertie une chaine ou un flux en réel flottant et l’autre permet la lecture d’une variable préfixée de son code.

Soit i le flux d’entrée standard : $090 pipo$ $084

global.LireCodeVar(i,variable) ; Le flux reste inchangé et variable=pipo

Soit i le flux d’entrée standard : 53.65e-3$ $084

res=global.Char2Double(i); Le flux devient : $084 et res=0.5365^E-1

Il y a deux variables entières globales, l’une permet de connaître à tout instant la ligne du programme source en cours de traitement et l’autre permet de connaître le nombre d’objets référencés dans les différentes tables des symboles. C’est une CLEF PRIMAIRE permettant de retrouver n’importe quels objets.

Nous avons implanté une gestion de débugage qui lorsque la variable globale _debug est activée produit un affichage, plusieurs niveaux de debug peuvent être implantés.

Il s’agit d’une gestion très sommaire pour relever les exceptions, en effet, il ne s’agit que de la redéfinition de la macro assert ; c’est une gestion bloquante. Un numéro d’exception est adjoint a la fonction assert permettant un affichage de la ligne ou s’est déclenchée l’erreur, le numéro du dernier objet créé ainsi que la nature de l’erreur.

L’étape suivante est composée de la vérification syntaxique et sémantique qui doivent aboutir à la génération de l’arbre.

La première étape de notre réflexion a été d’établir une structure de programmation nous permettant de faciliter la création de l’arbre pendant la vérification de la syntaxe. Nous avons donc défini une structure basée sur une classe principale, la classe Nœud. Cette classe, à l’origine de la création de l’arbre, sera expliquée ultérieurement.

Notre raisonnement a commencé par une réflexion sur la structuration du langage Pascal. Ce dernier est construit en deux grandes parties. Une partie déclarative et une partie de définitions.

La classe de départ est un Bloc. Elle hérite naturellement de Nœud, pour permettre la création de l’arbre. Cette classe génère un objet qui est la structure de base de la définition du code. Elle possède une table des symboles pour permettre la visibilité des variables, fonctions et autres déclarations.

La classe SuperBloc est une sous classe de la classe Bloc. Elle implémente le concept de la déclaration. Nous avons donc le principe implanté dans le schéma. Il en est de même pour la classe Program, Procedure, et Function qui sont des Superbloc particuliers.

La deuxième partie des classes héritant de Bloc sont de deux types :

Le principe de base est une analyse prenant un objet istream en argument, et lors de l’appel des constructeurs des classes, la génération de l’arbre et l’analyse du code se font simultanément. Lors de la création d’un SuperBloc, nous utilisons l’initialisation d’un Bloc. Le fait que nous ayons besoin d’utiliser la construction du SuperBloc avant, nous a obligé à ne pas appeler le constructeur définie du Bloc, mais un constructeur par défaut, suivie par une fonction d’initialisation de Bloc. En effet nous voyons sur le schéma, que la partie déclarative est avant la partie de définition.

Pour permettre le bon déroulement du programme il nous a fallu une série de classes ne faisant pas partie de cette architecture (voir schéma des classes). Nous allons maintenant détailler plus précisément l’implantation de toutes ces classes.

Lors de l’élaboration du compilateur, il nous a fallu faire une table des symboles, permettant d’identifier toutes les variables, quelles soient globales, où locales à un bloc. Notre choix a été alors d’associer une table par bloc. Cette méthode, possible grâce au langage objet comme C++, nous a permis d’éviter les problèmes de visibilité. Il est naturel, lors de l’élaboration d’un programme de considérer que la liste des variables accessibles, sont celles du bloc courant, et des blocs qui l’englobe. Nous avons repris exactement la même philosophie.

La classe TableSymbole est un objet contenant des membres, des constructeurs et des accesseurs, qui définissent une déclaration. Le bloc contient un membre _table_symbole qui est une liste chainée de ces éléments de base. Un objet TableSymbole se compose comme suit :

La gestion de la table des symboles se fait par l’intermédiaire de deux types de fonctions ; les AddTableSymbole et les FindTableSymbole. La première catégorie de fonctions, sont des fonctions d’ajout d’éléments dans la table des symboles. Elles vérifient que l’objet n’existe pas dans la table locale, et ajoute la référence. Il existe plusieurs types de fonctions d’ajout, permettant l’insertion de plusieurs types d’éléments. La seconde est une fonction de recherche dans la table des symboles, à partir d’un nom ou d’une référence, elle recherche dans les tables des symboles visibles l’objet. Ces fonctions sont essentielles au compilateur pour fonctionner normalement. Nous avons pour les utiliser depuis n’importe quel nœud, fait également une fonction de recherche de bloc, qui renvoie le bloc local dans lequel le nœud se trouve.

Nous avons fait un choix, à même de faciliter la compilation, en effectuant les ajouts et les vérifications dans la table des symboles lors de la création de l’arbre. Cette façon de procéder, est rendue possible grâce à la structuration de nos classes, et nous évite de créer les nœuds inéluctables aux déclarations. C’est une optimisation intéressante qui accélère la compilation.

Au sein de l’arbre de dérivation nous avons défini cinq types de nœuds.

Le chaînage entre un nœud père et ses fils est donc représenté comme ceci :

La construction d’un nœud nécessite de spécifier les pointeurs Père, Petit_frère, Fils et le champ (type si c’est un nœud de base, valeur numérique si c’est un " NœudInt " ou " NœudReal " ou " NœudBool ", référence si c’est un nœud " NœudVar ").

Les pointeurs Grand_frère et Petit_dernier ne sont pas accessibles à l’utilisateur et ont été implémentés pour faciliter la gestion interne de l’arbre et pour améliorer les temps de parcours.

L’insertion d’un nœud dans l’arbre peut être réalisée de deux façons. La première consiste simplement à spécifier le type du nœud à insérer. La deuxième nécessite au préalable la construction d’un nœud et se contente de l’attacher au sein de l’arbre.

Voici la description de la mise à jour des pointeurs lors d’une insertion.

Après insertion du nœud

Lorsqu’un nœud a été créé et inséré, l’utilisateur ne peut en aucun cas modifier les pointeurs Père, Petit_frère, et Fils.

La détection du " ; " déclenche l’appel de la construction de SuperBloc et attend un " . " final.

Il y a trois phases dans SuperBloc, une phase de détection des déclarations ( VAR, CONST, TYPE ) avec inscription des déclarations dans la table des symboles. Une 2^ème phase consiste à détecter d’éventuelle définition et déclaration des fonctions et procédures. Cette phase est primordiale puisque c’est elle qui génère la table des symboles. Et finalement une phase d’implantation du code.

C’est le nœud initiateur de l’implantation du code, c’est lui qui effectue la vérification de la syntaxe, des instructions et déclenche le constructeur approprié. Il réalise également un contrôle sémantique entre les identificateurs utilisés dans son bloc et ceux déclarés dans les différentes tables des symboles.

Il y a 2 phases ; une phase de définition et une phase de déclaration. La définition permet la récursion dans des procédures ou des fonctions imbriquées ; la définition permet une première vérification sémantique. La gestion du passage des paramètres est en interaction direct avec la table des symboles.

Function pipo(a :integer ; var b :real ; tab :tableau) :integer ;

Va générer, à la déclaration, une entrée dans la table des symboles de la forme :

Lors de la définition :

Tout langage comporte un certain nombre d’instructions de base nécessaires à toute opération. Ce sont en Pascal, le calcul des expressions, des affectations, des tests, des appels de procédures et de fonctions et nous y avons rajouté des primitives d’entrée/sortie.

Nous allons détailler l’implantation dans l’arbre des diverses instructions et règles de la grammaire.

Le principe de base de l’implantation de la grammaire dans l’arbre est résumé par le schéma suivant. Nous avons ici différents types de nœud d’un arbre, où a et b sont des symboles pouvant représenter différents vocabulaires.

L’aspect intéressant de ce schéma est la formation d’un nœud de type bloc, qui est le principe de base de la construction d’un programme. Un programme, est en effet une imbrication de blocs.

Une expression est une succession d’éléments qui permettent de calculer une expression arithmétique, c’est à dire un nombre.

Le but de notre travail est tout d’abord de lire cette expression, mais surtout de la représenter sous une forme facile à comprendre, à visualiser et à utiliser pour les opérations futures. C’est pour cela que nous utilisons un arbre.

Dans cet arbre chaque feuille représentera un terminal, et chaque nœud un connecteur différent ( opérateur, nom d’identificateur ).

Tous les noeuds non terminaux sont de même type ( ici Nœud ). Tous les terminaux ont quant à eux un type différent, correspondant au rôle de ces terminaux dans l’expression. Ces sous-types héritent tous de la classe Noeud, et ont chacun des éléments supplémentaires qui leur sont propres.

si la feuille est un entier , le noeud correspondant sera de type NoeudInt

réel NoeudReal

booléen NoeudBool

idem pour les identificateurs qui correspondent aux variables, constantes, fonctions ou bien tableau sauf qu’ils seront de type NoeudVar.

Tout ceci nous permet de gérer un arbre très efficacement qui est lui même très efficace.

Remarques :

Nous allons par contre voir comment sont représentés les tableaux car c’est dans cette section que nous les traitons.

Tout d’abord il faut trouver un identificateur en entrée, et vérifier qu’il existe bien dans la table des symboles et que c’est bien un tableau (cf. class TableSymbole) . Ensuite nous comptons le nombre d’argument et vérifions que ces derniers sont tous de type entier. Nous regardons aussi s’il n’y a pas d’erreur de syntaxe ( une virgule est absente ... ). Lorsque tout est OK, nous pouvons passer à la suite.

Voici un schéma représentant la grammaire que nous utilisons pour reconnaître une expression :

Nous l’avons implanté grâce à des fonctions récursives qui vont générer l’arbre au fur et à mesure. Cela ressemble aux automates : suivant le caractère lu nous passons dans un autre état en appelant une autre fonction récursive et en construisant l’arbre si nécessaire. Cette façon de faire nous permet de vérifier la syntaxe tout en générant l’arbre.

De plus dans la construction il nous arrive de sauvegarder des sous arbres qui ont été construits précédemment pour pouvoir ensuite les concaténer au dernier nœud créé.

Voici un exemple pour l’addition 1+2+3

Lecture de 1 => tmp = NoeudInt(1)

Lecture de + => tmp2 = Nœud(+)

Tmp1 devient le premier fils de tmp2

Lecture de 2 => tmp3 = NoeudInt(2)

Tmp3 devient le deuxième fils de tmp2

Lecture de + => tmp4 = Noeud(+)

Tmp2 devient le premier fils de tmp4

Lecture de 3 => tmp5 = NoeudInt(3)

Tmp5 devient le deuxième fils de tmp4

On retourne tmp4

Remarque : ces calculs sont en fait optimisés dans la programmation mais suivent les mêmes règles.

Voici un exemple pour la représentation grammaticale de l’expression : i+3=TOTO*tab[1,2]

dans l’arbre, où

Ci dessous se trouve un schéma grammatical représentant une affectation.

Nous pouvons constater qu’une affectation est en fait la lecture d’un identificateur, puis celle d’un  := et enfin celle d’une expression.

Une vérification est faite au niveau de variable pour vérifier qu’elle existe.

Le IF est une structure de test simple. Elle effectue une vérification sur un test, et exécute un des deux blocs joint.

La programmation de cette instruction est faite par la création d’un nœud de type Expression, un ou deux de type Bloc, que nous lions ensemble.

Le WHILE et le REPEAT utilisent le même principe pour la programmation. Ces deux schémas nous montrent les grandes lignes.

Le FOR est basé sur le même principe avec un niveau de difficulté légèrement supérieure. Nous considèrons qu’il existe deux types de FOR, les positifs et les négatifs. Les premiers partent d’une valeur, et vont à une autre valeur en additionnant 1, les second utilisent une décrémentation du compteur. Nous pouvons donc décomposer le FOR en quatres étapes : Une affectation, un test, un bloc et une incrémentation ou décrémentation. On a donc le schéma suivant :

Les appels n’utilisent pas de grands concept lors de la création de l’arbre. Il suppose tout de même un certain nombre de vérification, avant la création. En effet il faut vérifier l’existence de la fonction appelée. Puis vérifier que cette fonction comporte bien les bons paramètres. Il faut ensuite créer un arbre de la forme du schéma.

Ces deux fonctions ne créent pas d’arbre complexe, mais juste un nœud. Il est composé d’une référence dans la table des symboles, soit pour pointer l’objet qui recevra le résultat du READ, soit pour indiquer l’objet à afficher. Ces fonctions n’acceptent qu’un seul argument, contrairement au Turbo Pascal.

L’analyse sémantique a pour but de vérifier le sens d’un programme syntaxiquement correct. Elle doit donc inspecter si les variables sont bien déclarées et non dupliquées. Or, nous avons choisi pour des raisons d’optimisation de vérifier ces deux conditions à l’étape de l’analyse syntaxique. L’analyse sémantique de notre compilateur Pascal se résume donc à la conversion des types.

La conversion de type consiste à insérer des nœuds de transformation et à expliciter le type de certains opérateurs. Les nœuds de conversion peuvent contenir au sein du champ type l’information suivante :

Ä REAL_TO_INTEGER,

Ä INTEGER_TO_REAL,

Ä INTERGER_TO_BOOLEAN,

Ä BOOLEAN_TO_INTEGER,

Ä REAL_TO_BOOLEAN,

Ä BOOLEAN_TO_REAL,

Pour des raisons de commodité, nous avons géré le type BOOLEAN de la même façon qu’un type INTEGER.

La première étape consiste à rechercher pour chaque instruction stockée dans l’arbre les types prioritaires.

Deux cas doivent être distingués :

Ä Pour une affectation, le type des instructions situées à droite de l’affectation doit être identique au type de la variable ou du tableau situé à gauche de l’affectation. Le type prioritaire est donc celui de la variable ou du tableau.

Ä Pour les instructions de comparaisons (>, <, >=, <=, <>, =, …, OR, XOR, AND, NOT), le type prioritaire doit être recherché avant de réaliser les insertions de conversion.

Dans l’exemple ci-dessus, nous voyons qu’il est nécessaire de parcourir le sous-arbre de l’instruction pour déterminer que REAL est le type prioritaire.

La deuxième étape consiste à reparcourir l’arbre pour insérer les nœuds de conversion et pour modifier le type des opérateurs.

Lorsque le type prioritaire d’une instruction a été déterminé, chaque nœud dont le type est différent du type prioritaire doit être converti.

Dans l’exemple précédent, l’insertion d’un nœud " INTERGER_TO_REAL " doit être effectué et le type de l’opérateur doit être modifié.

Lorsque la conversion à réaliser est de type REAL_TO_INTEGER, INTERGER_TO_BOOLEAN, BOOLEAN_TO_INTEGER, REAL_TO_BOOLEAN, il n’y a pas de modification du type de l’opérateur à effectuer pour deux raisons. La première est que nous avons géré les types BOOLEAN de la même manière que les types INTEGER. La deuxième est que si un type opérateur n’est pas réel, nous le considérons au niveau de la génération de code comme un opérateur entre deux entiers.

Cette liste est composée d’une classe List trouvée sur internet, dans laquelle nous avons rajouté des fonctions utiles pour notre projet de compilation.

Nous avons donc implémenté deux classes :

ListElement : Cette classe nous permet en fait de créer des maillons de type TableSymbole, qui serviront de support pour la liste.

Les données membres sont

Le maillon suivant : de type ListElement

L'objet du maillon : de type TableSymbole

List : Cette classe génère une liste, et fournit un grand nombre d'outil pour l'utiliser

Les données membres sont

le premier maillon de la liste : de type ListElement

le dernier maillon de la liste : de type ListElement

Dans le schéma ci-dessous se trouve la représentation d’une liste avec nos classes

Voici une rapide énumération des fonctions disponibles dans la classe List :

IsEmpty

InserDebut

InsertFin

EnleveDebut

EnleveFin

AjouteListDebut

AjouterFin

RechercheCharList

RechercheRefList

Ref2CharList

Char2RefList

Comment fonctionne cette liste ?

A la création, cette liste est vide. Quand nous lui rajoutons un élément (un maillon), nous pouvons soit le mettre en début, soit en fin de liste. Une remarque très important est que les éléments ne sont pas triés. Nous avons aussi la possibilité de concaténer deux listes différentes. Pour la suppression d’un maillon, nous enlevons soit le premier, soit le dernier. Mais nous n’avons pas implanté de fonctions de suppressions d’un maillon n’importe où dans la liste. Pourquoi ?. Parce que nous ne traitons que des blocs de maillon, c’est à dire des suites successives de maillons. Et lorsqu’il faut les enlever de la liste, il suffit de les retirer par là où ils ont été inséré.

Il nous est aussi possible de savoir à tout moment si une liste est vide grâce à une fonction appropriée.

Il y a de plus des fonctions qui font appels à la classe TableSymbole : Ces fonctions permettent de rechercher dans la liste le maillon correspondant à une certaine demande, et renvoie son adresse.

Dans un premier temps, nous avions pensé générer du code pour la machine virtuelle Java. Rapidement, nous nous sommes rendus compte que cela allait engendrer de nombreuses difficultés liées aux contrôles de sécurité qu’effectue le simulateur Java avant et pendant l’exécution du code.

Pour ces raisons, nous avons préféré diriger notre choix sur la génération d’un code assembleur pour processeurs Mips.

Les avantages de notre choix :

Les inconvénients de notre choix :

Le code généré fonctionne donc principalement à l’aide de la pile. Cependant l’utilisation de six registres reste indispensable. Quatre afin de pouvoir exécuter les instructions Mips qui nécessitent comme opérandes des registres, $s0 et $s1 afin d’effectuer les calculs sur les entiers, puis $f0 et $f2, registres du copossesseur mathématique pour réaliser les calculs sur les réels. Les deux derniers registres utilisés sont $sp, le pointeur de pile et $s7, le pointeur sur le dernier bloc de variables locales alloués.

Comme le montre le schéma précédant, la génération du code est réalisée à l’aide de l’arbre et des tables de symboles que lui fournit l’analyse sémantique. Il est donc nécessaire d’interpréter cet arbre en lui associant les instructions assembleurs correspondantes.

Intéressons nous au code généré par les instructions suivantes :

Voici l’arbre (simplifié) généré par ces instructions :

Principe théorique de génération du code à partir de l’arbre logique :

Principe utilisé pour la génération du code à partir de l’arbre physique :

Les variables globales sont déclarées dès la compilation et sont stockées dans le segment de donné. Les variables locales sont allouées et désallouées sur la pile au cours de l’exécution du code assembleur.

A chaque appel d’une procédure/fonction et à plus forte raison, lors d’un appel récursif, il faut allouer un nouvel espace pour les variables locales. Les variables passées en paramètre à ces procédures/fonctions sont gérées de la même manière que les variables locales à la seule différence qu’elles sont initialisées par les arguments de la procédure/fonction.

L’allocation d’espace pour les variables locales est effectuée durant l’exécution du programme. Lors de l’appel d’une procédure/fonction, un bloc d’espace est réservé sur la pile. A la compilation, nous ne connaissons pas l’adresse des variables locales mais nous connaissons pour chaque variable son emplacement relatif par rapport au début du bloc courant. Ainsi nous avons lors de l’exécution du programme toujours accès aux variables en additionnant le déplacement relatif de la variable recherchée à la valeur du registre $s7 qui représente un pointeur sur le début du bloc courant. Ce pointeur est soigneusement remis à jour sur les bons blocs au fur et à mesure des appels.

Lors de l’appel successif de la même procédure/fonction, il est évidant grâce au principe cité ci-dessus, que l’utilisation des variables dans les procédures/fonctions englobées n’a aucune influence sur les valeurs des variables des procédures/fonctions englobantes. Les variables globales sont quant à elles uniques et leurs modifications est visible dans tout le programme.

Tout au long de la génération du code assembleur, il est nécessaire d’utiliser des labels. Ces labels sont donc générés en même temps que le code. Les labels fonctionnent par groupe, un label unique est donc utilisé un nombre de fois déterminé, à des emplacements déterminés. Un nombre inconnu de label peuvent être généré entre deux labels devant être identiques (cas de If imbriqué, etc ...). Il est donc impossible d’utiliser une fonction GénérerUnLabel() qui retournerait le label approprié au bon moment. Nous avons donc choisi d’utiliser une fonction GénérerLabels() qui empile tous les labels nécessaires à un moment donné, et une fonction PrendreLabel() qui renvoie un label après l’avoir dépilé sur cette pile.

Le Mips étant un processeur Risc, il possède un jeu d'instructions limité. Cela nous pose un problème lorsque nous souhaitons placer dans un registre un flottant car il n'existe pas d'instruction prévue à cet effet. L'astuce est de coder dans un premier temps ce flottant sur un entier de 32 bits en utilisant la notation suivante.

La représentation d'un réel sous Mips est définie par la norme IEEE. Sa forme générale est la suivante:

(-1)^S x (1+signifiant) x 2 ^E

Ä S représente le signe,

Ä signifiant est une fraction entre 0 et 1,

Ä E est l'exposant.

En appliquant cette formule, un flottant simple précision est stockée sous Mips au sein de 32 bits :

Prenons comme exemple le réel -0.75.

Sous forme de fraction ce chiffre est représenté par

-0.75 = -3 x 2 ^-2 = -11 x 2 ^-2 = -1.1 x 2 ^-1.

Sa représentation générale est donc

(-1)¹ x (1 + .1000 0000 0000 0000 0000 000) x 2 ^(-1+127).

En binaire :

En hexadécimal

La nouvelle représentation hexadécimale de nos réels nous permettra grâce à l'instruction li (load immédiat) de les charger dans un registre.

Nous allons montrer les différentes étapes de la compilation d’un fichier Pascal, calculant le PGCD de deux nombres.

program pgcd ;

var nombre_1 : integer;

var nombre_2 : integer;

begin

write ('Programme calculant le PGCD\n' );

write ('---------------------------\n\n');

write ('Valeur du premier nombre : ' );

read(nombre_1);

write ('\nValeur du deusieme nombre : ' );

read( nombre_2 );

while (nombre_1 <> nombre_2) do

begin

if (nombre_1 > nombre_2) then

begin

nombre_1 := nombre_1 - nombre_2;

end

else

begin

nombre_2 := nombre_2 - nombre_1;

end;

end;

write ('\nLe PGCD des deux nombres est : ' );

write (nombre_1);

end.

$037 $090 pgcd$ $084

$052 $090 nombre_1$ $059 $022 $084

$052 $090 nombre_2$ $059 $022 $084

$005

$055 $071 $089 'Programme calculant le PGCD\n'$ $072 $084

$055 $071 $089 '---------------------------\n\n'$ $072 $084

$055 $071 $089 'Valeur du premier nombre : '$ $072 $084

$039 $071 $090 nombre_1$ $072 $084

$055 $071 $089 '\nValeur du deusieme nombre : '$ $072 $084

$039 $071 $090 nombre_2$ $072 $084

$053 $071 $090 nombre_1$ $062 $090 nombre_2$ $072 $014

$005

$021 $071 $090 nombre_1$ $068 $090 nombre_2$ $072 $045

$005

$090 nombre_1$ $058 $090 nombre_1$ $076 $090 nombre_2$ $084

$017

$016

$005

$090 nombre_2$ $058 $090 nombre_2$ $076 $090 nombre_1$ $084

$017 $084

$017 $084

$055 $071 $089 '\nLe PGCD des deux nombres est : '$ $072 $084

$055 $071 $090 nombre_1$ $072 $084

$017 $073

jr $ra # Retour au systeme appellant

Nous sommes heureux d’avoir achevé ce projet de compilation dans les temps impartis. Nous en avons retiré un enrichissement personnel. Il nous à permis d’approfondir et de consolider nos connaissances en compilation. Les résultats obtenus sont très satisfaisants puisque d’un programme source Pascal nous sommes arrivés à générer un fichier en assembleur qui est exécuté par le simulateur Xspim sur Es2i. Ces résultats positifs n’ont pas été obtenu sans peine, nous estimons y avoir passé 350 heures homme soit environ 75 heures par personne.

L’étude de la conception à été la phase la plus difficile mais le temps consacré sur cette partie était indispensable, nous n’y avons pas rencontré d’erreur fondamentale par la suite.

L’analyse lexicale grâce à Lex a abouti rapidement.

De part notre travail de programmation orienté objet, nous avons rencontré quelques difficultés dans la réalisation des fonctions permettant l’analyse sémantique car elles vérifient la syntaxe et construisent simultanément l’arbre associé.

Pour la sémantique, nous avons effectué des conversions de type, les autres étapes qui incombent généralement à cette partie ayant été réalisées pendant l’analyse syntaxique et la génération du code intermédiaire.

La complexité de la génération du code intermédiaire a résidé surtout dans la réalisation simultané du code assembleur et du code permettant de le générer ainsi que la gestion des variables locales.

Une bonne organisation du groupe et son dynamisme nous a permis d’effectuer un assemblage rapide des différentes parties réalisées par chacun d’entre nous. Une distribution homogène des taches au sein du groupe nous a permis d’interagir sur les programmes pour assurer leur compatibilité.

Ayant abordé les principaux points stratégiques de la conception, nous avons décidé de l’interrompre, malgré l’absence de certaines fonctionnalités mineures.