Get Kontrollflussgraphen von Abstract Syntax-Baum

Question

Ich habe einen AST abgeleitet aus dem ANTLR Parser-Generator für Java. Was ich tun möchte, ist irgendwie ein Kontrollflussgraphen des Quellcodes zu konstruieren, wobei jede Anweisung oder ein Ausdruck eine eindeutige Knoten ist. Ich verstehe, es muss eine Rekursion zu dieser Identifikation sein, ich habe mich gefragt, was man als die beste Option vorschlagen würde, und wenn ANTLR ein Toolset hat kann ich für diesen Job verwenden. Prost, Chris

---

EDIT - Mein Hauptanliegen ist es, eine Kontrollflussgraphen (CFG) aus dem AST zu bekommen. Auf diese Weise kann ich eine Baumdarstellung der Quelle bekommen. Um zu klären, sowohl der Quellcode und die Implementierungssprache ist Java.

Answer 1

Normalerweise CFGs sind auf einer niedrigeren Ebene berechnet Darstellung (z.B. JVM Bytecode). Jemand hat eine These auf solche Dinge ein paar vor Jahren. Es könnte eine hilfreiche Art und Weise dort beschrieben wird, wie in dieser Darstellung zu erhalten.

Da Ihre Ausgangs- und Zielsprache gleich ist, gibt es keine Code-Generierung Schritt - bist du schon fertig! Aber jetzt haben Sie den AST zu gehen. An jedem Knoten des AST, muss man sich fragen: Ist dies ein „Springen“ Anweisung oder nicht? Methode aufruft und wenn Anweisungen sind Beispiele für Springen Anweisungen. So sind Schleifenkonstrukte (wie for und while). Anweisungen wie Addition und Multiplikation sind nicht-Springen.

First assoziiert mit jeder Java-Anweisung eines Knoten in der CFG, zusammen mit einem Eintritts- und Austrittsknoten. Als erste Annäherung, zu Fuß den Baum und:

1. , wenn die aktuelle Anweisung ist ein Methodenaufruf, herauszufinden, wo der Eingangsknoten für die entsprechende Stelle dieses Methodenaufrufes ist, und eine Kante von der aktuellen Anweisung zu diesem Eingangsknoten zeigt machen. wenn die Anweisung eine Methode Rückkehr ist, aufzuzählen, die Orte, die sie genannt haben könnte und eine Kante zu denen hinzuzufügen.
2. für jede nicht-Springen Anweisung, eine Kante zwischen ihm machen und die nächste Anweisung.

Dies wird Ihnen eine Art von CFG. Das Verfahren ist leicht behaart in Schritt 2, da die Methode aufgerufen in einer Bibliothek deklariert werden kann, und nicht anderswo in dem AST - wenn der so ist, entweder nicht über einen Rand bilden oder um eine Kante zu einem speziellen Knoten zu repräsentieren, dass die Eingabe machen Bibliothek Methode.

Ist das sinnvoll?

Answer 2

Die Herstellung eines vollständigen Kontrollflussgraphen, die wirklich berücksichtigt alle die Sprache nimmt Probleme sind schwieriger als es aussieht. Nicht nur müssen Sie erkennen, was erscheint die „Grundbausteine“ zu sein, aber Sie haben Funktionsaufrufe zu identifizieren (Art von einfach, aber die Identifizierung der target könnte härter sein), wo hinter den Kulissen Operationen wie Klasse initializers kann passieren. und um die Punkte zu kümmern, wo Ausnahmen auftreten können und wo geht die Steuerung, wenn eine Ausnahme auftritt.

Wenn Sie die meisten Sprachen sorgfältig prüfen, werden sie auch sein klar in Ausdrücken der Auswertung von Berechnungen der Bestellung, und dies zählt, wenn Sie zwei Nebenwirkungen in einem Ausdruck haben; der Steuerungsablauf sollte die Reihenfolge (oder die nicht-Ordnung reflektieren, wenn es nicht definiert ist).

Vielleicht möchten Sie nur eine Abstraktion des Kontrollfluss mit den Basisblöcken und das conditionals. das ist offensichtlich ein bisschen einfacher.

In beiden Fällen (einfache CFG oder Voll CFG), müssen Sie den AST gehen, einen Verweis auf mögliche Steuerfluß Ziele an jedem Punkt aufweist, (Beispielsweise für die meisten Fälle, wie beispielsweise IF-Anweisungen gibt es zwei Fluss Ziele: die THEN und ELSE-Klauseln). An jedem Knoten verbinden, die an die Knoten entsprechenden Steuerfluß Ziel, möglicherweise die Strömungs Ziele ersetzt (Zum Beispiel, wenn Sie eine IF begegnen).

