Conception du compilateur - Analyse sémantique

Nous avons appris comment un analyseur construit des arbres d'analyse dans la phase d'analyse syntaxique. L'arbre d'analyse simple construit dans cette phase n'est généralement d'aucune utilité pour un compilateur, car il ne contient aucune information sur la façon d'évaluer l'arbre. Les productions de la grammaire sans contexte, qui fait les règles de la langue, ne permettent pas de les interpréter.

Par exemple

E → E + T

La production CFG ci-dessus n'a pas de règle sémantique qui lui est associée, et elle ne peut pas aider à donner un sens à la production.

Sémantique

La sémantique d'un langage donne un sens à ses constructions, comme les jetons et la structure syntaxique. La sémantique aide à interpréter les symboles, leurs types et leurs relations les uns avec les autres. L'analyse sémantique juge si la structure syntaxique construite dans le programme source en tire une signification ou non.

CFG + semantic rules = Syntax Directed Definitions

Par exemple:

int a = “value”;

ne doit pas émettre d'erreur dans la phase d'analyse lexicale et syntaxique, car il est lexicalement et structurellement correct, mais il doit générer une erreur sémantique car le type d'affectation diffère. Ces règles sont fixées par la grammaire de la langue et évaluées en analyse sémantique. Les tâches suivantes doivent être effectuées en analyse sémantique:

• Résolution de la portée
• Vérification de type
• Vérification liée à la baie

Erreurs sémantiques

Nous avons mentionné certaines des erreurs sémantiques que l'analyseur sémantique devrait reconnaître:

• Incompatibilité de type
• Variable non déclarée
• Utilisation abusive de l'identifiant réservé.
• Déclaration multiple de variable dans une portée.
• Accéder à une variable hors de portée.
• Inadéquation des paramètres réels et formels.

Grammaire des attributs

La grammaire des attributs est une forme spéciale de grammaire sans contexte dans laquelle certaines informations supplémentaires (attributs) sont ajoutées à un ou plusieurs de ses non-terminaux afin de fournir des informations contextuelles. Chaque attribut a un domaine de valeurs bien défini, comme un entier, un flottant, un caractère, une chaîne et des expressions.

La grammaire des attributs est un moyen de fournir une sémantique à la grammaire sans contexte et elle peut aider à spécifier la syntaxe et la sémantique d'un langage de programmation. La grammaire des attributs (lorsqu'elle est considérée comme un arbre d'analyse) peut transmettre des valeurs ou des informations entre les nœuds d'un arbre.

Example:

E → E + T { E.value = E.value + T.value }

La partie droite du CFG contient les règles sémantiques qui spécifient comment la grammaire doit être interprétée. Ici, les valeurs des non-terminaux E et T sont additionnées et le résultat est copié dans le non-terminal E.

Les attributs sémantiques peuvent être attribués à leurs valeurs à partir de leur domaine au moment de l'analyse et évalués au moment de l'attribution ou des conditions. En fonction de la manière dont les attributs obtiennent leurs valeurs, ils peuvent être globalement divisés en deux catégories: les attributs synthétisés et les attributs hérités.

Attributs synthétisés

Ces attributs obtiennent des valeurs à partir des valeurs d'attribut de leurs nœuds enfants. Pour illustrer, supposons la production suivante:

S → ABC

Si S prend des valeurs de ses nœuds enfants (A, B, C), alors on dit qu'il s'agit d'un attribut synthétisé, car les valeurs de ABC sont synthétisées en S.

Comme dans notre exemple précédent (E → E + T), le nœud parent E tire sa valeur de son nœud enfant. Les attributs synthétisés ne prennent jamais les valeurs de leurs nœuds parents ou des nœuds frères.

Attributs hérités

Contrairement aux attributs synthétisés, les attributs hérités peuvent prendre des valeurs de parents et / ou de frères et sœurs. Comme dans la production suivante,

S → ABC

A peut obtenir des valeurs de S, B et C.B peut prendre des valeurs de S, A et C. De même, C peut prendre des valeurs de S, A et B.

Expansion : Lorsqu'un non-terminal est étendu aux terminaux selon une règle grammaticale

Reduction: Lorsqu'un terminal est réduit à son non-terminal correspondant selon des règles de grammaire. Les arbres de syntaxe sont analysés de haut en bas et de gauche à droite. Chaque fois que la réduction se produit, nous appliquons ses règles sémantiques (actions) correspondantes.

L'analyse sémantique utilise les traductions dirigées par la syntaxe pour effectuer les tâches ci-dessus.

L'analyseur sémantique reçoit AST (Abstract Syntax Tree) de son stade précédent (analyse syntaxique).

L'analyseur sémantique attache les informations d'attribut avec AST, qui sont appelées AST attribuées.

Les attributs sont deux valeurs de tuple, <nom d'attribut, valeur d'attribut>

Par exemple:

int value  = 5;
<type, “integer”>
<presentvalue, “5”>

Pour chaque production, nous attachons une règle sémantique.

SDT attribué S

Si un SDT utilise uniquement des attributs synthétisés, il est appelé SDT attribué par S. Ces attributs sont évalués à l'aide de SDT attribués par S dont les actions sémantiques sont écrites après la production (côté droit).

Comme illustré ci-dessus, les attributs dans les SDT attribués par S sont évalués dans une analyse ascendante, car les valeurs des nœuds parents dépendent des valeurs des nœuds enfants.

SDT attribué par L

Cette forme de SDT utilise à la fois des attributs synthétisés et hérités avec la restriction de ne pas prendre les valeurs des bons frères.

Dans les SDT attribués en L, un non-terminal peut obtenir des valeurs de ses nœuds parent, enfant et frère. Comme dans la production suivante

S → ABC

S peut prendre des valeurs de A, B et C (synthétisées). A peut prendre des valeurs de S uniquement. B peut prendre des valeurs de S et A. C peut obtenir des valeurs de S, A et B. Aucun non-terminal ne peut obtenir des valeurs du frère à sa droite.

Les attributs des SDT attribués par L sont évalués par analyse en profondeur d'abord et de gauche à droite.

Nous pouvons conclure que si une définition est attribuée en S, elle est également attribuée en L car la définition attribuée en L englobe les définitions attribuées en S.