Sujet du T.P. (résumé)

L’objet de ce travail est la réalisation d’un compilateur pour traduire des programmes écrits en L, qui est un langage de programmation à définir. Ce compilateur produit du code destiné à être interprété par la machine M, qui est une machine virtuelle à pile.

Le travail à faire se compose de quatre tâches :

• la définition du langage L, c’est-à-dire l’écriture de sa grammaire,
• la réalisation de l’analyseur syntaxique correspondant à cette grammaire,
• la transformation de l’analyseur en un compilateur, par l’ajout des opérations de génération de code,
• l’écriture de la machine M et la validation du tout.

Les éléments imposés de ce travail sont :

• un ensemble minimal de fonctionnalités du langage L, précisé dans le sujet,
• la spécification de la machine M, donnée également dans le sujet.

Planning

1. Sur l’analyseur lexical

• Liste des unités lexicales. Pour écrire l’analyseur lexical il faut avoir la liste des unités lexicales ce qui implique qu’on a déjà écrit les spécifications du langage à implémenter. Si ce n’est pas votre cas, donnez-vous pour objectif provisoire la reconnaissance des principales unités lexicales du langage C, éventuellement traduites en français pour bien montrer que ce sont les vôtres : si, tantque, retour, entier, ==, <=, etc.

Une fois choisies, les unités lexicales doivent faire l’objet d’une série de déclarations de constantes dans un fichier d’en-tête (nommé, par exemple, unitesLexicales.h) :

#define IDENTIF 301
#define NOMBRE 302
#define SI 303
#define ALORS 304
...

• Programme de test. Le but du TP est l’écriture de l’analyseur lexical, que vous validerez avec un programme de test dans le genre de celui-ci (si l’analyseur lexical provient de lex il faut lire yylex() au lieu de lireUnite()) :

#include <stdio.h>
#include "unitesLexicales.h"

extern char lexeme[];
extern int valeur;

int main(int argc, char **argv) {
    int uniteCourante;
    
    uniteCourante = lireUnite();
    while (uniteCourante != 0) {
        printf("unite %d", uniteCourante);

        if (uniteCourante == IDENTIF)
            printf(" (lexeme: '%s')\n", lexeme);
        else if (uniteCourante == NOMBRE)
            printf(" (valeur %d)\n", valeur); 
        else
            printf("\n");
        
        uniteCourante = lireUnite();
    }
}

Ce programme affiche les unités lexicales obtenues à partir d’un texte donné à l’entrée standard (indépendamment du fait que ce texte soit un programme correct ou non).

• Emploi d’un fichier source. Dans une deuxième étape (c.-à-d. lorsque vous aurez vérifié que le programme précédent est correct) vous ferez en sorte que le texte analysé soit lu dans un fichier. Si vous vous y prenez comme il faut, il suffira de changer le programme de test comme ceci :

#include <stdio.h>
#include "unitesLexicales.h"

extern char lexeme[];
extern int valeur;
extern FILE *ficEntree;

