Cours analyse semantique Théorie des langages-télécharg...

Théorie des langages : Cours analyse semantique

Télécharger PDF

Rôle de l'analyseur sémantique

L'analyseur lexical permet de vérifier le vocabulaire du programme source, tandis que l'analyseur syntaxique s'assure que le programme respecte la grammaire du langage. Pour générer le code objet, il est nécessaire de comprendre le sens du programme source. Cela implique un niveau de vérification plus profond que la simple analyse grammaticale : le niveau contextuel du programme source.

L'analyseur sémantique est le composant du compilateur chargé de cette vérification contextuelle. Ses rôles principaux incluent :

Vérifier la sémantique (le sens) du programme source.
Produire un ensemble d'informations appelées points de génération, utilisées lors de la génération du code.

Cette étape représente le travail le plus complexe et le plus important d'un compilateur, car elle consiste à valider la cohérence globale du programme source avant de produire le code objet. Par exemple, l'analyseur sémantique doit :

Gérer les identificateurs pour éviter les conflits ou les erreurs.
Représenter les objets du programme de manière cohérente.
Contrôler les types pour garantir leur compatibilité.
Détecter les erreurs sémantiques comme les variables non déclarées ou les incompatibilités de type.

Pour générer le code objet, le compilateur doit répondre à des questions telles que :

Quel type représente l'identificateur « x » (scalaire, tableau, fonction, etc.) ?
Y a-t-il des variables utilisées avant leur déclaration ?
Les types des variables dans une expression comme « x + y * z » sont-ils compatibles ?

L'analyse sémantique est généralement effectuée en parallèle avec l'analyse syntaxique. Elle permet de détecter des erreurs comme :

L'utilisation d'une variable non déclarée.
La déclaration multiple d'une même variable.
Un déséquilibre entre les paramètres effectifs et formels.
Une division par zéro.
Une incompatibilité de type (ex. : addition d'un entier et d'une chaîne de caractères).
Une erreur de portée (visibilité) d'une variable.

Stratégies d'analyse sémantique

Il existe deux principales stratégies pour réaliser l'analyse sémantique :

Pendant l'analyse syntaxique : cette méthode est la plus courante. Elle utilise une grammaire et des algorithmes adaptés pour intégrer l'analyse sémantique à l'analyse syntaxique, notamment les traductions dirigées par la syntaxe.
Après l'analyse syntaxique : on construit un modèle abstrait simplifié, comme l'arbre syntaxique abstrait (AST). Les vérifications sémantiques sont alors appliquées sur cet AST plutôt que sur l'arbre de dérivation.

Définitions dirigées par la syntaxe (DDS)

Pour traduire une construction dans un langage de programmation, un compilateur doit souvent conserver des informations supplémentaires au-delà du code généré. Ces informations sont appelées attributs, associés à chaque construction syntaxique. Un attribut représente une propriété élémentaire d'une construction, comme une chaîne de caractères, un nombre, un type ou une adresse mémoire.

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. Elle repose sur :

Une grammaire hors contexte (GHC) décrivant la structure syntaxique du programme.
Un ensemble d'attributs associés aux symboles de la grammaire.
Des règles sémantiques définissant le calcul des valeurs des attributs pour chaque production.

Une règle sémantique est une suite d'instructions algorithmiques, incluant :

Des opérations de calcul et d'assignation.
Des instructions de séquence, de choix ou de répétition.
Des appels de fonctions ou de procédures.
Des instructions d'affichage.

Une grammaire attribuée est composée de :

Une grammaire hors contexte G = <V, T, P, S>.
Un ensemble d'attributs pour certains symboles de G (non-terminaux et/ou terminaux).
Un ensemble de règles sémantiques associées aux productions de P.

Notations et exemples

En DDS, les notations suivantes sont utilisées :

X.a : désigne l'attribut « a » du symbole « X ».
X(0) : référence le symbole « X » dans une production.
X(i) : référence le i-ème symbole « X » dans la partie droite d'une production.

Un arbre syntaxique décoré est un arbre syntaxique où chaque nœud est enrichi avec les valeurs des attributs associés.

Exemple de DDS

Considérons la grammaire G = <{S}, {a, b, c}, P, S> avec les productions suivantes :

S → aSb
S → aS
S → cSacS
S → ε

On définit deux attributs :

Nba : nombre de « a » dans le mot.
Nbc : nombre de « c » dans le mot.

Voici les règles sémantiques associées :

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 := 0
- S(0).Nbc := 0

Dans cet exemple, les valeurs des attributs dépendent des attributs des symboles de la partie droite. Cela signifie que les attributs peuvent être calculés dès que ceux de tous les fils sont connus, de manière ascendante (des feuilles vers la racine).

