1 Introduction 2 Le Pascal
Contents
1. WriteUnary x end FIGURE 2 Un exemple de programme en Pascal simplifi LAG 0 ldc i 0 ujp main define fact lod i 1 1 lde i 1 add str lod ldc equ fjp facti ldc il str i 0 0 ujp fact2 define factl mst lod ldc sub H He peo pr pr oo a fact 0 5 cup lod mul str i 0 0 define fact2 retf define main read i H H me H peo peo pa str i 0 0 rde 40 str i101 mst 0 lod i 0 0 cup 1 fact str 10 0 lod i 0 0 prin lod i 0 1 prin stp 01 02 03 04 05 06 07 08 09 I oO O1 amp np Ne 21 22 23 24 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 program Factorial var a b integer function fact var x integer integer begin b b 1 if x 0 then fact 1 else fact x x fact x 1 end begin read a b 0 a fact a write a write b end FIGURE 3 Un exemple de programme en PCode et son quivalent Pascal lod T N A Met push sur la pile une copie de la valeur de type T stock e l adresse N A str T N A D place pop le sommet de la pile de type T vers l adresse N A mst N Cr e une stack frame en vue d un appel de fonction ou proc dure nesting courant N cup P L Appelle la fonction ou proc dure tiquette L avec P param tres retp Effectue un retour d appel de proc dure retf Effectue un retour d appel de fonction FIGURE 42. lt BLOCK gt gt lt ARGS gt gt lt IDLIST gt lt TYPE gt lt ARGS gt gt lt IDLIST gt lt TYPE gt begin lt STATEMENTOPT gt end gt lt STATEMENTLIST gt E gt lt STATEMENT gt gt lt STATEMENT gt lt STATEMENTLIST gt gt ID lt EXPRESSION gt gt lt CALL gt gt lt BLOCK gt gt if lt EXPRESSION gt then lt STATEMENT gt else lt STATEMENT gt gt while lt EXPRESSION gt do lt STATEMENT gt gt read ID gt write EXPRESSION gt ID gt ID lt EXPRESSION gt lt EXPRESSIONLIST gt gt lt EXPRESSION gt lt EXPRESSION gt lt OP gt gt lt EXPRESSION gt lt EXPRESSIONLIST gt gt ID gt NUM gt true gt false gt lt EXPRESSION gt gt lt EXPRESSION gt not lt EXPRESSION gt lt EXPRESSION gt lt OP gt lt EXPRESSION gt gt lt gt gt lt gt gt gt lt gt gt gt gt BENE Lx gt gt and gt or FIGURE 1 La grammaire du Pascal simplifi program Example var x y integer function Euclide var a b integer integer var c integer begin while b lt gt 0 do begin c b while a gt b do begin a a b Calcul de a modulo b end Euclide a end procedure WriteUnary var a integer begin while a gt 0 do begin write 1 a a 1 end end begin read x read y x Euclide x y write x
3. la table de parsing LL 1 pour cette grammaire ainsi que les ventuels calculs de First et de Follow qui vous auront t n cessaires 6 D corez la grammaire en lui ajoutant les instructions n cessaires pour i effectuer le contr le de type et ii produire du code pour la machine virtuelle 7 crivez un analyseur LL 1 en descente r cursive produisant du code pour la machine virtuelle dans un fichier texte 3 Si vous d sirez l impl menter dans un autre langage consultez d abord I assistant 8 Votre compilateur devra effectuer un contr le de type syst matique du code Chaque expression peut tre soit bool enne soit enti re et le compilateur devra renvoyer une erreur le cas ch ant parexemple a lt 3 and 2esterron De plus les appels de fonctions et proc dures doivent tres v rifi s pour s assurer que le nombre de param tres et leurs types soient corrects 9 Nous ne vous demandons pas de g rer le hiding des variables globales Si une variable locale a une fonction ou proc dure a le m me nom qu une variable globale votre compilateur peut renvoyer un erreur Dans le cas contraire les variables globales devront bien s r tre accessibles depuis l enti ret du programme comme dans l exemple de la figure 3 Le tout sera naturellement pr sent dans un rapport qui reprend les diff rentes informations de mand es et qui pr cise et justifie les choix et hypoth ses que vous aurez fa
4. Instructions de la GPMACHINE non vues au TP adresse absolue contenu du stack variable adresse N A 13 4 x 05 12 04 11 03 10 02 9 01 8 non d fini Euclide 00 7 5 x 6 E R 5 y 2 4 E 3 i E 2 non d fini Euclide 1 1 b 11 0 5 a 10 FIGURE 5 Contenu du stack l xecution du programme de la figure 3 2 appel fact ligne 4
5. Projet 1 du cours INFO F 403 TH ORIE DES LANGAGES ET DE LA COMPILATION PASCAL Nicolas MAQUET Ann e Acad mique 2009 2010 Comparing C and Pascal is rather like comparing a Learjet to a Piper Cub one is meant for getting something done while the other is meant for learning Brian W Kernighan 1 Introduction Le Pascal est un langage de programmation proc dural d velopp vers la fin des ann es soixante dont le but principal a t l apprentissage de la programmation structur e aux tudiants Comme son nom l indique la programmation structur e consiste organiser le code source en de multiples sous routines ind pendantes aussi appel es fonctions ou proc dures Une des vocations principales du Pascal tait donc d apprendre programmer sans goto bien que pour des raisons myst rieuses la maudite instruction fasse effectivement partie du language Au del de son usage purement acad mique le Pascal a volu en de nombreux dialectes dont certains ont eu du succ s dans l industrie comme Object Pascal ou Borland Delphi Aujourd hui le Pascal n est plus consid r comme un langage de programmation de premier plan mais il laisse derri re lui un v n rable h ritage que vous allez pouvoir honorer votre tour en lui d diant un com pilateur crit par vos soins 2 Le Pascal Le langage Pascal insiste tres fort sur les d clarations toute variable proc dure ou fonction doit imp rativement tre d c
6. a d claration de fonctions et proc dures imbriqu es ce que votre compilateur devra interdire Ce dernier devra n anmoins tre capable de compiler des programmes contenant des fonctions et proc dures traditionnelles Il n est pas possible en Pascal de donner une valeur initiale aux variables d clar es votre com pilateur devra initialiser les entiers z ro et les bool ens false La figure 2 donne un exemple de programme en Pascal simplifi Vous remarquerez que la mani re dont on sp cifie dans le code qu une fonction doit retourner une valeur est assez trange en effet il faut assigner 2 Videntifiant de la fonc tion la valeur souhait e Ceci peut tre fait plusieurs fois et m me aucune fois auquel cas la fonction renverra z ro si elle est enti re et false si elle est bool enne 3 Machine virtuelle Le but d un compilateur tant tout de m me la g n ration de code il est temps d introduire la machine vers le langage de laquelle nous allons compiler les programmes Il s agit de la GPMA CHINE qui fonctionne avec une pile et qui interpr te des instructions en PCode Vous trouverez cette machine virtuelle l adresse http www info fundp ac be gpm Un mode d emploi pour GPMACHINE est disponible sur la page web du TP Quelques unes des instructions de la GPMACHINE dont vous aurez besoin n ont pas t vues au TP Le tableau de la figure 4 reprend ces instructions additionelles Ces instructi
7. its Le code source de votre compilateur accompagn de ses Makefile de ses fichiers de test et de tout autre fichier n cessaire pour se convaincre que le travail a t bien fait doit tre envoy par e mail nmaquet ulb ac be Le tout doit tre remis pour le vendredi 26 f vrier 2010 Le travail peut tre fait par groupe de deux ce que nous recommandons ou individuellement Une d fense orale sera programm e lors de la correction du projet Bon travail 1 2 S 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 lt PROGRAM gt lt VARS gt lt IDLIST gt lt TYPE gt lt ROUTINELIST gt lt ROUTINE gt lt FUNCTION gt lt PROCEDURE gt lt ARGSOPT gt lt ARGS gt lt BLOCK gt lt STATEMENTOPT gt lt STATEMENTLIST gt lt STATEMENT gt lt CALL gt gt program ID lt VARS gt lt ROUTINELIST gt lt BLOCK gt gt var lt IDLIST gt lt TYPE gt lt VARS gt E gt ID lt IDLIST gt gt ID gt integer boolean lt ROUTINE gt lt ROUTINELIST gt gt lt FUNCTION gt gt lt PROCEDURE gt gt function ID lt ARGSOPT gt lt TYPE gt lt VARS gt lt BLOCK gt procedure ID lt ARGSOPT gt lt VARS gt
8. lar e avant de pouvoir tre utilis e Ceci a notamment pour but de rendre la compilation plus simple comme la nature de chaque identifiant est connue lorsque le compilateur la rencontre le contr le de type et la g n ration de code peuvent se faire en parall le Une autre particularit du Pascal est que le point virgule est un s parateur d instruction et non un ferminateur d instruction comme en C ou en Java Contrairement au C o toutes les routines sont appel es fonc tions le Pascal distingue les routines qui ne renvoient pas de valeur appel es proc dures de celles qui en renvoient appel es fonctions En Pascal les commentaires sont entour s d accolades Les identi fiants du Pascal pour les variables proc dures fonctions et le nom du programme doivent appartenir au langage de l expression r guli re a zA Z a zA Z 0 9 _ 1 On parle g n ralement de compilation en une passe Dans le cadre de ce projet vous devrez r aliser un compilateur pour une version largement sim plifi e du Pascal Tout d abord parmi les nombreux types de donn es diff rents du langage votre com pilateur ne devra en supporter que deux integer et boolean Aussi votre compilateur n aura pas a g rer les programmes qui g rent leur m moire de mani re dynamique ce qui se fait normalement en Pascal par le biais des primitives new et dispose quivalents des new et delete du C Enfin le Pascal supporte normalement l
9. n peut acc der au variables globales et ses variables locales mais pas aux variables locales des appels interm diaires Pour vous familiariser avec ces instructions nous vous conseillons de lire attentivement le code de la figure 3 et de l ex cuter avec la GPMACHINE le code de la figure 3 est disponible en version lectronique sur la page web de l assistant http www ulb ac be di ssd nmaquet 4 Desiderata tant donn e la grammaire du Pascal simplifi nous vous demandons d impl menter un compila teur pour ce langage Vous pouvez choisir de l impl menter en C ou en C Plus pr cis ment nous attendons de votre part le travail suivant 1 Identifiez les unit s lexicales du Pascal simplifi 2 Donnez un automate fini d terministe les reconnaissant 3 crivez un analyseur lexical qui reconna t les diff rentes unit s lexicales du Pascal simplifi Celui ci sera impl ment sous forme d une fonction qui chaque appel retournera la prochaine unit lexicale lue sur I input Une table des symboles sera galement impl ment e 4 Modifiez la grammaire du Pascal simplifi de telle sorte que a Celle ci soit LL 1 b Elle tienne compte de la priorit et de l associativit des op rateurs savoir du plus au moins prioritaire Op rateur s Associativit not droite x and gauche OT gauche gt lt gt lt lt gt gauche 5 Donnez
10. ons utilisent la notion de stack frame c est dire une portion du stack qui est r serv e soit l ex cution du bloc principal du programme nesting 0 soit l ex cution d une proc dure ou fonction nesting 1 Comme mentionn pr c demment le Pascal permet normalement la d claration de fonctions et proc dures imbriqu es de nesting sup rieur 4 1 mais vous ne devez pas vous en soucier Pour appeler une fonction ou proc dure vous devez proc der comme suit mst N alloue une nouvelle stack frame N est le nesting courant mettre les param tres de la proc dure ou fonction au sommet de la pile cup P L appelle la fonction ou proc dure d tiquette L avec P param tres au d but de la fonction ou proc dure appel e les param tres sont au sommet de la pile ex cution du code de la fonction ou proc dure retf pour une fonction ou retp pour une proc dure pour effectuer le retour l appelant sil appel tait une fonction la valeur de retour est au sommet de la pile L instruction mst N mark stack cr e une nouvelle stack frame o N est le nesting courant et a pour effet d allouer 5 nouvelles cases sur le stack Vous pouvez traiter les 4 cases du dessus comme une bo te noire son contenu sert aux instructions retf retp lod cup et str mais vous ne devez pas les utiliser directement Par contre la premi re des 5 cases mise sur le stack par mst sert communiquer la
11. valeur de retour d un appel de fonction et vous serez donc amen s modifier son contenu Les instructions lod N A et str N A permettent d acc der aux cases m moire du stack le 2 Le Pascal dispose normalement aussi d une instruction return classique qu on ne vous demande pas d impl menter param tre N doit valoir 0 si on veut acc der aux cases du bloc courant et 1 si on veut acc der aux cases du bloc de nesting inf rieur le param tre A est un d calage par rapport au d but de la stack frame courante Pour prendre un exemple concret si on ex cute le programme de la figure 3 jusqu au deuxi me passage la ligne 4 on suppose que l utilisateur veut calculer la factorielle de 5 on obtient le contenu du stack d crit la figure 5 Pour acc der la variable globale b le programme utilise les instructions lod 1 letstr 1 1 Pour acc der au param tre x qui se trouve au sommet de la pile le programme utilise Il instruction lod 0 5 puisqu elle se trouve un d calage 5 du d but de la stack frame courante Enfin pour acc der la valeur de retour de la fonction la pseudovariable Euclide le programme utilise l instruction str 0 0 puisque la valeur de retour est toujours la premi re valeur de la stack frame Vous remarquerez qu il n est pas possible d acc der aux stack frames situ es entre la stack frame courante et la stack frame globale ceci correspond au comportement attendu une proc dure ou fonctio
Download Pdf Manuals
Related Search