Générer une image d'un arbre et de ses nœuds

Sommaire du document

En programmation, nous manipulons souvent des arbres et des graphes, et il vient toujours un moment où nous souhaitons obtenir un affichage de la structure de l'arbre ou du graphe, que ce soit pour assurer la traçabilité (debugging), ou pour présenter la structure à d'autres personnes.

Nous pouvons utiliser l'outil Graphviz[ref 1]  pour afficher la structure d'un arbre sous forme d'image.

Exemple d'image de structure de l'arbre

AST d'une fonction main LSD010

Voici le code qui à été analysé par le compilateur LSD010 pour afficher cette image de l'arbre.

  1. void main()
  2. {
  3. {
  4. integer k;
  5. boolean b;
  6. }
  7. k=2;
  8. b=3<k;
  9. }

Code utilisé pour afficher l'arbre

L'exemple suivant nous montre le code en langage C qui permet d'afficher une image des nœuds de l'arbre syntaxique abstrait généré pour le compilateur LSD010 développé dans le cadre du cours de syntaxe et sémantique[ref 2]

  1. /*
  2.  * graphVizHelper.h : Helper for the graphViz tool (generation of images from a tree)
  3.  * @see http://www.graphviz.org/doc/info/command.html
  4.  * Part of the compiler project for LSD10 language
  5.  * Gaudry Stéphane
  6.  * More information on http://www.gaudry.be/programmer-arbre-image-noeuds.html
  7.  */
  8. #ifndef GRAPHVIZ_HELPER_H
  9. #define GRAPHVIZ_HELPER_H
  10.  
  11. #define GRAPHVIZ_CONFIG_FILE "astLSD10.dot"
  12.  
  13. /**
  14. * Generates an image of the AST into the current directory
  15. */
  16. void printGraph();
  17.  
  18. //void printGraph(char *xmlFileName, char *graphFileName);
  19. #endif

