Bonjour.

Je voudrais comprendre le fonctionnement de la fameuse table des symboles, utilisée dans les compilateurs afin d'y insérer des informations concernant les identifieurs du code source (informations que l'on récupérera plus tard dans le processus de compilation, afin d'analyser, et on s'en sert même pour la génération du code!).

Est-ce qu'il y a plusieurs tables de symboles ? J'ai imaginé ça : 

plusieurs tables de symboles :

	- table de symboles globale, qui ne s'efface pas (on peut
	  y retirer des variables, mais pas question d'erase la
          table en entier) et qui va contenir tous les noms des
          variables et leurs attributs (nom, taille, type, etc...)

	- table de symboles spécifique à chaque fonction, qui s'efface
	  entièrement à l'instruction "end" qui indique la fin de
          la structure de contrôle de la fonction (les changements
	  faits sur les autres tables de symboles pendant l'exécution
          de la structure de contrôle persistent)

Bien sur, j'ai lu plein de cours PDF, etc... Sur les tables des symboles, mais je n'arrive toujours pas à comprendre ce schéma :

Commence-t-on par les blocs les plus "internes" ou par les blocs les plus "externes" ?

Pour exemple, dans le code 

func main() {


   var c = "hey"

   if c == "hey" {
     var c = "hey2"
     print(c)
   }

}

^ Dans cet exemple, on commence à mettre les identifieurs dans la table à partir de quand ? À partir du bloc le plus externe ? C'est à dire, la fonction "main" ?

