Sommaire Définition du langage d’expérimentation Compilateur pour le langage Z minimal Extensions du langage Z minimal
Chapitre précédent Chapitre 15 : Procédures et fonctions Chapitre suivant
15.2 Table des procédures (TABPRO)
15.4 Organisation de la mémoire à l’exécution
15.10 Exemple 3 (Variables globales)
15.11 Exemple 4 (Références aux variables globales)
15.1 Introduction
Un programme exprimé avec le langage Z est un ensemble de modules. Le premier module est principal. Chaque module autre que le principal est soit une procédure (ACTION) ou une fonction (FONCTION).
Les paramètres d’un module doivent être déclarés. Ils sont transmis par référence (ou adresse). Cela veut dire qu’il ne sont pas protégés par le module.
Tous les objets déclarés (variables , structures, tableaux, … ) dans le module principal sont globaux à toutes les actions et fonctions.
Les objets globaux sont connus et peuvent être référencés dans toutes les actions et fonctions.
Si une variable est re déclarée avec le même nom dans une action secondaire ou fonction, elle sera considérée comme locale.
Si une variable utilisée dans un module n'est pas définie dans l'action ou la fonction, elle doit être globale(déclarée dans le module principal).
Chaque module est compilé séparément. Le compilateur range les informations relatives aux modules dans une table dite table des procédures.
Le résultat de chaque module compilé (forme interne) est sauvegardé dans un fichier.
La sémantique des procédures et des fonctions consiste à:
- résoudre le problème de la portée des objets, c’est à dire leur domaine de visibilité.
- définir une organisation de la mémoire à l’exécution et une stratégie de gestion des zones de données associées aux modules composant un programme.
- définir les quadruplets à générer,
- insérer les fonctions sémantiques dans les règles de grammaire correspondantes et les décrire en détail.
L’interprétation consiste à exécuter les quadruplets générés avec un langage de programmation.
15.2 Table des procédures (TABPRO)
Le compilateur possède une table contenant les caractéristiques de tous les modules compilés dans un programme. Elle renferme les informations suivantes:
Champs Signification
Nom Nom de la procédure ou fonction
Numéro Numéro attribué
Défini Booléen indiquant si le module a été défini
Type Type (si le module compilé est une fonction)
LONGZDD Longueur de la zone de données
QUADRUPLES Table des quadruplets
TABOB Table des objets
TABCOMP Table complémentaire
TABTYP Table des types
Remarquons que la table des constantes TABCONS n’est pas référencée dans la table TABPRO. Le compilateur utilise une seule table pour ranger les constantes de tous les modules du programme.
15.3 Portée des objets
La portée des objets consiste à reconnaître les objets locaux et globaux tels que décrit précédemment. Dans la phase de compilation il y a présence permanente des tables des symboles et des tables des objets de l’action principale et de l’action (ou la fonction) en cours de compilation.
Pour le programme principal, nous utilisons :
TABSYMG : table des symboles du module principal.
TABOBG : table des objets du module principal.
Pour un module (action ou fonction) en cours de compilation, nous utilisons :
TABSYM : table des symboles du module en cours de compilation.
TABOB : Table des objets du module en cours de compilation.
Les modules New_idf et Old_idf sont modifiés comme suit:
New_id(Idf)
Un nouvel identificateur vient d’être déclaré. .
- S’il s’agit de la compilation du module principal, il vérifie si l’identificateur Idf n’est pas déjà déclaré (n’existe pas dans la table TABSYMG) puis le met dans la table.
- S’il s’agit de la compilation d’un module secondaire (action ou fonction), il vérifie si l’identificateur Idf n’est pas déjà déclaré (n’existe pas dans la table TABSYM) puis le met dans la table.
Dans les deux cas, ce module rend l’indice du nouvel identificateur créé dans la table des symboles, -1 si échec.
Old_id(idf )à
Un identificateur vient d’être déclaré ou utilisé.
- S’il s’agit de la compilation du module principal, il recherche l’emplacement correspondant dans la table des symboles du module principal (TABSYMG).
- S’il s’agit de la compilation d’un module secondaire (action ou fonction), il recherche d’abord l’emplacement correspondant dans la table des symboles du module en cours de compilation (TABSYM). Si un tel emplacement n’existe pas, il continue la recherche dans TABSYMG.
Dans les deux cas, ce module rend l’indice du nouvel identificateur créé dans la table des symboles, -1 si échec.
15.4 Organisation de la mémoire à l’exécution
La figure 24 montre le format de la zone de données généralisée. Dans notre implémentation, une zone de données ne contient que des adresses ( vers n’importe quel type d’objet ). Les trois premiers mots de la zone de données sont des informations de lien et sont utilisés lors des appels de procédures et fonctions. Il y a un mot par paramètre et autant de mots que de variables locales déclarées dans le module et de variables temporaires créées par le compilateur.
Figure 24: Format de la zone de données
La figure 25 montre l’environnement d’exécution pour le scénario suivant:
l’action principale (P) appelle Q; Q appelle R; R appelle S. ZDDs est la zone de données du module en cours d’exécution. Une pile est utilisée pour la sauvegarde des zones de données de modules qui attendent les retours. Le fond de la pile contient les variables globales. Les zones de données et la table des constantes CONSTANTES contiennent des adresses vers les données qui sont rangées dans le tas.
Figure 25: Environnement d’exécution
Le tas est une zone mémoire commune à tous les modules. Il contient tous les objets utilisés : variables, structures, tableaux, ...
15.5 Quadruplets
Au niveau des déclarations ACTION(Parf1,Parf2,…) et FONCTION(Parf1, Parf2,….) : Type, nous utilisons le quadruplet (‘Proc’, A, B, C ) avec les paramètres A, B et C définis comme suit:
A : nombre de paramètres.
B : pointeur dans TABCOMP vers la liste des paramètres formels.
C : pointeur dans TABPRO.
Dans le cas d’une fonction, un paramètre est ajouté implicitement de type Type et contiendra le résultat de la fonction.
Au niveau de l’instruction APPEL Idf (Par1, Par2,…..) , le quadruplé (‘Appel’, A, B, C ) est utilisé avec les paramètres A, B et C définis comme suit:
A : pointeur dans TABOB vers une constante contenant le nom de l’appelée.
B : pointeur dans TABCOMP vers la liste des paramètres réels.
C : nombre de paramètres.
De plus, en fin de compilation d’un module, nous devons générer le quadruplet (‘Ret’, , , ) qui indique un retour vers le module appelant.
15.6 Syntaxe
Notre grammaire courante devient comme suit avec l’ajout en surbrillance des règles relatives à la définition des procédures et fonctions ainsi qu’à leur invocation.
Déclarations
<Algo Z> → [ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin [;] { ~<Act> | <Fonct>~ [;] }*
<Act> → Action Idf [ ( <Li> ) ] [;] [ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin
<Fonct> → Fonction Idf ( <Li> ) : <Typ> [ ~Soit|Soient~ <Ps> ] Debut <Lis> Fin
<Ps> → <S>;{ [~Soit|Soient~] <S>;}*
<S> → <Li> Sep ~ <Typ>| ~Action|Fonction(<Typ>)~ ~
<Li> → Idf {, Idf}*
<Typ> → Types | <Structsimple> | Tableau(<Lc>)[De~<Structsimple>|Types~ ]
<Structsimple> → [Structure ](Types {, Types }*)
<Lc> → Cste {, Cste}*
Instructions
< Lis > → < Inst > { ; < Inst > }*
<Inst> → Idf := <Exp> |
Lire ( Idf {, Idf }* ) |
Ecrire (<Exp> {,<Exp>}* ) |
Tantque <Exp> [ : ] <Lis> Fintantque |
Si <Exp> [:] <Lis> [Sinon <Lis>] Fsi |
Pour Idf:= <Exp>,<Exp> [, <Exp>][:] <Lis> Finpour |
Appel Idf [(Exp {,<Exp>}*)] |
~ Init_vecteur | Init_struct ~ ( Idf , [[ ~<Exp>|[[<Exp> {, <Exp>}*]] ~ {, ~<Exp>|[[<Exp> {, <Exp>}*]]~}* ]] ) |
Aff_element ( <Exp> [[ <Exp> {, <Exp> }* ]] ,<Exp> ) |
Aff_struct(Idf, Cste, <Exp>)
Expressions
<Exp> → <Exps>[ Opr <Exps>]
<Exps> → [Sign] <Terme> { Opa <Terme> }*
<Terme> → <Facteur>{Opm <Facteur>}*
<Facteur> → Idf [(Exp {,<Exp>}*)] | Cste | ( <Exp>) | <Fonct> | Non <Facteur> | Vrai | Faux | Chaine
<Fonct> → Element ( <Fonct> [[ <Exp> {, <Exp> }* ]] ) |
Struct ( Idf, Cste)
15.7 Fonctions sémantiques
Spécification de module (action ou fonction)
<S> → <Li> Sep Action F1 | Fonction (<Typ>) F2
F1
Soit L la liste des identificateurs créée par <Li>.
Pour chaque identificateur Idf :
- vérifier s’il n’est pas déjà déclaré, sinon Erreur.
-Le mettre dans TABPRO ( Champ Nom=Idf et champ Défini=Faux)
F2
Soit L la liste des identificateurs créées par <Li> et soit Typefonc le type retourné par <Typ>.
Pour chaque identificateur Idf :
- vérifier s’il n’est pas déjà déclaré, sinon Erreur.
- Le mettre dans TABPRO ( champ Nom=Idf , champ Défini=Faux et champ Type= Typefonc)
Déclaration d’une action
<Act> → Action F1 Idf F2 [ ( <Li> ) ] [;] F3 [ ~Soit|Soient~ <Ps> ] Debut F4 <Lis> Fin F5
F1
Initialiser un compteur pour l’attribution des adresses (Adrcour=3). Les trois premiers mots de la zone de données sont réservés.
F2
Vérifier que l’action Idf existe dans TABPRO. Sinon Erreur.
Mettre le champ Défini à Vrai. Soit Pttabpro l’emplacement de Idf.
F3
Soit L la liste des paramètres retournée par <Li>.
Créer les objets pour les paramètres et les mettre dans TABCOMP. Soit Pttabcomp l’emplacement dans cette table et N leur nombre.
Générer le quadruplet (‘Proc’, N, Pttabcomp, Pttabpro)
F4
Vérifier que tous les paramètres sont déclarés.
F5
Générer le quadruplet (‘Ret’, , ,).
Déclaration d’une fonction
<Fonct> → à Fonction F1 Idf F2 ( <Li> ) : <Typ> F3
[ ~Soit|Soient~ <Ps> ] Debut F4 <Lis> Fin F5
F1
Initialiser un compteur pour l’attribution des adresses. (Adrcour=3).
F2
Vérifier que la fonction Idf existe dans TABPRO. Sinon Erreur.
Mettre le champ Défini à vrai. Soit Pttabpro l’emplacement de Idf.
F3
Soit L la liste des paramètres retournée par <Li>.
Créer les objets pour les paramètres et les mettre dans TABCOMP. Soit Pttabcomp l’emplacement dans cette table et N leur nombre.
Ajouter un paramètre avec le nom de la fonction et ayant le type retourné par <Typ>.
Générer le quadruplet (‘Proc’, N+1, Pttabcomp, Pttabpro)
F4
Vérifier que tous les paramètres sont déclarés.
F5
Générer le quadruplet (‘Ret’, , ,).
Appel de procédure
<Inst> → Appel Idf F1 [(<Exp> F2 {,<Exp> F3 }*)] F4
F1
Vérifier que la procédure(ou action) Idf a été déclarée, sinon Erreur.
F2
Soit Temp le résultat retourné par <Exp>.
S’il s’agit d’une constante alors générer un temporaire Tempx du type de la constante et générer le quadruplet (‘Aff’, Temp, , Tempx).
Mettre Temp (ou Tempx) dans TABCOMP. Soit Pttabcomp son emplacement dans cette table.
Initialiser un compteur Compte à 1.
F3
Soit Temp le résultat retourné par <Exp>.
S’il s’agit d’une constante alors générer un temporaire Tempx du type de la constante et générer le quadruplet (‘Aff’, Temp, , Tempx).
Mettre Temp (ou Tempx) dans TABCOMP. Incrémenter Compte.
F4
Générer une constante chaîne de caractères pour Idf et créer dans TABOB un objet pour cette constante. Soit Pt1 son emplacement dans cette table.
Générer le quadruplet (‘Appel’, Pt1, Pttabcomp, Compte)
Remarque : la vérification sur le nombre de paramètres et la concordance des types est effectuée à l’exécution.
Appel de fonction
<Facteur> → Idf [( F1 <Exp> F2 {,<Exp> F2 }*)] F3
F1
Vérifier que la fonction Idf a été déclarée. Sinon Erreur. Soit Typefonc le type de la fonction Idf.
Générer un temporaire Tempf de type Typefonc et le mettre dans TABCOMP. Soit Pttabcomp son emplacement dans cette table.
Initialiser un compteur Compte à 1.
F2
Soit Temp le résultat retourné par <Exp>.
S’il s’agit d’une constante générer un temporaire Tempx du type de la constante et le mettre dans TABOB.
Générer le quadruplet (‘Aff’, Temp, , Tempx).
Mettre Temp (ou Tempx) dans TABCOMP.
Incrémenter Compte.
F3
Générer une constante chaîne de caractères pour Idf et créer dans TABOB un objet pour cette constante. Soit Pt1 son emplacement dans cette table.
Générer le quadruplet (‘Appel’, Pt1, Pttabcomp, Compte).
Retourner (Ptempf).
Remarque : la vérification sur le nombre de paramètres et la concordance des types est effectuée à l’exécution.
15.8 Exemple 1 (Actions)
Les figures 26 et 27 montrent respectivement les tables de compilations générées pour le programme principal et l’action Somme du programme source donné.
Figure 26: Tables de compilation(Programme principal)
Figure 27: Tables de compilation(Procédure)
15.9 Exemple 2 (Fonctions)
Les figures 28 et 29 montrent respectivement les tables de compilations générées pour le programme principal et la fonction Somme du programme source donné.
Figure 28: Tables de compilation(Programme principal)
Figure 29: Tables de compilation(Fonction)
15.10 Exemple 3 (Variables globales)
La figure 30 montre les tables de compilation générées pour le programme principal du programme source donné.
Figure 30: Tables de compilation(Programme principal)
15.11 Exemple 4 (Références aux variables globales)
La figure 31 montre les tables de compilation générées pour le programme principal du programme source donné. Les indices négatifs (en surbrillance) référencent des variables globales.
Figure 31: Tables de compilation(Action)
15.12 Interprétation
A la rencontre du quadruplet (‘Appel’, A, B, C ) avec les paramètres A, B et C définis comme suit:
A : pointeur dans TABOB vers une constante contenant le nom de l’appelée.
B : pointeur dans TABCOMP vers la liste des paramètres réels.
C : nombre de paramètres.
les opérations suivantes sont effectués:
- Vérification sur le nombre de paramètres et la concordance des types.
- Allocation d'une zone de données (Empilement) et mise à jour du sommet de pile.
- Mise à jour des informations de lien
Mot 0 <-- adresse zone de données de l'appelant.
Mot 1 <-- adresse vers un entier contenant le numéro de l’appelant.
Mot 2 <-- adresse vers un entier contenant le numéro du quadruplet
(adresse de retour) dans l'appelant.
- Passage des paramètres (transmission des adresses vers les mots Mot3, Mot4, ...de la zone de données de l’appelée) .
- Chargement des tables de l'appelée si elles n'existent pas en mémoire..
- Donner la main à l'appelée.
A la rencontre du quadruplet (‘Ret’, , , ) les opérations suivantes sont effectuées:
- Récupération du numéro du quadruplet de retour (adresse de retour) et le numéro de l’appelant qui sont dans la zone de données du module courant.
- Libération de la zone de données ( dépilement ) et mise à jour du sommet de pile.
- Si les tables de l'appelant n'existent pas en mémoire, les charger. ( cas des appels récursifs).
- Donner la main à l’appelant.
15.13 Remarques générales
Les procédures récursives sont gérées de la même manière.
Pendant l’interprétation ( ou exécution):
- les tables de compilation du module principal existent toujours en mémoire.
- au plus, les tables d’un module secondaire sont présentes en mémoire. Des opérations de « Swapping » sont alors entreprises comme suit : lors d’un appel ou d’un retour à un module , si les tables de ce dernier ne sont pas présentes en mémoire centrale alors elles y sont chargées.
Il est clair que les tables de compilation restent invariantes pendant l’exécution.