Grammaire et sémantique
Table des symboles
Génération de code
Travaux dirigés et travaux pratiques

Chapitre 8 : Définition de types

8.1 Grammaire et sémantique

8.1.1 Définition et utilisation de types

On définit le langage PP4 comme une extension de PP1 incluant la définition de types. On modifie la grammaire de PP1

`VARS`	`::=`	`var DECL { ; DECL } ;`
`DECL`	`::=`	`ID { , ID } : TYPE`
`TYPE`	`::=`	`ID \| int`

Les ID de TYPE doivent correspondre à un type déclaré précédemment :

`BLOCK`	`::=`	`CONSTS TYPES VARS INSTS`
`TYPES`	`::=`	`type TYPEDECL ; { TYPEDECL ; } \|` `e`
`TYPEDECL`	`::=`	`ID = array [ CONST ] of TYPE`
	`\|`	`ID = record CHAMPS { ; CHAMPS } end`
`CHAMPS`	`::=`	`ID { , ID } : TYPE`
`CONST`	`::=`	`ID \| NUM`

Cela permet la définition de types à partir des types de bases. Ces types sont utilisés pour la définition d'autres types et pour la déclaration de variables.

Sémantiquement, les types utilisés doivent être préalablement déclarés.

Les tableaux sont des tableaux à une dimension ¹ de taille constante indiquée par la constante CONST représentant une valeur immédiate ou le nom d'une constante précédemment déclarée.

8.1.2 Exemple

Définition d'une pile de complexes :

 const 
    TAILLE = 100 ; 
 type
    COMPLEX = record 
       RE, IM : int 
    end ; 
    COMPLEXTAB = array [ TAILLE ] of COMPLEX ;
    COMPLEXPILE = record 
       SOMMET : int ;
       PILE : COMPLEXTAB 
    end ;
 var 
    MAPILE : COMPLEXPILE ;

8.1.3 Utilisation des variables de types complexes

On modifie les règles de la grammaire de PP1 dans lesquelles figure le non-terminal ID pour autoriser la référence aux champs des enregistrements et aux éléments des tableaux :

`AFFEC`	`::=`	`VAR := EXPR`
`LIRE`	`::=`	`read ( VAR { , VAR } )`
`FACT`	`::=`	`VAR \| NUM \| ( EXPR )`

Le non-terminal VAR doit référencer une variable scalaire :

`VAR`	`::=`	`ID`
	`\|`	`VAR . ID`
	`\|`	`VAR [ EXPR ]`

La notation . accède à un champ d'une structure ; la notation [ ] à un élément d'un tableau.

8.2 Table des symboles

Pour mémoriser les informations contenues dans de telles déclarations de types, le compilateur ne peut plus se contenter d'une table des symboles aussi simple que précédemment. Il est nécessaire de construire une table des symboles qui reflète la structure du type construit ; les déclarations de types pour une telle table des symboles sont données à la figure 8.1.

 type 
    TYPEPT = ^TIPE ; 
    IDPT = ^IDENTIFICATEUR ;
 
    TYPECLASSES = (SCALAIRE, TABLEAU, ENREGISTREMENT) ;
    TIPE = 
       record
          TAILLE : integer ; 
          case CLASSE : TYPECLASSES of 
             SCALAIRE : (
                NOM : IDPT
                ) ;    
             TABLEAU : ( 
                TYPEELT : TYPEPT  
                ) ;    
             ENREGISTREMENT : (
                LISTECHAMPS : IDPT 
                )     
       end;
       
    IDCLASSES = (TYPECL, CONSTANTE, VARIABLE) ;
    IDENTIFICATEUR = 
       record
          NOM : ALFA ;
          GLIEN, DLIEN, SUIVANT : IDPT ;
          IDTYPE : TYPEPT ; 
          case CLASSE : IDCALSSES of 
             TYPECL : () ;
             CONSTANTE : (
                VALEUR : integer
                ) ;
             VARIABLE : (
                ADRESSE : integer 
                )    
       end ;

