Précédent Index Suivant

Chapitre 6 :   Variables de type tableau

6.1   Grammaire et sémantique

On définit le langage PP2 comme une extension de PP1 autorisant la déclaration et la manipulation de tableaux simples. On modifie la règle VARS pour autoriser la déclaration de tableaux ;
VARS ::= var DECL { , DECL } ; | e
DECL ::= ID | ID [ NUM ]
Sémantiquement, cela permet la déclaration de tableaux d'entiers de dimension 1 dont la borne inférieure est toujours zéro et la borne supérieure est indiquée par la constante NUM (qui doit être strictement positive). Le nombre d'éléments est immédiatement calculé à partir de ces deux informations ; il n'existe pas de tableau à un élément.

On modifie les règles dans lesquelles figure le non-terminal ID (à savoir AFFEC, LIRE et FACT) pour autoriser la référence à un élément de tableau en introduisant une règle VAR :
VAR ::= ID | ID [ EXPR ]
AFFEC ::= VAR := EXPR
LIRE ::= read ( VAR { , VAR } )
FACT ::= VAR | NUM | ( EXPR )
Sémantiquement, une variable VAR doit toujours référencer une variable simple ou un élément de tableau. Cela revient à dire que les noms de tableaux sont obligatoirement indicés dans une instruction. (En particulier, l'affectation directe de tableau n'est pas permise.)

6.2   Table des symboles

Lors de l'analyse d'une déclaration, on mémorise dans la table des symboles la taille du tableau (nombre d'éléments). Pour les symboles dénotant des variables simples, on mettra une taille à 1 (il n'y a pas de conflits avec les tableaux, les tableaux d'un élément n'existant pas en PP2). 
 var
    TABLESYM : array [TABLEINDEX] of record 
       NOM : ALFA ;
       CLASSE : CLASSES ; 
       ADRESSE : integer ;
       TAILLE : integer 
    end ;
On modifie la procédure TESTE_ET_ENTRE pour mettre à jour cette table des symboles : 
 procedure TESTE_ET_ENTRE (T:TOKENS; C:CLASSES) ; 
 begin 
    if TOKEN = T 
    then if C <> VARIABLE 
       then begin ENTRERSYM (C) ; NEXT_TOKEN end 
       else ENTRERVARIABLE (C) 
    else ERREUR 
 end ;
