Traduction Flashcards
Définition d’une passe
En compilation, une passe correspond à une lecture des données afin de les transformer.
Compilateur en trois passes : passe 1
Lecture du texte source par l’analyseur lexical et l’analyseur syntaxique. L’arbre abstrait est construit pendant l’analyse syntaxique.
Compilateur en trois passes : passe 2
Lecture des données (arbre généré à la fin de la passe 1) durant l’analyse sémantique (après analyse syntaxique). L’arbre généré à la fin de la passe 1 est décoré (on ajoute des informations aux éléments de cet arbre), et la TDS est créée et remplie.
Compilateur en trois passes : passe 3
Le générateur de code parcourt les données, c’est-à-dire maintenant l’arbre abstrait décoré et la TDS, afin de produire le code cible.
Exemples de contrôles sémantiques
- variable déclarée avant d’être utilisée
- pas de double déclaration (un même nom de variable n’est pas utilisé pour deux déclarations différentes, sauf si ces déclarations ont lieu dans des blocs différents).
- types cohérents lors des opérations (ex : on n’affecte pas une chaîne de caractères à une variable déclarée comme étant de type entier).
- paramètres passés à une fonction de même type que les paramètres définis lors de la déclaration de la fonction.
Espace de noms
Ensemble de ce qui est désignable dans un contexte donné par une méthode d’accès faisant usage de noms symboliques. Autrement dit, cela désigne un lieu abstrait (méthode, bloc, fichier…) conçu pour accueillir un ensemble de termes (variables ayant un nom défini).
Une variable est unique dans son espace de noms.
Région ou bloc
Une région dans un programme informatique correspond à l’intérieur d’une fonction, ou d’une structure, ou encore d’un fichier.
Pile des régions ouvertes
Pile utilisée lors de l’analyse sémantique (ou syntaxique, selon la méthode utilisée). On associe à chaque bloc dans le programme un entier unique. En parcourant l’arbre abstrait, dès qu’une région s’ouvre (ex : une accolade ouvrante), alors on empile son numéro dans cette pile. Dès que la région est refermée, le sommet de la pile est dépilé. Cela permet de déterminer d’une part le nombre d’imbrications maximal dans le programme ; d’autre part, on connaît le nombre d’imbrications de chaque région du programme.
AST (abstract syntax tree)
Pour faciliter l’analyse sémantique, on va simplifier et transformer l’arbre syntaxique “pur”. Cette simplification a lieu pendant l’analyse syntaxique, où l’on remplace et modifie en temps réel les branches de l’arbre en suivant un certain nombre de règles de transformation (appelées actions sémantiques).
Rappel sur les expressions régulières :
a+
a*
a?
a+ => “1 ou plusieurs a”
a+ => “0, 1 ou plusieurs a”
a? => “0 ou 1 a”
Action sémantique pour ANTLR : principe de base
→ ^(NOEUD feuille1 feuille2 …)
Cela remplace la branche courante par une branche ayant pour nœud NOEUD et les feuilles feuille1, feuille2, …
Action sémantique pour ANTLR : renommer
program : declaration + → ^(ROOT declaration+) ;
On renomme le nœud “program” en “ROOT”.
Action sémantique pour ANTLR : supprimer
variable : type ID ‘;’ → ^(DECL type ID) ;
On supprime le non-terminal ‘;’.
Action sémantique pour ANTLR : simplifier et réarranger
fonction : type ID ‘(‘ (formalParam (‘,’ formalParam)) ? ‘)’ block → ^(FONC type ID formalParam block) ;
On supprime les parenthèses et les virgules, et on regroupe les paramètres pour obtenir un arbre simplifié.
3 manières de réaliser un contrôle sémantique
- Les règles d’inférence
- Les grammaires attribuées
- L’utilisation de l’AST
Contrôles sémantiques statiques
Essentiel des contrôles effectués. Ils se déroulent à la compilation.
Ex : x/0 (écrit comme ça)
Contrôles sémantiques dynamiques
Effectués à l’exécution, ils nécessitent l’ajout de code assembleur supplémentaire dans le programme cible.
Ex : x/y avec y qui diminue jusqu’à valoir 0
Les 2 branches de l’AST à l’issue de l’analyse syntaxique
- Une branche déclaration (chacune des variables déclarées dans le programme y est présente)
- Une branche instruction (affectations de variables, utilisations de fonctions…)
Décoration de la branche déclaration de l’AST
Méthode qui associe des informations à chaque variable (type d’identificateur, type de variable, bloc de déclaration, portée dans le programme…)
Inconvénients : arbre lourd et difficile à lire par le générateur de code
Utilisation d’une table des symboles (TDS)
Méthode dans laquelle le générateur ne se sert plus de la branche déclaration. Il la remplace par une TDS, créée et remplie au cours de l’analyse sémantique (on peut aussi commencer le remplissage durant l’analyse syntaxique).
En général, une TDS par région puis regroupement en une TDS globale.
Contenu de la TDS pour un identificateur
- type, place mémoire occupée, et les bornes (si tableau)
- déplacement (différence d’adresses mémoires) nécessaire pour accéder à la variable depuis la base de la pile ou de la fonction
- visibilité et portée (numéro de bloc, nombre d’imbrications)
- arguments et leur type, type de retour (si fonction)
Définition d’un processus
Programme en cours d’exécution. Plus précisément :
- un ensemble d’instructions à exécuter, souvent chargé depuis une mémoire de masse (disque dur) vers la mémoire vive (RAM)
- un espace d’adressage en mémoire vive pour stocker les données de travail. Cet espace se divise en deux parties principales : la pile d’exécution (call stack) et le tas (heap).
Pile d’exécution
Sert à enregistrer des informations relatives à une fonction en train d’être exécutée et la trace de l’endroit où chaque fonction active doit retourner à la fin de son exécution (l’adresse de retour).
Tas
Utilisé pour allouer dynamiquement de l’espace mémoire à la demande du programme (malloc), par opposition à la pile qui est gérée automatiquement lors d’un appel de sous-routine ou de fonction. Il sert souvent à stocker des données de plus grande taille (tableaux, structures, et objets).
Cas des tableaux pour la mémoire
- Tableaux statiques (taille fixe, connue à la compilation) : pile
- Tableaux dynamiques (taille fixe, connue à l’exécution) : pile
- Tableaux flexibles (taille variable à l’exécution) : tas
Dans tous les cas, le nombre de dimensions du tableau est connu à la compilation.
Type statique vs type dynamique
- Statique : type associé à la variable au moment de la compilation
- Dynamique : type associé aux valeurs pendant l’exécution
Analyseur lexicale
- reconnaître les unités lexicales (ou tokens) qui sont les mots du langage et les présenter à l’analyseur syntaxique
- éliminer les commentaires, tabulations, espaces…
- afficher les erreurs lexicales (caractère inconnu)
Analyseur syntaxique
- vérifier que la phrase en entrée est bien formée (conforme à la syntaxe du langage définie par une grammaire)
- reconnaître les unités syntaxiques décrites par une grammaire (déclarations, affectations, instructions…)
- détecter les erreurs syntaxiques