Précédent Index Suivant

Chapitre 9 :   Procédures simples

On introduit donc ici les procédures simples, c'est-à-dire sans paramètres, sans déclarations locales, et non imbriquées. L'extension de PP1 ainsi construite se nomme PP5.

9.1   Grammaire et sémantique

Nous étendons la grammaire de PP1 par l'introduction d'une règle PROCS autorisant la définition de procédures :
PROGRAM ::= program ID ; BLOCK .
BLOCK ::= CONSTS VARS PROCS INSTS
PROCS ::= { proc ID ; INSTS ; }

On modifie également la règle INST pour inclure 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.

9.2   Extension du P-Code

Si un appel de procédure peut se voir comme un BRN (branchement inconditionnel) vers la première instruction de la procédure, le retour de procédure ne peut être un BRN car on ne connaît jamais à l'exécution le numéro de l'instruction (chez l'appelant) suivant l'appel. Plus précisément, ce numéro dépend de l'appel ; il peut y en avoir plusieurs dans un programme.

On introduit donc deux nouvelles instructions P-Code :
CAL i
empile le compteur d'instructions et réalise le branchement à l'instructioni

RET
dépile un numéro d'instruction et continue à ce numéro
On étend donc l'interpréteur P-Code (section 1.6 et figure 1.13) en conséquence : 
 with INST do
    case MNE of
       ...
       CAL : begin SP := SP + 1 ; MEM [SP] := PC ; PC := SUITE end ;
       RET : begin PC := MEM [SP] ; SP := SP - 1 end ;  
    end

9.3   Table des symboles

Les noms des procédures doivent être rangés dans la table des symboles. On ajoute une nouvelle classe, PROCEDURE (section 3.1). 
 type 
    CLASSES = (PROGRAMME, CONSTANTE, VARIABLE, PROCEDURE) ;
    CLASSET = set of CLASSES ;
À chacune des entrées de classe PROCEDURE de la table des symboles, on associe le nom de la procédure (champ ALFA) et le numéro de la première instruction P-Code générée pour cette procédure (champ ADRESSE).

9.4   Génération de code

La génération de code doit inclure la génération des différentes procédures. Après la génération de la première instruction de la procédure, il est nécessaire de mémoriser dans la table des symboles le numéro de cette instruction P-Code. à la fin de la procédure, on génère une instruction P-Code RET.

La génération pour une instruction PP5 d'appel de procédure consiste à rechercher le nom de la procédure dans la table des symboles et à générer l'instruction CAL <adresse>.

Deux remarques peuvent être faites sur la génération de code :

D'une part, les procédures sont traduites avant le programme principal. Le code généré pour un programme doit donc commencer par un saut inconditionnel vers le programme principal. On génère un BRN incomplet qui sera complété lorsqu'on va rencontrer le début du programme principal.

D'autre part, l'appel d'une procédure dans une procédure ne pose pas de problèmes particuliers. Il faut simplement que la procédure appelée soit définie avant la procédure appelante. Cette remarque peut être étendue à la récursivité (non croisée !) : une procédure peut s'appeler sans problèmes. Néanmoins, la récursivité de procédures sans paramètres ni déclarations locales n'est pas un outil très puissant.

9.5   Exemples

On donne ici deux exemples de programmes PP5 et leur traduction en P-Code.

9.5.1   Exemple simple

La compilation du programme PP5 (figure 9.1) 
 program UN ; 
 var A, B ; 
 proc MUL ; 
    begin 
       A := A * B 
    end ; 
 proc DEBUT ;
    begin 
       read (A) ; read (B) ;
       MUL
    end ; 
 begin
    DEBUT ; 
    write (A)  
 end.
Figure 9.1 : Exemple de code PP5 pour les appels de procédures.

utilise une table des symboles telles que celle-ci :
ALFA CLASSE ADRESSE
UN PROGRAM ---
A VARIABLE 0
B VARIABLE 1
MUL PROCEDURE 2
DEBUT PROCEDURE 10
pour produire le P-Code de la figure 9.2.
0   INT 2   réserve 2 emplacements pour A et B
1   BRN 16   saut au début du programme principal
2   LDA 0   début de la fonction MUL
3   LDA 0
4   LDV
5   LDA 1
6   LDV
7   MUL
8   STO
9   RET   fin de la fonction MUL
10   LDA 0   début de la fonction DEBUT
11   INN
12   LDA 1
13   INN
14   CAL 2   appel de la fonction MUL
15   RET   fin de la fonction DEBUT
16   CAL 9   début du programme principal (appel de la fonction DEBUT)
17   LDA 0
18   LDV
19   PRN
20   HLT   fin du programme principal

Figure 9.2 : Exemple de P-Code pour les appels de procédures.

9.5.2   Exemple récursif

Ce deuxième exemple de programme PP5 illustre les appels récursifs (figure 9.3). 
 program RECUR ; 
 var T, N ; 
 proc CALCUL ; 
    begin 
       read (N) ; 
       T := T * 10 + N ; 
       if N <> 0 then CALCUL
    end ; 
 begin
    T := 0 ; 
    CALCUL ; 
    write (T)   
 end.
Figure 9.3 : Exemple de code PP5 illustrant les appels récursifs de procédures.

La table des symboles utilisées lors de la compilation est la suivante :
ALFA CLASSE ADRESSE
RECUR PROGRAM ---
T VARIABLE 0
N VARIABLE 1
CALCUL PROCEDURE 2
Cette compilation produit le P-Code de la figure 9.4.
0   INT 2   réserve 2 emplacements pour T et N
1   BRN 20   saut au début du programme principal
2   LDA 1   début de la fonction CALCUL
3   INN
4   LDA 0
5   LDA 0
6   LDV
7   LDI 10
8   MUL
9   LDA 1
10   LDV
11   ADD
12   STO
13   LDA 1
14   LDV
15   LDI 0
16   NEQ
17   BZE 19
18   CAL 2   appel récursif à CALCUL
19   RET   fin de la fonction CALCUL
20   LDA 0   début du programme principal
21   LDI 0
22   STO
23   CAL 2   appel de CALCUL
24   LDA 0
25   LDV
26   PRN
27   HLT

Figure 9.4 : Exemple de P-Code pour les appels récursifs de procédures.

9.6   Travaux dirigés et travaux pratiques

  1. Modifier l'interpréteur de P-Code pour intégrer les instructions CAL et RET.

  2. Modifier les procédures TEST_ET_ENTRE et TEST_ET_CHERCHE de gestion de la table des symboles pour intégrer la gestion des entrées de type PROCEDURE.

  3. Implanter la compilation des procédures telles que définies dans ce chapitre. En particulier, écrire le code de la procédure PROCS, et modifier la procédure INST pour intégrer l'appel de procédure.
Précédent Index Suivant