Chapitre 10 : Déclarations locales
On introduit donc ici les déclarations de variables locales aux
procédures ; l'extension de PP5 ainsi construite se nomme PP6.
10.1 Grammaire et sémantique
Nous étendons la grammaire de PP5 par l'introduction d'une règle
PROCS autorisant la définition de procédures pouvant inclure
des déclarations de constantes et variables locales :
|
PROGRAM |
|
::= |
|
program ID ; BLOCK . |
|
|
BLOCK |
|
::= |
|
CONSTS VARS PROCS INSTS |
|
|
PROCS |
|
::= |
|
{ proc ID ; CONSTS VARS INSTS ; } |
|
De même que dans PP5, on autorise l'appel de procédure dans les
instructions :
|
INST |
|
::= |
|
... | APPEL | ... |
|
|
APPEL |
|
::= |
|
ID |
|
l'identificateur ID de la règle APPEL doit être le nom d'une
procédure précédemment définie.
Sémantiquement, nous définissons une notion de visibilité
des variables. Une variable locale n'est visible que dans la
procédure qui la déclare. Une variable globale est visible dans
une procédure s'il n'existe pas de variable locale portant le même
nom.
10.2 Visibilité des variables
Pour respecter cette règle de visibilité des variables locales, il
est nécessaire que les déclarations locales apparaissent dans la
table des symboles uniquement durant l'analyse de la procédure
correspondante.
On va donc gérer une table des symboles à deux niveaux. Le premier
niveau contient les déclarations globales (y compris les
déclarations de procédures, qui sont globales) ; le deuxième
niveau contient les déclarations locales à la procédure en cours
d'analyse. La limite entre ces deux niveaux est indiquée par la
variable LIMIT ; les entrées dans la table des symboles d'indice
supérieure à LIMIT sont locales.
On obtient la procédure PROCS d'analyse de déclarations de
procédures de la figure 10.1.
procedure PROCS ;
var LIMIT : integer ;
begin
while TOKEN = PROC_TOKEN do begin
NEXT_TOKEN ;
(* on entre le nom de la procedure en global *)
TESTE_ET_ENTRE (ID_TOKEN, PROCEDURE) ;
TESTE (PT_VIRG_TOKEN) ;
(* on memorise le dernier global *)
LIMIT := DERNIERSYM ;
if TOKEN = CONST_TOKEN then CONSTS ;
if TOKEN = VAR_TOKEN then VARS ;
INSTS ;
TESTE (PT_VIRG_TOKEN) ;
(* on oublie les declarations locales *)
DERNIERSYM := LIMIT ;
GENERER1 (RET)
end
end ;
Figure 10.1 : Procédure PROCS d'analyse de déclarations de procédures.
10.3 Allocation des variables
Deux solutions sont possibles pour l'allocation des variables locales :
l'allocation statique et l'allocation dynamique sur la pile.
10.3.1 Allocation statique
L'allocation statique associe un emplacement mémoire fixe dans la
pile à chaque variable, que celle-ci soit globale ou locale. à
chaque fois qu'une variable (globale ou locale) est déclarée, on
incrémente l'OFFSET, l'adresse suivante est donc allouée à la
variable.
Pour le programme
program X ;
var A, B ;
proc Y ;
var C, D ;
...
proc Z ;
var E, F ;
...
begin
...
end .
on obtient alors les adresses d'allocation dans la pile suivantes pour
les différentes variables
| Variable |
Adresse |
A de X |
0 |
B de X |
1 |
C de Y |
2 |
D de Y |
3 |
E de Z |
4 |
F de Z |
5 |
Toute variable a donc une adresse différente et toutes les adresses
sont connues à la compilation.
On obtient le schéma de P-Code suivant :
|
|
|
|
|
INT N |
|
|
|
réservation pour toutes les variables (globales et locales) |
|
|
|
|
|
|
BRN PP |
|
|
|
|
|
|
<proc> |
|
|
|
|
|
|
... |
|
|
|
|
|
|
RET |
|
|
|
|
|
|
<proc> |
|
|
|
|
|
|
... |
|
|
|
|
|
|
RET |
|
|
PP |
|
|
|
... |
|
|
|
|
|
|
<program> |
|
|
|
|
|
|
... |
|
|
|
|
|
|
HLT |
|
Cette solution est celle choisie par le langage FORTRAN. Cette
solution ne permet pas la récursivité, car à chaque appel d'une
procédure ce sont toujours les mêmes adresses qui sont utilisées.
Si l'on désire autoriser la récursivité (comme en Pascal ou en
PP6 !), il faut des adresses différentes pour chaque appel
récursif.
10.3.2 Allocation dynamique sur la pile
Afin d'associer des adresses différentes aux variables à chaque
appel récursif, il devient impossible de connaître les adresses
lors de la compilation (le nombre d'appels récursifs ne pouvant
être connu). On va donc allouer dynamiquement sur la pile les
variables locales. On obtient le schéma de P-Code suivant :
|
|
|
|
|
INT N |
|
|
|
réservation pour les variables globales |
|
|
|
|
|
|
BRN PP |
|
|
|
|
|
|
INT N1 |
|
|
|
réservation dynamique pour les variables de P1 |
|
|
|
|
|
|
<proc> |
|
|
|
|
|
|
... |
|
|
|
|
|
|
RET |
|
|
|
|
|
|
INT N2 |
|
|
|
réservation dynamique pour les variables de P2 |
|
|
|
|
|
|
<proc> |
|
|
|
|
|
|
... |
|
|
|
|
|
|
RET |
|
|
PP |
|
|
|
... |
|
|
|
|
|
|
<program> |
|
|
|
|
|
|
HLT |
|
Les adresses associées aux variables locales sont alors des adresses
relatives au début de la zone allouée dynamiquement dans la pile.
Pour le même programme
program X ;
var A, B ;
proc Y ;
var C, D ;
...
proc Z ;
var E, F ;
...
begin
...
end .
on obtient alors les adresses d'allocation suivantes pour les
différentes variables
| Variable |
Adresse |
A de X |
globale 0 |
B de X |
globale 1 |
C de Y |
relative 0 |
D de Y |
relative 1 |
E de Z |
relative 0 |
F de Z |
relative 1 |
Modifier la procédure PROCS pour prendre en compte cette
allocation des variables.
10.4 Accès aux variables locales
L'accès à une variable globale se fait par un LDA i avec i
un déplacement par rapport à la base de la mémoire,
c'est-à-dire par rapport à la base de la pile dans la zone
réservée par le INT n du programme principal.
L'accès à une variable locale se fera par LDL i avec i un
déplacement par rapport à la base de la zone mémoire
réservée par le INT n exécuté à l'appel de la
procédure.
Il se pose alors le problème suivant : comment connaître cette
adresse de base lors de l'exécution ?
-
Lorsque l'on appelle une procédure, c'est simple : la base
pour la procédure appelée est le pointeur de pile au
moment de l'appel ;
- Au retour de la procédure, il faut retrouver la base de la
procédure appelante.
L'idée est de chaîner les zones de la pile. Par exemple, lorsque le programme principal a appelé la procédure P1 qui a elle-même appelé la procédure P2, l'état de la pile est celui de la figure 10.2.
| |
|------------|
| variables |
| locales de |
| P2 |
|------------|
| ------------+
|------------| |
| AR |<--|-------- BASE
|------------| |
| variables | |
| locales de | |
| P1 | |
|------------| |
| ------------|----+
|------------| | |
| AR |<--+ |
|------------| |
| variables | |
| globales | |
+------------+<-------+
Figure 10.2 : État de la pile aprés l'appel de la procédure P2, appelée par la procédure P1, elle-même appelée par
le programme principal.
BASE est une variable de l'interpréteur de P-Code qui pointe sur
la base de la zone de la procédure en cours d'exécution. BASE
vaut zéro lorsque l'exécution est dans le programme principal.
On modifie en conséquence les instructions CAL, RET
de l'interpréteur et on ajoute l'instruction LDL.
10.5 Travaux dirigés et travaux pratiques
-
Quels sont les avantages et inconvénients d'une allocation
statique des variables locales telle qu'elle est réalisée en
Fortran ?
- Donner le P-Code à générer et l'évolution, lors de la
compilation, de la table des symboles utilisée pour l'exemple de
programme PP6 de la figure 10.3.
program X ;
var A ;
proc Y ;
var B ;
begin
read (B) ;
A : = A + B
end ;
proc Z ;
var B ;
begin
read (B) ;
A : = A * B ;
Y
end ;
begin
read (A) ;
Z ;
write (A)
end .
Figure 10.3 : Exemple de programme PP6.
- Même chose pour le programme récursif de la
figure 10.4.
program INVERT ;
var OK ;
proc INV ;
var N ;
begin
read (N) ;
if N <> OK then INV ;
write (N)
end ;
begin
OK := 0 ;
INV
end .
Figure 10.4 : Exemple de programme PP6 récursif.
- On modifiera le code de la procédure
PROCS donnée à la
figure 10.1 pour prendre en compte l'allocation des
variables locales relativement à la base de la zone locale de
mémoire.
-
Donner le nouveau code des instructions P-Code
CAL,
RET, et LDL.
- Implémenter les références aux variables en fonction de leur
classe : variable locale ou variable globale.