Code c (project/source/graphVizHelper.c) (235 lignes) :
  1. /*
  2.  * graphVizHelper.c : Helper for the graphViz tool (generation of images from a tree)
  3.  * @see http://www.graphviz.org/doc/info/command.html
  4.  * Part of the compiler project for LSD10 language
  5.  * Gaudry Stéphane
  6.  * More information on http://www.gaudry.be/programmer-arbre-image-noeuds.html
  7.  */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <time.h>
  12. #include "common.h"
  13. #include "graphVizHelper.h"
  14. #include "y.tab.h"
  15. #if(VERBOSE_LEVEL<=DEB_E)
  16. #include <errno.h>
  17. #endif
  18. extern AstNode *rootNode;
  19.  
  20. /*
  21.  * **********************************************************
  22.  * Internal business
  23.  * **********************************************************
  24.  */
  25.  
  26. #define GRAPH_RIGHT 0
  27. #define GRAPH_LEFT 1
  28. #define GRAPH_ROOT -1
  29.  
  30. int isGraphVisInstalled()
  31. {
  32. return 1;//todo : get it dynamically
  33. }
  34.  
  35. /**
  36.  * http://www.graphviz.org/doc/info/command.html
  37.  */
  38. void generateImage(char *dotFileName)
  39. {
  40. time_t now;
  41. struct tm *timeinfo;
  42.  
  43. now = time(NULL);//time ( &now );
  44. timeinfo = localtime ( &now );
  45.  
  46. char commandString[100];
  47. //todo : set the timeinfo int values on a 2 digits format
  48. sprintf(
  49. commandString,
  50. "%slsd10_Img%d%d%d%d%d%d.jpg %s",
  51. "dot -Tjpg -o",
  52. timeinfo->tm_year+1900,
  53. timeinfo->tm_mon+1,
  54. timeinfo->tm_mday,
  55. timeinfo->tm_hour,
  56. timeinfo->tm_min,
  57. timeinfo->tm_sec,
  58. dotFileName);
  59. printf("\n;\tGenerating image from dot file : %s\n",commandString);
  60.  
  61. int ret = 0;
  62. ret = system (commandString);
  63. //printf ("ret = %d\n", ret);
  64.  
  65. }
  66.  
  67. void printGraphDotHeader(FILE * graphFile)
  68. {
  69.  
  70. if(graphFile!=NULL)
  71. {
  72. fprintf(graphFile, "digraph LSD10{\n");
  73. fprintf(graphFile, "\tbgcolor=white \n");
  74. fprintf(graphFile, "\tnode [");
  75. fprintf(graphFile, "color=\"#9DACBF\", ");
  76. fprintf(graphFile, "fontcolor=\"#000000\", ");
  77. fprintf(graphFile, "style=filled");
  78. fprintf(graphFile, "];\n");
  79. fprintf(graphFile, "\tedge [arrowsize=2, color=\"#000000\"];\n");
  80. }
  81. }
  82.  
  83. void printGraphDotFooter(FILE * graphFile)
  84. {
  85.  
  86. if(graphFile!=NULL)
  87. {
  88.  
  89. time_t now;
  90. struct tm *timeinfo;
  91.  
  92. now = time(NULL);//time ( &now );
  93. timeinfo = localtime ( &now );
  94. // fprintf(graphFile, "}\n");
  95. // fprintf(graphFile, "digraph INFO{\n");
  96. fprintf(
  97. graphFile,
  98. "\t\"Generated by the SSHD09 LSD010 compiler\\n%d/%d/%d %dHr %d\\nWith GraphViz engine\" [",
  99. timeinfo->tm_mday,
  100. timeinfo->tm_mon+1,
  101. timeinfo->tm_year+1900,
  102. timeinfo->tm_hour,
  103. timeinfo->tm_min,
  104. timeinfo->tm_sec
  105. );
  106. fprintf(graphFile, "shape=box, ");
  107. fprintf(graphFile, "color=\"#FF9933\", ");
  108. fprintf(graphFile, "fontcolor=\"#000000\"");
  109. fprintf(graphFile, "];\n");
  110. fprintf(graphFile, "}\n");
  111. }
  112. }
  113. /**
  114.  * Prints an AST node into the graph file
  115.  * Pre-condition : dotFile not null
  116.  */
  117. void printGraphNode(FILE *dotFile, AstNode *node, int depth, int psn)
  118. {
  119. if(node!=NULL)
  120. {
  121. if(node->parent!=NULL)
  122. {
  123. fprintf(dotFile, "\t\"%p\" -> ", node->parent);
  124. }
  125. else
  126. {
  127. fprintf(dotFile, "\t");
  128. }
  129. fprintf(
  130. dotFile,
  131. "\"%p\";\n\t\"%p\" [shape=%s, color=\"%s\", fontcolor=\"%s\", label=\"%s%s%s%s : \\n%s %s\\nLine %d char %d\"];\n",//print position?
  132. node,
  133. node,
  134. //node->type>LEX_FIRST_TOKEN&&node->type<LEX_LAST_TOKEN?"polygon":"box",
  135. psn==GRAPH_LEFT?"hexagon":(psn==GRAPH_RIGHT?"box":"doublecircle"),
  136. (node->type==NODE_TYPE_DECLARATION
  137. || node->type==NODE_TYPE_FUNCTION
  138. || node->type==NODE_TYPE_PARAM_DECL
  139. )?"#677E96":psn==GRAPH_LEFT?"#e6e8f2":(psn==GRAPH_RIGHT?"#AAB5C6":"#C0C0C0"),
  140. (node->type==NODE_TYPE_DECLARATION
  141. || node->type==NODE_TYPE_FUNCTION
  142. || node->type==NODE_TYPE_PARAM_DECL
  143. )?"#FFFFFF":"#000000",
  144. typeToString(node->type),
  145. node->subtype!=NODE_TYPE_NOTHING?" (":"",
  146. node->subtype!=NODE_TYPE_NOTHING?typeToString(node->subtype):"",
  147. node->subtype!=NODE_TYPE_NOTHING?")":"",
  148. typeToString(node->info->type),
  149. node->info->name,
  150. node->debug->line,
  151. node->debug->linePsn
  152. );
  153. printGraphNode(dotFile, node->left, depth+1, GRAPH_LEFT);
  154. printGraphNode(dotFile, node->right, depth+1, GRAPH_RIGHT);
  155. }
  156. //else fprintf(dotFile, "null");
  157. }
  158. void printGraphDotFromXML(char *xmlFileName, char *dotFileName)
  159. {
  160.  
  161. FILE * graphFile;
  162. time_t genTime = time(NULL);
  163. if(xmlFileName==NULL)xmlFileName=AST_XML_FILE;
  164. if(dotFileName==NULL)dotFileName=GRAPHVIZ_CONFIG_FILE;
  165. graphFile = fopen(dotFileName, "w");
  166. if(graphFile!=NULL)
  167. {
  168. printf("\n;\tGenerating AST Graph from %s into %s file ... (%s, col %d)", xmlFileName, dotFileName, __FILE__, __LINE__);
  169. printGraphDotHeader(graphFile);
  170. //todo : read info from XML file to generate the dot file
  171. fprintf(graphFile, "Warning : reading from XML is not yet implemented\n");
  172. printGraphDotFooter(graphFile);
  173. fclose(graphFile);
  174.  
  175. #if(VERBOSE_LEVEL<=DEB_EXEC)
  176. printMsg(DEB_EXEC,"...OK Graph printed", __FILE__, __LINE__);
  177. #endif
  178.  
  179. if(isGraphVisInstalled()==1)
  180. {
  181. generateImage(dotFileName);
  182. }
  183. }
  184. else
  185. {
  186. #if(VERBOSE_LEVEL<=DEB_EXEC)
  187. printMsg(DEB_EXEC,"Printing AST into Graph file ... Can't open file", __FILE__, __LINE__);
  188. printMsg(DEB_E, (char *)strerror(errno), __FILE__, __LINE__);
  189. #endif
  190. }
  191. }
  192.  
  193. void printGraphDotFromAST(char *dotFileName)
  194. {
  195.  
  196. FILE * graphFile;
  197. time_t genTime = time(NULL);
  198. if(dotFileName==NULL)dotFileName=GRAPHVIZ_CONFIG_FILE;
  199. graphFile = fopen(dotFileName, "w");
  200. if(graphFile!=NULL)
  201. {
  202. printf("\n;\tGenerating AST Graph from last compilation into %s file ... (%s, col %d)", dotFileName, __FILE__, __LINE__);
  203. printGraphDotHeader(graphFile);
  204. printGraphNode(graphFile, rootNode, 0, GRAPH_ROOT);
  205. printGraphDotFooter(graphFile);
  206. fclose(graphFile);
  207.  
  208. #if(VERBOSE_LEVEL<=DEB_EXEC)
  209. printMsg(DEB_EXEC,"...OK Graph printed", __FILE__, __LINE__);
  210. #endif
  211. }
  212. else
  213. {
  214. #if(VERBOSE_LEVEL<=DEB_EXEC)
  215. printMsg(DEB_EXEC,"Printing AST into Graph file ... Can't open file", __FILE__, __LINE__);
  216. printMsg(DEB_E, (char *)strerror(errno), __FILE__, __LINE__);
  217. #endif
  218. }
  219. }
  220.  
  221. /*
  222.  * **********************************************************
  223.  * Implementation of the header exposed items
  224.  * See graphVizHelper.h for these functions comments
  225.  * **********************************************************
  226.  */
  227.  
  228. void printGraph()
  229. {
  230. printGraphDotFromAST(GRAPHVIZ_CONFIG_FILE);
  231. if(isGraphVisInstalled()==1)
  232. {
  233. generateImage(GRAPHVIZ_CONFIG_FILE);
  234. }
  235. }

