PROJET DE COMPILATION

Gilles BRETZNER
Nicolas MEUNIER
Blandine FRANCART
Abdoulkader OSMAN GUEDI - Chef de Projet -

Au début de l'informatique, on programmait directement les ordinateurs en langage machine. Cela s'est vite avéré fastidieux. On a très vite essayé d'utiliser les possibilités de l'informatique pour faciliter le travail de programmation. Pour cela, il a fallu construire des programmes qui traduisent des énoncés exprimés dans le langage de haut niveau utilisé par les programmeurs, ce que l'on appelle le langage source,en instructions pour la machine cible. Les programmes effectuant ce genre d'opération s'appellent des compilateurs (ou des interprètes, nous verrons la différence par la suite, mais pour l'instant elle n'est pas fondamentale).

Définition

Selon une définition simplifiée, un compilateur est un programme qui lit un programme écrit dans un langage (C, C++ ?, ici on s'intéressera qu'à PASCAL) source et le traduit en un programme équivalent écrit dans un autre langage cible. Et ce dernier a pour rôle de signaler la présence d'erreurs dans le programme source.

**Figure 1.1:** Définition
$\includegraphics[scale=0.8]{images/def.eps}$

Réalisation d'un compilateur

Un compilateur est en d'autre terme un programme de conversion, c'est à dire on part toujours d'un programme source pour en obtenir un programme exécutable. Pour réaliser ce programme de conversion on a deux méthodes :
1. En assembleur : programmation en code assembleur
2. En C : programmation en code C sous linux/Unix en utilisant des outils efficaces tel que Lex.

Phases de compilation

Principe

Un compilateur est découpé en plusieurs phases. Chaque phase constitue une partie de traduction en elle-même (voir Figure ci-dessous).

**Figure 2.1:** Les phases de la compilation
$\includegraphics[scale=0.75]{images/phase.eps}$

Analyse lexicale

Définition

L'analyse lexicale consiste à la première phase d'un compilateur, cette phase consiste à segmenter un texte source en un ensemble de mots que l'on appelle traditionnellement «tokens» (leur terme exact est «lexème», ce qui signifie unité lexicale). Il s'agit d'une part de déterminer la suite des caractères comprenant le token, et d'autre part d'identifier le type de token (identificateur, nombre, opérateur, etc.) On peut en déduire que l'analyse lexicale permet d'isoler les unités lexicales d'un programme qui est dans notre projet un programme source PASCAL, le but essentiel de cette phase est le repérage et/ou l'isolement des unités lexicales du programme (langage) et permet de détecter les unités qui ne font pas partie du langage. Pour cela, on dispose de deux méthodes :

L'automate d'état fini

Desciption

L'automate d'état fini représente l'une de méthode utilisée pour la détermination des unités lexicales. Les automates sont capables de reconnaître et de définir précisément les différents types d'un langage. Nous avons généré dans un premier temps à modéliser un automate d'état fini complet (voir ci-dessous) qui reconnaît la langage Pascal (Mini-Pascal). Pour pouvoir implémenter la première version (mypcv1 voir dans l'avancement), nous avons génère une matrice d'incidence qui correspond à l'automate. La matrice d'incidence correspond à un tableau dont les colonnes représentent les unités lexicales. La matrice d'incidence permet de décrire structurellement l'automate (voir figure ci-dessous). L'inconvénient de cette méthode est à chaque fois qu'une mise à jour et/ou un changement s'effectue sur l'automate on doit régénérer la matrice d'incidence correspondante.

**Figure 2.2:** L'automate d'état fini
$\includegraphics[scale=0.8]{images/auto.eps}$

Type	Entier	Lettre	.	Sépar	+ - * /	Espace	:	=	{ (	*	) }	[	> <	]
1	2	4	-7	-7	-8	1	5	9	6	7	-7	8	-10	-7
2	2	-1	3	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1
3	3	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2	-2
4	4	4	-3	-3	-3	-3	-3	-3	-3	-3	-3	-3	-3	-3
5	-7	-7	-7	-7	-7	-7	-7	-4	7	-7	-7	-7	-7	-7
6	-7	-7	-7	-7	-7	-7	-7	-7	-7	-5	-7	-7	-7	-7
7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-6	-7	-7	-7
8	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-9
9	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-7	-10	-7

la Matrice d'incidence

A l'aide de cet outil (Lex) nous avons implémenté la deuxième version (mypcv2 voir dans l'avancement), l'avantage de ce dernier est le gain de temps à la conception, souplesse, optimisation des flux dans l'analyseur, avantages du C.