Attributs synthétisés et hérités

On distingue deux types d'attributs :

Attributs synthétisés : calculés pour un non-terminal en fonction des attributs de ses fils. Leur évaluation se fait des feuilles vers la racine.
Attributs hérités : calculés en fonction des attributs du non-terminal parent ou d'autres symboles de la partie droite. Leur évaluation se fait de la racine vers les feuilles.

Une grammaire attribuée est dite S-attribuée si tous ses attributs sont synthétisés. Dans le cas contraire, elle peut combiner attributs synthétisés et hérités.

Exemple de grammaire S-attribuée

Considérons la grammaire pour les expressions arithmétiques :

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(0).val := E.val
F → digit : F(0).val := digit.lexval

Pour l'entrée 3 * 5 + 4, les règles permettent de calculer la valeur finale en remontant de la feuille vers la racine.

Grammaire L-attribuée

Une grammaire attribuée est dite L-attribuée si elle ne contient que des attributs hérités qui ne dépendent pas des frères droits. Cela permet d'évaluer les attributs lors d'une analyse syntaxique descendante.

Exemple d'attributs hérités

Pour la grammaire T → F T' avec :

T'.her := F.val
T'.syn := T'.her (pour T' → *F T')
T'.syn := T'.her (pour T' → ε)
F → digit : F(0).val := digit.lexval

Dans cet exemple, les attributs hérités sont calculés en fonction des attributs du père, tandis que les attributs synthétisés dépendent des fils.

Construction de l'arbre syntaxique abstrait (AST)

L'arbre syntaxique abstrait (AST) est un modèle simplifié déduit de l'arbre de dérivation, ne conservant que les informations nécessaires à l'analyse sémantique. Ses avantages incluent :

L'indépendance entre l'analyse syntaxique et la traduction.
La flexibilité par rapport à la grammaire utilisée.
La simplification de l'analyse sémantique.

Bien que les DDS soient essentielles pour la construction d'un AST, elles permettent de guider cette création. Pour les expressions arithmétiques, on utilise trois primitives :

CréerNœud(op, fg, fd) : crée un nœud avec une étiquette « op » et deux pointeurs vers les fils gauche (« fg ») et droit (« fd »).
CréerFeuille(id, e) : crée un nœud avec une étiquette « id » et un pointeur vers l'entrée de l'identificateur dans la table des symboles.
CréerFeuille(nb, val) : crée un nœud avec une étiquette « nb » et un champ « val » contenant la valeur numérique.

Génération de code intermédiaire

Le code intermédiaire est une représentation simplifiée et indépendante du langage source, facilitant la génération du code objet. Parmi les formats courants, on trouve le code à trois adresses, qui permet de décomposer les instructions en opérations élémentaires.

Traduction des expressions

Les expressions arithmétiques sont traduites en code intermédiaire pour optimisation et génération du code objet.

Traduction des énoncés de contrôle

Les structures de contrôle comme if, do...while et while sont converties en code intermédiaire pour une exécution efficace.

Traduction des expressions booléennes

Les expressions logiques, telles que e1 && e2, sont transformées en instructions conditionnelles dans le code intermédiaire.

Optimisation du code

L'optimisation du code vise à améliorer les performances et la taille du programme généré sans altérer son comportement. Elle repose sur des transformations appliquées aux blocs de base et au graphe de flot de contrôle.

Transformations courantes

Parmi les optimisations préservant le comportement, on trouve :

La propagation des copies (ou des constantes), qui remplace les variables par leurs valeurs connues.
L'identification de sous-expressions communes locales ou globales, évitant des calculs redondants.
L'élimination de code mort, supprimant les instructions inutiles.

Exemple d'optimisation

Pour un graphe de flot donné, les optimisations incluent :

La propagation de valeur pour remplacer les variables par leurs valeurs calculées.
L'identification de sous-expressions globales communes pour éviter des répétitions.

FAQ

Quelle est la différence entre analyseur syntaxique et analyseur sémantique ?

L'analyseur syntaxique vérifie que le programme respecte la grammaire du langage, tandis que l'analyseur sémantique valide la cohérence globale du programme, comme les types des variables ou leur déclaration.

Pourquoi utiliser un arbre syntaxique abstrait (AST) ?

L'AST simplifie l'analyse sémantique en ne conservant que les informations essentielles, indépendamment de la grammaire utilisée. Cela améliore l'efficacité et la modularité du compilateur.

Quels sont les types d'attributs en DDS ?

Les attributs en DDS sont classés en deux catégories : les attributs synthétisés, calculés à partir des fils, et les attributs hérités, calculés en fonction du parent ou d'autres symboles.