La procédure ENTRERVARIABLE se charge de l'entrée dans la table des symboles d'une variable simple ou d'un tableau. 
 procedure ENTRERVARIABLE (C:CLASSES) ; 
 begin 
    if DERNIERSYM = INDEXMAX then ERREUR ; 
    DERNIERSYM := DERNIERSYM + 1 ; 
    with TABLESYM [DERNIERSYMB] do begin 
       NOM := SYM ; 
       CLASSE := C ; 
       TAILLE := 1 ; 
       ADRESSE := OFFSET
    end ; (* with *)
    NEXT_TOKEN ; 
    if TOKEN = CROCH_OUV_TOKEN then begin
       (* c'est un tableau *)
       NEXT_TOKEN ; 
       TESTE (NUM_TOKEN) ; 
       TESTE (CROCH_FER_TOKEN) ; 
       TABLESYM [DERNIERSYM]. TAILLE  := VAL + 1   
    end ; 
    OFFSET := OFFSET + TABLESYM [DERNIERSYM]. TAILLE   
 end ;

6.3   Génération de code

La génération de code pour accéder à un élément de tableau doit inclure la génération du code pour calculer l'adresse de cet élément. En effet, cette adresse ne peut être calculée à la compilation car l'élément accédé dépend de l'exécution.

Le code généré pour t [expression] doit permettre d'obtenir sur la pile l'adresse du (expression+ 1)ième élément du tableau t ; c'est-à-dire adresse (t) + expression !

Pour cela on doit générer le P-Code :
LDA adresse (t)
<code pour expression>
ADD
Donc, par exemple, pour l'affectation t [expression] := expr2, on génère:
LDA adresse (t)
<code pour expression>
ADD
<code pour expr2>
STO
D'où la modification de la procédure AFFEC : 
 procedure AFFEC ; 
 begin
    TESTE_ET_CHERCHE (ID_TOKEN, VARIABLE) ; 
    GENERER2 (LDA, TABLESYM [PLACESYM]. ADRESSE) ; 
    if TABLESYM [PLACESYM]. TAILLE > 1
       then begin
       (* On a un tableau, il faut un [ *)
          TESTE (CROCH_OUV_TOKEN) ; 
          EXPR ; 
          TESTE (CROCH_FER_TOKEN) ; 
          GENERER1 (ADD) ; 
       end ; 
    TESTE (AFFEC_TOKEN) ; 
    EXPR ; 
    GENERER1 (STO) 
 end ;
On modifie de même les procédures FACT et LIRE qui sont les seules à référencer des noms de tableaux.

6.4   Travaux dirigés et travaux pratiques

  1. Modifier le compilateur pp1 (qui devient pp2) pour autoriser la manipulation de tableaux simples.

  2. Modifier la grammaire de PP2 pour autoriser l'utilisation de constantes dans la déclaration de tableaux ; par exemple : 
     program tab_const ;
 const TAILLE = 64 ; 
 var tab [ TAILLE ] ;
    Prendre cette nouvelle grammaire en compte pour modifier le compilateur pp2.

    Il est aussi possible d'autoriser les tailles à être des expressions simples et évaluables à la compilation formées à base de constantes déclarées et/ou de littéraux. Qu'en pensez-vous. Comment l'implémenter ? (Se reporter à l'exercice 2.)

  3. Lors de l'accès à un élément de tableau, on génère le code nécessaire au calcul de son adresse car, de manière générale, celle-ci ne peut pas être définie à la compilation. Cependant, dans certains cas, il est possible de déterminer cette adresse dès la compilation. Il n'est donc plus nécessaire de générer un tel code. Quels sont les cas où cela est possible ? Comment prendre en compte cette optimisation dans le compilateur pp2 ?

  4. On aurait pu étendre la syntaxe de PP1 de la manière suivante :
    VARS ::= var DECL { , DECL } ; | e
    DECL ::= ID | ID [ NUM ] | ID [ NUM .. NUM ]
    Cela permet la déclaration de tableaux d'entiers indicés par un intervalle de valeurs.
    1. Que doit-on mémoriser dans la table des symboles ?
    2. Réécrire les procédures ENTRERVARIABLE et AFFEC pour de tels tableaux.

  5. On peut généraliser la manipulation de tableaux à la manipulation de tableaux à plusieurs dimensions.
    1. Proposer une syntaxe pour de tels tableaux.

    2. Quelle est la structure en mémoire pour de tels tableaux ? Comment obtient-on l'adresse d'un élément d'un tel tableau ?

    3. Quelles informations doivent donc être rangées dans la table des symboles lors de la déclaration d'un tableau multi-dimensionnel ?

  6. Lors de l'utilisation des tableaux de dimension 1 décrits dans ce chapitre, on ne se soucie pas d'éventuels débordements d'indices. Faites en sorte que cette erreur soit signalée. Dans certains cas on peut signaler l'erreur dès la compilation ; envisagez aussi cette solution (cf. l'exercice 3 ci-dessus).

    Dans le cas général, lorsque l'on dispose de la valeur de l'indice d'un tableau sur la pile, il est nécessaire de comparer cette valeur avec la borne supérieure du tableau et de laisser cette valeur sur la pile pour la suite du traitement. Comment réaliser cette opération en P-Code ? Est-il imaginable d'étendre le P-Code par une instruction appropriée ?

    En cas d'erreur pour débordement, on s'arrêtera sur une instruction P-Code d'arrêt sur erreur OOB (out of bounds).

  7. Il est possible d'étendre la grammaire de PP2 pour autoriser l'affectation directe entre tableaux de même taille. Pour permettre cette affectation entre tableau, on introduit une nouvelle instruction P-Code :
    MOV n
    Cette instruction attend deux adresses sur la pile (a1 au sous-sommet et a2 au sommet) et réalise la recopie de n valeurs lues à partir de l'adresse a2 dans les adresses successives à partir de a1.
Précédent Index Suivant