int main(int argc, char **argv) {
    int uniteCourante;

    ficEntree = fopen(argv[1], "r");
    if (ficEntree == NULL) {
        fprintf(stderr, "impossible ouvrir %s\n", argv[1]);
        return -1;
    }
    
    uniteCourante = lireUnite();
    while (uniteCourante != 0) {
    ...

N.B. Si vous avez utilisé lex, le fichier ficEntree s’appelle yyin.

• Lex. Utiliser lex est certainement la manière la plus rapide d’obtenir un analyseur lexical correct et efficace. La fonction lireUnite s’appelle alors yylex. On prendra garde au fait qu’il y a plusieurs versions de lex et flex et que la nature du lexème (appelé yytext) n’y est pas toujours très évidente – parfois c’est un tableau de caractères, parfois un pointeur – ce qui rend sa déclaration externe hasardeuse. Vous pouvez pallier cette difficulté en déclarant votre propre variable (exemple : char lexeme[1000]) et dans l’analyseur lexical y recopier le lexeme (exemple : strcpy(lexeme, yytext)) lorsque cela est utile.

• Analyse lexicale et Java. Si vous avez décidé de réaliser votre compilateur en Java vous devrez vous passer de lex, sauf si vous êtes extrêmement aguerris dans l’utilisation des méthodes natives en Java (c’est-à-dire la bibliothèque JNI, Java Native Interface).

Si vous ne connaissez pas JNI, il vous est conseillé d’écrire une classe (nommée ci-dessous Lexical), sous-classe de java.io.StreamTokenizer, et d’y redéfinir surtout la méthode nextToken. La version de nextToken héritée de StreamTokenizer faisant le plus gros du travail, il ne vous restera à programmer que la recherche des « mots » dans une table donnée au départ (par exemple une java.util.HashMap) afin de distinguer les mots clés des identificateurs et obtenir les unités lexicales associées.

Vous rencontrerez un problème avec les opérateurs formés de deux caractères spéciaux ("==", "<=", etc.). C’est un problème mineur, mais difficile à traiter. Compte tenu du temps disponible, il vous est conseillé de vous en débarrasser en prescrivant que votre langage n’a pas de tels opérateurs doubles (il suffit, par exemple, de décider qu’on doit écrire « si (x infegal 0)... » au lieu de « si (x <= 0)... ».

• Programme de test en Java. Si vous programmez en Java, votre programme de test ressemblera à ceci :

import java.io.*;

public class Test {

    public static void main(String[] args) {
        Reader lecteur = new InputStreamReader(System.in);
        Lexical analyseur = new Lexical(lecteur);

        int uniteCourante = analyseur.nextToken();
        while (uniteCourante != Lexical.TT_EOF) {
            System.out.print("unite " + uniteCourante);

            if (uniteCourante == Lexical.IDENTIF)
                System.out.println(" (lexeme: " + analyseur.lexeme() + ")");
            else if (uniteCourante == Lexical.NOMBRE)
                System.out.println(" (valeur " + analyseur.valeur() + ")"); 
            else
                System.out.println();
            
            uniteCourante = analyseur.nextToken();
        }
    }
}

• Reconnaissance des opérateurs simples. Lex ou pas, il y a un choix à faire à propos de la reconnaissance des unités formées d’un unique caractère spécial. Soit on considère que l’analyseur lexical veille à ne reconnaître que les opérateurs légitimes, ce qui en lex donne une longue collection de règles de la forme

"+"    return '+';
"-"    return '-';
";"    return ';';
"("    return '(';
...
.      erreur("caractère illegal");

soit on décide que l’analyseur doit « laisser passer » tout caractère non reconnu à un autre titre. En lex, cela donne une unique règle (évidemment placée en dernière position) de la forme

.      return yytext[0];

Ce choix n’a pas de conséquence sur la conception du compilateur, à part ceci : dans le premier cas, les caractères illégaux donnent lieu à une erreur lexicale ; dans le second, ils produisent une erreur de syntaxe. On vous conseille de choisir le plus simple, c’est-à-dire la deuxième manière.

• Caractères blancs. N’oubliez pas que, dans tous les cas, les caractères blancs (espaces, tabulations, fins de ligne) doivent disparaître durant l’analyse lexicale.

2. Sur l’analyseur syntaxique

• Grammaire. A la suite du premier TP vous avez donc un analyseur lexical en état de marche, basé sur une liste d’unités lexicales peut-être provisoire mais à laquelle il vous sera facile d’ajouter ou retrancher des mots clés.

D’autre part, vous avez réfléchi à la définition du langage que vous voulez compiler et vous en avez écrit la grammaire. Pour dépanner ceux qui n’auraient pas eu le temps de faire cela, voici une telle grammaire (les terminaux sont en majuscules ou entre apostrophes, le symbole de départ est programme) :

• Exemple. Voici un programme correct pour la grammaire précédente (il s’agit d’un exercice classique dit « des tours de Hanoi ») :

fonction deplacer(a, b) 
{
    ecrire(1000 * a + b);
}

fonction hanoi(n, a, b, c) 
{
    si n != 0 alors 
    {
        appel hanoi(n - 1, a, c, b);
        appel deplacer(a, b);
        appel hanoi(n - 1, c, b, a);
    }
}
    
fonction principale() 
    entier n;
{    
    n = lire();
    appel hanoi(n, 1, 2, 3);
}.

• A propos des entrées-sorties. La grammaire ci-dessus montre une manière de réaliser les entrées-sorties différente de celle qui est conseillée dans le sujet distribué (sur papier). Dans ce document on vous dit d’implémenter les entrées-sorties par deux fonctions prédédefinies lire et ecrire « compilées à la main » mais, à part cela, traitées comme des fonctions ordinaires.

Ci-dessus on vous suggère plutôt d’incorporer ces opérations au langage : LIRE et ECRIRE sont deux unités lexicales particulières et les textes « lire() » (une sorte de facteur) et « ecrire(expression); » (une sorte d’instruction) sont reconnus par le compilateur et traités spécifiquement. Cette manière est probablement plus facile à comprendre, bien qu’un peu plus lourde à réaliser.

• Le pied à l’étrier. Pour obtenir l’analyseur syntaxique il suffit de prendre les règles de la grammaire (les productions) et les traduire en C, en écrivant une fonction pour chaque non terminal, selon la méthodologie expliquée en cours. C’est tellement simple, quand on a compris le principe, qu’on n’ose pas se jeter à l’eau... Pour vous aider à démarrer voici deux exemples :

1° La fonction correspondant au symbole de départ (le membre gauche de la première règle) de la grammaire montrée ci-dessus. La productions est :

programme -> { declarVariable } { declarTableau } { declarFonction } '.'

Puisqu’une déclaration de variable commence nécessairement par le terminal ENTIER, une déclaration de tableau par TABLEAU et une déclaration de fonction par FONCTION, cela se traduit par la fonction :

void programme(void) {
    while (uc == ENTIER)
        declarationVariable();
    while (uc == TABLEAU)
        declarationTableau();
    while (uc == FONCTION)
        declarationFonction();
    if (uc != '.')
        erreur("'.' attendu");
    uc = yylex();
}

2° La production concernant instructionAffect

instructionAffect -> IDENTIF [ '[' expression ']' ] '=' expression ';'

donne lieu à la fonction suivante (notez que lorsque cette fonction est appelée il est certain que uc == IDENTIF) :

void instructionAffect(void) {
    uc = yylex();
    if (uc == '[') {
        uc = yylex();
        expression();
        if (uc != ']')
            erreur("']' attendu");
        uc = yylex();
    }
    if (uc != '=')
        erreur("'=' attendu");
    uc = yylex();
    expression();
    if (uc != ';')
        erreur("';' attendu");
    uc = yylex();
}

• Programme principal. On déclenche l’analyse du texte source en commandant la reconnaissance du symbole de départ (cela est la définition même du symbole de départ). Ce qui donne un programme principal dans le genre de :

int main(int argc, char **argv) {
    initialisation de yyin    
    
    uc = yylex();
    programme();
    printf("\nSyntaxe OK\n");
}

Ce programme est facile à comprendre : après avoir amorcé l’unité lexicale courante (uc) on lance la reconnaissance du symbole de départ, programme. Si le texte source contient une erreur de syntaxe, l’analyseur en mourra (puisque la fonction erreur appelle exit) ; par conséquent, si on revient de l’analyseur, c’est que le texte était syntaxiquement correct.

En réalité, le programme précédent ne détecterait pas la présence d’éléments illégaux à la suite d’un texte correct, ce qui est un peu regrettable. On préfère donc améliorer le programme précédent en imposant qu’après la reconnaissance d’un programme correct l’unité courante doit se trouver placée sur la fin du fichier :

int main(int argc, char **argv) {
    initialisation de yyin    
    
    uc = yylex();
    programme();
    if (uc != 0)   
        erreur("du texte après la fin du programme");
    printf("\nSyntaxe OK\n");
} 

N.B. Lex et flex représentent la fin du fichier source par la valeur 0. On prendra garde au fait que cette valeur est différente de celle de la constante EOF (généralement l’entier -1).

3. Sur l’analyse syntaxique, suite

Pas de conseil vraiment nouveau pour cette troisième tranche de travaux. Le but est de vous assurer que vous possédez un analyseur correct et complet. Pour cela il vous faudra faire tourner l’analyseur d’une part sur des textes sources mettant en œuvre toutes les possibilités du langage L, d’autre part sur différents textes sources provoquant toutes les erreurs possibles.

• Afficher le texte source. Par défaut, l’analyseur lexical produit par lex n’affiche pas les unités reconnues. Un tel comportement ne vous convient pas car, en cas d’erreur, vous n’aurez pas d’indication sur le point du texte source que l’analyseur a réussi à atteindre avant de s’arrêter (s’il s’agit d’une erreur dans le texte source) ou de se planter (s’il s’agit d’une erreur dans l’analyseur).

Pour obtenir l’affichage du texte source au fur et à mesure de l’analyse lexicale il vous faudra ajouter la commande « ECHO; » dans la partie action de chaque règle. Si vous avez écrit l’analyseur lexical en C, obtenir l’affichage du texte source vous sera encore plus facile.

• Compter les lignes. Une autre manière de renseigner sur l’endroit du texte source où une erreur a été trouvée consiste à compter les lignes (c’est-à-dire détecter les apparitions du caractère \n) et à afficher le numéro de la ligne courante dans les messages d’erreur. Ajoutez ce qu’il faut à l’analyseur lexical pour obtenir un tel décompte des lignes.

• Utiliser un débogueur. Dans le développement de l’analyseur vous gagnerez beaucoup de temps si vous vous aidez d’un débogueur. Cela vous permettra, par exemple, d’exécuter l’analyseur pas à pas tout en surveillant la valeur de l’unité courante, notamment pour découvrir les appels de yylex manquants ou en trop.

4.  Sur le dictionnaire

L’étape suivante du travail consiste à ajouter des vérifications sémantiques à votre analyseur syntaxique. Pour fixer les idées, disons que votre analyseur pourra désormais détecter des erreurs telles que :

• « identificateur déjà déclaré », dans une déclaration globale ou locale, si l’identificateur en question a déjà été déclaré au même niveau,
• « identificateur non déclaré », dans une instruction (i.e. un texte qui n’est pas une déclaration), si l’identificateur en question n’a pas été déclaré, ni localement ni globalement
• « ce n’est pas une variable », « ce n’est pas un tableau », sur un identificateur apparaissant dans une expression ou une instruction d’affectation,
• « ce n’est pas une fonction », « mauvais nombre d’arguments », dans un appel de fonction,
• etc.

Pour être en mesure de faire de telles vérifications vous devez ajouter à votre analyseur une structure de données appelée ici dictionnaire des identificateurs. Pour cela, vous devez choisir :

• La structure de chaque article du dictionnaire. On vous conseille de définir une structure à cinq champs : l’identificateur en question et quatre informations associées (des entiers) : la classe, le type, l’adresse et un éventuel complément qui n’est utile que pour les fonctions.

Vous pouvez donner au champ identificateur soit le type tableau de caractères (de taille connue) soit le type pointeur de caractère. L’inconvénient dans le premier cas est que cela introduit une limitation dans la taille des identificateurs et qu’il va falloir modifier (légèrement) l’analyseur lexical. L’inconvénient dans le second cas est que les ajouts d’identificateurs au dictionnaire impliqueront des « malloc » et qu’il faudra donc ne pas oublier les « free » correspondants lors de l’éventuelle destruction d’un dictionnaire.

La distinction entre la classe (C_VARIABLE, C_FONCTION, etc.) et le type (T_ENTIER, T_TABLEAU, etc.) d’un identificateur est classique mais dans notre compilateur elle n’a pas beaucoup de sens car notre langage L est très simple du point de vue des types. Si vous y tenez, vous pouvez retenir un seul de ces deux champs et lui faire jouer les deux rôles.

Les valeurs de ces champs sont des constantes définies à cet effet (n’utilisez pas les constantes définissant les unités lexicales, elles n’ont rien à voir avec ce qui nous occupe ici).

La question des adresses sera vue plus tard.

• La structure du dictionnaire lui-même. Si notre compilateur devait faire une carrière commerciale cette question serait très importante, car les compilateurs passent beaucoup de temps à rechercher des identificateurs dans le dictionnaire et il est primordial que ce dernier permette des recherches rapides. Mais puisque nous ne travaillons pas dans cet esprit nous allons nous contenter d’un dictionnaire dont les principales qualités sont la clarté et la simplicité, les recherches n’y étant pas aussi rapides qu’elles le pourraient.

On vous conseille donc d’implémenter le dictionnaire par un tableau dont les éléments sont les structures expliquées au point précédent. A ce tableau sont associés deux niveaux, base et sommet, gérés comme expliqué dans le echo sujet sur papier (voyez la figure 1, page 5).

• L’interface du dictionnaire, c’est-à-dire les fonctions et variables à travers lesquelles les autres parties de l’analyseur utilisent le dictionnaire. Si vous n’avez pas d’idée précise sur la question, sachez qu’on peut avoir tous les services nécessaires à travers le tableau dico, les indices base et sommet et deux fonctions simples :

int recherche(char *identificateur, int haut, int bas);

qui recherche dans le dictionnaire un article associé à l’identificateur indiqué. La recherche se fait à reculons de haut–1 jusqu’à bas (il est supposé que bas <= haut; si bas = haut c’est que le dictionnaire est vide). La fonction renvoie l’indice du premier article convenant, ou une valeur négative si un tel article n’existe pas, et

int ajout(char *identificateur);

qui crée un nouvel article dans le dictionnaire (au sommet) et en renvoie l’indice. Le champ identificateur est initialisé avec l’identificateur indiqué (attention, s'agissant de chaînes de caractères, une simple affectation ne suffit peut-être pas...), les autres champs sont initialisés à zéro. Cette fonction se charge de déclencher une erreur en cas de débordement du dictionnaire.

• Exemple : utilisation du dictionnaire à l’occasion d’une déclaration. Examinons ce que devient l’analyse d’une déclaration de variable, dans le cas de la grammaire donnée en exemple plus haut. La production est

declarationVariable -> ENTIER IDENTIF ';'

Dans l’analyseur syntaxique cela s’est traduit par une fonction

void declarVariable(void) {
    uc = yylex();
    if (uc != IDENTIF)
        erreur("identificateur attendu");
    uc = yylex();
    if (uc != ';')
        erreur("';' attendue");
    uc = yylex();
}

Après l’introduction du dictionnaire, cela devient

void declarVariable(void) {
    int id;
    
    uc = yylex();
    if (uc != IDENTIF)
        erreur("identificateur attendu");
    
    id = recherche(lexeme, sommet, base);
    if (id >= 0)
        erreur("identificateur deja declaré");
    id = ajout(lexeme);
    dico[id].classe = contexteLocal ? C_VAR_LOCALE : C_VAR_GLOBALE;
    dico[id].type = T_ENTIER;     
        
    uc = yylex();
    if (uc != ';')
        erreur("';' attendue");
    uc = yylex();
}

N.B. Initialement nulle, la variable globale contexteLocal devient 1 (vraie) lorsque l’analyseur « entre » dans une fonction et redevient 0 (fausse) quand il en « sort » (à propos des points d’« entrée » et de « sortie » d’une fonction. Cela permet d’utiliser la même fonction declarVariable pour analyser les déclarations de variables globales et les déclarations de variables locales.

• Exemple : utilisation du dictionnaire dans la partie exécutable. Regardons l’instruction « appel d’une fonction ». La grammaire dit

instructionAppel -> APPEL IDENTIF '(' finAppelFonction ')' ';'

Dans l’analyseur syntaxique cela se traduit par

void instructionAppel(void) {
    uc = yylex();  
    if (uc != IDENTIF)
        erreur("identificateur attendu");
    uc = yylex();  
    if (uc != '(')
        erreur("'(' attendue");
    uc = yylex();  
    finAppelFonction();
    if (uc != ')')
        erreur("')' attendue");
    uc = yylex();  
    if (uc != ';')
        erreur("';' attendue");
    uc = yylex();  
}

Voici ce qu’ajoute le dictionnaire :

void instructionAppel(void) {
    int id;
    
    uc = yylex();  
    if (uc != IDENTIF)
        erreur("identificateur attendu");

    id = recherche(lexeme, sommet, 0);
    if (id < 0)
        erreur("identificateur non declare");
    if (dico[id].classe != C_FONCTION)
        erreur("ce n'est pas une fonction");

    uc = yylex();  
    if (uc != '(')
        erreur("'(' attendue");
    uc = yylex();
  
    finAppelFonction(id);

    if (uc != ')')
        erreur("')' attendue");
    uc = yylex();  
    if (uc != ';')
        erreur("';' attendue");
    uc = yylex();  
}

N.B. Ci-dessus on passe id, l’indice dans le dictionnaire, à finAppelFonction afin que cette dernière, chargée d’analyser les arguments effectifs de l’appel, puisse vérifier qu’il y en a le nombre voulu (dans un compilateur plus complexe cette fonction devrait vérifier également que les arguments effectifs ont des types compatibles avec ceux des arguments formels).

• Les adresses des variables globales. Comme nous verrons à la section suivante, les adresses des variables globales sont relatives à une certaine base qui n’est pas connue durant la compilation, mais uniquement lors de l’exécution. Cette base est notée BEG (comme Base de l’Espace Global) et a pour valeur l’indice de la première cellule mémoire libre, à la suite du code produit par le compilateur. Il est clair que la valeur de BEG n’est pas connue durant la compilation : il faut attendre la fin de celle-ci pour connaître la taille du code produit.

Il découle de tout cela que la première variable globale a l’adresse 0 (qui, à l’exécution, se traduira par BEG + 0), la deuxième variable globale l’adresse 1 (BEG + 1), la troisième l’adresse 2, etc. La règle est simple : l’adresse d’une variable globale est la somme des tailles des variables que le compilateur a précédemment rencontrées.

Pour gérer cela il suffit donc de se donner un compteur, appelons-le adresseGlobaleCourante, initialisé à zéro et incrémenté de 1 à chaque déclaration de variable.

Les tableaux sont traités exactement de la même manière, sauf que lors de la déclaration d’un tableau adresseGlobaleCourante n’est pas incrémenté de 1 mais de la taille du tableau.

• Travail à faire. Vous devez écrire les définitions des types, variables et les deux fonctions, recherche et ajout, mentionnés plus haut, puis passer en revue votre analyseur pour déceler tous les endroits où il faut ajouter (il ne s’agit que d’ajouts!) du code nouveau pour effectuer l’analyse sémantique.

Pour tester le dictionnaire réalisé

• écrivez des codes sources qui provoquent toutes les erreurs sémantiques possibles ;
• ajoutez à votre analyseur du code (provisoire) affichant le dictionnaire, par exemple à la fin de l’analyseur de chaque fonction (afin de contrôler le dictionnaire local correspondant).

5 et 6. Sur la production de code

La définition du langage machine se trouve dans le sujet en papier, ou bien ici. Ce langage est défini par un ensemble de codes numériques, appelés opcodes, qui doivent faire l’objet d’une collection de définitions de constantes (par exemple dans un fichier opcodes.h) :

#define EMPC 1
#define EMPL 2
#define DEPL 3
...

Veillez à ce que les identificateurs des opcodes soient tous différents des autres constantes déjà utilisées (unités lexicales, valeurs du dictionnaire, etc.). N’essayez pas de réutiliser ici ces constantes préexistantes, elles n’ont rien à voir avec le langage machine.

Dans cette partie du travail, l’exercice mental à faire constamment est le suivant : étant donnée une construction du langage L (une instruction, une expression, etc.), déterminer :

1. quel code machine en est la traduction (ce qui implique qu’on est capable d’imaginer et de comprendre l’exécution ultérieure de ce code)
2. comment faire pour que l’analyse de la construction en question produise le code machine correspondant.

• Exemple (du cours). Soient x, y, et z des variables globales d’adresses respectives 0, 1 et 2. Étant donnée l’expression qui en L s’écrit comme ceci :

123 * x + y

sa traduction en langage machine est la suite des 8 codes

EMPC 123 EMPG 0 MUL EMPG 1 ADD 

qu’on affichera de préférence, pour faciliter la lecture :

EMPC 123
EMPG 0
MUL
EMPG 1
ADD 

Pour comprendre pourquoi la suite de codes ci-dessus est la traduction de l’expression donnée plus haut il faut en imaginer l’exécution. Si vous comprenez cette exécution vous constaterez qu’elle ajoute une valeur au sommet de la pile  (la valeur de l’expression).

• Exemple. Considérons maintenant l’instruction

z = 123 * x + y;

sa traduction en langage machine est la suite des 10 codes

EMPC 123 EMPG 0 MUL EMPG 1 ADD DEPG 2  

ou

EMPC 123
EMPG 0
MUL
EMPG 1
ADD
DEPG 2 

Si vous imaginez l’exécution de cette suite de codes vous constaterez que son exécution laisse la pile dans l’état où elle se trouvait lorsque cette suite a commencé à être exécutée.

On retiendra (et on vérifiera) que, en tout circonstance :

• l’exécution d’une suite de codes qui est la traduction d’une expression ajoute une (et une seule) valeur au sommet de la pile,
• l’exécution d’une suite de codes qui est la traduction d’une instruction laisse la pile comme elle était.

• Production de code. Supposons que la mémoire de la machine cible est représentée par un grand tableau mem déclaré (MAXMEM est une constante préalablement définie) :

int mem[MAXMEM];

Puisque le compilateur dépose le code produit directement dans la mémoire de la machine, une opération comme « générer l’instruction ADD » se programme tout simplement par

mem[iMem++] = ADD;

(iMem est un compteur initialisé à 0 une seule fois au début de la compilation ). De même, une opération comme « générer l’instruction EMPG 1 » donne :

mem[iMem++] = EMPG;
mem[iMem++] = 1;

Le travail qui vous reste à faire maintenant est donc de trouver les endroits, dans l’analyseur que vous avez déjà, dans lesquels ajouter de telles productions de code. Par exemple, l’instruction « EMPC 123 » correspondant à l’apparition dans le programme source de la constante 123, qui est une sorte de facteur. Donc la production des codes « EMPC 123 » se passe pendant l’analyse d’un facteur, c’est-à-dire dans la fonction :

void facteur(void) {
    switch (uc) {
        case NOMBRE:
            uc = yylex();
            break;
        case ’(’:
            uc = yylex();
    ... etc. ...
    }
}

L’endroit où générer les deux codes indiqués est facile à trouver :

void facteur(void) {
    switch (uc) {
        case NOMBRE:
            mem[iMem++] = EMPC;
            mem[iMem++] = atoi(lexeme);
            uc = yylex();
            break;
        case ’(’:
            uc = yylex();
    ... etc. ...
    }
}

• Les adresses des fonctions. Il a été dit que la rencontre de la déclaration d’une fonction provoque l’ajout de son nom dans le dictionnaire (global), avec diverses informations, dont son nombre d’arguments et son adresse. Cela est évidemment nécessaire au compilateur pour traiter correctement les appels de la fonction ultérieurement rencontrés.

L’adresse d’une fonction est l’endroit de la mémoire où son code commence, c’est-à-dire tout simplement la valeur qu’a iMem juste avant de débuter la compilation du bloc qui constitue le corps de la fonction.

• Autres exemples. D’autres exemples de production de code très instructifs sont une instruction conditionnelle si...alors...sinon... ou bien une boucle tantque...faire...

Examinons quel doit être le code produit dans le cas d’une instruction conditionnelle : le texte source peut-être de la forme

si expression alors instruction₁ sinon instruction₂

le code produit ressemblera à ceci

    [ code produit par ]
    [ la compilation   ]
    [ de expression    ]
    SIFAUX a 
    [ code produit par ]
    [ la compilation   ]
    [ de instruction1  ]
    SAUT b
 a  [ code produit par ]
    [ la compilation   ]
    [ de instruction2  ]
 b  ...

Il vous reste à
    - trouver ce qu’il faut ajouter à l’analyseur que vous possédez déjà, et à quels endroits, pour qu’il produise le code ci-dessus
    - surmonter la difficulté créée par le fait qu’au moment où le compilateur doit produire l’instruction « SIFAUX a » la valeur de a n’est pas encore connue ; remarque analogue pour la production de « SAUT b ».

• Les variables locales et les arguments des fonctions. Pendant la compilation de la partie exécutable (les instructions qui forment le corps d’une fonction) deux ensembles de variables sont accessibles :
    - les variables globales, représentées dans le code produit par des déplacements relatifs à BEG (qui ne change pas durant tout le programme),
    - les variables locales (et les arguments) de la fonction active, et uniquement de celle-là.

Par fonction active nous entendons la plus récemment appelée des fonctions non encore terminées ; ses variables locales et arguments occupent le dessus de la pile. Notez que les variables locales et les arguments des autres fonctions appelées et non encore terminées (par exemple, la fonction qui a appelé la fonction active, celle qui a appelé celle-là, etc.) ne sont pas perdues ; elles sont simplement inaccessibles tant que la fonction active n’a pas terminé (ces variables sont dans la pile, enfuies de plus en plus profondément qu’on regarde des fonctions de plus en plus anciennement appelées).

Pour ce qui concerne l’accès aux variables locales et aux arguments, la figure importante :

Un indice, noté BEL (comme Base de l’Espace Local) indique la première variable locale, celle à qui le compilateur a attribué l’adresse 0 ; BEL + 1 indique la deuxième variable locale et, plus généralement, la cellule mémoire correspondant à la variable locale qui a reçu du compilateur l’adresse i est mem[BEL + i].

Les arguments sont eux aussi représentés par des déplacements relatifs à BEL, mais des déplacements négatifs (ils sont « de l’autre côté » de BEL). Cela provient du fait que c’est la fonction appelante, avant l’appel de la fonction en question, qui a mis les arguments effectifs au sommet de la pile (alors que BEL n’avait pas encore la valeur qui nous intéresse ici). C’est le premier argument qui se trouve le plus éloigné de BEL. Étudiez la figure ci-dessus, vous comprendrez ceci :

l’argument d’adresse k (k varie de 0 à nbrArgs–1) se trouve dans la cellule mem[BEL - (nbrArgs + 2) + k]

« Sous » les arguments, une cellule a été réservée dans la pile pour recevoir le résultat de la fonction. Par conséquent, pendant le déroulement de la fonction :

le résultat de la fonction se trouve dans la cellule mem[BEL - (nbrArgs + 3)]

Le travail qui consiste à remplacer dans le dictionnaire k, le rang d'un argument, par – (nbrArgs + 2) + k doit être fait par le compilateur

• soit une fois pour toutes, dès la rencontre de la parenthèse ')' à la fin des arguments
• soit par la suite, chaque fois que le compilateur rencontre une référence à un argument (comme facteur ou comme membre gauche d’une affectation)

Dans le deuxième cas, ce calcul suppose qu’on a connaît constamment la valeur de nbrArgs, le nombre d’arguments de la fonction qu’on est en train de compiler. Réfléchissez un peu, vous verrez qu’on peut avoir cette valeur à partir du dico et de la valeur de base.

• L’appel d’une fonction. L’appel des fonctions est assez bien décrit dans le sujet sur papier, pages 6 et 7. Ce texte explique en particulier le rôle précis des instructions ENTREE et SORTIE (il s’agit d’entrer et de sortie d’une fonction, cela n’a rien à voir avec la lecture et l’écriture de données).

7.  Sur la machine virtuelle

• Organisation. Il s’agit de simuler un processeur capable d’exécuter le langage machine donné. Vous pouvez organiser votre programme de deux manières :

1. Le compilateur dépose le code généré directement dans la mémoire de la machine virtuelle ; ainsi, à la fin de la compilation tout est en place pour l’exécution. Dans cette organisation, compilateur et machine virtuelle sont deux parties d’un même programme.
2. Le compilateur range le code généré dans un fichier « objet », d’où il est extrait au moment de l’exécution ; le compilateur et la machine virtuelle sont alors deux programmes séparés. Légèrement plus compliquée, cette manière de procéder est plus proche du fonctionnement réel des compilateurs ; par exemple, elle permet l’exécution d’un programme compilé « longtemps » à l’avance.

En outre, la deuxième manière de procéder ouvre la porte, pour ceux qui auront du temps et de la curiosité, à la mise en place d’un éditeur de liens permettant l’assemblage de fichiers objets compilés séparément.

• Programmation. Je ne peux guère vous donner des tuyaux sur la machine virtuelle sans faire l’exercice à votre place ! Il s’agit de simuler l’exécution des codes définis par la table donnée dans le sujet. Cette table est très précise à propos de l'effet de chaque code.

Les « conseils » suivants sont des évidences :

• plus c’est simple, plus c’est crédible,
• comme mémoires utilisables vous n’avez droit qu’au tableau mem, les registres CO, BEL, BEG et SP et une ou deux variables éphémères,
• l’exécution est séquentielle, sauf dans le cas de certaines instructions : SAUT, SIVRAI, SIFAUX, APPEL et RETOUR.

• Démarrage et arrêt. Deux points restent à régler : à quel endroit du code l’exécution du programme commence-t-elle (on appelle cela le « point d’entrée » du programme) et comment s’arrête-t-elle ? Vous pouvez traiter ces questions à la manière de Pascal (le langage), en fixant dans la grammaire qu’il doit exister une fonction principale qui n’est pas compilée comme les autres. Cela vous permet de déterminer, pendant la compilation, le point d’entrée et l’endroit où il faut générer une instruction STOP.

Ou bien, de manière bien plus simple et élégante, vous pouvez décider (comme en C, Java, etc.) que pour le compilateur toutes les fonctions sont équivalentes. Ensuite, au moment de l’exécution, une convention indique le nom de la fonction par laquelle l’exécution doit commencer. Par exemple, on peut, avant de commencer la compilation, initialiser la mémoire avec les codes

0 PILE 1
2 APPEL 0
4 STOP
5 ... 

A la fin de la compilation il faut chercher dans le dictionnaire l’adresse de la fonction nommée principale (ou tout autre nom convenu) et en copier l’adresse dans la case mem[3]. Le code est alors prêt, l’exécution commencera par l’instruction d’adresse 0 et l’arrêt de la machine se produira automatiquement au retour de la fonction principale.