Je reviendrais plus en détails sur le code quand j'aurais plus de temps, mais voici déjà quelques explications...

Comme nous pouvons le constater dans le fichier d'en-tête, une seule fonction est proposée ici : void printGraph();. Cette fonction génère un fichier DOT défini dans l'en-tête par la constante GRAPHVIZ_CONFIG_FILE, car dans notre cas un seul fichier est utilisé et est écrasé à chaque analyse de code avec le compilateur LSD010.
Ce fichier est seulement destiné à être appelé par l'outil GraphViz pour créer une image des nœuds de l'arbre. Comme nous utiliserons le style "dot" de GraphViz pour notre image, nous pouvons retenir "dot" comme extension de notre fichier temporaire, afin de nous en souvenir.

Nous pouvons aussi générer un fichier de configuration pour GraphViz au départ d'un fichier XML généré par void printXMLTree(FILE *file, pAST_NODE node, int depth) lors de la dernière analyse par le compilateur LSD010. Ce fichier contient les différentes données de notre AST [“Abstract Syntaxic Tree”[2]].

Exemple fichier de configuration pour GraphViz

Reprennons un instant notre exemple de code qui à été analysé par le compilateur LSD010. Voici le fichier de configuration de GraphViz généré par un appel à void printGraph() pour produire l'image de l'exemple.

  1. digraph LSD10{
  2. bgcolor=white
  3. node [color="#9DACBF", fontcolor="#000000", style=filled];
  4. edge [arrowsize=2, color="#000000"];
  5. "0x91789c0";
  6. "0x91789c0" [shape=doublecircle, color="#677E96", fontcolor="#FFFFFF", label="Functions : \nNo Type Functions\nLine 1 char 4"];
  7. "0x91789c0" -> "0x9178960";
  8. "0x9178960" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="Function : \nvoid main\nLine 1 char 8"];
  9. "0x9178960" -> "0x9178900";
  10. "0x9178900" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="Structural node : \nNo Type {{decl}statement}\nLine 9 char 1"];
  11. "0x9178900" -> "0x9178898";
  12. "0x9178898" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="function body : \nNODE_TYPE_TODO Statements node\nLine 9 char 1"];
  13. "0x9178898" -> "0x9178830";
  14. "0x9178830" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="function body : \nNODE_TYPE_TODO Statements node\nLine 9 char 1"];
  15. "0x9178830" -> "0x91787c8";
  16. "0x91787c8" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Statement : \nNODE_TYPE_CHECK Statement : 'LExpr = RExpr;'\nLine 8 char 6"];
  17. "0x91787c8" -> "0x9178750";
  18. "0x9178750" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="Right expression : \nboolean _2\nLine 8 char 6"];
  19. "0x9178750" -> "0x91786f0";
  20. "0x91786f0" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="Right expression : \nNODE_TYPE_TODO _1\nLine 8 char 6"];
  21. "0x91786f0" -> "0x9178690";
  22. "0x9178690" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Id : \nNo Type k\nLine 8 char 6"];
  23. "0x9178750" -> "0x9178620";
  24. "0x9178620" [shape=box, color="#AAB5C6", fontcolor="#000000", label="number : \ninteger CONSTANT, NUMBER\nLine 8 char 3"];
  25. "0x91787c8" -> "0x91785b8";
  26. "0x91785b8" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Id : \nNo Type b\nLine 8 char 2"];
  27. "0x9178898" -> "0x9178548";
  28. "0x9178548" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Statement : \nNODE_TYPE_CHECK Statement : 'LExpr = RExpr;'\nLine 7 char 4"];
  29. "0x9178548" -> "0x91784d0";
  30. "0x91784d0" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="number : \ninteger CONSTANT, NUMBER\nLine 7 char 3"];
  31. "0x9178548" -> "0x9178468";
  32. "0x9178468" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Id : \nNo Type k\nLine 7 char 2"];
  33. "0x9178900" -> "0x91783f8";
  34. "0x91783f8" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Type declarations : \nNo Type Declarations node\nLine 6 char 1"];
  35. "0x91783f8" -> "0x9178390";
  36. "0x9178390" [shape=hexagon, color="#e6e8f2", fontcolor="#000000", label="Type declarations : \nNo Type Declarations node\nLine 6 char 1"];
  37. "0x9178390" -> "0x9178348";
  38. "0x9178348" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Type declaration : \nboolean b\nLine 5 char 9"];
  39. "0x91783f8" -> "0x9178298";
  40. "0x9178298" [shape=box, color="#AAB5C6", fontcolor="#000000", label="Type declaration : \ninteger k\nLine 4 char 9"];
  41. "Generated by the SSHD09 LSD010 compiler\n22/4/2010 4Hr 1\nWith GraphViz engine" [shape=box, color="#FF9933", fontcolor="#000000"];
  42. }

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/langages-lsd10-source.html

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Notes

  1. a,b,c,d,e 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.

  2. a,b Abstract Syntaxic Tree : correspond à « arbre syntaxique abstrait” en français

  3.  AST : “Abstract Syntaxic Tree” (en français, « arbre syntaxique abstrait »)

 

Références

  1. Consulter le document html Langue du document: uk Graph Visualization Software : http://www.graphviz.org/Credits.php, Graphviz (version 24/04/10)
  2. livre Langue du document: fr IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique (Janvier 2010)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Liste des images

  1. AST d'une fonction main LSD010 (Référence : infobrol)

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-7435
Document créé le 25/04/10 14:16, dernière modification le Vendredi 17 Juin 2011, 12:12
Source du document imprimé : http:///www.gaudry.be/programmer-arbre-image-noeuds.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,12 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Si un problème a une solution, alors il est inutile de s'en inquiéter ; s'il n'en a pas, s'inquiéter n'y changera rien

Proverbe tibétain
 
l'infobrol
Nous sommes le Dimanche 28 Mai 2017, 05:14, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)