Figure 8.1 : Déclarations de types pour la table des symboles.

La déclaration de la pile de complexes définie à la section 8.1.2 créerait une structure de données interne au compilateur telle celle décrite à la figure 8.2.

La table des symboles est une liste de noeuds de type IDENTIFICATEUR ; la liste est chaînée par les champs GLIEN et DLIEN (liens droit et gauche).

Chaque IDENTIFICATEUR correspond au nom d'un type (TYPECL), d'une constante (CONSTANTE), ou d'une variable (VARIABLE) ; ce nom est contenu dans le champ NOM.

Le champ IDTYPE indique le type de l'objet. Pour une constante, on stocke sa valeur (VALEUR); pour une variable son adresse d'allocation dans la pile ² si l'objet est un objet de premier niveau (déclaré en temps que variable dans le programme); si l'objet est un champ de structure, on stocke son adresse relative au début de l'enregistrement le contenant ³.

Un type est représenté par un noeud de type TIPE. Un type est SCALAIRE, TABLEAU, ou ENREGISTREMENT. Le champ TAILLE contient le nombre d'éléments d'un tableau, 1 pour un scalaire, la somme de la taille des champs du type pour un enregistrement.

Pour un scalaire, on stocke son NOM (ici uniquement int). Pour un tableau, on stocke le type de ses éléments (TYPEELT). Pour un enregistrement, on établit une liste chaînée de ses champs (LISTECHAMPS) qui sont des noeuds de type IDENTIFICATEUR reliés par le champ SUIVANT. Le champ ADRESSE est alors l'adresse relative du champ dans l'enregistrement.

Figure 8.2 : Structure de la table des symboles pour la pile de complexes.

8.3 Génération de code

La génération de code doit prendre en compte la structure ainsi définie pour accéder aux différents éléments des objets du type.

Par exemple, lorsque le programmeur écrit

 MAPILE. PILE [MAPILE. SOMMET]. IM

le compilateur doit générer le code calculant l'adresse de cette partie imaginaire du complexe en sommet de pile, et cela à partir de l'adresse de base de MAPILE et de la valeur de MAPILE. SOMMET, cette dernière n'étant pas connue avant l'exécution. Le code de la figure 8.3 réalise un tel adressage.

1 LDA 0 empile l'adresse de base de MAPILE

2 LDA 1 empile l'adresse relative de PILE/MAPILE

3 ADD ® adresse de base de MAPILE. PILE

4 LDA 0 empile l'adresse de base de MAPILE

5 LDA 0 empile l'adresse relative de SOMMET/MAPILE

6 ADD ® adresse de MAPILE. SOMMET

7 LDV ® valeur de MAPILE. SOMMET

8 LDI 1 |

9 SUB | enleve 1 pour l'indicage

10 LDI 2 empile la taille des elements de MAPILE. PILE

11 MUL ®deplacement pour acceder MAPILE. PILE [MAPILE. SOMMET]

12 ADD ® adresse de MAPILE. PILE [MAPILE. SOMMET]

13 LDA 1 empile l'adresse relative de IM/COMPLEX

14 ADD ® adresse de MAPILE. PILE [MAPILE. SOMMET]. IM

Figure 8.3 : P-code pour accéder à MAPILE. PILE [MAPILE. SOMMET]. IM.

Il apparaît que le code généré peut être long et donc coûteux en temps d'exécution. Des langages offrent la possibilité de << factoriser >> ce calcul d'adresse. C'est le cas de l'instruction with de Pascal :

 with MAPILE. PILE [MAPILE. SOMMET] do 
    begin
       RE := ...  
       IM := ... 
    end ;

Les douze premières instructions du P-Code de la figure 8.3 ne sont générées qu'une fois, l'adresse obtenue est utilisée pour chacun des accès à RE et IM.

8.4 Travaux dirigés et travaux pratiques

