Compilation [PDF]

Zitiervorschau

SOMMAIRE Sommaire ............................................................................................................................................... i Chapitre 1. Qu'est ce que la compilation ? ................................................................................ 1 1. Pourquoi ce cours ? ................................................................................................................... 2 2. Structure d'un compilateur ...................................................................................................... 2 3. Phases d'analyses ...................................................................................................................... 3 3.1 Analyse lexicale (appelée aussi Analyse linéaire) .............................................................. 3 3.2 Analyse syntaxique (Analyse hiérarchique ou grammaticale) ......................................... 3 3.3 Analyse sémantique (analyse contextuelle) ......................................................................... 3 4. Phases de production ................................................................................................................ 3 4.1 Génération de code ................................................................................................................. 3 4.2 Optimisation de code .............................................................................................................. 4 5. Phases parallèles ....................................................................................................................... 4 5.1 Gestion de la table des symboles........................................................................................... 4 5.2 Gestion des erreurs.................................................................................................................. 4 6. Conclusion .................................................................................................................................. 4 Chapitre 2. Analyse lexicale ......................................................................................................... 7 1. Unités lexicales et lexèmes ...................................................................................................... 7 2. Spécification des unités lexicales ........................................................................................... 7 3. Attributs ...................................................................................................................................... 8 4. Analyseur lexical ....................................................................................................................... 9 5. Erreurs lexicales ....................................................................................................................... 11 Chapitre 3. L'outil (f)lex ......................................................................................................... 12 1. Structure du fichier de spécifications (f)lex .................................................................. 12 2. Les expressions régulières (f)lex ...................................................................................... 12 3. Variables et fonctions prédéfinies ....................................................................................... 14 4. Exemples de fichier .l ............................................................................................................. 14 5. Exercices .................................................................................................................................... 14 Chapitre 4. Analyse syntaxique ................................................................................................. 16 1. Grammaires et Arbres de dérivation ................................................................................... 16 2. Grammaires .............................................................................................................................. 16 3. Arbre de dérivation ................................................................................................................. 18 4. Mise en oeuvre d'un analyseur syntaxique ........................................................................ 20 4.1 Analyse descendante ............................................................................................................ 20 4.1.1

Exemples.................................................................................................................................. 20

4.2 Table d'analyse LL(1) ............................................................................................................ 22 4.2.1 4.2.2 4.2.3 4.2.4

Calcul de PREMIER ............................................................................................................... 22 Calcul de SUIVANT ............................................................................................................... 23 Construction de la table d'analyse .......................................................................................... 25 Analyseur syntaxique.............................................................................................................. 25

4.3 Grammaire LL(1) ................................................................................................................... 28 4.3.1 4.3.2 4.3.3 4.3.4

5.

Récursivité à gauche ................................................................................................................ 29 Grammaire propre ................................................................................................................... 31 Factorisation à gauche ............................................................................................................. 31 Conclusion ............................................................................................................................... 32

Analyse ascendante................................................................................................................. 33

Cours de Compilation

i

6.

Erreurs syntaxiques................................................................................................................. 39 6.1 Récupération en mode panique........................................................................................... 40 6.2 Récupération au niveau du syntagme ................................................................................ 40 6.3 Productions d'erreur ............................................................................................................. 41 6.4 Correction globale ................................................................................................................. 41 Chapitre 5. Traduction dirigée par la syntaxe ......................................................................... 42 1. Définition dirigée par la syntaxe ......................................................................................... 42 2. Arbre syntaxique décoré ........................................................................................................ 42 3. Attributs synthétisés et hérités ............................................................................................. 43 3.1 Attributs synthétisés ............................................................................................................. 43 3.2 Attributs hérités ..................................................................................................................... 43 4. Graphe de dépendances ......................................................................................................... 44 5. Evaluation des attributs ......................................................................................................... 47 5.1 Après l'analyse syntaxique................................................................................................... 47 5.2 Pendant l'analyse syntaxique............................................................................................... 47 6. Exercices .................................................................................................................................... 52 Chapitre 6. L'outil yacc/bison ................................................................................................ 54 1. Structure du fichier de spécifications bison..................................................................... 54 2. Attributs .................................................................................................................................... 55 3. Communication avec l'analyseur lexical : yylval ........................................................... 55 4. Variables, fonctions et actions prédéfinies ........................................................................ 56 5. Conflits shift-reduce et reduce-reduce ................................................................................ 56 6. Associativité et priorité des symboles terminaux ............................................................. 56 7. Récupération des erreurs ....................................................................................................... 57 8. Options de compilations Bison ............................................................................................ 57 9. Exemples de fichier .y............................................................................................................. 58 10. Exercices .................................................................................................................................... 59 Chapitre 7. Analyse sémantique ................................................................................................ 61 1. Portée des identificateurs ...................................................................................................... 61 2. Contrôle de type ...................................................................................................................... 62 3. Surcharge d'opérateurs et de fonctions ............................................................................... 64 4. Fonctions polymorphes .......................................................................................................... 65 5. Environnement d'exécution .................................................................................................. 69 5.1 Organisation de la mémoire à l'exécution.......................................................................... 69 5.2 Allocation dynamique : gestion du tas ............................................................................... 70 6. Génération de code ................................................................................................................. 72 6.1 Code intermédiaire................................................................................................................ 72 6.2 Caractéristiques communes aux machines cibles ............................................................. 72 6.3 Code à 3 adresses simplifié .................................................................................................. 72 6.4 Production de code à 3 adresses.......................................................................................... 74 6.4.1 6.4.2

7.

Expressions arithmétiques ....................................................................................................... 74 Expressions booléennes............................................................................................................ 75

Optimisation de code ............................................................................................................. 77

Cours de Compilation

ii

CHAPITRE 1. QU'EST CE QUE LA COMPILATION ? Tout programmeur utilise jour après jour un outil essentiel à la réalisation de programmes informatiques : le compilateur. Un compilateur est un logiciel particulier qui traduit un programme écrit dans un langage de haut niveau (par le programmeur) en instructions exécutables (par un ordinateur). C'est donc l'instrument fondamental à la base de tout réalisation informatique.

Figure 1.1: Chaîne de développement d'un programme

Tout programme écrit dans un langage de haut niveau (dans lequel il est fait abstraction (sauf pour quelques instructions) de la structure et des détails du calculateur sur lequel les programmes sont destinés à être exécutés) ne peut être exécuté par un ordinateur que s'il est traduit en instructions exécutables par l'ordinateur (langage machine, instructions élémentaires directement exécutables par le processeur). Lorsque le langage cible est aussi un langage de haut niveau, on parle plutôt de traducteur. Autre différence entre traducteur et compilateur : dans un traducteur, il n'y a pas de perte d'informations (on grade les commentaires, par exemple), alors que dans un compilateur il y a perte d'informations. Une autre phase importante qui intervient après la compilation pour obtenir un exécutable est la phase d'éditions de liens. Un éditeur de liens résout entre autres les références à des appels de routines dont le code est conservé dans des librairies. En général, un compilateur comprend une partie éditeur de liens. Nous n'en parlerons pas ici. En outre, sur les systèmes modernes, l'édition des liens est faite à l'exécution du programme ! (Le programme est plus petit et les mises à jour plus faciles). On ne parlera pas non plus de la précompilation (cf. préprocesseur C). Attention, il ne faut pas confondre les compilateurs et les interpréteurs ! Un compilateur est Cours de Compilation

1

