Projet ICE4404P: écrire un compilateur
Projet ICE4404P
Projet ICE4404P Alain Chillès 2022 – 2023
Le projet est à rendre pour le 11 janvier, avant 23h55. Il sera rendu sur Moodle sous la forme d’une archive .zip contenant
- Un rapport écrit en .pdf, contenant les explications de ce qui a été fait et de ce qui n’a pas été fait.
- Des codes écrits en langage C comme décrit plus loin.
- Un fichier LAC (voir la section 4) et un fichier VM (voir la section 6).
1 Description générale
1.1 Tâches
Ce projet consiste à écrire un compilateur d’un langage très simple en respectant les étapes usuelles et en utilisant les outils du cours. Il comporte plusieurs phases
- Analyse lexicale.
- Analyse syntaxique.
- Analyse sémantique.
- Interprétation (fonctionnement comme une calculatrice – sans programmation).
- Compilation en machine virtuelle.
- Exécution en machine réelle. Le code à compiler et à exécuter est le suivant.
Fichier factorielle.lac
1 \ Fichier "factorielle.lac"
2
3 ( Ce fichier est un "exemple" étudié pour tester
4 l'analyseur lexical écrit en phase 1 du projet)
5
6 : fact ( n -- n!)
7 dup 0=
8 if
9 drop 1
10 else
11 dup 1- recurse *
12 then ;
13
14 : go ( n -- )
15 " Factorielle" count type
16 dup .
17 " vaut :
18 " count type
1
19 fact . cr ;
20
21 " -(1-2)+(3-4)x(-5)" calculate go1.2 Détails du système
Pour pouvoir compiler et exécuter le code ci-dessus, nous disposerons d’une machine virtuelle. Elle est constituée
- d’un processeur dont le type est défini dans la section 5 ;
- d’un tableau d’entiers, appelé « table des symboles », qui contiendra les correspondances entre les noms des objets et leur code, il sera nommé LAC et sera défini dans la section 4 ;
- d’une machine virtuelle, nommée VM, qui sera un tableau d’entiers contenant la description des codes, elle sera définie à la section 4 ;
- d’une pile LIFO dite « pile de données », appelée data_stack, qui sera une pile pouvant contenir des entiers et qui servira à passer les paramètres aux fonctions, elle sera décrite à la section 5 ;
- d’une pile LIFO dite « pile de retour », appelée return_stack, qui sera une pile pouvant contenir des
entiers et dont le rôle sera expliqué à la section 7.
2 Analyse lexicale
2.1 Lexèmes
Les éléments du langage sont
- Les identificateurs (toute chaîne de caractère d’au moins un caractère, composée à l’aide des lettres, chiffres et symboles de ponctuation, sauf le caractère blanc [noté ␣]).
- Les entiers relatifs.
- Les chaînes de caractères (toute chaîne de caractère commençant par ␣"␣ (ou "␣ en début de ligne), ne contenant pas le caractère " à l’intérieur et se terminant par le caractère "). On fera attention qu’elle peut être sur plusieurs lignes et donc contenir des sauts de ligne.
- Les commentaires de ligne commençant par les caractères ␣\␣ (ou \␣ en début de ligne) et finissant en fin de ligne.
- Les commentaires multi-lignes commençant par les caractères ␣(␣ (ou (␣ en début de ligne) et se terminant par ). En représentant ces lexèmes par
- M("\
") les identificateurs (par exemple M("if")) - N(\
) les entiers relatifs (par exemple N(-5)) - S("\<chaîne>") les chaînes de caractères (par exemple S("Bonjour\nà tous"))
2.2 Résultat
Les commentaires de ligne et multi-lignes seront supprimés dans la liste (ou le tableau) de lexèmes, car ils ne servent en rien à la compilation.
Ainsi, le code fourni ci-dessus (code du fichier factorielle.lac), produira la liste (ou le tableau) de lexèmes suivant. ▶▶▶ M(":") → M("fact") → M("dup") → M("0=") → M("if") → M("drop") → N(1) → M("else") → M("dup") → M("1-") → M("recurse") → M("*") → M("then") → M(";") → M(":") → M("go") → S("Factorielle") → M("count") → M("type") → M("dup") → M(".") → S("vaut␣:\n") → M("count") → M("type") → M("fact") → M(".") → M("cr") → M(";") → S("-(1-2)+(3-4)x(-5)") → M("calculate") → M("go")
2.3 Production
- Un fichier analex.h
- Un fichier analex.c
- Un fichier permettant de tester l’analyseur, appelé projet1.c 2.4 Contraintes
- L’analyse lexicale sera faite à l’aide d’expressions régulières et d’automates finis déterministes.
- Les codes doivent pouvoir être compilés sur Linux, sans warning ni error avec la commande
Terminal
$ gcc -Wall projet1.c3 Analyse syntaxique
3.1 Attendus
L’analyse syntaxique se focalisera sur la ligne 21 du code, " -(1-2)+(3-4)x(-5)" calculate. Elle demandera en particulier de traduire l’expression -(1-2)+(3-4)x(-5) en un arbre syntaxique, on devrait obtenir
On autorisera
- les entiers naturels (∈ N) et les entiers relatifs (∈ Z) ;
- les opérateurs +, − et ×, ils seront associatifs à gauche et × sera prioritaire sur les deux autres ;
- le signe − sera l’opérateur − (dans 1 − 2) ou devant un nombre (dans −5) ou devant une parenthèse (dans −(1 − 2)).
On n’autorisera pas les expressions du type + − 5 etc. en respectant les règles usuelles. Pour faire l’analyse syntaxique, on pourra utiliser une grammaire BNF ou un automate à pile. Ce choix sera clairement documenté dans le rapport et la grammaire BNF ou l’automate seront décrits dans le rapport. L’analyseur syntaxique doit obligatoirement produire un arbre syntaxique !
3.2 Production
-
Un fichier anasynt.h
-
Un fichier anasynt.c
-
Un fichier permettant de tester l’analyseur, appelé projet2.c
4 Analyse sémantique et compilation des fonctions du processeur
4.1 Diverses fonctions
L’analyse sémantique consistera essentiellement à s’assurer que les fonctions utilisées sont bien définies. Pour cela, on fera la différence entre
-
les fonctions du processeur (simulant les instructions d’un processeur réel), qui seront codées par un numéro, leurs codes seront écrits en langage C ;
-
les fonctions LAC (dans l’exemple à traiter, il s’agit essentiellement de fact et de go, mais aussi 0= et 1-) ; l’objectif n’étant pas d’apprendre à coder en LAC, on minimisera l’utilisation de ces fonctions.
4.2 Codage
Les fonctions doivent donc être stockées dans les composants du système. Ces composants sont
-
la table des symboles LAC qui contient
-
la machine virtuelle VM qui contient uniquement les codes des fonctions.
4.2.1 Le processeur
Le processeur sera défini comme un tableau de fonctions void−→void, son code est Source C
1 // Définition du processeur 2 typedef void (*base)(void); // Type de la fonction de base 3 base processeur[50]; // Taille à préciserSupposons connue une fonction plus (de type void−→void) qui représente l’addition, écrite en langage C, alors on pourra la déclarer comme une fonction du processeur de la manière suivante (ici, on lui affecte le numéro 0) Source C
1 // Supposons la fonction plus bien définie 2 // On la place dans le processeur 3 processeur[0] = + // Le numéro pourrait être différentet son utilisation se fera de la manière suivante Source C
1 // Utilisation de la fonction du processeur 2 processeur[0]();4.2.2 Les chaînes de caractères
En LAC, les chaînes de caractères sont codées par sa longueur, suivie des codes ASCII des caractères la constituant, ainsi "Alain" sera codée
4.2.3 La machine virtuelle VM
La machine virtuelle VM est un tableau d’entiers, l’accès à une valeur sera donc de la forme VM[i], où i sera appelé l’adresse de la valeur trouvée en VM[i]. Supposons qu’on veuille coder la fonction +, comme fonction numéro 0 du processeur et que ce soit la première fonction codée dans la machine virtuelle, alors on aura dans la machine virtuelle Adresse 0 1 VM -1 0 où le 0 représente l’adresse de la fonction + (cette adresse s’appelle Code field address, on l’appellera Cfa), le −1 signifiant que cette fonction est une fonction du processeur et le 0 est le numéro du processeur.
4.2.4 La table des symboles LAC
La table des symboles LAC est un tableau d’entiers. Supposons qu’on veuille coder la fonction +, comme première fonction dans la table des symboles, on aura alors Adresse 0 1 2 3 LAC 0 1 43 0
Où 0 représente le Cfa de la fonction (adresse dans la machine virtuelle où commence le code de la fonction), 1 désigne l’adresse dans la table des symboles où commence le nom (ici +) de la fonction, cette adresse s’appelle le Name field address et sera notée Nfa. Ainsi, la fonction + est définie par
- un numéro processeur : 0
- un Cfa : 0
- un Nfa : 1. L’adresse 0 où la valeur est 0 est codée ainsi pour reconnaître les erreurs sémantiques, c’est-à-dire l’utilisation d’une fonction non encore définie.
L’analyse sémantique consiste donc à coder une fonction find qui a pour paramètre un lexème M(
) et qui renvoie le Cfa de ou une erreur si la fonction n’est pas définie.
Supposons que la deuxième fonction à définir soit la fonction swap (numéro de processeur 1), on aurait alors la situation suivante
Adresse 0 1 2 3 4 5 6 7 8 9 10 LAC 0 1 43 0 1 4 115 119 97 112 2 Adresse 0 1 2 3 VM -1 0 -1 1
La fonction swap est définie par
- un numéro processeur : 1
- un Cfa : 2
- un Nfa : 5
Noter à l’adresse 4 de LAC, la présence du Nfa de + qui a été définie juste avant swap. La fonction find cherche le
mot à partir du dernier défini !
On mettra dans LAC le Nfa du mot précédemment défini, juste avant le Nfa du nouveau mot qu’on écrit
dans LAC.
4.3 Production
- Un fichier find.h
- Un fichier find.c
- Un fichier permettant de tester la fonction find appelé projet3.c, elle travaille essentiellement sur la table des symboles. 5 5 Interprétation 5.1 Description Interpréter un langage consiste à pouvoir l’exécuter sans compilation (sauf les fonctions qu’on utilise), par exemple, on pourrait taper une ligne du genre Terminal $ lac LAC> 1 2 - -1 3 4 - -5 + . --> 6 Le langage fonctionne de la manière suivante
- quand on lui fourni un lexème N(-5), par exemple, il met -5 sur la pile ;
- quand il rencontre un lexème M(+), par exemple, il va chercher le Cfa de + dans LAC, puis son code dans VM et, comme c’est une fonction processeur, il exécute la fonction ! Ainsi 1 2 + est interprété de la manière suivante
- N(1), on empile 1 sur data_stack ;
- N(2), on empile 2 sur data_stack ;
- M("+"), on exécute la fonction plus qui a été codée de telle manière qu’elle dépile 1 et 2, les additionne et
empile 3.
Une pile aura le type
Source C
1 struct pile { 2 int (*pop)(void); 3 void (*push)(int); 4 }; 5 6 typedef struct pile pile;La fonction plus pourrait être défini par Source C
1 void plus(void) 2 { 3 data_stack.push(data_stack.pop()+data_stack.pop()); 4 }5.2 Production
- Un fichier interpret.h
- Un fichier interpret.c
- Un fichier permettant de tester le mode interprété, appelé projet4.c.
6 Compilation
Il s’agit ici d’automatiser la compilation des fonctions processeur et de décrire la compilation des fonctions LAC.
6.1 Compilation des fonctions processeurs
Étant donnée une fonction en langage C connue (par exemple code_dup), écrire une fonction compile_base qui prend trois paramètres
- le nom dans LAC (ici dup) ;
- le nom de la fonction en langage C de type void−→void qui va la coder dans le processeur (ici code_dup) ;
- le numéro utilisée pour la coder dans le processeur (supposons ici que c’est 2), on aurait l’appel
Source C
1 compile_base("dup", code_dup, 2);
qui remplirait convenablement le processeur, la tables des symboles LAC et la machine virtuelle VM.
6.2 Compilation des fonctions LAC
On veut coder la fonction 1- donc le code LAC pourrait être 1 -, où 1 est le chiffre et - la soustraction usuelle. Il faut décider comment on code cette nouvelle fonction dans LAC et VM.
- Rien ne change dans LAC, on va coder de la manière suivante (on suppose connu le Nfa du dernier mot
défini – noté ici n), donc la fonction 1- a pour Cfa, y et pour Nfa, x+1.
Adresse · · · x x + 1 x + 2 x + 3 x + 4
LAC · · · n 2 49 45 y
Dans la machine virtuelle, on va coder de la manière suivante (en bleu, les Cfa)
Adresse · · · y y + 1 y + 2 y + 3
VM · · · u 1 v w
où
(a) u est le Cfa d’une fonction processeur nommée (lit) dont le rôle est de signaler à l’exécuteur que la
valeur suivante est une donnée à mettre sur la pile de données ; elle a été obtenue (après avoir écrit la
fonction mylit en C) par
Source C
1 compile_base("(lit)", mylit, 3);
(b) v est le Cfa d’une fonction processeur - qui effectue une soustraction ; elle a été obtenue (après avoir
écrit la fonction moins en C) par
Source C
1 compile_base("-", moins, 4);
(c) w est le Cfa d’une fonction processeur (fin) dont le rôle est de signaler à l’exécuteur que la fonction
en cours se termine ; elle a été obtenue (après avoir écrit la fonction myfin en C) par
Source C
1 compile_base("(fin)", myfin, 5);
La fonction 1- pourra être compilée par une commande du type
Source C
1 compile_lac("1-", "1 -");
le premier paramètre étant le nom dans LAC et le second étant le code la définissant.
7
6.3 Les fonctions à compiler
- : signale un début de compilation, le terme après est le nom de la fonction dans LAC (ici fact et go sont des fonctions LAC définies par cette déclaration), c’est la fonction processeur n°6 ;
- dup duplique la valeur sur le sommet de la pile de données (fonction processeur n°2) ;
- = teste si les deux valeurs sur la pile de données sont égales, dépose -1 sur la pile de données si elles sont
6.5 Quelques explications sur les chaînes de caractères
- À la compilation Fichier 1 : essai ( -- ) " Bonjour" count type ; pourra être codé dans VM par
Adresse x x + 1 x + 2 x + 3 x + 4 x + 5 x + 6 x + 7 x + 8 x + 9 x + 10 x + 11 VM c1 7 66 111 110 106 111 117 114 c2 c3 c4 str count type (fin) où — x est le Cfa de essai — c1 est le Cfa d’une fonction (str) qui indique qu’arrive une chaîne de caractères — c2 est le Cfa de count — c3 est le Cfa de type — c4 est le Cfa de (fin)
- En mode interprété Fichier 1 " Bonjour" count type Il suffit de ranger quelque part (appelée parfois TIB – Terminal Input Buffer ) et proprement (s’il y a plusieurs chaînes – non demandé) les chaînes lues. Fichier 1 " Bonjour " " Alain !" catenate count type 6.6 Production
- Un fichier compilation.h
- Un fichier compilation.c
- Un fichier permettant de tester la compilation, appelé projet5.c.
7 Exécution
Nous avons toutes les informations contenues dans LAC et VM. Comment faire fonctionner tout cela ? Avec la pile de retour ! Supposons connus les fonctions de base (lit), (fin), + et . et les fonctions LAC définies par Fichier
Quelques remarques
- À chaque lecture de VM, on empile l’adresse où on est (pour pouvoir y retourner, c’est pourquoi on l’appelle « pile de retour »).
- Après chaque exécution d’une fonction processeur, on dépile la pile de retour et on augmente de 1 l’adresse, puis on l’exécute.
- Les fonctions (lit) et (fin) manipulent la pile de retour ! Il y en a d’autres...
7.1 Production
- Un fichier executeur.h
- Un fichier executeur.c
- Un fichier permettant de tester la compilation, appelé projet6.c.
- On verrait l’impression à l’écran de 125.
