Théorie des langages : Cours analyse semantique
Télécharger PDF1 Chapitre 5 : L’analyse sémantique COMPILATION 2013/2014 Sommaire Rôle de l’analyseur sémantique Définitions dirigées par la syntaxe Construction de l’arbre syntaxique abstrait 2013/2014 RÔLE DE L'ANALYSEUR SÉMANTIQUE 2013/2014 Rôle de l’analyseur sémantique L’analyseur lexical nous permet de vérifier le vocabulaire du programme source et l’analyseur syntaxique nous permet de vérifier si le programme source respecte la grammaire du langage. Pour générer le code objet, nous avons besoin de comprendre le sens du programme source. Il y a donc un autre niveau de vérification plus profond que celui de la vérification grammaticale. C’est le niveau contextuel du programme source. 2013/2014 Rôle de l’analyseur sémantique L’analyseur sémantique est le programme qui se charge de la vérification du contexte du programme source. Rôles principaux de l’analyseur sémantique : Vérifier la sémantique (le sens) du programme source. Produire un ensemble d’informations appelées points de génération qui seront utilisées par la génération de code. 2013/2014 Rôle de l’analyseur sémantique L’analyseur sémantique représente le plus gros travail d’un compilateur et le plus difficile, car il s’agit de vérifier la cohérence globale du programme source avant de générer le code objet. Il doit faire, par exemple : La gestion des identificateurs. La représentation des objets du programme. Le contrôle de type. La représentation des points de génération. 2013/2014 2 Rôle de l’analyseur sémantique Pour générer le code objet, le compilateur a besoin de la réponse à plusieurs questions, comme : Est-ce que l’identificateur "x" désigne un scalaire, un tableau, une fonction, etc ? Y a-t-il des variables utilisées avant d’être déclarées ? Dans l’expression "x+y*z", les variables ont-t-ils des types compatibles ? 2013/2014 Rôle de l’analyseur sémantique C’est l’analyseur sémantique qui donnera les réponses à de telles questions. L’analyse sémantique est généralement effectuée en même temps que l’analyse syntaxique. Lors de son travail, l’analyseur sémantique doit également détecter les erreurs sémantiques du programme source. Exemples d’erreurs sémantiques : Une variable non déclarée mais utilisée. 2013/2014 Rôle de l’analyseur sémantique Une variable est déclarée plusieurs fois. Le nombre des paramètres effectifs n’est pas égal à celui des paramètres formels. Une division par 0. Une incompatibilité de type (entier additionné à une chaîne de caractères, indice de tableau de type réel, etc). Erreur de portée d’une variable (visibilité). 2013/2014 Rôle de l’analyseur sémantique 2013/2014 Analyseur lexical Analyseur syntaxique Tables des symboles Programme source Lexèmes AST Analyseur sémantique Place de l’analyseur sémantique Rôle de l’analyseur sémantique Il y a deux stratégies pour effectuer l’analyse sémantique : Au cours de l’analyse syntaxique (le plus utilisé) : il faut utiliser une grammaire et des algorithmes d’analyse de cette grammaire qui favorisent l’analyse sémantique pendant l’analyse syntaxique. Dans ce cas, on utilise ce qu’on appelle des "traductions dirigées par la syntaxe". 2013/2014 Rôle de l’analyseur sémantique Après l’analyse syntaxique : on construit un modèle abstrait lequel va simplifier notre analyse syntaxique. Le modèle général utilisé s’appelle "l’arbre syntaxique abstrait" (AST, pour Abstract Syntax Tree). Dans ce cas, les vérifications sémantiques vont opérer sur l’AST et non pas sur l’arbre de dérivation.
2013/2014 3 DÉFINITIONS DIRIGÉES PAR LA SYNTAXE 2013/2014 Définitions dirigées par la syntaxe (DDS) Pour traduire une construction d’un langage de programmation, un compilateur peut avoir besoin de garder trace de nombreuses informations en plus du code engendré par cette construction. D’une manière abstraite, on parlera d’attributs associés à la construction. Un attribut représente une propriété élémentaire d’une construction d’un langage de programmation.
2013/2014 Définitions dirigées par la syntaxe (DDS) Un attribut peut représenter tout ce qu’on veut : Une chaîne de caractères; Un nombre; Un type; Une adresse mémoire, etc. Une définition dirigée par la syntaxe (DDS) est un formalisme qui permet de spécifier la traduction des constructions des langages de programmation. 2013/2014 Définitions dirigées par la syntaxe (DDS) Une DDS utilise une GHC pour spécifier la structure syntaxique du texte d’entrée. À chaque symbole de la grammaire, on associe un ensemble d’attributs. À chaque production de la grammaire, on associe un ensemble de règles sémantiques pour calculer la valeur de chaque attribut associé à un symbole qui apparaît dans la production. 2013/2014 Définitions dirigées par la syntaxe (DDS) Une règle sémantique est une suite d’instructions algorithmiques. Ainsi, une règle sémantique peut contenir : Une opération de calcul et d’assignation. Une instruction de séquence, de choix ou de répétition. Un appel de fonction ou de procédure. Une instruction d’affichage, etc. 2013/2014 Définitions dirigées par la syntaxe (DDS) Définition. Une grammaire attribuée est la donnée : D’une grammaire hors contexte G = <V, T, P, S>. D’un ensemble d’attributs pour certains symboles de G (les symboles de V et/ou de T). D’un ensemble de règles sémantiques associées à ses règles de production P. Une grammaire attribuée est également nommée Définition Dirigée par la Syntaxe (DDS). 2013/2014 4 Définitions dirigées par la syntaxe (DDS) Notations pour une DDS : "X.a" désigne l’attribut "a" du symbole "X". S’il y a plusieurs symboles X dans une production, on note : "X (0)
" pour référencer "X" si l’on a "X ...". "X (i)
" pour référencer le i ème symbole "X" se trouvant à gauche dans la partie droite de la production. Définition. On appelle arbre syntaxique décoré un arbre syntaxique sur les nœuds duquel on rajoute la valeur de chaque attribut. 2013/2014 Définitions dirigées par la syntaxe (DDS) Exemple : Considérons la grammaire G = <{S}, {a, b, c}, P, S> où P est l’ensemble des productions : S aSb | aS | cSacS | On considère les deux attributs : Nba : le nombre de "a" dans le mot. Nbc : le nombre de "c" dans le mot. Une DDS permettant de calculer ces attributs pourrait être par exemple : 2013/2014 Définitions dirigées par la syntaxe (DDS) Production Règle sémantique S aSb S(0) .Nba S(1) .Nba + 1 S(0) .Nbc S(1) .Nbc S aS S(0) .Nba S(1) .Nba + 1 S(0) .Nbc S(1) .Nbc S cSacS S(0) .Nba S(1) .Nba + S(2) .Nba + 1 S(0) .Nbc S(1) .Nbc + S(2) .Nbc + 2 S S(0) .Nba 0S (0)
.Nbc 0 2013/2014 Définitions dirigées par la syntaxe (DDS) Dans cet exemple de DDS, on remarque que les valeurs des attributs des symboles en partie gauche dépendent des celles des attributs des symboles de la partie droite. Donc, pour cette DDS, on peut calculer les valeurs des attributs d’un nœud de l’arbre syntaxique dès que celles des attributs de tous ses fils ont été calculées. Voyons cela sur un exemple, w = acaacabb. 2013/2014 Définitions dirigées par la syntaxe (DDS) 2013/2014 s s a b s c a s c s a s a b 0 0 0 0 0 1 0 1 2 3 2 4 Nombre de a Nombre de c Définitions dirigées par la syntaxe (DDS) On distingue deux classes d’attributs : Les attributs synthétisés. Les attributs hérités. La façon dont on calcule un attribut détermine sa classe. Définition. Un attribut est dit synthétisé lorsqu’il est calculé pour le non terminal de la partie gauche en fonction des attributs des non terminaux de la partie droite. les valeurs des attributs des symboles en partie gauche dépendent des celles des attributs des symboles de la partie droite. 2013/2014 5 Définitions dirigées par la syntaxe (DDS) Un attribut synthétisé signifie que sur l’arbre décoré, la valeur de l’attribut en nœud se calcule en fonction des attributs de ses fils. Donc, le calcul de l’attribut synthétisé se fait des feuilles vers la racine de l’arbre. Définition. Une grammaire attribuée est dite S-
attribuée, si tous ses attributs sont synthétisés (elle n’a aucun attribut hérité). 2013/2014 Définitions dirigées par la syntaxe (DDS) Production Règle sémantique E E+T E(0) . val E(1) . val + T. val E T E(0) . val T. val T T*F T(0) . val T(1) . val * F. val T F F (E) F digit T(0) . val F. val F(0) . val E.val F(0) . val digit.lexval 2013/2014 Définitions orientées-
syntaxe S-attribuées Entrée : 3*5 + 4 2013/2014 Définitions dirigées par la syntaxe (DDS) Définition. Un attribut est dit hérité lorsqu’il est calculé à partir des attributs du non terminal dans la partie gauche, et éventuellement des attributs d’autres non terminaux de la partie droite.
Un attribut hérité signifie que sur l’arbre décoré, la valeur de l’attribut en nœud se calcule en fonction des attributs de ses frères et de son père. Cela signifie que le calcul de l’attribut hérité se fait de la racine vers les feuilles. Remarque : il existe des grammaires attribuées qui possèdent à la fois des attributs hérités et des attributs synthétisés. 2013/2014 Définitions dirigées par la syntaxe (DDS) Définition. Une grammaire L-attribuée est une grammaire attribuée n’ayant que des attributs hérités qui ne dépendent pas des frères droits. Les attributs d’une grammaire L-attribuée peuvent être évaluées lors d’une analyse syntaxique descendante. Remarque : il existe des grammaires attribuées qui possèdent à la fois des attributs hérités et des attributs synthétisés. 2013/2014 Définitions dirigées par la syntaxe (DDS) Production Règle sémantique T F T’ T′. her F.valT (0)
.val T′.syn T’ *F T’ T’(1) . her T’(0) . her × F.val T’(0) . syn T’(1) . syn T’ F digit T’(0) . syn T’(0) . her F(0) . val digit.lexval 2013/2014 6 Utilisation des attributs hérités Entrée : 3 * 5 Les attributs hérités sont illustrés à gauche, et les attributs synthétisés, à droite. 2013/2014 Graphes de dépendance 2013/2014 Ordre d’évaluation des attributs 2013/2014 Ordre d’évaluation des attributs 2013/2014 CONSTRUCTION DE L'ARBRE SYNTAXIQUE ABSTRAIT 2013/2014 Construction de l’arbre syntaxique abstrait Arbre syntaxique abstrait (AST) : c’est un arbre déduit de l’arbre de dérivation dans lequel on ne conserve que les informations utiles pour l’analyse sémantique. Avantages des AST : Indépendance entre analyse syntaxique et traduction. Indépendance de la grammaire utilisée. Simplification de l’analyse sémantique. 2013/2014 7 Construction de l’arbre syntaxique abstrait 2013/2014 Construction de l’arbre syntaxique abstrait Cependant, les DDS sont importantes puisque la construction d’un AST doit passer par une DDS. Voyons comment on crée une AST pour les expressions arithmétiques. On a besoin de 3 primitives : CréerNœud(op, fg, fd) : crée un nœud étiqueté par « op » avec deux champs « fg » et « fd » (
« fg » : pointeur vers le fils gauche, « fd » : pointeur vers le fils droit). 2013/2014 Construction de l’arbre syntaxique abstrait CréerFeuille(id, e) : crée un nœud étiqueté par
« id » avec un champ « e » qui est un pointeur vers l’entrée de l’identificateur dans la table des symboles. CréerFeuille(nb, val) : crée un nœud étiqueté par « nb » avec un champ « val » qui est la valeur du nombre. On utilise une DDS qui va nous guider pour construire l’AST. 2013/2014 Construction de l’arbre syntaxique abstrait 2013/2014 Construction de l’arbre syntaxique abstrait 2013/2014 Construction d’arbres de syntaxe 2013/2014 8 Construction d’arbres de syntaxe 2013/2014 Construction d’arbres de syntaxe 2013/2014 Construction d’arbres de syntaxe 2013/2014 Construction d’arbres de syntaxe 2013/2014 Construction d’arbres de syntaxe 2013/2014 Représentation des types 2013/2014 9 Types et déclarations 2013/2014 Types et déclarations 2013/2014 Systèmes de types concrets 2013/2014 Un vérificateur de types 2013/2014 Un vérificateur de types 2013/2014 Disposition des données locales 2013/2014 10 Déclarations 2013/2014 GÉNÉRATION DE CODE INTERMÉDIAIRE 2013/2014 2013/2014 Représentations intermédiaires 2013/2014 Code à trois adresses 2013/2014 Code à trois adresses 2013/2014 11 Implantation des énoncés à 3 adresses 2013/2014 Traduction des expressions 2013/2014 Traduction des énoncés de contrôle 2013/2014 Traduction des énoncés de contrôle : if 2013/2014 Traduction des énoncés de contrôle: do . . . while 2013/2014 Traduction des énoncés de contrôle: while 2013/2014 12 Traduction des expressions booléennes : e1 && e2 2013/2014 OPTIMISATION DU CODE 2013/2014 Introduction 2013/2014 Considérations liées au design du générateur de code 2013/2014 Considérations liées au design du générateur de code 2013/2014 Considérations liées au design du générateur de code 2013/2014 13 Blocs de base et graphe de flot de contrôle 2013/2014 Blocs de base 2013/2014 Blocs de base 2013/2014 Blocs de base 2013/2014 Graphes de flot de contrôle 2013/2014 Graphes de flot de contrôle 2013/2014 14 Optimisation du code 2013/2014 Introduction 2013/2014 Introduction 2013/2014 Transformations sur les blocs de base 2013/2014 Optimisations préservant le comportement 2013/2014 Propagation des copies (des constantes) 2013/2014 15 OPTIMISATION : EXEMPLE COMPLET 2013/2014 Exemple 2013/2014 Exemple : graphe de flot 2013/2014 Exemple: Identification de sous-expressions locales communes 2013/2014 Exemple: Identification de sous-expressions locales communes 2013/2014 Exemple : Propagation de valeur + élimination de code mort 2013/2014 16 Exemple: Identification de sous-expressions globales communes 2013/2014 Exemple: Identification de sous-expressions globales communes 2013/2014 Exemple : Propagation de valeur + élimination de code mort 2013/2014 Exemple : Identification de sous-expressions globales communes 2013/2014 Exemple: Propagation de valeur 2013/2014 Exemple: Propagation de valeur + élimination de code mort 2013/2014