un programme (de traduction automatique d'un programme écrit dans un langage source en un programme écrit dans un langage cible). Au lieu de produire un programme cible comme dans le cas d'un compilateur, un interprète exécute lui même au fur et à mesure les opérations spécifiées par le programme source. Il analyse une instruction après l'autre puis l'exécute immédiatement. A l'inverse d'un compilateur, il travaille simultanément sur le programme et sur les données. Généralement les interpréteurs sont assez petits. Il existe des langages qui sont à mi-chemin de l'interprétation et de la compilation. Par exemple Java, le source est compilé pour obtenir un fichier (.class) ''byte code'' qui sera interprété par une machine virtuelle. En règle générale, le programmeur dispose d'un calculateur concret (cartes équipées de processeurs, puces de mémoire, ...). Le langage cible est dans ce cas défini par le type de processeur utilisé. Mais si l'on écrit un compilateur pour un processeur donné, il n'est alors pas évident de porter ce compilateur (ce programme) sur une autre machine cible. C'est pourquoi (entre autres raisons), on introduit des machines dites abstraites qui font abstraction des architectures réelles existantes. Ainsi, on s'attache plus aux principes de traduction, aux concepts des langages, qu'à l'architecture des machines. Cf. machine abstraite Java.

1. Pourquoi ce cours ? Il est évident qu'il n'est pas nécessaire de comprendre comment est écrit un compilateur pour savoir comment l'utiliser. De même, un informaticien a peu de chances d'être impliqué dans la réalisation ou même la maintenance d'un compilateur pour un langage de programmation majeur. Alors pourquoi ce cours ? Le but de ce cours est de présenter les principes de base inhérents à la réalisation de compilateurs. Les idées et techniques développées dans ce domaine sont si générales et fondamentales qu'un informaticien (et même un scientifique non informaticien) les utilisera très souvent au cours de sa carrière (traitement de données, moteurs de recherche, etc.). Nous verrons les principes de base inhérents à la réalisation de compilateurs : analyse lexicale, analyse syntaxique, analyse sémantique, génération de code. En outre, comprendre comment est écrit un compilateur permet de mieux comprendre les "contraintes" imposées par les différents langages lorsque l'on écrit un programme dans un langage de haut niveau. Nous avons déjà étudié les outils fondamentaux utilisés pour effectuer ces analyses : fondements de base de la théorie des langages (grammaires, automates, ...), méthodes algorithmiques d'analyse, ...

2. Structure d'un compilateur // Morceau de programme en C #include int CalculDeMaValeurGeniale(float * tab) { int i,j; float k1,k2; ... k2=2*k1+sin(tab[j]); if (k2>i) ... La compilation se décompose en deux phases :

Cours de Compilation

2

une phase d'analyses, qui va reconnaître les variables, les instructions, les opérateurs et élaborer la structure syntaxique du programme ainsi que certaines propriétés sémantiques une phase de synthèse et de production qui devra produire le code cible.

3. Phases d'analyses (appelée aussi Analyse linéaire) Dans cette étape, il s'agit de reconnaître les "types" des "mots" lus. Pour cela, on lit le programme source de gauche à droite et les caractères sont regroupés en unités lexicales. L'analyse lexicale se charge de : Éliminer les caractères superflus (commentaires, espaces, ...) Identifier les parties du texte qui ne font pas partie à proprement parler du programme mais sont des directives pour le compilateur Identifier les symboles qui représentent des identificateurs, des constantes réelles, entière, chaînes de caractères, des opérateurs (affectation, addition, ...), des séparateurs (parenthèses, points virgules, ...)

, les mots clefs du langage, ... C'est cela que l'on appelle des unités

2.1

lexicales. Outils théoriques utilisés : expressions régulières et automates à états finis

3.1 Analyse syntaxique (Analyse hiérarchique ou grammaticale) Il s'agit de regrouper les unités lexicales en structures grammaticales, de découvrir la structure du programme. L'analyseur syntaxique sait comment doivent être construites les expressions, les instructions, les déclarations de variables, les appels de fonctions, ... Exemple. En C, une sélection simple doit se présenter sous la forme : if (expression) instruction Si l'analyseur syntaxique reçoit la suite d'unités lexicales MC_IF IDENT OPREL ENTIER ... il doit signaler que ce n'est pas correct car il n'y a pas de ( juste après le if Outils théoriques utilisés : grammaires et automates à pile

3.2 Analyse sémantique (analyse contextuelle) Dans cette phase, on opère certains contrôles (contrôles de type, par exemple) afin de vérifier que l'assemblage des constituants du programme a un sens. On ne peut pas, par exemple, additionner un réel avec une chaîne de caractères, ou affecter une variable à un nombre, ... Outil théorique utilisé : schéma de traduction dirigée par la syntaxe

4. Phases de production 4.1 Génération de code Il s'agit de produire les instructions en langage cible. En général, on produira dans un premier temps des instructions pour une machine abstraite (virtuelle). Puis ensuite on fera la traduction de ces instructions en des instructions directement exécutables par la machine réelle sur laquelle on veut que le compilateur s'exécute. Ainsi, le portage du compilateur sera facilité, car la traduction en code cible virtuel sera faite une fois pour toutes, indépendamment de la machine cible réelle. Il ne reste plus ensuite qu'à étudier les problèmes spécifiques à la machine cible, et non plus les problèmes de reconnaissance du programme (cf. Java).

Cours de Compilation

3

4.2 Optimisation de code Cette phase tente d'améliorer le code produit de telle sorte que le programme résultant soit plus rapide. Il y a des optimisations qui ne dépendent pas de la machine cible : élimination de calculs inutiles (faits en double), élimination du code d'une fonction jamais appelée, propagation des constantes, extraction des boucles des invariants de boucle, ... Et il y a des optimisations qui dépendent de la machine cible : remplacer des instructions générales par des instructions plus efficaces et plus adaptées, utilisation optimale des registres, ...

5. Phases parallèles 5.1 Gestion de la table des symboles La table des symboles est la structure de données utilisée servant à stocker les informations qui concernent les identificateurs du programme source (par exemple leur type, leur emplacement mémoire, leur portée, visibilité, nombre et type et mode de passage des paramètres d'une fonction, ...). Le remplissage de cette table (la collecte des informations) a lieu lors des phases d'analyse. Les informations contenues dans la table des symboles sont nécessaires lors des analyses syntaxique et sémantique, ainsi que lors de la génération de code.

5.2 Gestion des erreurs Chaque phase peut rencontrer des erreurs. Il s'agit de les détecter et d'informer l'utilisateur le plus précisément possible : erreur de syntaxe, erreur de sémantique, erreur système, erreur interne. Un compilateur qui se contente d'afficher syntax error n'apporte pas beaucoup d'aide lors de la mise au point. Après avoir détecté une erreur, il s'agit ensuite de la traiter de telle manière que la compilation puisse continuer et que d'autres erreurs puissent être détectées. Un compilateur qui s'arrête à la première erreur n'est pas non plus très performant. Bien sûr, il y a des limites à ne pas dépasser et certaines erreurs (ou un trop grand nombre d'erreurs) peuvent entraîner l'arrêt de l'exécution du compilateur.

6. Conclusion Figure 2.1: Structure d'un compilateur

Cours de Compilation

4

Pendant toutes les années 50, les compilateurs furent tenus pour des programmes difficiles à écrire. Par exemple, la réalisation du premier compilateur Fortran nécessita 18 hommesannées de travail (1957). On a découvert depuis des techniques systématiques pour traiter la plupart des tâches importantes qui sont effectuées lors de la compilation.

Différentes phases de la compilation

Outils théoriques utilisés

Phases d'analyse

analyse lexicale

expressions régulières

(scanner)

automates à états finis

analyse syntaxique

grammaires

(parer)

automates à pile

analyse sémantique

traduction dirigée par la syntaxe

Phases de production génération de code

traduction dirigée par la syntaxe

optimisation de code Gestions parallèles

table des symboles traitement des erreurs

Contrairement à une idée souvent répandue, la plupart des compilateurs sont réalisés (écrits) dans un langage de haut niveau, et non en assembleur. Les avantages sont multiples : facilité de manipulation de concepts avancés maintenabilité accrue du compilateur portage sur d'autres machines plus aisé Par exemple, le compilateur C++ de Björne Stroustrup est écrit en C, .... Il est même possible

Cours de Compilation

5

d'écrire un compilateur pour un langage L dans ce langage L (gcc est écrit en C ...!) (bootstrap).

Cours de Compilation

6

CHAPITRE 2.

ANALYSE LEXICALE

L'analyseur lexical constitue la première étape d'un compilateur. Sa tâche principale est de lire les caractères d'entrée et de produire comme résultat une suite d'unités lexicales que l'analyseur syntaxique aura à traiter. En plus, l'analyseur lexical réalise certaines tâches secondaires comme l'élimination de caractères superflus (commentaires, tabulations, fin de lignes, ...), et gère aussi les numéros de ligne dans le programme source pour pouvoir associer à chaque erreur rencontrée par la suite la ligne dans laquelle elle intervient. Dans ce chapitre, nous abordons des techniques de spécifications et d'implantation d'analyseurs lexicaux. Ces techniques peuvent être appliquées à d'autres domaines. Le problème qui nous intéresse est la spécification et la conception de programmes qui exécutent des actions déclenchées par des modèles dans des chaînes (traitement de données, moteurs de recherche, ...).

1. Unités lexicales et lexèmes Définition 3.1 collective.

Une unité lexicale est une suite de caractères qui a une signification

Exemples : les chaînes sont des opérateurs relationnels. L'unité lexicale est OPREL (par exemple). Les chaînes toto, ind, tab, ajouter sont des identificateurs (de variables, ou de fonctions). Les chaînes if, else, while sont des mots clefs. Les symboles ,.;() sont des séparateurs. Définition 3.2 Un modèle est une règle associée à une unité lexicale qui décrit l'ensemble des chaînes du programme qui peuvent correspondre à cette unité lexicale. Définition 3.3 On appelle lexème toute suite de caractère du programme source qui concorde avec le modèle d'une unité lexicale.

Exemples : L'unité lexicale IDENT (identificateurs) en C a pour modèle : toute suite non vide de caractères composée de chiffres, lettres ou du symbole "_" et qui commencent par une lettre. Des exemples de lexèmes pour cette unité lexicale sont : truc, i,a1, ajouter_valeur ... L'unité lexicale NOMBRE (entier signé) a pour modèle : toute suite non vide de chiffres précédée éventuellement d'un seul caractère parmi . Lexèmes possibles : -12, 83204, +0 ... L'unité lexicale REEL a pour modèle : tout lexème correspondant à l'unité lexicale NOMBRE suivi éventuellement d'un point et d'une suite (vide ou non) de chiffres, le tout suivi éventuellement du caractère E ou e et d'un lexème correspondant à l'unité lexicale NOMBRE. Cela peut également être un point suivi d'une suite de chiffres, et éventuellement du caractère E ou e et d'un lexème correspondant à l'unité lexicale NOMBRE. Exemples de lexèmes : 12.4, 0.5e3, 10., -4e-1, -.103e+2 ... Pour décrire le modèle d'une unité lexicale, on utilisera des expressions régulières.

2. Spécification des unités lexicales

Cours de Compilation

7

Nous disposons donc, avec les E.R., d'un mécanisme de base pour décrire des unités lexicales. Par exemple, une ER décrivant les identificateurs en C pourrait être : ident = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v |w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q |R|S|T|U |V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r| s|t|u|v|w|x|y|z|A|B |C|D|E|F|G|H|I|J|K|L|M |N|O |P|Q| R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9|_)* C'est un peu chiant et illisible ... Alors on s'autorise des définitions régulières et le symbole - sur des types ordonnés (lettres, chiffres, ...). Une définition régulière est une suite de définitions de la forme

où chaque ri est une expression régulière sur l'alphabet nom différent.

, et chaque di est un

Exemple : l'unité lexicale IDENT (identificateurs) en C devient

Remarque IMPORTANTE : toutes les unités lexicales ne peuvent pas être exprimées par des définitions régulières. Par exemple une unité lexicale correspondant au modèle "toute suite de a et de b de la forme anbn avec " ne peut pas être exprimée par des définitions régulières, car ce n'est pas un langage régulier (mais c'est un langage que l'on appelle hors contexte, on verra plus tard qu'on peut s'en sortir avec les langages hors contexte et heureusement). Autre exemple : il n'est pas possible d'exprimer sous forme d'ER les systèmes de parenthèses bien formés, ie les mots (), (())(), ()(()()(())) .... Ce n'est pas non plus un langage régulier (donc les commentaires à la Pascal ne forment pas un langage régulier).

3. Attributs Exemples : Pour ce qui est des symboles =, , , l'analyseur syntaxique a juste besoin de savoir que cela correspond à l'unité lexicale OPREL (opérateur relationnel). C'est seulement lors de la génération de code que l'on aura besoin de distinguer < de >= (par exemple). Pour ce qui est des identificateurs, l'analyseur syntaxique a juste besoin de savoir que c'est l'unité lexicale IDENT. Mais le générateur de code, lui, aura besoin de l'adresse de la variable correspondant à cet identificateur. L'analyseur sémantique aura aussi besoin du type de la variable pour vérifier que les expressions sont sémantiquement correctes. Cette information supplémentaire, inutile pour l'analyseur syntaxique mais utile pour les autres phases du compilateur, est appelée attribut.

Cours de Compilation

8

4. Analyseur lexical Récapitulons : le rôle d'un analyseur lexical est la reconnaissance des unités lexicales. Une unité lexicale peut (la plupart du temps) être exprimée sous forme de définitions régulières. Dans la théorie des langages, on définit des automates qui sont des machines théoriques permettant la reconnaissance de mots (voir chapitre 8). Ces machines ne marchent que pour certains types de langages. En particulier : Théorème 3.9 Un langage régulier est reconnu par un automate fini. Contentons nous pour l'instant de donner un exemple d'automate : Le langage régulier décrit par l'ER (abbc|bacc)+c(c|bb)* est reconnu par l'automate : état a b c 0

1 4

1

2

2

3

3 4

6 5

5

3

6

1 4 7

7

8 7

8

7

Bon, un langage régulier (et donc une ER) peut être reconnu par un automate. Donc pour écrire un analyseur lexical de notre programme source, il "suffit" (...) donc d'écrire un programme simulant l'automate reconnaissant les unités lexicales. Lorsqu'une unité lexicale est reconnue, elle envoyée à l'analyseur syntaxique, qui la traite, puis repasse la main à l'analyseur lexical qui lit l'unité lexicale suivante dans le programme source. Et ainsi de suite, jusqu'à tomber sur une erreur ou jusqu'à ce que le programme source soit traité en entier (et alors on est content). Exemple de morceau d'analyseur lexical pour le langage Pascal (en C) : c = getchar(); switch (c) { case ':' : c=getchar(); if (c== '=') { unite_lex = AFFECTATION; c= getchar(); }

Cours de Compilation

9

else unite_lex = DEUX_POINTS; break; case '10 ) if (y10) if (y10) if (yaS'| T->T' T'->bTT'| Or on a S -> TScS' -> T'ScS' -> ScS' damned une récursivité à gauche !!!! Eh oui, l'algo ne marche pas toujours lorsque la grammaire possède une règle A-> 4.3.2 Grammaire propre

Définition 5.12 Une grammaire est dite propre si elle ne contient aucune production A-> Comment rendre une grammaire propre ? En rajoutant une production dans laquelle le A est remplacé par , ceci pour chaque A apparaissant en partie droite d'une production, et pour chaque A d'un A -> Exemple : S -> a Tb|aU T -> bTaTA| U -> a U | b devient S -> a Tb|ab|aU T -> bTaTA|baTA|bTaA|baA U -> a U | b 4.3.3 Factorisation à gauche

L'idée de base est que pour développer un non-terminal A quand il n'est pas évident de choisir l'alternative à utiliser (ie quelle production prendre), on doit réécrire les productions de A de façon à différer la décision jusqu'à ce que suffisamment de texte ait été lu pour faire le bon choix.

Exemple : Au départ, pour savoir s'il faut choisir ou , il faut avoir lu la 5ième lettre du mot (un a ou un c). On ne peut donc pas dès le départ savoir quelle production prendre. Ce qui est incompatible avec une grammaire LL(1). (Remarque : mais pas avec une grammaire LL(5), mais ce n'est pas notre problème.) Factorisation à gauche : Pour chaque non-terminal A trouver le plus long préfixe

Cours de Compilation

commun à deux de ses alternatives ou plus

31

Si , remplacer pas par ) par les deux règles

(où les

ne commencent

finpour Recommencer jusqu'à ne plus en trouver.

Exemple :

Factorisée à gauche, cette grammaire devient : 4.3.4 Conclusion

Si notre grammaire est LL(1), l'analyse syntaxique peut se faire par l'analyse descendante vue ci-dessus. Mais comment savoir que notre grammaire est LL(1) ? Etant donnée une grammaire

1. la rendre non ambiguë. Il n'y a pas de méthodes. Une grammaire ambiguë est une grammaire qui a été mal conçue. 2. éliminer la récursivité à gauche si nécessaire 3. la factoriser à gauche si nécessaire 4. construire la table d'analyse Il ne reste plus qu'a espérer que ça soit LL(1). Sinon, il faut concevoir une autre méthode pour l'analyse syntaxique. Exemple : grammaire des expressions arithmétiques avec les opérateurs + et * . Mais elle est ambiguë. Pour lever l'ambiguïté, on considère les priorités classiques des opérateurs et on obtient la grammaire non ambiguë :

Après suppression de la récursivité à gauche, on obtient

Cours de Compilation

32

Inutile de factoriser à gauche. Cette grammaire est LL(1) (c'est l'exemple que l'on a utilisé tout le temps). Autre exemple : la grammaire

n'est pas LL(1). Or elle n'est pas récursive à gauche, elle est factorisée à gauche et elle n'est pas ambigüe !

5. Analyse ascendante Principe : construire un arbre de dérivation du bas (les feuilles, ie les unités lexicales) vers le haut (la racine, ie l'axiome de départ). Le modèle général utilisé est le modèle par décallages-réductions. C'est à dire que l'on ne s'autorise que deux opérations :  

décalage (shift) : décaler d'une lettre le pointeur sur le mot en entrée réduction (reduce) : réduire une chaîne (suite consécutive de terminaux et non terminaux à gauche du pointeur sur le mot en entrée et finissant sur ce pointeur) par un non-terminal en utilisant une des règles de production

Exemple :

avec le mot u=aacbaacbcbcbcbacbc on ne peut rien réduire, donc on décale on ne peut rien réduire, donc on décale on ne peut rien réduire, donc on décale ah ! On peut réduire par on ne peut rien réduire, donc on décale

... on peut utiliser on ne peut rien réduire, donc on décale on ne peut rien réduire, donc on décale On peut utiliser On peut utiliser

Cours de Compilation

33

décalage décalage réduction par réduction par réduction par décalage décalage réduction par réduction par décalage décalage décalage réduction par décalage décalage réduction par réduction par réduction par terminé !!!! On a gagné, le mot est bien dans le langage. En même temps, on a construit l'arbre (figure 5.2). Figure 5.2: Analyse ascendante

Cours de Compilation

34

Conclusion : ça serait bien d'avoir une table qui nous dit si on décale ou si on réduit, et par quoi, lorsque le pointeur est sur une lettre donnée. Table d'analyse LR (on l'appelle comme ça parce que, de même que la méthode descendante vue précédemment ne permettait d'analyser que les grammaires LL(1), cette méthode va permettre d'analyser les grammaires dites LR). En fait, ce n'est pas vraiment un tableau, c'est plutôt une sorte d'automate, qu'on appelle automate à pile. Cette table va nous dire ce qu'il faut faire quand on lit une lettre a et qu'on est dans un état i - soit on décale Dans ce cas, on empile la lettre lue et on va dans un autre état j. Ce qui sera noté dj - soit on réduit par la règle de production numéro p, c'est à dire qu'on remplace la chaîne en sommet de pile (qui correspond à la partie droite de la règle numéro p) par le non-terminal de la partie gauche de la règle de production, et on va dans l'état j qui dépend du non-terminal en question. On note ça rp - soit on accepte le mot. Ce qui sera noté ACC - soit c'est une erreur. Case vide Construction de la table d'analyse : utilise aussi les ensembles SUIVANT ( et donc PREMIER), plus ce qu'on appelle des fermetures de 0-items. Un 0-item (ou plus simplement item) est une production de la grammaire avec un "." quelque part dans la partie droite. Par exemple (sur la gram ETF) : E -> E . + T ou encore T-> F. ou encore F -> . ( E ) Fermeture d'un ensemble d'items I : 1- Mettre chaque item de I dans Fermeture(I) 2- Pour chaque item i de Fermeture(I) de la forme

.B

Pour chaque production B rajouter l'item B . dans Fermeture(I) 3- Recommencer 2 jusqu'à ce qu'on n'ajoute rien de nouveau

Cours de Compilation

35

Exemple : soit la grammaire des expressions arithmétiques

et soit l'ensemble d'items { T T * . F, E {T T*.F, E E.+T, F .nb, F .(E)}

E.+T}. La fermeture de cet ensemble d'items est :

Transition par X d'un ensemble d'items I :

(I,X)=Fermeture ( tous les items

X.

où

Sur l'exemple ETF : soit I={T T*.F, E E.+T, F (I,F) = { T T*F.} (I,+) = { E E+.T, T .T*F, T .F, F .nb,F

.X .nb, F

est dans I) .(E)} on aura

.(E)}

Collection des items d'une grammaire : 0- Rajouter l'axiome S' avec la production S' S 1- Mettre dans l'item I0 la Fermeture de S' .S}) 2- Mettre I0 dans Collection 3 - Pour chaque I dans Collection faire Pour chaque X tel que (I, X) est non vide ajouter ce (I, X) dans Collection Fin pour 4 - Recommencer 3 jusqu'à ce qu'on n'ajoute rien de nouveau Construction de la table d'analyse SLR : 1- Construire la collection d'items {I0, ... In} 2- l'état i est contruit à partir de Ii : a) pour chaque (Ii , a) = Ij : mettre décalage par j dans la case M[i,a] b) pour chaque (Ii , A) = Ij : mettre aller à j dans la case M[i,A] c) pour chaque . contenu dans I i : pour chaque a de SUIVANT(A) faire mettre reduction par numéro (de la règle ) dans la case M[i,a] Avec notre exemple ETF, on obtient la table d'analyse LR état nb + 0

