Chapitre 11 : Procédures imbriquées
On introduit donc ici les procédures imbriquées ; la version
ainsi modifiée de PP6 s'appelle PP7.
11.1 Grammaire et sémantique
La grammaire de PP6 est modifiée de la manière suivante :
|
PROGRAM |
|
::= |
|
program ID ; BLOCK . |
|
|
BLOCK |
|
::= |
|
CONSTS VARS PROCS INSTS |
|
|
PROCS |
|
::= |
|
{ proc ID ; BLOCK ; } |
|
Les procédures peuvent maintenant être imbriquées.
Sémantiquement, la règle de visibilité est définie comme suit
: une déclaration locale n'est visible que dans le bloc qui la
déclare et les blocs englobés dans celui-ci.
11.2 Accès aux variables
Il est donc nécessaire de gérer la table des symboles en pile :
| |
|---------------|
| | declarations du bloc en cours
| | d'analyse
| |
|---------------|
| | declarations du bloc englobant
| |
|---------------|
| |
| |
| | declarations globales
| |
| |
| |
+---------------+
De plus, on associe à chaque entrée de la table des symboles le
niveau de la déclaration (dans un champ NIVEAU) :
+---------------+
| niv0 |
| +-----------+ |
| | niv1 | |
| | | |
| | +-------+ | |
| | | niv2 | | |
| | | | | |
| | | | | |
| | +-------+ | |
| +-----------+ |
| |
| +-----------+ |
| | niv1 | |
| | | |
| | | |
| +-----------+ |
+---------------+
L'accès aux variables est donc différent selon leur niveau :
-
Si le numéro de niveau est 0, la variable est une variable
globale. On y accède par un
LDA i.
- Si le numéro de niveau est le numéro du niveau courant, la
variable est locale à la procédure en cours. On y accède par une
instruction
LDL i.
- Si le numéro du niveau est différent de zéro et du niveau
courant. De combien de zones faut-il descendre pour trouver la
variable ?
En solution à ce problème, la première idée peut être : il
faut descendre de nc - nv (nc : niveau courant, nv : niveau de
la variable). C'est une idée fausse ; nous allons détailler
l'accès à une telle variable sur un exemple.
Tout d'abord quelques éléments de réponse :
Il est impossible de connaître lors de la compilation l'adresse
d'une telle variable. Par exemple, à cause de la récursivité.
D'autre part, les niveaux de procédures empilés sur la pile sont
croissants, mais pas strictement croissants.
Regardons sur l'exemple suivant : on considère le
programme de la figure 11.1
program X ; (* niveau 0 *)
var A; (* niveau 0 *)
proc Y ; (* niveau 0 *)
var B ; (* niveau 1 *)
proc Y1 ; (* niveau 1 *)
var C ; (* niveau 2 *)
begin
C := B + A
end ;
proc Y2 ;
var B ;
begin
Y1
end ;
begin
Y2
end ;
begin
Y
end .
Figure 11.1 : Exemple d'imbrication des niveaux dans un programme PP7.
et l'accès à A, C et B dans l'instruction C := B + A
au cours de l'analyse de Y1 (niveau 2) ; on a la table des symboles
suivante :
| ALPHA |
CLASSE |
ADRESSE |
NIVEAU |
| C |
VARIABLE |
0 |
2 |
| Y1 |
PROCEDURE |
adr2 |
1 |
| B |
VARIABLE |
0 |
1 |
| Y |
PROCEDURE |
adr1 |
0 |
| A |
VARIABLE |
0 |
0 |
| X |
PROGRAMME |
--- |
0 |
Comme le niveau de A est 0, on génère un LDA 0. Comme le
niveau de C est égal au niveau courant, on génère un
LDL 0.
à l'exécution, l'état de la pile sera celui de la figure 11.2.
| |
|----------|
| C | |
|----------| |
+-----------|----- | |-- appel de Y1 (n1)
| |----------| |
| | AR | |
| |==========|
| | B | |
| |----------| |
| +---------|----- | |-- appel de Y2 (n1)
| | |----------| |
+-|-------->| AR | |
| |==========|
c'est ce B la qui ----> | | B | |
doit etre accede | |----------| |
| +-------|----- | |-- appel de Y (n0)
| | |----------| |
+-|------>| AR | |
| |==========|
| | A | |-- globale (n0)
+------>+----------+
Figure 11.2 : État de la pile lors de l'exécution de
C := B + A
dans le programme de la figure
11.1.
Le B qui doit être accédé est celui de Y, il est donc
nécessaire de descendre de 2 zones (ce qui est différent de la
différence des niveaux de déclaration : 2-1 = 1)
Pour ce faire, on va chaîner (par un lien dit statique),
à l'exécution, les positions de la pile qui correspondent à un
niveau de déclaration. Dans ce cas, la différence de niveau
correspond bien au nombre de liens statiques qu'il faut parcourir (en
descendant dans la pile) pour accéder à la zone voulue.
On introduit donc une modification de l'instruction P-Code LDI :
LDL i n
Les paramètres sont i, l'adresse relative au début de la zone,
et n, le nombre de liens statiques à parcourir pour accéder à
cette zone. Remarquons que ces deux paramètres sont calculables à
la compilation.
L'ancienne version de LDL i est équivalente à LDL i 0.
On reprend l'exemple de la figure 11.1.
La pile de la figure 11.3
indique les liens de chaînage dynamique et les liens de
chaînage statique sur la pile.
| |
|----------|
| C |
|----------|
| ------|---------+
|----------| |
+-----------|----- | |
| |----------| |
| | AR | |
| |==========| |
| | B | |
| |----------| |
| | ------|---------+
| |----------| |
| +---------|----- | |
chainage | | |----------| | chainage
dynamique +-|-------->| AR | | statique
| |==========| |
| | B | |
| |----------| |
| | ------|-----+ |
| |----------| | |
| +-------|----- | | |
| | |----------| | |
+-|------>| AR |<----|---+
| |==========| |
| | A | |
+------>+----------+<----+
Figure 11.3 : Liens de chaînage statique et dynamique dans la pile.
Le P-Code généré est donné à la figure 11.4.
|
0 |
|
|
|
BRN 17 |
|
|
|
|
|
|
1 |
|
|
|
BRN 14 |
|
|
2 |
|
|
|
INT 1 |
|
|
3 |
|
|
|
LDL 0 0 |
|
|
|
accès à C de Y1 |
|
|
4 |
|
|
|
LDL 0 1 |
|
|
|
accès à B de Y |
|
|
5 |
|
|
|
LDV |
|
|
6 |
|
|
|
LDA 0 |
|
|
|
accès à A de X |
|
|
7 |
|
|
|
LDV |
|
|
8 |
|
|
|
ADD |
|
|
9 |
|
|
|
STO |
|
|
10 |
|
|
|
RET |
|
|
11 |
|
|
|
INT 1 |
|
|
12 |
|
|
|
CAL 2 |
|
|
13 |
|
|
|
RET |
|
|
14 |
|
|
|
INT 1 |
|
|
15 |
|
|
|
CAL 11 |
|
|
16 |
|
|
|
RET |
|
|
17 |
|
|
|
INT 1 |
|
|
18 |
|
|
|
CAL 1 |
|
|
19 |
|
|
|
HLT |
|
Figure 11.4 : P-Code généré pour le programme de la
figure
11.1.
11.3 Travaux dirigés et travaux pratiques
-
Modifier l'interprétation de l'instruction
LDL pour prendre en
compte les deux paramètres. (Cela peut amener des changements dans le
format des sources P-Code, les instructions acceptaient auparavant au
plus un paramètre).
- Intégrer la gestion du niveau dans les procédures de
génération de code. On introduit une variable globale
NIVEAU qui contient le numéro du niveau courant. Cette
variable NIVEAU est utilisée lors de l'entrée dans la table
des symboles.
- Modifier les procédures de génération de l'accès à une
variable (c'est-à-dire
AFFEC, LIRE, et FACT)
en fonction du niveau courant et du niveau de la variable.