LEX -> générateur ou d'analyseur lexical

Lex est un utilitaire fourni avec Unix/Linux. Il permet de créer automatiquement le code source d'un analyseur lexical, à partir d'instructions contenues dans un fichier et il permet de faire des recherches de mots dans un texte et d'associer aux mots trouvés un bloc d'action. Les actions seront effectuées dans le langage de notre choix, ce sera donc le C dans notre cas. L'appel à Lex génère automatiquement la matrice d'incidence à partir des règles définies dans le fichier lex. Les règles définies correspondent à des expressions régulières qui permettent de reconnaître les différentes unités lexicales. Nous avons mis en place un fichier (analex.l) qui contient expressions régulières et cet outil Lex nous génère automatiquement un fichier en C qui la matrice d'incidence correspondant aux expressions régulières.

Analyse syntaxique

Définition

L'analyse syntaxique correspond à la deuxième phase d'un compilateur, et cette dernière permettra de décrire un langage sous forme d'une grammaire ainsi que les productions correspondes. Cette phase détermine la grammaire du langage comme tout autre langage naturel (La grammaire du langage français). Par exemple pour la boucle for en C for (initialisation ; condition ; incrémentation), l'analyse syntaxique nous indique qu'il faut trois arguments séparer par des points virgules et le tout entre parenthèses. Lors de l'analyse syntaxique, on vérifie que l'ordre des tokens correspond à l'ordre définit pour le langage. On dit que l'on vérifie la syntaxe du langage à partir de la définition de sa grammaire. Dans le cadre de notre projet nous avons utilisé les diagrammes de Conway pour le langage de Pascal. Ces diagrammes permettent de visualiser la composition syntaxique d'une phrase du langage Pascal ainsi que les relation entre les différents symboles.

Diagrammes de Conway

Dans cette partie nous avons défini les déférents diagrammes de Conway avec les symboles non terminaux et les symboles terminaux (rendu par l'analyseur lexical Lex).

En Pascal un programme commence par le Mot-clé « Program » suivi par un identifient qui indique le nom du programme, ensuite on définit l'entête qui se termine par un point virgule « ; », puis un bloc et enfin le programme se termine par un point (.). (Voir figure ci-dessous).

**Figure 2.3:** Programme
$\includegraphics[scale=0.8]{images/programme.eps}$

L'entête correspond à un ensemble d'identificateurs entre parenthèses séparer par des virgules (Voir figure 5).

**Figure 2.4:** Figure 5 En-tête
$\includegraphics[scale=0.8]{images/entete.eps}$

Le bloc représente un ensemble de constantes, de déclarations, et de instructions,(Voir ci-dessous).

**Figure 2.5:** Bloc
$\includegraphics[scale=0.8]{images/bloc.eps}$

**Figure 2.6:** Constante
$\includegraphics[scale=0.8]{images/const.eps}$

Le diagramme des déclarations en Pascal se représente comme ceci,(Voir ci-dessous).

**Figure 2.7:** Déclaration
$\includegraphics[scale=0.8]{images/dcl.eps}$

Le diagramme des instructions en Pascal se représente comme ceci,(Voir ci-dessous).

**Figure 2.8:** Instruction
$\includegraphics[width=12cm]{images/inst.eps}$

Le diagramme d'une condition en Pascal se représente comme ceci,(Voir ci-dessous).

**Figure 2.9:** Condition
$\includegraphics[scale=0.8]{images/cond.eps}$

Le diagramme des expressions en Pascal se représente comme ceci,(Voir ci-dessous).

**Figure 2.10:** Expression
$\includegraphics[scale=0.8]{images/expr.eps}$

**Figure 2.11:** Terme
$\includegraphics[scale=0.8]{images/terme.eps}$

Dans le cadre de notre projet nous ne prenons pas en compte les fonctions et les procédures en Pascal, Mais toute même ils se représentent comme ceci :

D'où <Nom> et Argument correspondent à des identifiants et Type correspond à soit INTEGER, REEL, BOOLEAN, STRING ...

Module de symbole

Définition

Le module de symbole est représenté par une table qui stocke toutes les informations concernant une variable et une constante. Cette table nous permettra aussi de détecter les erreurs syntaxiques : par exemple de vérifier si une variable est bien déclarée et même la valeur de cette variable s'il s'agit d'une constante. Les informations à stocker dans la table de symbole :

Le champ Nom correspond au nom de la variable.
Le champ Type correspond au type de la variable qui soit INTEGER, REEL, BOOLEAN, STRING ...
Le champ Val correspond à la valeur de la variable lors de la déclaration qui est nulle pour les variables et la valeur effective pour les constantes.
Le champ depl correspond au déplacement de la variable ou de la constante
c'est à dire on attribue un entier lors de la déclaration et ce dernier correspondra à son déplacement par rapport au autres variables.

Implémentation d'une table de symbole

En ce qui concerne l'implémentation de la table de symbole nous avons utilisé un tableau dont chaque case est une structure qui stocke les informations d'une variable ou une constante. Nous avons implémenté aussi toutes les fonctions pour faciliter les accès (renvoie du depl ... voir les sources).
Et cela se représente comme ceci :

NOM	TYPE	VALEUR	DEPLACEMENT
I	CONST	3.1415	0
j	INTEGER	0	1
x	REAL	0	2
y	BOOLEAN	0	3

Génération du P.code

Définition

Le P.code se défini comme un ensemble de code à machine à pile et il intervient à l'exécution du programme Pascal ( c'est à dire la compilation a réussi ). Ce code intermédiaire est interprété par une pile qui utilisera aussi la table de symbole. Il y a un code spécifique pour chaque instruction et nous allons devoir gérer l'écriture post-fixée des différentes opérations arithmétiques ou de comparaisons ce qui nous facilitera à mettre en forme les expressions dans la pile. La gestion de la pile consiste à faire des opérations arithmétiques et de comparaisons ...

