Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 44 IV. Traduction

SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 44 IV. Traduction dirigée par la syntaxe : 1. Généralités : Comme son nom l’indique, la traduction dirigée s’élabore en parallèle avec l’analyse syntaxique et plus exactement c’est l’analyse syntaxique qui oriente la traduction. Pour traduire une construction d’un langage de programmation, un compilateur peut avoir besoin de garder trace de nombreuses informations, par conséquent, on parlera, de manière abstraite, d’attributs associés à la construction, les valeurs de ces attributs sont calculées par des règles sémantiques associées aux productions de la grammaire. Il existe deux notations pour associer des règles sémantiques aux productions : les définitions dirigés pas la syntaxe et les schémas de traduction 2. Définition Une définition dirigée par la syntaxe utilise une grammaire non contextuelle pour spécifier la structure syntaxique du texte d'entrée. A chaque symbole de la grammaire, on associe un ensemble d'attributs et, à chaque production, un ensemble de règles sémantiques pour calculer la valeur des attributs associés aux symboles apparaissant dans cette production. La grammaire et l'ensemble des règles sémantiques constituent la définition dirigée par la syntaxe. On notera X.l l’attribut d’étiquette l associé au symbole X . S'il y a plusieurs symboles X dans une production, on les noteraX1,X2,….Xn, et X(0) s'il est en partie gauche. 3.Structure d’une définition dirigée par la syntaxe : Dans une DDS chaque production AB de la grammaire possède un ensemble de règles sémantiques de la forme b :=f(c1,c2….ck) où f est une fonction et/ 1- Soit b est un attribut synthétisé de A. 2- Soit b est un attribut hérité d’un des symboles en partie droite de la production. Et c1,c2….ck sont des attributs de symboles quelconques de la production, dans les deux cas on dit que b dépend de c1,c2….ck. Les terminaux devraient ne posséder que des attributs synthétisés, la valeur des attributs des terminaux est fournie par l’analyseur lexical Exemple : soit la DDS d’un programme de calculatrice de bureau Productions Règles sémantiques L E n EE1+T ET TT*F TF F( E ) Fchiffre Imprimer (e.val) E.val := E1.val + T.val E.val :=T.val T.val :=T1.val* F.val T.val := F.val F .val := E.val F.val := chiffre.vallex DDS d’une calculatrice de bureau La règle associée à la production LEn définissant l’axiome L, est un appel de procédure qui imprime la valeur engendrée par E, cette règle peut être considérée comme définissant un attribut factice du non-terminal L 3.1 Attributs synthétisés : Un attribut est synthétisé si sa valeur, à un nœud d'un arbre syntaxique, est déterminée à partir de valeurs d'attributs des fils de ce nœud. Les attributs synthétisés sont utilisés intensivement en pratique. Une définition dirigée par la syntaxe qui utilise uniquement des attributs synthétisés est appelée une définition S-attribuée. SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 45 Les attributs synthétisés ont la propriété de pouvoir être évalués au cours d'un simple parcours ascendant de l'arbre syntaxique. Un arbre syntaxique pour une définition S-attribuée peut toujours être décoré en évaluant les règles sémantiques pour les attributs de chaque nœud du bas vers le haut, des feuilles vers la racine Exemple 2(Attributs synthétisés) : soit la définition S-attribuée présenté dans l’exemple 1 : La figure suivante présente un arbre décoré pour la chaine d’entrée 3*5+4n(n caractère de fin de ligne) L E.val=19 n E.val=15 T.val=4 T.val=15 F.val=4 T.val=3 * F.val=5 chiffre.vallex=4 F.val=3 chiffre.vallex=5 chiffre.vallex=3 Arbre syntaxique décoré pour 3*5+4n 3.2 Attributs hérités Un attribut est hérité si sa valeur, à un nœud d'un arbre syntaxique, est déterminée à partir de valeurs d'attributs du père et/ou des frères de ce nœud. Bien qu'il soit toujours possible de réécrire une définition dirigée par la syntaxe de façon à n'utiliser que des attributs synthétisés, il est souvent plus naturel d'utiliser des définitions avec attributs hérités. Exemple 3 ( Attributs hérités) : un exemple d’attribut hérité est la déclaration d’identificateurs typés. On veut reconnaitre les expressions type x1,x2………………xn avec type un non-terminal correspondant à int ou real et déclarer les identificateurs du bon type dans la table des symboles par l’action add( x,type, T) qui ajoute le type de chaque identificateur à son entrée dans la table des symboles D T L L.typh := T.typ Tint T.typ := int T real T.typ := real LL1 ,id L1.typh:=L.typh ; add( id.entrée, L.typh) Lid add (id.entrée, L.typh) DDS avec l’attribut hérité L.typh D T.typ=real L.typh= real Real L.typh=real , id1 id2 Arbre syntaxique avec un attribut hérité typh à chaque nœud étiqueté L SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 46 4. Graphes de dépendances : Si un attribut b à un nœud d’un arbre syntaxique dépend d’un attribut c, la règle sémantique définissant b en ce nœud doit être évaluée après la règle sémantique qui définit c. les interdépendances entre les attributs hérités et synthétisés aux nœuds d’un arbre syntaxique peuvent être décrites par un graphe orienté appelé graphe de dépendances. En introduisant un attribut factice b pour toute règle sémantique qui consiste en appel de procédure. Le graphe a un sommet pour chaque attribut Il ya un arc du sommet correspondant à c au sommet correspondant à b si l’attribut b dépend de c Dans le cas des attributs synthétisés les arrêtes sont dirigées des fils vers le père Dans le cas des attributs hérités on peut avoir une arête du père vers le fils ou d’un frère à un autre. Plus précisément, le graphe de dépendance pour un arbre syntaxique donné est construit de la façon suivante : Pour chaque nœud n de l’arbre syntaxique faire Pour chaque attribut a du symbole de la grammaire étiquetant n faire Construire un sommet dans le graphe de dépendance pour a ; Pour chaque nœud n de l’arbre syntaxique faire Pour chaque règle sémantique b := f( c1,c2…,ck) associée à la production appliquée en n faire Pour i :=1 à K faire Construire un arc du sommet correspondant à ci au sommet correspondant à b ; Exemple 4 : Production règle sémantique E E1 + E2 E.val= E1.val + E2.val E ●val E1 ●val + E2 ●val Les lignes pointillées représentent l’arbre syntaxique et ne font pas partie du graphe de dépendance Exemple5 :voici le graphe de dépendances pour l’arbre syntaxique de l’exemple 3 : Chacune des procédures add (id.entrée, L.typh) associées aux productions définissant L conduit à la création d’un attribut factice Remarque : si le graphe de dépendance contient un cycle, l'évaluation des attributs est alors impossible L’évaluation de ces règles sémantiques stocke le type real dans l’entrée de chaque identificateur dans la table des symboles. Plusieurs méthodes ont été proposées pour évaluer les règles sémantiques : SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 47 Méthodes fondées sur l’arbre syntaxique :-déterminent un ordre d’évaluation à partir d’un tri topologique du graphe de dépendance construit d’après l’arbre syntaxique, ceci pour chaque texte d’entrée. -Echec dans le cas d’un graphe cyclique. Méthodes fondées sur les règles sémantiques : -au moment de la construction du compilateur, on analyse les règles sémantiques associées aux productions, soit à la main soit par un outil spécialisé -pour chaque production, l’ordre d’évaluation des attributs associés est pré calculé et sera utilisé au moment de l’évaluation. Méthode à ordre fixe : -choix d’un ordre d’évaluation sans tenir compte des règles sémantiques, l’ordre d’évaluation est imposé par la méthode d’analyse. Les deux dernières méthodes ne font pas appel à un graphe de dépendance : efficacité en temps et en mémoire. 5. Evaluation ascendante des définitions S-attribuées Maintenant nous pouvons commencer à étudier comment implanter des traducteurs à partir de ces définitions, les attributs synthétisés peuvent être évalués par un analyseur syntaxique ascendant au fur et à mesure que le texte d’entrée est lu. Une définition syntaxique est dite S-attribuée si elle ne comporte que des attributs synthétisés. Un traducteur pour une définition S-attribuée peut souvent être implantée à l’aide d’un constructeur d’analyseur syntaxique LR. Un analyseur syntaxique ascendant utilise une pile pour garder de l’information sur les sous arbres qui ont été reconnus. Nous pouvons ajouter des champs à la pile d’analyse pour stocker les valeurs des attributs synthétisés. SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 48 Les attributs synthétisés de cet arbre peuvent être évalués par un analyseur syntaxique LR au cours de l’analyse ascendante de la phrase 3*5+4n Flot d’entrée Etat Val Productions utilisées Fragment de code 3 *5+4 *5+4 *5+4 *5+4 5+4 +4 +4 +4 +4 4 N N N 3 F T T* T*5 T*F T E E+ E+4 E+F E+ T 3 3 3 3 3 – 5 3 – 5 15 15 15 15 – 4 15 – 4 15 – 4 F id T F F id TT*F ET F id TF Val[future-sommet]:=val[s-2]*val[s] SAOUDI Lalia Traduction dirigée par la syntaxe 2007/2008 Page 49 N E 19 EE+T Val[future-sommet]:=val[s-2]+val[s] 6. Evaluation L-attribuées : Nous présentons maintenant une classe de définitions dirigées par la syntaxe, appelées L-attribuées, dont les attributs peuvent toujours être évalués en profondeur ( L est l’abréviation de Left car l’information véhiculée par les uploads/Industriel/ traduction.pdf