La table des symboles est représentée par une liste doublement chaînée : liens DLIEN et GLIEN (figures 8.1 et 8.2). Quelle est l'utilité d'un tel double chaînage ?
Modifier la grammaire de PP1 pour accepter les définitions de types introduites ici. Prendre en compte cette nouvelle grammaire pour l'écriture de l'analyseur syntaxique de pp4. Implanter la gestion de la table des symboles et la modification des règles sémantiques. Modifier la gestion des erreurs en conséquence. Prendre en compte les accès aux éléments de structure et de tableaux lors de la génération de code.
La grammaire proposée pour PP4 oblige la déclaration préalable d'un type nommé à chaque niveau. Pascal accepte aussi des déclarations de types << anonymes >>; par exemple la déclaration
```
 var 
    MAPILE : record
       SOMMET : int ; 
       PILE : array [TAILLE] of record 
          RE, IM : int 
       end 
    end ; 
```
Proposer une grammaire pour une telle déclaration. Modifier pp5 en conséquence.
Soient les déclarations
```
 type 
    LISTS : array [10] of int ; 
 var 
    X : LISTS ; 
    A : array [10] of int ; 
    B : array [10] of int ; 
    Y : LISTS ; 
```
Il peut sembler évident que les deux variables A et B soient de même type, et même que X et Y soient de même type que A et B. Cependant, cette équivalence, nommée équivalence structurelle de types, n'est pas facile à contrôler. L'équivalence nominale de types reconnaît uniquement les variables X et Y comme ayant le même type. Cette équivalence nominale est facile à vérifier : deux objets sont nominalement équivalent si leurs champs IDTYPE référence un même noeud TIPE⁴.

Cette notion d'équivalence est primordiale si l'on désire autoriser l'affectation directe de structures complexes (enregistrements ou tableaux)⁵
1. Implanter ces affectations en considérant uniquement les affectations entre objets nominalement équivalents comme valides ;
2. Qu'en est-il des variables A et B d'une déclaration
```
 var 
    A, B : array [10] of int ; 
```
3. Considérer maintenant l'équivalence structurelle des types.
D'autres constructeurs de types sont proposés en Pascal ; considérons les intervalles :
```
 const 
    TAILLE = 100 ; 
 type 
    INDICE = 1 .. TAILLE ; 
    TAB = array [INDICE] of int ; 
```
Y a-t-il une difficulté majeure à leur implantation dans pp5 ? Quelle garantie peut attendre le programmeur de leur utilisation ? Comment assurer cette garantie ?

Ces types sont parfois critiqués car ils mènent à des ambiguïtés. Par exemple, une valeur 34 peut être de type 0..45 et aussi 30..90. Comment contrer cette objection ?
Pascal propose des enregistrements avec variantes. Quel est l'avantage d'une telle construction. Considérer l'allocation de ces enregistrements.
Les ensembles.
Pourquoi Pascal n'oblige-t-il pas la définition d'un type à apparaître avant la définition du type pointeur vers ce type ?

Comment ces définitions peuvent-elles être prises en compte ? Comment construire la table des symboles ?
Comment implanter l'instruction with de Pascal (se référer à la section 8.3).
Proposer une implantation des tableaux de taille dynamique. Ces tableaux sont explicitement alloués et désalloués par le programmeur ; par exemple :
```
 var 
    TAB : array [dynamic] of int ; 
    I : int ; 
    
    read (I) ; 
    allocate (TAB, I) ; 
    ...
    desallocate (TAB) ;
```
Il peut être intéressant d'associer un << entête >> à chaque tableau dynamique. Quelles contraintes doivent vérifier l'allocation de tels tableaux ?

1: Cependant il est possible de manipuler des tableaux de plusieurs dimensions par la déclaration de tableaux de tableaux...
2: Cette adresse est déterminée par le compilateur lors de l'allocation des variables.
3: Cette adresse est déterminée par la taille des champs précédant le champ en question dans la structure.
4: On notera, en particulier sur l'exemple, que le noeud correspondant au type prédéfini scalaire entier n'existe qu'en un exemplaire référencé par les différents IDENTIFICATEURs de ce type.
5: Se reporter à l'exercice 7pour les problèmes liés à de telles affectations.