Implémentation du P.code

Description du P.code

CODE	Désignation
LOD	Charge une variable en haut de pile
LIT	Charge une littéral en haut de pile
OPR	Effectue une opération arithmétique ou de comparaison
STO	Copie la valeur du haut pile au déplacement indiqué
OUT	Affiche sur la sortie standard (stdout)
INP	lire sur l'entrée standard (stdin)
NOP	Pas d'opération
JPC	Saut conditionnel à la ligne souhaitée
JMP	Saut inconditionnel à la ligne souhaitée
INR	Alloue une place mémoire pour une variable ou une constante
STP	Indique la fin du programme
RST	Appel d'un system call

Mise en place du P.code

Pour l'implémentation nous avons d'abord stocké dans un tableau les différents opérateurs arithmétiques et de comparaisons, et cela se présente comme ceci :

Ensuite une structure qui contient un entier qui représente l'adresse du pointeur qui pointe sur le haut de la pile et un entier qui indique l'adresse de la base (ceci est nulle dans notre cas, car nous ne prenons pas en compte les fonctions et les procédures. Et un tableau de structure dont chaque case correspond à un segment qui indique la nom et la valeur de la variable (voir exemple ci-dessous).

Exemple d'un P.code généré

13 LOD 0, depl(j)
14 LIT 0, 10
15 OPR 0, 5
16 JPC 0, 19
17 LOD 0, depl(j)
18 LIT 0, 1
19 OPR 0, 0
17 STO 0, depl(j)
18 JMP 0, 13
19 NOP 0, 0

20 LOD 0, depl(x)
21 LIT 0, 0
22 OPR 0, 9
23 JPC 0, 29
24 LOD 0, depl(PI)
25 LIT 0, 9
26 OPR 0, 3
27 STO 0, depl(x)
28 JMP 0, 33
29 LOD 0, depl(PI)
30 LOD 0, depl(PI)
31 OPR 0, 3
32 STO 0, depl(r)
33 STP 0, 0

34 OUT 0, depl("Hello");
35 OUT 0, depl ("Saisir un entier ");
36 INP 0, depl(j)
37 OUT 0, depl("j")
38 OUT 0, depl("=")
39 OUT 0, depl(j)
40 STP 0, 0

L'interpréteur "pile d'exécution"

Définition

Une pile représente un changement dynamique des données qui sont stockées dedans, et dans notre cas elle consiste à interpréter un code intermédiaire «P.code» qui résulte d'un programme PASCAL.

Implémentation du P.code

L'implémentation de la pile consiste un tableau de structure dont cette dernière représente trois champs :
1) Un pointeur sur l'adresse du haut de la pile «PP».
2) Un pointeur sur l'adresse de la base de la pile «Base».
3) Une structure qui représente un segment de la pile (Nom et Valeur).

Exemple

A chaque opération on empile les valeurs des variables ou des constantes puis on effectue l'opération en haut de la pile et le STO permet de dépiler et affecter la valeur qui se trouve en haut de la pile à l'emplacement indiquée de même pour le JPC qui dépile et saute à la ligne indiquée.

