Keine Cache-Version

Caching deaktiviert Standardeinstellung für diese Seite:aktiviert (code LNG204)
Wenn die Anzeige zu langsam ist, können Sie den Benutzermodus deaktivieren, um die zwischengespeicherte Version anzuzeigen.

Analyse syntaxique : l'AST

Structure de l'arbre

Conventions

Dans la mesure ou ce code est susceptible d'être utilisé dans un cadre plus vaste qu'un seul fichier, nous allons veiller à placer dans un fichier d'en-tête toutes les définitions qu'il est possible d'appeler depuis un autre fichier. Dans cet exemple, le fichier de code est ast.c, et le fichier d'en-tête est ast.h.
Nous veillerons aussi à ce qu'aucun autre élément ne figure dans ast.h (tout ce qui n'est utilisé que au sein de ast.c ne doit pas être exposé).

Pour des raisons de maintenance et de lisibilité, nous utiliserons autant que possible des variables définies sous la forme de constantes.

Nous utiliserons une structure tout à fait traditionnelle d'un arbre binaire (rappel : les arbres en informatique). Nous programmerons notre compilateur en langage C, donc nous allons créer une structure pour manipuler plus facilement ces informations.

Nous avons besoin au minimum dans notre structure d'un pointeur vers le fils de gauche, et un pointeur vers le fils de droite.
Par commodité, nous pouvons aussi maintenir un pointeur vers le nœud parent, ce qui nous permet de "remonter" dans l'arbre lors du parcours de ce dernier.

Comme cet agrégat d'informations (sous forme de structure en langage C) représente un nœud de l'AST [“Abstract Syntaxic Tree”1], nous allons le nommer astNode.

Afin de séparer les différentes responsabilités en entités distinctes, nous pouvons placer dans une autre structure C (astNodeInfo) les informations qui portent sur le code analysé.
Nous pouvons aussi garder dans une structure C (debugInfo) certaines informations relatives à la position des différents éléments du code analysé.

Structure des nœuds de l'AST

Inhaltsverzeichnis Haut

nœud de structure : astNode

  1. struct astNode
  2. {
  3. /*One of the NODE_TYPE_xxx constant*/
  4. int type;
  5. /*Value information*/
  6. struct astNodeInfo *info;
  7. struct debugInfo *debug;
  8. struct astNode *parent;
  9. struct astNode *right;
  10. struct astNode *left;
  11. };

Nous avons dans chaque nœud nos trois pointeurs classiques : le nœud "fils de gauche", le nœud "fils de droite", et le nœud parent.

Nous maintenons aussi deux pointeurs particuliers : info et debug car leurs informations ne concernent pas la manière dont notre arbre syntaxique est formé.

Par contre, nous maintenons au sein de la structure astNode le type de nœud dans une variable type. Cette variable nous informe de la signification de cette partie de code analysé par rapport à l'ensemble de la structure de notre arbre.
Nous utiliserons une des constantes dont le nom débute par NODE_TYPE_... que nous avons définie dans le fichier d'en-tête C.

Constantes NODE_TYPE_xxx

A titre d'exemple, voici quelques valeurs utilisées :

  • NODE_TYPE_REXP : un nœud de type "expression droite".
  • NODE_TYPE_DECL_FUNCTION : un nœud de type "déclaration de fonction".
  • NODE_TYPE_FUNCTION_CALL : un nœud de type "appel de fonction".
  • etc.
En pratique, comme nous avons un certain nombre de types de nœuds soumis aux mêmes règles imposées par la spécification du langage LSD010, nous pouvons utiliser pour la variable type une même valeur pour ces différents éléments, et utiliser une variable subtype pour stocker le type exact.

