Obtenir le graphe de flux de contrôle à partir de l'arbre de syntaxe abstraite

Question

Je possède un AST dérivé du générateur d’analyseur ANTLR pour Java. Ce que je veux faire, c'est en quelque sorte construire un graphe de flux de contrôle du code source, où chaque instruction ou expression est un nœud unique. Je comprends que cette identification doit être récursive. Je me demandais ce que vous suggériez comme la meilleure option et si ANTLR dispose d’un ensemble d’outils que je pourrais utiliser pour ce travail. À votre santé, Chris

EDIT - Ma principale préoccupation est d’obtenir un diagramme de flux de contrôle (CFG) de l’AST. De cette façon, je peux obtenir une représentation arborescente de la source. Pour clarifier, le code source et le langage d’implémentation sont tous deux Java.

Answer 1

Généralement, les CFG sont calculés sur une représentation de niveau inférieur (par exemple, le pseudo-code JVM). Quelqu'un a une thèse sur de telles choses quelques-unes il y a des années. Il pourrait y avoir une méthode utile décrite ici pour savoir comment obtenir cette représentation.

Puisque vos langues source et cible sont identiques, il n’ya pas d’étape de génération de code - vous avez déjà terminé! Cependant, maintenant vous devez marcher l'AST. À chaque nœud de l'AST, vous devez vous poser la question suivante: s'agit-il d'un "saut"? instruction ou pas? Les appels de méthode et les instructions if sont des exemples d'instructions de saut. Il en va de même pour les constructions en boucle (telles que pour et tant que ). Les instructions telles que l’addition et la multiplication ne sautent pas.

Associez d’abord à chaque instruction java un nœud du fichier CFG, ainsi qu’un nœud d’entrée et de sortie. En première approximation, parcourez l’arbre et:

1. si l'instruction en cours est un appel de méthode, déterminez l'emplacement du nœud d'entrée pour le corps correspondant de cet appel de méthode et créez un bord pointant de l'instruction en cours vers ce nœud d'entrée. si l'instruction est un retour de méthode, énumérez les espaces qui auraient pu l'appeler et ajoutez un bord à ceux-ci.
2. pour chaque instruction qui ne saute pas, définissez un bord entre elle et la suivante.

Cela vous donnera une sorte de CFG. La procédure est légèrement poilue à l’étape 2 car la méthode appelée peut être déclarée dans une bibliothèque et pas ailleurs dans l’AST. Dans ce cas, ne créez pas d’arête ou ne définissez pas d’arête sur un nœud spécial représentant l’entrée de celle-ci. méthode de la bibliothèque.

Cela a-t-il un sens?

Answer 2

Produire un graphe de flux de contrôle complet prenant réellement en compte tout le langage problèmes est plus difficile qu'il n'y paraît. Non seulement vous devez identifier quoi semble être les "blocs de base", mais vous devez identifier les appels de fonction (facile, mais identifier la cible pourrait être plus difficile), où des opérations en coulisse telles que des initialiseurs de classe peuvent avoir lieu. et s'inquiéter des points où des exceptions peuvent se produire et où le contrôle va si une exception se produit.

Si vous examinez attentivement la plupart des langues, elles seront également clair sur l'ordre de l'évaluation des calculs dans les expressions, et cela compte si vous avez deux effets secondaires dans une expression; le flux de contrôle doit refléter l'ordre (ou le non-ordre, si ce n'est pas défini).

Peut-être voulez-vous seulement une abstraction du flux de contrôle avoir les blocs de base et les conditions. C'est évidemment un peu plus facile.

Dans les deux cas (simple CFG ou full CFG), vous devez marcher sur l'AST, en chaque point faisant référence à d'éventuelles cibles de flux de commande (par exemple, dans la plupart des cas, tels que les instructions IF, il existe deux cibles de flux: les clauses THEN et ELSE). À chaque nœud, liez ce nœud au cible de flux de contrôle appropriée, remplaçant éventuellement les cibles de flux (par exemple, lorsque vous rencontrez un IF).