y	0
x	0
j	0
PI	3.1415
NOM	VALEUR

L'interface graphique

Conception de l'interface graphique

Implémentation de l'interface graphique

En ce qui concerne l'implémentation de l'interface graphique nous avons choisi java comme langage de programmation.

Maquette de l'interface graphique

Documentation

Conclusion

Outils et langages utilisés

1) Les langages : C et java
2) Les outils : Lex/flex
3) Les Logiciels : Net Beans et sun one studio

Problèmes rencontrés

Nous devions définir le nombre d'états que nous voulions afficher dans notre automate. Par conséquent, nous devions établir la limite entre l'analyse lexicale et l'analyse syntaxique. Par exemple, devions nous définir le commentaire l'affectation (...) comme intervenant dans le domaine syntaxique ou lexicale. Dans notre cas, nous avons décidé de l'insérer directement dans le langage lexical. C'est à dire ceci représentait de choisir et/ou de déterminer la frontière entre l'analyse lexicale et l'analyse syntaxique, ce pour cela que les décisions ci-dessus mentionnées étaient choisies.
L'interface graphique :

Nous avions deux principaux solutions pour réaliser l'interface, Tcl/Tk et Java. Ayant déjà réalisé une interface graphique à l'aide de tcl/tk l'année dernière dans le projet client - serveur, nous voulions découvrir un nouveau langage comme Java. Nous devons découvrir le langage Java à l'aide de la documentation Internet et quelques cours de Java que nous n'avons pas encore approfondir. Ainsi avec l'utilisation de tcl tk, il suffit de travailler avec des pipes. Toutefois, ceci est plus difficile à l'aide de java. Ainsi, le problème majeur est de découvrir ce langage et de pouvoir assembler le langage C et le langage Java. Lors de la réalisation de l'interface, nous devions comprendre le fonctionnement de la création des objets et la maîtrise du positionnement des objets.
Enfin, nous sommes en train de réfléchir sur la programmation des procédures événementiels des objets (boutons,...).

Conclusion

Ce projet nous a permis d'éclairer et de répondre à certaines questions par exemple:
comment le compilateur procède à la fois la vérification et génération d'un code exécutable, quelles sont les différentes possibilitées ...
Nous avons appris les différentes méthodes permettant la mise en place d'un compilateur et l'exécution d'un programme en passant de la compilation à l'interprétation...

Le mode d'emploi

Le compilateur

Nous avons effectué cinq versions du compilateur dont chacune de version consécutive est incluse,dans toutes les versions (mypcv1 à 5) il y a un Makefile qui permet de compiler et aussi nous avons mis à disposition des fichiers de PASCAL pour le jeu d'essai. Ces versions peuvent être exécuter sur Linux et Solaris suivant la compilation choisit.
1) Sur linux : make linux
2) Sur Solaris : make solaris
3) Et pour réinitialiser : make clean

L'utilisation des différentes versions,chaque version prend un argument qui correspond au nom du fichier PASCAL dont l'extension est «.p».

Et en sortie nous avons un fichier dont l'extension est «.l» qui correspond aux listings, pour la cinquième version nous avons de plus deux fichiers qui correspondent à la table de symbole et au pcode.

L'interpréteur

L'utilisation de l'iinterpréteur est efficace et cela nous permet de mieux le gérer avec l'interface. Pour la compilation, elle est identique au programme du compilateur PASCAL c'est à dire fonctionne sur Linux et solaris et la réinitialisation est de même.

2) Pour exécuter avec la présence d'un break point «bp» :
* pile fichier.pcode bp numéro_de_ligne

3) Pour exécuter ligne par ligne «next» :
* pile fichier.pcode next numéro_de_ligne

L'interface graphique

L'utilisation de l'interface graphique est conviviale à l'utilisateur et fonctionne aussi sur Linux et Solaris.

1) Sur linux : chargé Principale.java dans Net Beans(dans les développements) ou mode commande $runide puis chargé.

Si le temps nous permettra, Nous allons mettre en place un programme d'installation du compilateur ainsi que l'interpréteur et l'interface graphique associée.

Annexe

Sources du compilateur, de l'interpréteur et de l'interface graphique

Les sources de différentes version peuvent être télécharger soit :
1. Sur antares user-id : e0101913
2. Sur http://www.ifrance.com/A-O-G

À propos de ce document...

This document was generated using the LaTeX2HTML translator Version 2002-1 (1.68)