« Etant donné que nous travaillons avec un arbre binaire (nous n'avons au maximum que deux enfants), comment pouvons-nous stocker plus de deux enfants pour un même nœud ? »

Ce n'est pas possible. Mais nous pouvons contourner le problème en créant un type NODE_TYPE_CONTAINER, qui ne possède pas de signification propre, et que nous n'utilisons que pour contourner cette limitation.
Nous pouvons décider de stocker dans le fils de gauche le premier enfant, puis placer dans le fils de droite un "container" qui possède comme fils de gauche le second enfant, puis un autre "container" à droite, et ainsi de suite.

Partie récursive de l'AST

Inhaltsverzeichnis Haut

Information sur le contenu : astNodeInfo

  1. struct astNodeInfo
  2. {
  3. /*ID, Name of the item (variable, function, etc.)*/
  4. char *name;
  5. /*LSD10 Type of the item, one of the VAR_TYPE_xxx constants*/
  6. int type;
  7. /*
  8. Integer value for the integer vars
  9. O (false) or 1 (true) for the boolean vars
  10. */
  11. int value;
  12. };

Cette structure C contient les informations relatives à la partie de code analysée qui correspond à notre nœud de l'AST.

Nous avons un pointeur name vers le nom de l'élément analysé (une variable, une fonction, etc.).

Nous avons une variable value qui contient la valeur de l'élément analysé. Dans le cas d'un booléen, cette valeur est remplacée par son équivalant numérique4.

Nous avons une variable type pour le type de l'élément analysé. Nous parlons ici d'un des types de données définis dans le langage LSD010, que nous utilisons sous la formes d'une des constantes suivantes :

  • VAR_TYPE_VOID : type "vide" utilisé dans les déclarations de fonctions qui ne retournent pas de valeurs.
  • VAR_TYPE_BOOLEAN : type booléen, qui peut prendre la valeur "true" ou "false"5.
  • VAR_TYPE_INTEGER : type "numérique entier".
  • VAR_TYPE_INTSTACK : type "tableau".

Nous pouvons parler de valeur syntaxique pour notre variable type, et de valeur sémantique pour notre variable value.

Attention à ne pas confondre la variable type dans astNodeInfo qui concerne le type LSD010 de la partie de code analysé, et type dans astNode qui concerne la structure de l'arbre syntaxique abstrait.
En pratique, nous ne pouvons généralement déterminer le type LSD010 que pour les nœuds de déclaration de fonction, déclaration de variable, ou nœuds paramètres de fonction. Quand nous effectuons dans notre compilateur la vérification de type, nous devons retrouver ces nœuds de déclaration pour déterminer le type LSD010 du nœud que nous évaluons (une variable, une expression, etc.).
Nous pouvons donc ajouter une variable computedType, qui est initialisée avec la valeur NODE_TYPE_TODO. Lors de la première recherche, nous lui affectons le type que nous avons trouvé, et nous ne devons plus effectuer de recherche par la suite.
Bien que ce choix soit discutable, j'ai en pratique deux pointeurs firstReturnStatement et nextReturnStatement dans la structure astNodeInfo.
  • Le pointeur firstReturnStatement est différent de NULL seulement dans le cas d'un nœud de type NODE_TYPE_FUNCTION. Dans ce cas (un nœud de fonction), le pointeur nous dirige vers le nœud qui contient la première instruction de type "return", si au moins un "return" est présent.
  • Le pointeur nextReturnStatement est différent de NULL seulement dans le cas d'un nœud de type "return". Dans ce cas , le pointeur nous dirige vers le nœud qui contient la prochaine instruction de type "return" au sein de la même fonction, si il en existe un.
Ces deux pointeurs permettent entre autre de vérifier si une fonction de type VAR_TYPE_VOID ne contient pas un retour de valeur, etc.

Inhaltsverzeichnis Haut

Informations de traçabilité (debug) : debugInfo

  1. struct debugInfo
  2. {
  3. char* file;
  4. int line;
  5. int linePsn;
  6. };

Cette structure C contient les informations relatives à la position de la partie de code analysée qui correspond à notre nœud de l'AST.

Nous avons les variables suivantes :

  • un pointeur file vers le nom du fichier analysé.
  • une variable line qui contient le numéro de ligne de la partie de code analysée.
  • une variable linePsn qui contient la position dans la ligne (la colonne) de la partie de code analysée.

Au départ, ces données étaient seulement destinées à fournir l'information nécessaire pour la traçabilité du code lors de la gestion d'erreurs et de l'affichage de certains messages. Au cours du développement du compilateur LSD010, j'ai utilisé ces informations à des fins de vérifications (par exemple les "forward declarations" interdites par le langage LSD010), donc le nom "debug" n'est plus approprié.

Nous pouvons constater que ces informations sont aussi présentes dans la structure YYLTYPE du fichier y.tab.h6, et moyennant certaines manipulations, YACC [“Yet Another Compiler Compiler”9] peut effectuer le travail à notre place.

Inhaltsverzeichnis Haut

Afficher la structure de l'arbre

Nous pouvons simplement parcourir l'AST et provoquer un affichage de chaque nœud sur la console.

Les navigateurs affichent généralement les documents XML de manière dynamique (nous pouvons développer ou réduire les nœuds par un simple clic) si nous n'avons pas défini de style. Il nous suffit donc d'ouvrir un fichier, de parcourir l'AST et d'écrire les informations de chaque nœud entre des balises XML.

Comme « un petit dessin vaut mieux qu'un long discours », nous allons afficher l'arbre sous forme d'image... Vous pouvez consulter cette page pour voir comment générer une image d'un arbre.

Inhaltsverzeichnis Haut

Code source du compilateur LSD010

Vous pouvez explorer et consulter la totalité du code source de l'exemple du compilateur LSD010 à cette adresse : https://www.gaudry.be/de/langages-lsd10-source-rf-project/source/ast.h.html

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 02/05/2010, zuletzt geändert 28/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/langages-analyse-syntaxique-ast.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen

  1. a,b,c,d,e,f… 1 weitere Links… Abstract Syntaxic Tree : entspricht « arbre syntaxique abstrait » en français

  2. a,b,c,d,e,f AST : “Abstract Syntaxic Tree” (en français, « arbre syntaxique abstrait »)

  3. a,b,c,d,e,f… 3 weitere Links… LSD010 : Langage Simple et Didactique Il existe une un certain nombre d'interprétations de l'acronyme LSD (Langage Symbolique Didactique, Langage Sans Difficulté, Langage Simple et Didactique). LSD010 est la version 2010 de la suite LSD80, LSD_02, LSD03, LSD04, LSD05, LSD06, LSD07, LSD08, et LSD09.

  4.  Valeur booléenne LSD010 : Deux alternatives s'offrent à nous pour coder sous forme d'entier les valeurs true et false :
    - utiliser les constantes retournées dans notre fichier lsd10.lex sans se soucier de leur valeur numérique exacte (la solution que je préfère).
    - utiliser les valeurs 1 pour true, et 0 pour false (la solution adoptée dans cet exemple).

  5.  Type booléen LSD010 : Les valeurs "true" et "false" sont aussi définies sous formes de constantes, dans l'énumération yytokentype du fichier y.tab.h lors de la compilation de notre fichier lsd10.lex.

  6.  Fichier y.tab.h : Vous pouvez consulter un exemple de code source du fichier y.tab.h

  7.  Gnu's Not Unix : entspricht « GNU n'est pas UNIX » en français

  8.  GNU : “Gnu's Not Unix” (en français, « GNU n'est pas UNIX ») Groupement de logiciels libres. Il s'agit d'un acronyme récursif, car nous retrouvons l'acronyme dans sa propre définition.

  9. a,b Yet Another Compiler Compiler : entspricht « Encore un autre compilateur de compilateur » en français

  10.  YACC : “Yet Another Compiler Compiler” (en français, « Encore un autre compilateur de compilateur ») Nous emploierons le terme Yacc, mais il peut s'agir de Bison, son équivalant GNU

Inhaltsverzeichnis Haut

Referenzen

  1. Buch Sprache des Dokuments:fr IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (January 2010)
  2. Buch Sprache des Dokuments:fr Compilateurs : Dick Grune, Henry E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen, Cours et exercices corrigés
  3. Buch Sprache des Dokuments:fr Compilateurs : A. Aho, M. Lam, R. Sethi, J. Ulman, Principes; techniques et outils

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut