Précédent Index Suivant

Chapitre 3 :   Analyse sémantique

Une fois le texte source reconnu syntaxiquement correct, il y a lieu de voir si le texte vérifie des règles non-exprimées par la syntaxe. C'est le rôle de l'analyse sémantique.

3.1   Table des symboles

Pour le langage PP1, cela consiste essentiellement à vérifier que les identificateurs utilisés sont bien déclarés. Pour cela, il est nécessaire de mémoriser les identificateurs déclarés pour tester la déclaration ou non des identificateurs utilisés. Cette mémorisation se fait dans une table des symboles.

Dans cette table, on associe à chaque entrée (chaque identificateur) toutes les informations connues sur lui, pour le moment : 
 type 
    TABLEINDEX = 1 .. INDEXMAX ; 
    CLASSES = (PROGRAMME, CONSTANTE, VARIABLE) ; 
    CLASSET = set of CLASSES ; 
 var  
    TABLESYM : array [TABLEINDEX] of record 
       NOM : ALFA ;
       CLASSE : CLASSES 
    end ; 
    DERNIERSYM : TABLEINDEX ; (* indice du dernier symbole entre *)
La table des symboles est manipulée par deux fonctions :
ENTRERSYM
ajoute le symbole SYM dans la table des symboles avec la classe passée en paramètre ; une version de base peut être la suivante : 
 procedure ENTRERSYM (C:CLASSES) ; 
 begin 
    if DERNIERSYM = INDEXMAX then ERREUR ; 
    DERNIERSYM := DERNIERSYM + 1 ;
    with TABLESYM [DERNIERSYM] do 
       begin NOM := SYM ; CLASSE := C end
 end ;
CHERCHERSYM
recherche l'identificateur SYM dans la table des symboles parmi les classes permises passées en paramètre et retourne l'index de l'entrée correspondante dans la table des symboles, ou s'arrête sur ERREUR ; on donne ici une version de base : 
 procedure CHERCHERSYM (var INDEX:TABLEINDEX ; PERMIS:CLASSET) ; 
 var FIN : booleen ;
 begin 
    INDEX := DERNIERSYM ; FIN := false ;
    while not FIN do begin 
       if INDEX = 0 then FIN := true
       else if TABLESYM [INDEX].NOM = SYM
          then FIN := true 
          else INDEX := INDEX - 1 
    end ; 
    if INDEX = 0 then ERREUR (* SYM absent *)
    else if not (TABLESYM[INDEX].CLASSE in PERMIS)
       then ERREUR ;  (* SYM pas de bonne classe *)  
 end ;

3.2   Entrée dans la table des symboles

La procédure ENTRERSYM est utilisée lors de la déclaration de symboles par l'intermédiaire d'une procédure TESTE_ET_ENTRE qui vérifie que le prochain token est celui attendu et qui met à jour la table des symboles : 
 procedure TESTE_ET_ENTRE (T:TOKENS ; C:CLASSES) ; 
 begin 
    if TOKEN = T then 
       begin
          ENTRERSYM (C) ; 
          NEXT_TOKEN 
       end
    else ERREUR 
 end ;
Cette fonction TESTE_ET_ENTRE est appelée lors de la déclaration de symboles ; c'est-à-dire dans les fonctions CONSTS, VARS et PROGRAM, par exemple : 
 procedure PROGRAM ; 
 begin 
    TESTE (PROGRAM_TOKEN) ; 
    TESTE_ET_ENTRE (ID_TOKEN, PROGRAMME) ; 
    TEST (PT_VIRG_TOKEN) ; 
    BLOCK ; 
    if TOKEN <> POINT_TOKEN then ERREUR 
 end ;

3.3   Consultation de la table des symboles

De manière symétrique, une procédure TESTE_ET_CHERCHE est une évolution de la procédure TESTE qui de plus recherche le symbole SYM dans la table des symboles par un appel à CHERCHESYM, l'index du symbole recherché dans la table des symboles est retourné par la variable PLACESYM : 
 var PLACESYM : TABLEINDEX ; 

 procedure TESTE_ET_CHERCHE (T:TOKENS; PERMIS:CLASSET) ;
 begin 
    if TOKEN = T then begin 
       CHERCHERSYM (PLACESYM, PERMIS) ; 
       NEXT_TOKEN ; 
    else ERREUR ; 
 end ;
Cette fonction est appelée lors de l'utilisation d'identificateur, c'est-à-dire par FACT, AFFEC, et LIRE. On a par exemple : 
 procedure AFFEC ; 
 begin 
    TESTE_ET_CHERCHE (ID_TOKEN, VARIABLE) ; 
    TESTE (AFFEC_TOKEN) ; 
    EXPR ; 
 end ; 

 procedure FACT ; 
 begin
    if TOKEN = ID_TOKEN 
       then TESTE_ET_CHERCHE (ID_TOKEN, [CONSTANTE, VARIABLE]) 
    else if TOKEN = NUM_TOKEN 
       then NEXT_TOKEN  
    else begin
       TESTE (PAR_OUV_TOKEN) ; 
       EXPR ; 
       TESTE (PAR_FER_TOKEN) ; 
    end
 end ;

3.4   Travaux dirigés et travaux pratiques

  1. Les versions proposées de ENTRERSYM et CHERCHERSYM ne tiennent pas compte des doubles déclarations. Comment prendre ces déclarations fautives en compte ?

    Serait-il imaginable d'accepter des déclarations telles que : 
     var A, B, A ;
    et telles que 
     const A = 3 ; 
 var A ;
  2. La recherche de symboles est telle que deux symboles de classes différentes ne peuvent avoir le même nom. Cette règle est-elle nécessaire ?

  3. Écrire l'analyseur sémantique de PP1. On testera que les identificateurs ne sont pas déclarés plusieurs fois.

  4. Il est intéressant de proposer à l'utilisateur la production d'une table des symboles. Cette option peut être activée par le passage d'un paramètre au compilateur, par exemple 
     pp1 -tablesymb
    ou par l'utilisation d'une directive de compilation incluse dans un commentaire : 
     (*$T+ *)
    pour l'activation de la production de la table des symboles, et 
     (*$T- *)
    pour la désactivation. Quelles sont les avantages de l'une et l'autre des méthodes. Sont-elles incompatibles ? Proposer une implantation.

  5. Il est possible d'imaginer que les identificateurs non déclarés doivent être traités comme des variables (déclaration implicite ; c'est le cas en Fortran) et mis dans la table des symboles au moment de leur première référence. Est-ce une bonne idée ? Comment l'implémenter ?

  6. La table des symboles proposée en exemple est une simple table. Il est possible d'implanter cette table par des arbres binaires de recherches ou d'aider la recherche par une table de hashage. Est-ce une bonne idée ? Quel problème pourrait survenir ?
Précédent Index Suivant