1. Homepage
  2. Programming
  3. Projet ICE4404P: écrire un compilateur

Projet ICE4404P: écrire un compilateur

Contact Us On WeChat
écrire un compilateurC

Projet ICE4404P

Projet ICE4404P Alain Chillès 2022 – 2023 CourseNana.COM

Le projet est à rendre pour le 11 janvier, avant 23h55. Il sera rendu sur Moodle sous la forme d’une archive .zip contenant CourseNana.COM

  1. Un rapport écrit en .pdf, contenant les explications de ce qui a été fait et de ce qui n’a pas été fait.
  2. Des codes écrits en langage C comme décrit plus loin.
  3. 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 CourseNana.COM

  1. Analyse lexicale.
  2. Analyse syntaxique.
  3. Analyse sémantique.
  4. Interprétation (fonctionnement comme une calculatrice – sans programmation).
  5. Compilation en machine virtuelle.
  6. Exécution en machine réelle. Le code à compiler et à exécuter est le suivant.

Fichier factorielle.lac CourseNana.COM

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 go

1.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 CourseNana.COM

  1. d’un processeur dont le type est défini dans la section 5 ;
  2. 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 ;
  3. 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 ;
  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 ;
  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 CourseNana.COM

  6. 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é ␣]).
  7. Les entiers relatifs.
  8. 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.
  9. Les commentaires de ligne commençant par les caractères ␣\␣ (ou \␣ en début de ligne) et finissant en fin de ligne.
  10. 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
  11. M("\") les identificateurs (par exemple M("if"))
  12. N(\) les entiers relatifs (par exemple N(-5))
  13. 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. CourseNana.COM

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") CourseNana.COM

2.3 Production

  1. Un fichier analex.h
  2. Un fichier analex.c
  3. Un fichier permettant de tester l’analyseur, appelé projet1.c 2.4 Contraintes
  4. L’analyse lexicale sera faite à l’aide d’expressions régulières et d’automates finis déterministes.
  5. Les codes doivent pouvoir être compilés sur Linux, sans warning ni error avec la commande Terminal
    $ gcc -Wall projet1.c

    3 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 CourseNana.COM

On autorisera CourseNana.COM

  1. les entiers naturels (∈ N) et les entiers relatifs (∈ Z) ;
  2. les opérateurs +, − et ×, ils seront associatifs à gauche et × sera prioritaire sur les deux autres ;
  3. 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 ! CourseNana.COM

3.2 Production

  1. Un fichier anasynt.h CourseNana.COM

  2. Un fichier anasynt.c CourseNana.COM

  3. Un fichier permettant de tester l’analyseur, appelé projet2.c CourseNana.COM

    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 CourseNana.COM

  4. 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 ; CourseNana.COM

  5. 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. CourseNana.COM

    4.2 Codage

    Les fonctions doivent donc être stockées dans les composants du système. Ces composants sont CourseNana.COM

  6. la table des symboles LAC qui contient CourseNana.COM

  7. la machine virtuelle VM qui contient uniquement les codes des fonctions. CourseNana.COM

    4.2.1 Le processeur

    Le processeur sera défini comme un tableau de fonctions void−→void, son code est Source C CourseNana.COM

    1 // Définition du processeur
    2 typedef void (*base)(void); // Type de la fonction de base
    3 base processeur[50]; // Taille à préciser

    Supposons 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 CourseNana.COM

    1 // Supposons la fonction plus bien définie
    2 // On la place dans le processeur
    3 processeur[0] = &plus; // Le numéro pourrait être différent

    et son utilisation se fera de la manière suivante Source C CourseNana.COM

    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 consti￾tuant, ainsi "Alain" sera codée CourseNana.COM

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. CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

  1. un numéro processeur : 0
  2. un Cfa : 0
  3. 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. CourseNana.COM

Supposons que la deuxième fonction à définir soit la fonction swap (numéro de processeur 1), on aurait alors la situation suivante CourseNana.COM

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 CourseNana.COM

La fonction swap est définie par CourseNana.COM

  1. un numéro processeur : 1
  2. un Cfa : 2
  3. 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

  4. Un fichier find.h
  5. Un fichier find.c
  6. 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
  7. quand on lui fourni un lexème N(-5), par exemple, il met -5 sur la pile ;
  8. 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
  9. N(1), on empile 1 sur data_stack ;
  10. N(2), on empile 2 sur data_stack ;
  11. 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 CourseNana.COM

    1 void plus(void)
    2 {
    3 data_stack.push(data_stack.pop()+data_stack.pop());
    4 }

    5.2 Production

  12. Un fichier interpret.h
  13. Un fichier interpret.c
  14. 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. CourseNana.COM

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 CourseNana.COM

  1. le nom dans LAC (ici dup) ;
  2. le nom de la fonction en langage C de type void−→void qui va la coder dans le processeur (ici code_dup) ;
  3. 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. CourseNana.COM

  4. 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

  5. : 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 ;
  6. dup duplique la valeur sur le sommet de la pile de données (fonction processeur n°2) ;
  7. = 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

  1. À 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) CourseNana.COM

  1. 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
  2. Un fichier compilation.h
  3. Un fichier compilation.c
  4. 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 CourseNana.COM

Quelques remarques CourseNana.COM

  1. À chaque lecture de VM, on empile l’adresse où on est (pour pouvoir y retourner, c’est pourquoi on l’appelle « pile de retour »).
  2. 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.
  3. Les fonctions (lit) et (fin) manipulent la pile de retour ! Il y en a d’autres...

    7.1 Production

  4. Un fichier executeur.h
  5. Un fichier executeur.c
  6. Un fichier permettant de tester la compilation, appelé projet6.c.
  7. On verrait l’impression à l’écran de 125.

Get Expert Help On This Assignment

Scan above qrcode with Wechat

écrire un compilateur代写,C代写,écrire un compilateur代编,C代编,écrire un compilateur代考,C代考,écrire un compilateurhelp,Chelp,écrire un compilateur作业代写,C作业代写,écrire un compilateur编程代写,C编程代写,écrire un compilateurprogramming help,Cprogramming help,écrire un compilateurassignment help,Cassignment help,écrire un compilateursolution,Csolution,