*

d5

(

)

$

d4

1 2 3

1

d6

2

r2 d7

r2

r2

3

r4 r4

r4

r4

4

d5

E T F

ACC

d4

Cours de Compilation

8 2 3

36

5

r6 r6

r6

r6

6

d5

d4

9 3

7

d5

d4

10

8

d6

d11

9

r1 d7

r1

r1

10

r3 r3

r3

r3

11

r5 r5

r5

r5

Analyseur syntaxique SLR : On part dans l'état 0, et on empile et dépile non seulement les symboles (comme lors de l'analyseur LL) mais aussi les états successifs. Exemple : l'analyse du mot est donnée figure 5.3. La figure 5.4 donne l'analyse du mot 3+4*2$. On peut aussi dessiner l'arbre obtenu (figure 5.5)

Figure: Analyse LR du mot

Figure: Analyse LR du mot

Cours de Compilation

37

Figure 5.5: arbre de dérivation du mot 3+4*2

Remarques : 

cette méthode permet d'analyser plus de grammaires que la méthode descendante (car il y a plus de grammaires SLR que LL)

Cours de Compilation

38

  

en TP on va utiliser un outil (bison) qui construit tout seul une table d'analyse LR (LALR en fait, mais c'est presque pareil) à partir d'une grammaire donnée dans cette méthode d'analyse, ça n'a strictement aucune importance que la grammaire soit récursive à gauche, même au contraire, on préfère. Les grammaires ambigües provoquent des conflits o conflit décalage/réduction : on ne peut pas décider à la lecture du terminal a s'il faut réduire une production ou décaler le terminal o conflit réduction/réduction : on ne peut pas décider à la lecture du terminal a s'il faut réduire une production