Merci pour votre aide ! (source de l'image : http://coursenligne.insa-rouen.fr/UNIT-CoursDeCompilation/Theme04/support_web_theme04/)

-
Edité par JomtekYT1 8 septembre 2018 à 0:32:20

Salut,

une table de symbole, c'est juste un moyen de structurer les données. Une sorte d'AST, mais spécifique au type d'expression.

Par exemple :

int My_Var = 8;

Le compilateur scannera cette expression, et l'ajoutera à la table de symbole adéquat, sous une forme proche de ;

| name |  type  | value |
'My_Var'  'int'    '8'

Généralement, on utilise une classe spécifique pour chaque type d'expression. Il peut y en avoir des centaines.

Pour une variable, cela pourrait ressembler à ceci en C++ :

namespace Parser {
  enum Type { INT, CHAR, LONG, DOUBLE, FLOAT };
  namespace Expression {
    class Variable_Decl {
      private:
        struct table {
          std::string name;
          Type type;
          std::string value;
        };
      std::vector<table> AllVariablesDecl;
 
      table &GetVarByName(std::string name) {
        for (size_t i = 0; i < AllVariablesDecl.size(); ++i)
          if (AllVariablesDecl[i].name == name) return AllVariablesDecl[i];
        throw std::range_error("Unknown variable called '" + name.c_str() + "'");
      }
 
      public:
        void append(std::string name, Type type, std::string value) {
          AllVariablesDecl.push_back({ name, type, value });
        }
        bool AlreadyExists(std::string name) {
          for (auto item : AllVariablesDecl)
            if (item.name == name) return true;
          return false;
        }
        void EraseVariable(std::string name) {
          for (size_t i = 0; i < AllVariablesDecl.size(); ++i) {
            if (AllVariablesDecl[i].name == name) {
              AllVariablesDecl.erase(AllVariablesDecl.begin() + i);
              return;
            }
          }
        }
        void ModifyVariableValue(std::string name, std::string NewValue) {
          GetVarByName(name).value = NewValue;
        }
    };
  }
}
 
...
 
/*
  int MyVar = 8;
  MyVar = 10;
*/
 
Parser::Expression::Variable_Decl variables;        // On déclare une "table" propre aux variables
variables.append("MyVar", Parser::Type::INT, "8");    // On ajoute la variable 'MyVar'
variables.ModifyVariableValue("MyVar", "10");       // On modifie la variable 'MyVar'
// on change de block, 'MyVar' est donc détruit :
variables.EraseVariable("MyVar");             // On supprime la variable 'MyVar' de la table

Évidemment, c'est un brouillon. En pratique, il y a beaucoup plus de choses à prendre en compte, et on implémentera la classe dans un .cpp pour que ce ne soit pas trop dégueulasse, comme ici....

Ensuite, on aura tout une autre classe pour les fonctions, les conditions, les boucles, ...

J'ai également simplifié les values. Une valeur ne se résume pas à une chaine de caractère. Il faudra donc créer une classe spécifique aux valeurs possibles, ....

Le schéma que tu montres n'est pas très simple à comprendre. Il t'explique juste le niveau de traitement du code selon l'endroit abstrait où il se situe (sa portée).

Le niveau 0 serait ceci :

#include <foo>
#include <bar>
#include <oof>
...
#define FOO
#define PI 3.14
...

Donc, le préprocesseur.

Le niveau 1, le programme dans son entièreté (sans les expressions de préprocesseur) :

int MyGlobalVar = 9;

int main() { ... }
void foo(args) { ... }

template<...>
class bar { ... };

Le niveau 2, les fonctions / classes / ... au niveau interne (+ paramètres / templates) :

class foo { ... };

int main(int argc, char *argv[]) { ... };

Le niveau 3, les expressions locales :

int main(int argc, char *argv[]) {
    char *args[] = argv;
    int NumberOfArgs = argc;
    if (NumberOfArgs > 1) { ... }
    else return 1;
}

Et le niveau 4, les blocs de code inter-fonction, comme les boucles ou les conditions :

if (NumberOfArgs > 1) {
    for (unsigned int i = 0; i < NumberOfArgs; ++i) {
        ...
    }
}

L'analyse d'un programme se fait généralement de cette manière, mais il y a des langages qui ne suivent pas le même schéma, comme Haskell par exemple.

Dans ton exemple (que je me suis permit de modifier légèrement),

func main() {
   var c = "hey"
   if (c == "hey") {
     var c = "hey2"
     print(c)
   }
}

On commencerait par le niveau 2 :

func main();

Ensuite, le niveau 3 :

var c = "hey"

Puis le niveau 4 :

if (c == "hey");

Puis on repasserait au niveau 3 pour les expressions locales ;

var c = "hey2"
print(c)

Donc : 2; 3; 4; 3.

En fait, ces niveaux, on s'en fout un peu. Ce qui est important à retenir, c'est la logique d'analyse du programme, et la façon dont le code est représenté et structuré dans le compilateur.

-
Edité par vanaur 8 septembre 2018 à 14:29:23

Ah, j'y vois mieux 

Comment les langages qui incluent la possibilité de créer des "threads" font ?

Si deux variables du même nom sont définies/modifiées en même temps dans une boucle présente dans deux thread lancés simultanément ?

func main() {
	thread.start(sub() thread_1)  # commande fictive, inventée
				      # pour l'exemple
	thread.start(sub() thread_2)
}

func thread_1() {
	while True {
		var c = "hey" # -> même table des symboles, si
			      # on ne change pas de bloc, 
			      # il y a une surcharge ?
		print(c) 
	}
}

func thread_2() {
	while True {
		var c = "hey2"
		print(c)
	}
}

Comme tu peux le voir, deux variables qui ont pour nom "c" sont définies continuellement (car dans une boucle while) dans deux

fonctions différentes (les fonctions exécutent leur code en même temps, car elles ont été lancées en tant que "thread").

Comment le compilateur peut-il gérer de telles situations ?

-
Edité par JomtekYT1 9 septembre 2018 à 11:01:26

Les threads, c'est franchement pas ma tasse de thé

Je ne saurais donc pas te répondre de manière très complète, mais j'imagine que l'utilisation de threads ne changerait pas grand-chose à l'analyse du programme. Je pense même que cela ne changerait rien car les threads ne sont pas de l'ordre du langage ou du compilateur, mais du système d'exploitation. On utilise des bibliothèques pour manipuler les threads, comme on utiliserait la bibliothèque standard en fait, même si certains langages ont intégré cette fonctionnalité à leur sémantique et parfois leur grammaire.

Pour les variables à nom identique, ça ne fonctionnerait normalement pas, car qu'elle soit dans un thread ou non, le compilateur doit faire la distinction.