Chapitre 7 : Variables de type enregistrement
7.1 Grammaire et sémantique
On définit le langage PP3 comme une (nouvelle) extension de PP1
autorisant la déclaration et la manipulation de structures
(enregistrements) simples ; on abandonne donc temporairement les
tableaux. On modifie la règle VARS pour autoriser la déclaration de structures ;
|
VARS |
|
::= |
|
var DECLS ; | e |
|
|
DECLS |
|
::= |
|
DECL {, DECL} |
|
|
DECL |
|
::= |
|
ID | ID ( DECLS ) |
|
Sémantiquement, cela permet la déclaration de structures
composées d'enregistrements qui sont eux-mêmes soit des variables
simples, soit des structures.
Par exemple,
var A, B (C, D), E, F (A, B (C, D)) ;
définit deux variables simples A et E, et deux variables
structures B et F. La structure B déclare deux variables
entières simples tandis que l'enregistrement F déclare une
variable simple et un enregistrement de deux variables.
On modifie les règles dans lesquelles figure le non-terminal ID
(à savoir AFFEC, LIRE et FACT) pour autoriser la
référence à un champ d'enregistrement par une notation pointée
(règle VAR) :
|
VAR |
|
::= |
|
ID {. ID} |
|
|
AFFEC |
|
::= |
|
VAR := EXPR |
|
|
LIRE |
|
::= |
|
read ( VAR { , VAR } ) |
|
|
FACT |
|
::= |
|
VAR | NUM | ( EXPR ) |
|
Sémantiquement, une variable VAR doit toujours référencer une
variable simple ; en particulier, les affectations directes entre
structures ne sont pas permises.
7.2 Table des symboles
Les déclarations sont des arbres. Aussi, on les mémorisera
dans la table des symboles sous forme d'arbres. Pour faciliter
l'implantation dans la table des symboles, on associe à chaque
variable un lien horizontal et un lien vertical. Le lien horizontal
référence un frère dans la déclaration, le lien vertical
référence le fils aîné. La
figure 7.1 est une représentation de
l'exemple de déclaration donné ci-dessus.
A ---> B --------------> E ---> F ---> *
| | | |
V V V V
* C ---> D ---> * * A ---> B ---> *
| | | |
V V V V
* * * C ---> D ---> *
| |
V V
* *
Figure 7.1 : Représentation d'une déclaration d'enregistrements.
On remarque que les feuilles n'ont pas de lien vertical. On code cette
structure dans la table des symboles par l'ajout de deux champs LV
et LH.
var
TABLESYM : array [TABLEINDEX] of record
NOM : ALFA ;
CLASSE : CLASSES ;
ADRESSE : integer ;
LV : integer ;
LH : integer
end ;
On prend comme convention que le champ ADRESSE représente un
déplacement par rapport à l'adresse du père dans l'arbre et
représente une adresse absolue (en fait relative à 0 !) pour le
premier niveau de déclaration (dont les variables simples).
Pour l'exemple
var A, B (C, D), E, F (A, B (C, D)) ;
on aura la table des symboles de la figure 7.2.
| |
NOM |
ADRESSE |
LH |
LV |
| 0 |
A |
0 |
1 |
* |
| 1 |
B |
1 |
4 |
2 |
| 2 |
C |
0 |
3 |
* |
| 3 |
D |
1 |
* |
* |
| 4 |
E |
3 |
5 |
* |
| 5 |
F |
4 |
* |
6 |
| 6 |
A |
0 |
7 |
* |
| 7 |
B |
1 |
* |
8 |
| 8 |
C |
0 |
9 |
* |
| 9 |
D |
1 |
* |
* |
Figure 7.2 : Table des symboles pour une déclaration d'enregistrements.
Dans cette table, une * signifie qu'un lien est terminal. On le
codera par une valeur invalide, par exemple -1. La déclaration de
l'exemple nécessite une allocation de 7 entiers (variable
OFFSET).
Il faut écrire les deux procédures d'analyse des déclarations
DECLS et DECL. Ces procédures retournent par un paramètre
BASE l'adresse dans la table des symboles de la première entrée
analysée. Cette adresse est utilisée pour rattacher la
déclaration à son père dans l'arbre. Le code des deux
procédures est donné aux figures 7.4
et 7.3.
procedure DECLS (var BASE:integer) ;
var START : integer ; TBASE : integer ;
begin
START := DERNIERSYMB ;
DECL (TBASE) ;
while TOKEN = VIRG_TOKEN do
begin
NEXT_TOKEN ;
DECL (TBASE)
end ;
TABLESYM [TBASE]. LH := -1 ; (* fin du niveau de declaration *)
BASE := START
end ;
Figure 7.3 : Procédure DECLS, analyse de déclarations d'enregistrements.
procedure DECL (var BASE:integer) ;
var START : integer ; OLD_OFFSET : integer ;
begin
if DERNIERSYM = INDEXMAX then ERREUR ;
START := DERNIERSYMB ;
DERNIERSYMB := DERNIERSYMB + 1 ;
if TOKEN <> ID_TOKEN then ERREUR ;
with TABLESYM [START] do begin
NOM := SYM ;
CLASSE := VARIABLE ;
ADRESSE := OFFSET ;
LH := -1 ; (* provisoirement *)
LV := -1 (* provisoirement *)
end ;
NEXT\_TOKEN ;
if TOKEN = PAR_OUV_TOKEN then begin
(* les offset sont comptes a partir du pere *)
OLD_OFFSET := OFFSET ; OFFSET := 0 ;
NEXT_TOKEN ;
DECLS (TABLESYM [START]. LV) ;
if TOKEN <> PAR_FER_TOKEN then ERREUR
else NEXT_TOKEN ;
OFFSET := OLD_OFFSET + OFFSET
end else
OFFSET := OFFSET + 1 ;
TABLESYM [START]. LH := DERNIERSYMB ;
BASE := START
end ;
Figure 7.4 : Procédure DECL, analyse de déclarations d'enregistrements.
7.3 Génération de code
La génération de code pour accéder à un champ de structure
utilise l'adresse de ce champ. Cette adresse peut être définie
lors de la compilation. Étant donnée la manière dont on a construit
la table des symboles, pour obtenir l'adresse d'une variable il suffit
d'additionner les champs ADRESSE des ID rencontrés.
On utilisera la procédure CHERCHERSYM modifiée :
procedure CHERCHERSYM (var INDEX: TABLEINDEX ;
PERMIS: CLASSET ;
DEBUT: TABLEINDEX) ;
Le paramètre DEBUT indique l'entrée dans la table des symboles
à partir de laquelle rechercher le symbole en suivant les liens
LH. Comme par le passé, cette procédure retourne dans son
premier paramètre INDEX l'indice dans la table des symboles du
symbole trouvé.
On écrit ensuite la procédure VAR d'analyse d'une variable qui
laisse sur la pile P-Code l'adresse de la variable :
procedure VAR ;
var BASE : integer ; ADR : integer ;
begin
if TOKEN <> ID_TOKEN then ERREUR ;
else NEXT_TOKEN ;
CHERCHERSYM (INDEX, [VARIABLE], 0) ; (* niveau 0 *)
ADR := TABLESYM [INDEX]. ADRESSE ;
while TOKEN = PT_TOKEN do
begin
NEXT_TOKEN ;
if TOKEN <> ID_TOKEN then ERREUR
else NEXT_TOKEN ;
CHERCHESYM (INDEX, [VARIABLE], INDEX) ;
ADR := ADR + TABLESYM [INDEX]. ADRESSE
end ;
GENERER2 (LDA, ADR)
end ;
Cette procédure est appelée par les trois procédures
FACT,
AFFEC, et
LIRE
que l'on modifiera en conséquence.
7.4 Travaux dirigés et travaux pratiques
-
Construire le compilateur
pp3 comme une modification de pp1
implantant la manipulation d'enregistrements telle qu'elle est
décrite dans ce chapitre. On veillera de plus à modifier la
production de la table des symboles
(exercice 4).
- Les procédures
DECL et DECLS données dans ce chapitre ne
testent pas la présence éventuelle de doubles déclarations.
Quelle information doit passer entre ces procédures pour
détecter de telles déclarations. Implanter ce mécanisme de
détection des déclarations fautives.
- La manipulation d'enregistrements peut être la source d'autres
erreurs. Dresser une liste de ces erreurs et en ajouter la
détection dans le compilateur.
Modifier le code de recouvrement d'erreurs pour l'étendre au langage
PP3.
De nouveaux cas de figures de corrections d'erreurs
apparaissent-ils ? Les prendre en compte.