ou une production

On doit alors résoudre les conflits en donnant des priorités aux actions (décaler ou réduire) et aux productions. Par exemple, soit la grammaire Soit à analyser 3+4+5. Lorsqu'on lit le 2ième + on a le choix entre o

réduire ce qu'on a déjà lu par . Ce qui nous donnera finalement le calcul (3+4)+5 o décaler ce +, ce qui nous donnera finalement le calcul 3+(4+5). Ici on s'en cague car c'est pareil. Mais bon, + est associatif à gauche, donc on préfèrera réduire. Soit à analyser 3+4*5. Lorsqu'on lit le * on a encore un choix shift/reduce. Si l'on réduit on calcule (3+4)*5, si on décale on calcule 3+(4*5) ! On ne peut plus s'en foutre ! Il faut décaler Soit à analyser 3*4+5. On ne s'en fout pas non plus, il faut réduire ! Bref, il faut mettre quelque part dans l'analyseur le fait que * est prioritaire sur +.

6. Erreurs syntaxiques Beaucoup d'erreurs sont par nature syntaxiques (ou révélées lorsque les unités lexicales provenant de l'analyseur lexical contredisent les règles grammaticales). Le gestionnaire d'erreur doit - indiquer la présence de l'erreur de façon claire et précise - traiter l'erreur rapidement pour continuer l'analyse - traiter l'erreur le plus efficacement possible de manière à ne pas en créer de nouvelles. Heureusement, les erreurs communes (confusion entre deux séparateurs (par exemple entre ; et ,), oubli de ;, ...) sont simples et un mécanisme simple de traitement suffit en général. Cependant, une erreur peut se produire longtemps avant d'être détectée (par exemple l'oubli d'un { ou } dans un programme C). La nature de l'erreur est alors très difficile à déduire. La plupart du temps, le gestionnaire d'erreurs doit deviner ce que le programmeur avait en tête. Lorsque le nombre d'erreur devient trop important, il est plus raisonnable de stopper l'analyse5.4. Il existe plusieurs stratégies de récupération sur erreur : mode panique, au niveau du syntagme5.5, productions d'erreur, correction globale. Une récupération inadéquate peut provoquer une avalanche néfastes d'erreurs illégitimes, c'est à dire d'erreurs qui n'ont pas été faites par le programmeur mais sont la conséquence du changement d'état de l'analyseur lors de la récupération sur erreur. Ces erreurs illégitimes peuvent être syntaxiques mais également

Cours de Compilation

39

sémantiques. Par exemple, pour se récupérer d'une erreur, l'analyseur syntaxique peut sauter la déclaration d'une variable. Lors de l'utilisation de cette variable, l'analyseur sémantique indiquera qu'elle n'a pas été déclarée. 6.1 Récupération en mode panique C'est la méthode la plus simple à implanter. Quand il découvre une erreur, l'analyseur syntaxique élimine les symboles d'entrée les uns après les autres jusqu'à en rencontrer un qui appartienne à un ensemble d'unités lexicales de synchronisation, c'est à dire (par exemple) les délimiteurs (;, end ou }), dont le rôle dans un programme source est clair. Bien que cette méthode saute en général une partie considérable du texte source sans en vérifier la validité, elle a l'avantage de la simplicité et ne peut pas entrer dans une boucle infinie. 6.2 Récupération au niveau du syntagme Quand une erreur est découverte, l'analyseur syntaxique peut effectuer des corrections locales. Par exemple, remplacer une , par un ;, un wihle par un while, insérer un ; ou une (, ...Le choix de la modification à faire n'est pas évident du tout du tout en général. En outre, il faut faire attention à ne pas faire de modifications qui entraînerait une boucle infinie (par exemple décider d'insérer systématiquement un symbole juste avant le symbole courant). L'inconvénient majeure de cette méthode est qu'il est pratiquement impossible de gérer les situations dans lesquelles l'erreur réelle s'est produite bien avant le point de détection. On implante cette récupération sur erreur en remplissant les cases vides des tables d'analyse par des pointeurs vers des routines d'erreur. Ces routines remplacent, insèrent ou suppriment des symboles d'entrée et émettent les messages appropriés. Exemple : grammaire des expressions arithmétiques

La table d'analyse LR avec routines d'erreur est état nb +

*

(

)

$

E

e1

1

0

d3 e1 e1 d2 e2

1

e3 d4 d5 e3 e2 ACC

2

d3 e1 e1 d2 e2

e1

3

r4 r4 r4 r4 r4

r4

4

d3 e1 e1 d2 e2

e1

7

5

d3 e1 e1 d2 e2

e1

8

6

e3 d4 d5 e3 d9

e4

7

r1 r1 d5 r1 r1

r1

8

r2 r2 r2 r2 r2

r2

9

r3 r3 r3 r3 r3

r3

Cours de Compilation

6

40

Les routines d'erreur étant : e1 : (routine appelée depuis les états 0, 2, 4 et 5 lorsque l'on rencontre un opérateur ou la fin de chaîne d'entrée alors qu'on attend un opérande ou une parenthèse ouvrante) Emettre le diagnostic operande manquant Empiler un nombre quelconque et aller dans l'état 3 e2 : (routine appelée depuis les états 0,1,2,4 et 5 à la vue d'une parenthèse fermante) Emettre le diagnostic parenthèse fermante excédentaire Ignorer cette parenthèse fermante e3 : (routine appelée depuis les états 1 ou 6 lorsque l'on rencontre un nombre ou une parenthèse fermante alors que l'on attend un opérateur) Emettre le diagnostic opérateur manquant Empiler + (par exemple) et aller à l'état 4 e4 : (routine appelée depuis l'état 6 qui attend un opérateur ou une parenthèse fermante lorsque l'on rencontre la fin de chaîne) Emettre le diagnostic parenthèse fermante oubliée Empiler une parenthèse fermante et aller à l'état 9 6.3 Productions d'erreur Si l'on a une idée assez précise des erreurs courantes qui peuvent être rencontrées, il est possible d'augmenter la grammaire du langage avec des productions qui engendrent les constructions erronées. Par exemple (pour un compilateur C) : if E I

(erreur : il manque les parenthèses)