Faire cela pour la sémantique du langage complet de Java (ou C) est assez beaucoup de travail. Vous voudrez peut-être simplement utiliser un outil qui calcule cette sur l'étagère. Voir http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html pour ce que cela ressemble vraiment, sortir de nos outils.

Answer 3

Sur la base de certains commentaires, il semble que le PO souhaite vraiment faire génération de code - pour convertir l'AST en une séquence d'instructions de niveau inférieur basée sur des blocs de base et des points de saut.

La génération de code est très spécifique à la langue et beaucoup de travail a été consacré à ce sujet. Avant de générer du code, vous devez connaître votre langue cible , qu'il s'agisse d'un assembleur ou simplement d'un autre langage de haut niveau. Une fois que vous avez identifié cela, il vous suffit de parcourir l'AST et de générer une séquence d'instructions qui implémente le code dans l'AST. (Je dis que c'est simple, mais que cela peut être difficile - il est difficile de généraliser, car les considérations ici sont plutôt spécifiques au langage.)

La représentation que vous choisissez pour la génération de code contiendra le graphe de flux de contrôle, de manière implicite ou explicite. Si votre langue cible est de niveau assez bas (proche de l'assembleur), le graphique de contrôle-flux devrait être relativement facile à extraire.

(Veuillez commenter si vous souhaitez plus de précisions.)

Answer 4

Avez-vous déjà essayé ANTLR Studio ? Il ne génère pas le graphe AST du trou, mais pour examen, il est déjà très utile.

Answer 5

Auparavant, j’utilisais graphviz , en particulier l'outil de création de points, pour: générer le graphique. J'ai créé le fichier d'entrée par points en parcourant le graphe de contrôle au moment de la compilation.

La disposition des graphes est un problème difficile , et graphviz fait un excellent travail. Il peut générer des formats ps, pdf et divers formats d'image, et la présentation est généralement assez intuitive à regarder. Je le recommande vivement.

Answer 6

Je ne pense pas pouvoir répondre à votre question de la manière que vous recherchez peut-être, car je ne connais aucun moyen, dans ANTLR, de produire un CFG avec ou sans AST. En bref, vous utiliseriez ce que produit ANTLR pour générer un programme Java séparé afin de produire un fichier CFG. Vous utiliseriez l’arbre de syntaxe généré par ANTLR comme entrée pour générer votre fichier CFG dans un programme Java distinct de votre propre création. À ce stade, vous construisez essentiellement un compilateur. La différence entre votre " compilateur " et une machine virtuelle Java signifie que votre sortie est une représentation visuelle (CFG) de la façon dont un programme branche ses différents chemins d’exécution et un compilateur JVM / Java produit du code à exécuter sur une machine réelle (CPU).

Une analogie est si quelqu'un s'assoit pour écrire un livre (en anglais par exemple), les mots utilisés dans les phrases sont les JETONS d'un langage informatique, les phrases sont formées de la même manière que les grammaires sans contexte expriment un code informatique valide , et paragraphes & amp; Des romans entiers racontent une histoire de la même manière que l'analyse sémantique / compilateurs / CFG pourrait produire / représenter des programmes logiquement valides qui font réellement quelque chose d'utile et sont plus ou moins exempts de bugs logiques. En d’autres termes, une fois que vous avez dépassé le problème de la syntaxe valide (structure de phrase correcte), tout le monde peut écrire plusieurs phrases sur une page, mais seules certaines combinaisons de phrases produisent un texte qui fait réellement quelque chose (raconter une histoire).

Ce que vous demandez, c'est ce dernier élément - comment s'y prendre pour prendre un arbre de syntaxe et transformer ou interpréter ce que l'AST fait logiquement. Et bien sûr, vous aurez besoin de créer un " compilateur " pour chaque langue pour laquelle vous voulez faire cela. Avoir une grammaire correcte ne vous dit pas ce que fait un programme - ce n’est qu’un programme qui est correct du point de vue de la grammaire.

Les linters, les surligneurs de syntaxe et les IDE sont tous construits autour de l’idée de faire de cette dernière pièce du puzzle une tâche plus facile et plus efficace pour les humains.