Um dies für die vollständige Sprachsemantik von Java (oder C) ist ganz viel Arbeit. Vielleicht möchten Sie einfach ein Werkzeug verwenden, die diese berechnet ab Lager. Siehe http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html für das, was diese wirklich aussehen, aus unseren Werkzeugen kommen.

Answer 3

Basierend auf einigen Kommentaren, es klingt wie wirklich das OP tun will Codegenerierung -. den AST in eine untergeordneten Abfolge von Anweisungen basierend auf Basisblocks und Sprungpunkten

konvertieren

Code-Generierung ist sehr sprachspezifisch, und eine Menge Arbeit hat sich zu diesem Thema gestellt worden. Bevor Sie Code-Generierung tun müssen Sie wissen, Ihre Zielsprache - ob Assembler oder einfach einige andere High-Level-Sprache. Sobald Sie diese identifiziert haben, müssen Sie einfach die AST gehen und eine Folge von Befehlen zu erzeugen, die den Code in dem AST implementiert. (Ich sage das ist einfach, aber es kann schwierig sein - es ist schwer zu verallgemeinern, da die hier Überlegungen sind ziemlich sprachspezifisch.)

Die Darstellung, die Sie für die Codegenerierung wählen, wird die Steuerflussgraphen, implizit oder explizit enthalten. Wenn Ihre Zielsprache ziemlich Low-Level (nahe Assembler) ist, dann sollten die Steuerflussgraphen relativ leicht zu extrahieren.

(Bitte kommentieren Sie, wenn Sie weitere Klärung möchten.)

Answer 4

Haben Sie jemals tryed ANTLR Studio ? Es ist nicht das Loch AST Graphen erzeugen, aber für die Überprüfung, seine schon recht hilfreich.

Answer 5

Als ich dies in der Vergangenheit getan habe, habe ich graphviz , das Punktwerkzeug insbesondere auf erzeugt die Grafik. Ich habe die Punkteingabedatei durch tatsächlich die Steuerflussgraphen bei der Kompilierung durchlaufen.

Graph Layout ist ein hartes Problem und graphviz hat eine ausgezeichnete Arbeit. Das Script kann zu ps, pdf, und verschiedene Bildformate, und das Layout ist in der Regel ziemlich intuitiv zu betrachten. Ich empfehle es.

Answer 6

Ich glaube nicht, ich in der Lage sein, Ihre Frage in einer Art und Weise zu beantworten, die Sie vielleicht für suchen, da ich weiß nicht von irgendeiner Weise in ANTLR eine CFG mit oder ohne AST zu produzieren. Aber, kurz gesagt würden Sie verwenden, was ANTLR erzeugt ein separates Java-Programm zur Erzeugung eines CFG zu erzeugen. Sie würden verwenden die ANTLR Syntaxbaum erzeugt als Eingabe Ihrer CFG in einem separaten Java-Programm Ihrer eigenen Kreation zu erzeugen. An diesem Punkt sind Sie im Wesentlichen den Bau eines Compilers. Der Unterschied zwischen „Compiler“ und einer JVM ist, dass Ihr Ausgang ist eine visuelle Darstellung (CFG), wie ein Programm verzweigt seinen verschiedenen Ausführungspfade und eine JVM / Java-Compiler erzeugt Code zur Ausführung auf einer realen Maschine (CPU).

Eine Analogie ist, wenn jemand ein Buch (zum Beispiel in englischer Sprache) zu schreiben, setzt sich, verwendet die einzelnen Wörter in Sätzen die TOKENS einer Computersprache sind, Sätze werden auf ähnliche Art und Weise, die kontextfreie Grammatiken ausdrücken gültigen Computercode gebildet und Absätze & ganze Romane einer Geschichte in ähnlicher Weise sagen, dass semantische Analyse / Compiler / CFG produzieren könnte / repräsentieren logisch gültige Programme, die tatsächlich etwas nützliches und sind mehr oder weniger tun, die Logik Bugs frei. Mit anderen Worten, wenn man einmal die Frage der gültigen Syntax (korrekter Satzbau) zu erhalten, kann man ein paar Sätze auf einer Seite schreiben, sondern nur bestimmte Kombinationen von Sätzen Text erzeugen, die tatsächlich etwas tut (einer Geschichte erzählen).

Was Sie sind gefragt ist, dass letzte Stück - wie über die Einnahme einen Syntaxbaum zu gehen und Transformieren oder zu interpretieren, was die AST logisch tatsächlich der Fall ist. Und natürlich müssten Sie für jede Sprache, die Sie einen „Compiler“ bauen wollen, dies zu tun. ist eine korrekte Grammatik Mit Ihnen nicht sagen, was ein Programm tut -. nur, dass ein Programm aus einer Grammatik Perspektive richtig ist

Linters und Syntaxhervorhebungen und IDEs alle um die Idee zu versuchen, gebaut werden dieses letzte Stück des Puzzles machen eine einfachere und effizientere Aufgabe für den Menschen.