if ( E ) then I (erreur : il n'y a pas de then en C)

6.4 Correction globale Dans l'idéal, il est souhaitable que le compilateur effectue aussi peu de changements que possible. Il existe des algorithmes qui permettent de choisir une séquence minimale de changements correspondant globalement au coût de correction le plus faible. Malheureusement, ces méthodes sont trop coûteuses en temps et en espace pour être implantées en pratique et ont donc uniquement un intérêt théorique. En outre, le programme correct le plus proche n'est pas forcément celui que le programmeur avait en tête ...

Cours de Compilation

41

CHAPITRE 5.

TRADUCTION DIRIGEE PAR LA SYNTAXE

Un schéma de traduction dirigée par la syntaxe (TDS) est un formalisme permettant d'associer des actions à une production d'une règle de grammaire.

1. Définition dirigée par la syntaxe Chaque symbole de la grammaire (terminal ou non) possède un ensemble d'attributs . Chaque règle de production de la grammaire possède un ensemble de règles sémantiques qui permettent de calculer la valeur des attributs associés aux symboles apparaissant dans la production.

Une règle sémantique est une suite d'instructions algorithmiques : elle peut contenir des affectations, des si-sinon, des instructions d'affichage, ... Définition 6.1 On appelle définition dirigée par la syntaxe (DDS), la donnée d'une grammaire et de son ensemble de règles sémantiques. On notera X.a l'attribut a du symbole X. S'il y a plusieurs symboles X dans une production, on , et X(0) s'il est en partie gauche.

les notera

Exemple : Grammaire attributs : nba (calcul du nombre de a), nbc (du nombre de c) une DDS permettant de calculer ces attributs est alors : production

Règle sémantique S(0).nba:=S(1).nba+1 S(0).nbc:=S(1).nbc S(0).nba:=S(1).nba+1 S(0).nbc:=S(1).nbc S(0).nba:=S(1).nba+S(2).nba+1 S(0).nbc:=S(1).nbc+S(2).nbc+2 S(0).nba:=0 S(0).nbc:=0

2. Arbre syntaxique décoré Définition 6.2 On appelle arbre syntaxique décoré un arbre syntaxique sur les noeuds duquel on rajoute la valeur de chaque attribut.

Cours de Compilation

42

Exemple : la figure 6.1 donne l'arbre syntaxique décoré pour le mot acaacabb et la DDS définie précédemment. Figure 6.1: Calcul du nombre de a et c pour acaacabb

3. Attributs synthétisés et hérités On distingue deux types d'attributs : les synthétisés et les hérités. 3.1 Attributs synthétisés 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. Sur l'arbre décoré : la valeur d'un attribut en un noeud se calcule en fonction des attributs de ses fils. C'est à dire que le le calcul de l'attribut se fait des feuilles vers la racine. Les attributs synthétisés peuvent être facilement évalués lors d'une analyse ascendante (donc par exemple avec yacc/bison). Mais pas du tout lors d'une analyse descendante. Dans l'exemple donné, nba et nbc sont des attributs synthétisés. 3.2 Attributs hérités Un attribut est dit hérité lorsqu'il est calculé à partir des attributs du non terminal de la partie gauche, et éventuellement des attributs d'autres non terminaux de la partie droite. Sur l'arbre décoré : la valeur d'un attribut à un noeud se calcule en fonction des attributs des frères et du père. C'est à dire que le calcul de l'attribut se fait de la racine vers les feuilles. Si les attributs d'un noeud donné ne dépendent pas des attributs de ses frères droits, alors les attributs hérités peuvent être facilement évalués lors d'une analyse descendante, mais pas lors d'une analyse ascendante. Remarque : l'axiome de la grammaire doit être de la forme pour pouvoir initialiser le calcul.

(un seul non-terminal)

Figure 6.2: Niveau d'imbrication des )

Cours de Compilation

43

Exemple : calcul du niveau d'imbrication des ) dans un système de parenthèses bien formé.

Grammaire : DDS : production action sémantique S.nb:=0 S(1).nb:=S(0).nb+1 S(2).nb:=S(0).nb écrire S.nb La figure 6.2 donne l'arbre décoré pour le mot (())(()())()

4. Graphe de dépendances Une DDS peut utiliser à la fois des attributs synthétisés et des attributs hérités. Il n'est alors pas forcémment évident de s'y retrouver pour calculer ces attributs. L'attribut machin dépend de l'attribut bidule qui lui-même dépend de l'attribut truc ...Il faut établir un ordre d'évaluation des règles sémantiques. On construira ce qu'on appelle un graphe de dépendances. Exemple : Soit la DDS suivante (totalement stupide) qui fait intervenir deux attributs hérités h et r et deux attributs synthétisés s et t. production

action sémantique

Cours de Compilation

44

E.h:=2*E.s+1 S.r:=E.t E(0).s:=E(1).s+E(2).s E(0).t:=3*E(1).t-E(2).t E(1).h:=E(0).h E(2).h:=E(0).h+4 nombre E.s:= nombre E.t:=E.h +1 La figure 6.3 donne un exemple d'arbre décoré. Figure 6.3: Attributs hérités et synthétisés

Définition 6.3 On appelle graphe de dépendances le graphe orienté représentant les interdépendances entre les divers attributs. Le graphe a pour sommet chaque attribut. Il y a un arc de a à b ssi le calcul de b dépend de a. On construit le graphe de dépendances pour chaque règle de production, ou bien directement le graphe de dépendances d'un arbre syntaxique donné. C'est ce dernier qui permet de voir dans quel ordre évaluer les attributs. Mais il est toujours utile d'avoir le graphe de dépendances pour chaque règle de production afin d'obtenir "facilement" le graphe pour n'importe quel arbre syntaxique. Figure 6.4: Graphes de dépendances pour les productions

Figure 6.5: Graphe de dépendances de l'arbre syntaxique

Cours de Compilation

45

: Sur l'exemple : La figure 6.4 donne le graphe de dépendances pour chaque règle de production, et la figure 6.5 le graphe de dépendance de l'arbre syntaxique. Remarque : si le graphe de dépendance contient un cycle, l'évaluation des attributs est alors impossible. Exemple : Soit la DDS suivante (a hérité et b synthétisé) production action sémantique S.a:=S.b S(0).b:=S(1).b+S(2).b+T.b S(1).a:=S(0).a S(2).a:=S(0).a+1 T.a:=S(0).a+S(0).b+S(1).a T(0).b:=P.a+P.b P.a:=T(0).a+3 T(1).a:=...

Le graphe de dépendance associé peut contenir un cycle (voir figure 6.6), le calcul est donc impossible. Figure 6.6: Cycle dans le graphe de dépendance

Cours de Compilation

46

5. Evaluation des attributs 5.1 Après l'analyse syntaxique On peut faire le calcul des attributs indépendamment de l'analyse syntaxique : lors de l'analyse syntaxique, on construit (en dur) l'arbre syntaxique6.1, puis ensuite, lorsque l'analyse syntaxique est terminée, le calcul des attributs s'effectue sur cet arbre par des parcours de cet arbre (avec des aller-retours dans l'arbre suivant l'ordre d'évaluation des attributs). Cette méthode est très coûteuse en mémoire (stockage de l'arbre). Mais l'avantage est que l'on n'est pas dépendant de l'ordre de visite des sommets de l'arbre syntaxique imposé par l'analyse syntaxique (une analyse descendante impose un parcours en profondeur du haut vers le bas, de la gauche vers la droite, une analyse ascendante un parcours du bas vers le haut, ...). On peut également construire l'arbre en dur pour une sous-partie seulement du langage.

5.2 Pendant l'analyse syntaxique On peut évaluer les attributs en même tant que l'on effectue l'analyse syntaxique. Dans ce cas, on utilisera une pile pour conserver les valeurs des attributs, cette pile pouvant être la même que celle de l'analyseur syntaxique, ou une autre. Cette fois-ci, l'ordre d'évaluation des attributs est tributaire de l'ordre dans lequel les noeuds de l'arbre syntaxique sont "crées"6.2 par la méthode d'analyse. Exemple avec un attribut synthétisé : évaluation d'une expression arithmétique avec une analyse ascendante. Une TDS est

production

action sémantique

traduction avec une pile

E(0).val:=E(1).val+T.val tmpT = depiler() tmpE = depiler() empiler(tmpE+tmpT) E(0).val:=E(1).val-T.val tmpT = depiler() tmpE = depiler() empiler(tmpE-tmpT) E.val:=T.val

Cours de Compilation

47

T(0).val:=T(1).val*F.val tmpF = depiler() tmpT = depiler() empiler(tmpT*tmpF) T.val:=F.val F.val:=E.val nb

F.val:=nb

empiler(nb)

L'analyse syntaxique s'effectue à partir de la table d'analyse LR donnée. Par exemple, pour le mot 2*(10+3) on obtiendra :

Pile

entrée action

pile des attributs

2*(10+3)$ d5

$ $

2

*(10+3)$ r6 :

$

F

*(10+3)$ r4 :

2

$

T

*(10+3)$ d7

2

$

T

*

(10+3)$ d4

2

$

T

*

(

10+3)$ d5

2

$

T

*

(

10

+3)$ r6 :

$

T

*

(

F

+3)$ r4 :

2 10

$

T

*

(

T

+3)$ r2 :

2 10

$

T

*

(

E

+3)$ d6

2 10

$

T

*

(

E

+

3)$ d5

2 10

$

T

*

(

E

+

3

)$ r6 :

$

T

*

(

E

+

F

)$ r4 :

2 10 3

$

T

*

(

E

+

T

)$ r1 :

2 13

$

T

*

(

E

)$ d11

2 13

$

T

*

(

E

$

T

*

F

$ $

)

$

nb

nb

nb

r5 :

2

2 10

2 10 3

2 13

$ r3 :

26

T

$ r2 :

26

E

$ ACCEPTÉ !!!

26

Cours de Compilation

48

Exemple avec un attribut hérité : reprenons l'attribut hérité qui calcule le niveau d'imbrication des ) dans un système de parenthèses bien formé.

production action sémantique

traduction avec une pile

S.nb:=0

empiler(0)

empiler(sommet()+1) écrire S.nb

Ecrire depiler()

On effectue une analyse descendante, donc il nous faut la table d'analyse LL : PREMIER(S')=PREMIER donc

(

)

, SUIVANT

et SUIVANT

,

$

S' S Analysons le mot (()(()))()

Pile

entrée action

pile des attributs écritures

$ S'

(()(()))()$

0

$S

(()(()))()$

01

$ S)S(

(()(()))()$

01

$ S)S

()(()))()$

012

$ S)S)S(

()(()))()$

012

$ S)S)S

)(()))()$

01

$ S)S)

)(()))()$

01

$ S)S

(()))()$

012

$ S)S)S(

(()))()$

012

$ S)S)S

()))()$

0123

$ S)S)S)S(

()))()$

0123

$ S)S)S)S

)))()$

012

$ S)S)S)

)))()$

012

Cours de Compilation

2

3

49

$ S)S)S

))()$

01

$ S)S)

))()$

01

$ S)S

)()$

0

$ S)

)()$

0

$S

()$

01

$ S)S(

()$

01

$ S)S

)$

0

$ S)

)$

0

$S

$

$

$

2

1

1

0

FINI Mais, vu que les attributs synthétisés s'évaluent avec une analyse ascendante et les attributs hérités avec une analyse descendante, comment on fait quand on a à la fois des attributs synthétisés et hérités ? Hein ? Souvent, on peut utiliser des attributs synthétisés qui font la même chose que les hérités que l'on voulait. Exemple : compter le nombre de bit à 1 dans un mot binaire.

Grammaire : DDS avec attribut hérité : production action sémantique B.nb:=0 B(1).nb:=B(0).nb B(1).nb:=B(0).nb+1 écrire B.nb DDS avec attribut synthétisé : production action sémantique écrire B.nb B(0).nb:=B(1).nb

Cours de Compilation

50

B(0).nb:=B(1).nb+1 B.nb:=0 La figure 6.7 donne les arbres décorés pour le mot 10011. Figure 6.7: Arbre décoré pour 10011 avec des attributs (a)hérités (b) synthétisés

Parfois, il est nécessaire de modifier la grammaire. Par exemple, considérons une DDS de typage de variables dans une déclaration Pascal de variables (en Pascal, une déclaration de variable consiste en une liste d'identificateurs séparés par des virgules, suivie du caractère ':', suivie du type. Par exemple : a,b : integer)

production :T

Id

action sémantique L.type:=T.type mettre dans la table des symboles le type L.type pour Id

, Id

L(1).type:=L(0).type mettre dans la table des symboles le type L(0).type pour Id

integer T.type:=entier char

T.type:=caractere

C'est un attribut hérité. Pas possible de trouver un attribut synthétisé faisant la même chose avec cette grammaire. Changeons la grammaire !

production

action sémantique

Id L

mettre dans la table des symboles le type L.type pour Id

, Id L

L(0).type:=L(1).type mettre dans la table des symboles le type L(1).type pour Id

:T

L.type:=T.type

Cours de Compilation

51

integer T.type:=entier char

T.type:=caractere

Et voilà ! Mais bon, ce n'est pas toujours évident de concevoir une DDS n'utilisant que des attributs hérités ou de concevoir une autre grammaire permettant de n'avoir que des synthétisés. Heureusement, il existe des méthodes automatiques qui transforment une DDS avec des attributs hérités et synthétisés en une DDS équivalente n'ayant que des attributs synthétisés. Mais nous n'en parlerons pas ici, cf bouquins. Une autre idée peut être de faire plusieurs passes d'analyses, suivant le graphe de dépendances de la DDS. Par exemple (DDS donnée précédemment) : une passe ascendante permettant d'évaluer un certain attribut synthétisé s, puis une passe descendante pour évaluer des attributs hérités h et r, puis enfin un passe ascendante pour évaluer un attribut synthétisé t.

6. Exercices 1. (a) Ecrire une DDS n'utilisant que des attributs synthétisés qui calcule le nombre de a contenus dans un mot de (a|b)*. Donner un arbre décoré pour le mot bbabaab (b) Même question avec des attributs hérités. 2. Considérons la grammaire suivante qui génère des expressions arithmétiques formées de constantes entières et réelles et de l'opérateur +

Lorsque l'on additionne 2 entiers, le résultat est un entier, sinon c'est un réel (a) Ecrire une DDS donnant le type de l'expression (b) Donner un arbre décoré pour le mot 5+3.05+10 3. On considère un robot qui peut être commandé pour se déplacer d'un pas vers l'est, l'ouest, le nord ou le sud à partir de sa position courante. Une séquence de tels déplacements peut être engendrée par la grammaire debut L fin est | sud | nord | ouest La position du robot est donnée dans le plan (le nord étant en haut). (0,0) est la position initiale du robot. (a) Ecrire une DDS affichant les positions successives (x,y) du robot. (b)

Cours de Compilation

52

Donner un arbre décoré pour le mot debut est est nord ouest sud sud nord ouest fin

4. (a) Ecrire une DDS donnant le nombre maximum de a consécutifs dans un mot de (a|b)* (exemple : pour aababaaaba il faut donner 3) (b) Donner un arbre décoré pour le mot aababaaaba 5. Ecrire une DDS permettant de traduire un entier sous forme binaire en sa valeur décimale. Donner un exemple d'arbre décoré. 6. Même exercice que précédemment avec des réels. 7. Considérons la grammaire suivante qui génère des expressions arithmétiques formées des opérateurs + et *, et de la variable x et de constantes : E E+T|T T T*F|F F nb | x (a) Ecrire une DDS qui calcule la dérivée d'une telle expression (b) Donner un arbre syntaxique décoré pour la chaîne 2*x*x+5*x+3

Cours de Compilation

53

CHAPITRE 6.

L'OUTIL YACC/BISON

De nombreux outils ont été bâtis pour construire des analyseurs syntaxiques à partir de grammaires. C'est à dire des outils qui construisent automatiquement une table d'analyse à partir d'une grammaire donnée. YACC est un utilitaire d'unix, bison est un produit gnu. YACC/bison accepte en entrée la description d'un langage sous forme de règles de productions et produit un programme écrit dans un langage de haut niveau (ici, le langage C) qui, une fois compilé, reconnaît des phrases de ce langage (ce programme est donc un analyseur syntaxique). YACC signifie Yet Another Compiler Compiler, c'est à dire encore un compilateur de compilateur. Cela n'est pas tout à fait exact, yacc/bison tout seul ne permet pas d'écrire un compilateur, il faut rajouter une analyse lexicale (à l'aide de (f)lex par exemple) ainsi que des actions sémantiques pour l'analyse sémantique et la génération de code. YACC/bison construit une table d'analyse LALR qui permet de faire une analyse ascendante. Il utilise donc le modèle décallages-réductions.

1. Structure du fichier de spécifications bison %{ déclaration (en C) de variables, constantes, inclusions de fichiers, %} déclarations des unités lexicales utilisées déclarations de priorités et de types %% règles de production et actions sémantiques %% routines C et bloc principal Les symboles terminaux utilisables dans la description du langage sont - des unités lexicales que l'on doit impérativement déclarer par %token nom. Par exemple : %token MC_sinon %token NOMBRE

- des caractères entre quotes. Par exemple : '+' 'a' - des chaînes de caractères entre guillemets. Par exemple : "+=" "while" Les symboles non-terminaux sont les caractères ou les chaînes de caractères non déclarées comme unités lexicales. yacc/bison fait la différence entre majuscules et minuscules. SI et si ne désignent pas le même objet. Les règles de production sont des suites d'instructions de la forme non-terminal : | | ;

prod1 prod2 ... prodn

Les actions sémantiques sont des instructions en C insérées dans les règles de production. Elles sont exécutées chaque fois qu'il y a réduction par la production associée.

Cours de Compilation

54

Exemples : G : S B 'X' {printf("mot reconnu");} ; S : A {print("reduction par A");} T {printf("reduction par T");} 'a' ;

La section du bloc principal doit contenir une fonction yylex() effectuant l'analyse lexicale du texte, car l'analyseur syntaxique l'appelle chaque fois qu'il a besoin du terminal suivant. On peut - soit écrire cette fonction - soit utiliser la fonction produite par un compilateur (f)lex appliqué à un fichier de spécifications nom.l. Dans ce cas, il suffira d'inclure le fichier lex.yy.c produit par (f)lex et de rajouter la bibliothèque (f)lex lors de la compilation C du fichier nom.tab.c (avec cc nom.tab.c -ly -l(f)l).

2. Attributs A chaque symbole (terminal ou non) est associé une valeur (de type entier par défaut). Cette valeur peut être utilisée dans les actions sémantiques (comme un attribut synthétisé). Le symbole $$ référence la valeur de l'attribut associé au non-terminal de la partie gauche, tandis que $i référence la valeur associée au i-ème symbole (terminal ou non-terminal) ou action sémantique de la partie droite. Exemple : expr : expr '+' expr { tmp=$1+$3;} '+' expr { $$=tmp+$6;}; Par défaut, lorsqu'aucune action n'est indiquée, yacc/bison génère l'action {$$=$1;}

3. Communication avec l'analyseur lexical : yylval L'analyseur syntaxique et l'analyseur lexical peuvent communiquer entre eux par l'intermédiaire de la variable int yylval. Dans une action lexicale (donc dans le fichier (f)lex par exemple), l'instruction return(unité) permet de renvoyer à l'analyseur syntaxique l'unité lexicale unité. La valeur de cette unité lexicale peut être rangée dans yylval. L'analyseur syntaxique prendra automatiquement le contenu de yylval comme valeur de l'attribut associé à cette unité lexicale. La variable yylval est de type YYSTYPE (déclaré dans la bibliothèque yacc/bison) qui est un int par défaut. On peut changer ce type par un #define YYSTYPE autre_type_C ou encore par %union { champs d'une union C } qui déclarera automatiquement YYSTYPE comme étant une telle union.

Par exemple %union { int entier; double reel; char * chaine; } Cours de Compilation

55

permet de stocker dans yylval à la fois des int, des double et des char *. L'analyseur lexical pourra par exemple contenir {nombre}

{ yylval.entier=atoi(yytext); return NOMBRE; }

Le type des lexèmes doit alors être précisé en utilisant les noms des champs de l'union %token NOMBRE %token IDENT CHAINE COMMENT

On peut également typer des non-terminaux (pour pouvoir associer une valeur de type autre que int à un non-terminal) par %type S %type expr

4. Variables, fonctions et actions prédéfinies YYACCEPT : instruction qui permet de stopper l'analyseur syntaxique. Dans ce cas, yyparse retourne la valeur 0 (succés). YYABORT : instruction qui permet également de stopper l'analyseur. yyparse retourne alors 1, ce qui peut être utilisé pour signifier l'échec de l'analyseur. yyparse() : appel de l'analyseur syntaxique. main() : le main par défaut se contente d'appeler yyparse(). L'utilisateur peut écrire son propre main dans la partie du bloc principal. %start non-terminal : action pour signifier quel non-terminal est l'axiome. Par défaut, c'est le premier décrit dans les règles de production.

5. Conflits shift-reduce et reduce-reduce Lorsque l'analyseur est confronté à des conflits, il rend compte du type et du nombre de conflits rencontrés : > bison exemple.y conflicts: 6 shift/reduce, 2 reduce/reduce

Il y a un conflit reduce/reduce lorsque le compilateur a le choix entre (au moins) deux productions pour réduire une chaîne. Les conflits shift/reduce apparaissent lorsque le compilateur a le choix entre réduire par une production et décaller le pointeur sur la chaîne d'entrée. yacc/bison résoud les conflits de la manière suivante : conflit reduce/reduce : la production choisie est celle apparaissant en premier dans la spécification. conflit shift/reduce : c'est le shift qui est effectué. Pour voir comment bison a résolu les conflits, il est nécessaire de consulter la table d'analyse qu'il a construit. Pour celà, il faut compiler avec l'option -v. Le fichier contenant la table s'appelle y.output

6. Associativité et priorité des symboles terminaux On peut essayer de résoudre soit même les conflits (ou tout du moins préciser comment on veut les résoudre) en donnant des associativités (droite ou gauche) et des priorités aux symboles terminaux. Les déclarations suivantes (dans la section des définitions)

Cours de Compilation

56

%left term1 term2 %right term3 %left term4 %nonassoc term5 indiquent que les symboles terminaux term1, term2 et term4 sont associatifs à gauche, term3 est associatif à droite, alors que term5 n'est pas associatif. Les priorités des symboles sont données par l'ordre dans lequel apparaît leur déclaration d'associativité, les premiers ayant la plus faible priorité. Lorsque les symboles sont dans la même déclaration d'associativité, ils ont la même priorité. La priorité (ainsi que l'associativité) d'une production est définie comme étant celle de son terminal le plus à droite. On peut forcer la priorité d'une production en faisant suivre la production de la déclaration %prec terminal-ou-unite-lexicale ce qui a pour effet de donner comme priorité (et comme associativité) à la production celle du terminal-ou-unite-lexicale (ce terminal-ou-unitelexicale devant être défini, même de manière factice, dans la partie Ib). Un conflit shift/reduce, i.e. un choix entre entre une réduction et un décallage d'un symbole d'entrée a, est alors résolu en appliquant les règles suivantes : si la priorité de la production est supérieure à celle de a, c'est la réduction qui est effectuée si les priorités sont les mêmes et si la production est associative à gauche, c'est la réduction qui est effectuée dans les autres cas, c'est le shift qui est effectué.

7. Récupération des erreurs Lorsque l'analyseur produit par bison rencontre une erreur, il appelle par défaut la fonction yyerror(char *) qui se contente d'afficher le message parse error, puis il s'arrête. Cette fonction peut être redéfinie par l'utilisateur. Il est possible de traiter de manière plus explicite les erreurs en utilisant le mot clé bison error. On peut rajouter dans toute production de la forme

une production

error

Dans ce cas, une production d'erreur sera traitée comme une production classique. On pourra donc lui associer une action sémantique contenant un message d'erreur. Dès qu'une erreur est rencontrée, tous les caractères sont avalés jusqu'à rencontrer le caractère correspondant à . Exemple : La production instr error ; indique à l'analyseur qu'à la vue d'une erreur, il doit sauter jusqu'au delà du prochain ";" et supposer qu'une instr vient d'être reconnue. La routine yyerrok replace l'analyseur dans le mode normal de fonctionnement c'est à dire que l'analyse syntaxique n'est pas interrompue.

8. Options de compilations Bison l'option -v produit un fichier nom.output contenant un descriptif des conflits shift/reduce et reduce/reduce détectés et indique de quelle façon ils ont été résolus. Il est fortement conseillé de consulter ce fichier afin de vérifier que les conflits sont résolus comme on le désire. Cours de Compilation

57

l'option -d produit un fichier nom.tab.h contenant les définitions (sous forme de #define) des unités lexicales rencontrées et du type YYSTYPE s'il est redéfini.

9. Exemples de fichier .y Cet exemple reconnaît les mots qui ont un nombre pair de a et impair de b. Le mot doit se terminer par le symbole $. Cet exemple ne fait pas appel à la fonction yylex générée par le compilateur (f)lex. %% mot : PI '$' ;

{printf("mot accepte\n");YYACCEPT;}

PP : 'a' IP | 'b' PI | /* vide */ ; IP : 'a' PP | 'b' II | 'a' ; PI : 'a' II | 'b' PP | 'b' ; II : 'a' PI | 'b' IP | 'a' 'b' | 'b' 'a' ; %% int yylex() { char car=getchar(); if (car=='a' || car=='b' || car=='$') return(car); else printf("ERREUR : caractere non reconnu : %c ",car); } Ce deuxième exemple lit des listes d'entiers précédées soit du mot somme, soit du mot produit. Une liste d'entiers est composée d'entiers séparés par des virgules et se termine par un point. Lorsque la liste débute par somme, l'exécutable doit afficher la somme des entiers, lorsqu'elle débute par produit, il doit en afficher le produit. Le fichier doit se terminer par $. Cet exemple utilise la fonction yylex générée par le compilateur flex à partir du fichier de spécification exemple2.l suivant %{ #include int nbligne=0; %} chiffre [0-9] entier {chiffre}+ espace [ \t] %% somme return(SOMME); produit return(PRODUIT);

Cours de Compilation

58

\n [.,] {entier}

nbligne++; return(yytext[0]); { yylval=atoi(yytext); return(NOMBRE);

} {espace}+ /* rien */; "$" return(FIN); . printf("ERREUR ligne %d : %c inconnu\n",nbligne,yytext[0]); %% Le fichier de spécifications yacc est alors le suivant %token SOMME %token PRODUIT %token NOMBRE %token FIN %% texte : liste texte | FIN {printf("Merci et a bientot\n");YYACCEPT;} ; liste : SOMME sentiers '.' {printf("la somme est %d\n",$2);} | PRODUIT pentiers '.' {printf("le produit est %d\n",$2);} ; sentiers : sentiers ',' NOMBRE {$$=$1+$3;} | NOMBRE {$$=$1;} ; pentiers : pentiers ',' NOMBRE {$$=$1*$3;} | NOMBRE {$$=$1;} ; %% #include "lex.yy.c"

Le Makefile pour compiler tout ça est CC=gcc exemple2 : lex.yy.c exemple2.tab.c $(CC) exemple2.tab.c -o exemple2 -ly -lfl lex.yy.c : exemple2.l flex exemple2.l exemple2.tab.c : exemple2.y lex.yy.c bison exemple2.y

10. Exercices 1. Ecrire un fichier de spécification Bison permettant de reconnaitre si une expression est correctement parenthésée ou non. 2. Modifier l'exercice précédent pour afficher les niveaux d'imbrication. Exemple : l'expression (()()(()))() doit donner 1 2 2 2 3 1.

Cours de Compilation

59

3. Modifier l'exercice 1 en considérant les mots begin et end au lieu des parenthèses. 4. Mini-calculateur de bureau. On considère la grammaire des expressions arithmétiques suivante :

NOMBRE (où NOMBRE est un nombre entier) (a) Écrire un programme qui indique si une expression arithmétique donnée est correcte ou non. (b) Compléter les fichiers de spécifications précédents pour  

permettre la reconnaissance de séquences d'expressions, à raison d'une par ligne, autoriser les lignes blanches entre les expressions.

(c) Compléter les fichiers de spécifications précédents pour que le programme retourne la valeur de chaque expression arithmétique rentrée, en considérant qu'on ne traite que des entiers. (d) Même question en considérant également des nombres réels. 5. Même exercice que précédemment en considérant cette fois la grammaire ambiguë suivante : NOMBRE

Cours de Compilation

60

CHAPITRE 7.

ANALYSE SEMANTIQUE

Certaines propriétés fondamentales du langage source à traduire ne peuvent être décrites à l'aide de la seule grammaire hors contexte du langage, car justement elles dépendent du contexte. Par exemple (exemples seulement, car cela dépend du langage source ) : - on ne peut pas utiliser dans une instruction une variable qui n'a pas été déclarée au préalable - on ne peut pas déclarer deux fois une même variable - lors d'un appel de fonction, il doit y avoir autant de paramètres formels que de paramètres effectifs, et leur type doit correspondre - on ne peut pas multiplier un réel avec une chaîne Le rôle de l'analyse sémantique (que l'on appelle aussi analyse contextuelle) est donc de vérifier ces contraintes. Elle se fait en général en même temps que l'analyse syntaxique, à l'aide d'actions sémantiques insérées dans les règles de productions (i.e. à l'aide de TDS). Les contraintes à vérifier dépendant fortement des langages, il n'y a pas vraiment de méthode universelle pour effectuer l'analyse sémantique. Dans ce chapitre, nous donnerons une liste de problèmes rencontrés plutôt que des solutions qui marchent à tous les coups.

1. Portée des identificateurs On appelle portée d'un identificateur la (les) partie(s) du programme où il est valide et a la signification qui lui a été donné lors de sa déclaration. Cette notion de validité et visibilité dépend bien sûr des langages. Par exemple, en Cobol tous les identificateurs sont partout visibles. En Fortran, C, Pascal, ..., les identificateurs qui sont définis dans un bloc ne sont visibles qu'à l'intérieur de ce bloc; un identificateur déclaré dans un sous-bloc masque un identificateur de même nom déclaré dans un bloc de niveau inférieur. En Algol, Pascal, Ada et dans les langages fonctionnels, il peut y avoir une imbrication récursive des blocs sur une profondeur quelconque (cf letrec)... Par exemple, l'analyseur sémantique doit vérifier si chaque utilisation d'un identificateur est légale, ie si cet identificateur a été déclaré et cela de manière unique dans son bloc. Il faut donc mémoriser tous les symboles rencontrés au fur et à mesure de l'avancée dans le texte source. Pour cela on utilise une structure de données adéquate que l'on appelle une table des symboles. La table des symboles contient toutes les informations nécessaires sur les symboles (variables, fonctions, ...) du programme : - identificateur (le nom du symbole dans le programme) - son type (entier, chaîne, fonction qui retourne un réel,...) - son emplacement mémoire - si c'est une fonction : la liste de ses paramètres et leurs types - ... Lors de la déclaration 8.1 d'une variable, elle est stockée dans cette table (avec les informations que l'on peut déja connaitre). Il faut préalablement regarder si cette variable n'est pas déjà contenue dans la table. Si c'est le cas, c'est une erreur. Lors de l'utilisation d'une variable, il faut vérifier qu'elle fait partie de la table (on peut alors récupérer son type, donner ou modifier une valeur, ...). Il faut donc munir la table des symboles de procédures d'ajout, suppression et recherche. La

Cours de Compilation

61

structure d'une table des symboles peut aller du plus simple au plus compliqué (simple tableau trié ou non trié, liste linéaire, forme arborescente, table d'adressage dispersé (avec donc des fonctions de hachage), ...), cela dépend de la complexité du langage à compiler, de la rapidité que l'on souhaite pour le compilateur, de l'humeur du concepteur du compilateur, .... Dans certains langages, on peut autoriser qu'un identificateur ne soit pas déclaré dans son bloc B à condition qu'il ait été déclaré dans un bloc d'un niveau inférieur qui contient B. Il faut également gérer le cas où un identificateur est déclaré dans au moins deux blocs différents B contenu dans B' (dans ce cas, l'identificateur de plus haut niveau cache les autres). On peut alors utiliser une pile pour empiler la table des symboles et gérer ainsi la portée des identificateurs. Mais il y a d'autres méthodes, comme par exemple coder la portée dans la table des symboles, pour chaque symbole. Figure 9.1: Portée des identificateurs : empilement de la table des symboles

2. Contrôle de type Lorsque le langage source est un langage typé, il faut vérifier la pertinence des types des objets manipulés dans les phrases du langage. Exemples : en C, on ne peut pas additionner un double et un char *, multiplier un int et un struct, indicer un tableau avec un float, affecter un struct * à un char ... Certaines opérations sont par contre possibles : affecter un int à un double, un char à un int, ... (conversions implicites). Définition 8.1 On appelle statique un contrôle de type effectué lors de la compilation, et dynamique un contrôle de type effectué lors de l'exécution du programme cible.

Cours de Compilation

62

Le contrôle dynamique est à éviter car il est alors très difficile pour le programmeur de voir d'où vient l'erreur (quand il y en a une). En pratique cependant, certains contrôles ne peuvent être fait que dynamiquement. Par exemple, si l'on a int tab[10]; int i; ... ... tab[i] ...

le compilateur ne pourra pas garantir en général8.2 qu'à l'exécution la valeur de i sera comprise entre 0 et 9. Exemples de TDS de contrôle de type : Règle de production action sémantique I.type :=

si Id.type=E.type alors vide sinon erreur_type_incompatible(ligne,Id.type,E.type)

I(0).type := si E.type=booleen alors I(1).type sinon erreur_type(ligne,...) E.type :=

Recherche_Table(Id)

E(0).type := si E(1).type=entier et E(2).type=entier alors entier sinon si (E(1).type ou (E(2).type

reel et E(1).type reel et E(2).type

entier) entier) alors

erreur_type_incompatible(ligne,E(1).type,E(2).type) sinon reel E(0).type := si E(1).type=entier et E(2).type=entier alors entier sinon erreur_type(ligne,...)

Ça a l'air assez simple, non ? Maintenant imaginons le boulot du compilateur C lorsqu'il se trouve confronté à un truc du genre s->t.f(p[*i])-&j Il faut alors trouver une représentation pratique pour les expressions de type. Exemple : codage des expressions de type par Ritchie et Johnson pour un compilateur C. On considère les constructions de types suivantes : pointeur(t) : un pointeur vers le type t fretourne(t) : une fonction (dont les arguments ne sont pas spécifiés) qui retourne un objet de type t tableau(t) : un tableau (de taille indeterminée) d'objets de type t

Cours de Compilation

63

Ces constructeurs étant unaires, les expressions de type formés en les appliquant à des types de base ont une structure très uniforme. Par exemple caractère fretourne(caratère) tableau(caractère) fretourne(pointeur(entier)) tableau(pointeur(fretourne(entier))) Chaque constructeur peut être représentée par une séquence de bits selon un procédé d'encodage simple, de même que chaque type de base. Par exemple constructeur codage pointeur

01

tableau

10

fretourne

11

type de base codage entier

0000

booléen

0001

caractère

0010

réél

0011

Les expressions de type peuvent maintenant être encodée comme des séquences de bit expression de type

codage

caractère 000000 0010 fretourne(caractère) 000011 0001 pointeur(fretourne(caractère)) 000111 0001 tableau(pointeur(fretourne(caractère))) 100111 0001 Cette méthode a au moins deux avantages : économie de place et il y a une trace des différents constructeurs appliqués.

3. Surcharge d'opérateurs et de fonctions Des opérateurs (ou des fonctions) peuvent être surchargés c'est à dire avoir des significations différentes suivant le contexte. Par exemple, en C, la division est la division entière si les deux opérandes sont de type entier, et la division réelle sinon. Dans certains langages8.3, on peut redéfinir un opérateur standard, par exemple en Ada les instructions function "*" (i,j : integer) return complexe; function "*" (x,y : complexe) return complexe; surchargent l'opérateur * pour effectuer aussi la multiplication de nombres complexes (le type complexe devant être défini). Maintenant, si l'on rencontre 3*5, doit-on considérer la

Cours de Compilation

64

multiplication standard qui retourne un entier ou celle qui retourne un complexe ? Pour répondre à cette question, il faut regarder comment est utilisée l'expression. Si c'est dans 2+(3*5) c'est un entier, si c'est dans z*(3*5) où z est un complexe, alors c'est un complexe. Bref, au lieu de remonter un seul type dans la TDS, il faudra remonter un ensemble de types possibles, jusqu'à ce que l'on puisse conclure. Et je ne parle pas de la génération de code ...

4. Fonctions polymorphes Une fonction (ou un opérateur) est dite polymorphe lorsque l'on peut l'appliquer à des arguments de types variables (et non fixés à l'avance). Par exemple, l'opérateur & en C est polymorphe puisqu'il s'applique aussi bien à un entier qu'à un caractère, une structure définie par le programmeur, .... On peut également, dans certains langages, se définir une fonction calculant la longueur d'une liste d'éléments, quelque soit le type de ces éléments. Cette fois-ci, il ne s'agit plus seulement de vérifier l'équivalence de deux types, mais il faut les unifier. Un des problèmes qui se pose alors est l'inférence de type, c'est à dire la détermination du type d'une construction du langage à partir de la façon dont elle est utilisée. Ces problèmes ne sont pas simples et sont étudiés dans le cadre des recherches en logique combinatoire et en lambda-calcul. Le lambda-calcul permet de définir et d'appliquer les fonctions sans s'occuper des types.

5. La table des symboles Pour un compilateur, la TDS est l’attribut hérité de premier rang, ensuite c’est la structure de donnée la plus importante après l’arbre syntaxique. Les principales opérations associées à une TDS sont : - insertion. Utilisée pour enregistrer les informations fournies par les déclarations. - Recherche. Elle permet d’extraire les informations associées à un nom - Suppression. Cette opération permet de retirer les informations fournies par une déclaration qui n’est plus valide (applicable). Ces trois caractéristiques vont orienter le choix des structures de données appropriées pour l’organisation de la TDS pour un accès rapide et facile.

5.1 La structure de la TDS Avant tout il faudrait savoir qu’une TDS est un dictionnaire. L’efficacité des trois opérations de base est traitée dans le cours de structure de données. Couramment, l’implantation des dictionnaire peut se faire par liste linéaire, par arbre de recherche (binaire, B-tree, AVL) et les tables de hachage. 5.1.1 Les listes linéaires insertion en temps constant O(1), recherche et suppression en temps linéaire suivant la taille de la liste O(n). =>Bon candidat pour l’implémentation des compilateurs pour lequel les phases d’analyse n’est pas critique (les prototypes ou compilateur expérimentaux, les interpréteurs pour des petits programmes).

Cours de Compilation

65

5.1.2 Les arbres de recherches insertion assez coûteuse Complexité des suppressions inefficacité 2/3 => Très peu utilisé pour les TDS 5.1.3 Les tables de hachage offre un temps constant pour les trois opérations O(1) => très bon candidat pour l’implémentation des TDS Une table de hachage est un tableau indexé par les entiers. Une fonction de hachage permet de transformer la clé de recherche (ici le nom de l’identificateur) en un entier appelé valeur de hachage qui correspond à l’indice du tableau où est stocké l’item recherché. Attention la fonction de hachage doit distribuer uniformément les clés=> équilibrage de la Table, assurer les performances de recherche et de suppression la fonction de hachage doit s’exécuter en temps constant ou pire en temps linéaire (taille des clés). Gestion des collisions : le plus simple c’est de considérer chaque entrée de la table comme une liste chaînée

Indice s

Buckets

Liste des Items

0

i

1

size

j

2 3

temp

4 5 6 Exemple de TDS de taille 7. Nous avons inséré les identificateurs (i, j, size, temp) et size et j ont la même valeur de hachage. Sur la figure size précède j, ceci dépend de la méthode d’insertion des items dans une liste. Communément l’insertion se fait en tête, puisque un identificateur nouvellement déclaré a plus de chance d’être utilisé immédiatement. Le nombre d’entrée de la TDS est connu pendant la construction du compilateur. Cette taille est généralement un nombre premier (permet de définir des meilleurs fonctions de hachage). Par exemple il est préférable de choisir 211 au lieu de 200. 5.1.4 Les fonctions de hachage Convertir une chaîne de caractères (nom de l’identificateur) en un entier de l’intervalle *0.. size-1] où size est la taille de la table. Premièrement convertir chaque caractère de la chaîne en un entier, en pascal on utilisera la fonction ord qui retourne la valeur ASCII d’un caractère, en C c’est automatique si on utilise un caractère dans une expression arithmétique. Ensuite combiner ces codes (en les additionnant) pour obtenir un entier unique. Enfin le

Cours de Compilation

66

moduler (mod en pascal et % en C) afin de l’insérer dans l’intervalle *0..size-1].

  h(id )    ci  mod size  ci id  Dans cette combinaison, on peut ignorer certains caractères et ne considérer que les premier caratères, ou bien le premier, celui du milieu et le dernier. Cette méthode n’est pas adaptée pour un compilateur puisque les programmeurs utilisent généralement des noms comme temp1, temp2, temp, etc. et cette méthode causera fréquemment des collisions. Une autre méthode populaire consiste à additionner tous les caractères. Là aussi on n’est pas sorti de l’auberge, puisque toutes les permutations d’une chaînes causeront des collisions, par exemple xtemp et tepmx. Solution : utiliser une constante  comme facteur multiplicatif. Cette constante doit être une puissance de 2 pour simplifier l’exponentiation (qui se réduire à un décalage)

 n n i  h    ci  mod size  i 1  #define

SIZE …

#define

SHIFT

4

int hash( char *key) { int temp = 0 ; int i = 0 ; while (key[ i ] != ‘\0’) { temp = ((temp