2010-12-19 8 views
6

Ich versuche herauszufinden, wie ich meine LEParserCfgVisitor-Klasse implementieren kann, um ein Kontrollflussdiagramm aus einem Abstract-Syntax-Tree zu erstellen, das bereits mit JavaCC generiert wurde . Ich weiß, dass es bereits existierende Tools gibt, aber ich versuche es in Vorbereitung auf mein Compiler-Finale.Erstellen eines Kontrollflussdiagramms von einem AST mit einem Besuchermuster mit Hilfe von Java

Ich weiß, dass ich eine Datenstruktur haben muss, die den Graphen im Speicher hält, und ich möchte Attribute wie IN, OUT, GEN, KILL in jedem Knoten behalten, um einen Kontrollfluss zu machen Analyse später.

Mein Hauptproblem ist, dass ich nicht herausgefunden habe, wie man die verschiedenen Blöcke miteinander verbindet, um die richtige Kante zwischen den Blöcken zu haben, je nach ihrer Art: Zweig, Schleifen usw. Mit anderen Worten: Ich habe einen expliziten Algorithmus gefunden, mit dem ich meinen Besucher aufbauen kann.

Hier ist mein leerer Besucher. Sie können sehen, es zu den grundlegenden langage Ausdrücke arbeitet, wie wenn, während und Grundoperationen (+, -, x, ^, ...)

public class LEParserCfgVisitor implements LEParserVisitor 
{ 
    public Object visit(SimpleNode node, Object data) { return data; } 

    public Object visit(ASTProgram node, Object data) { 
    data = node.childrenAccept(this, data); 
    return data; 
    } 

    public Object visit(ASTBlock node, Object data) { 
    } 

    public Object visit(ASTStmt node, Object data) { 
    } 

    public Object visit(ASTAssignStmt node, Object data) { 
    } 

    public Object visit(ASTIOStmt node, Object data) { 
    } 

    public Object visit(ASTIfStmt node, Object data) { 
    } 

    public Object visit(ASTWhileStmt node, Object data) { 
    } 

    public Object visit(ASTExpr node, Object data) { 
    } 

    public Object visit(ASTAddExpr node, Object data) { 
    } 

    public Object visit(ASTFactExpr node, Object data) { 
    } 

    public Object visit(ASTMultExpr node, Object data) { 
    } 

    public Object visit(ASTPowerExpr node, Object data) { 
    } 

    public Object visit(ASTUnaryExpr node, Object data) { 
    } 

    public Object visit(ASTBasicExpr node, Object data) { 
    } 

    public Object visit(ASTFctExpr node, Object data) { 
    } 

    public Object visit(ASTRealValue node, Object data) { 
    } 

    public Object visit(ASTIntValue node, Object data) { 
    } 

    public Object visit(ASTIdentifier node, Object data) { 
    } 
} 

jemand mir eine Hand geben?

Danke!

Antwort

11

Um Überlegungen zu Datenflüssen (gen/kill/use/def) zu machen, benötigen Sie zunächst einen Kontrollflussgraphen.

Um eines zu konstruieren, erstellen Sie an jedem Baumknoten (z. B. innerhalb jedes spezifischen Knotenbesuchers) das Stück des Graphen, das der Knoten darstellt; Übergeben Sie den Eintrittspunktbogen und den Austrittsbogen für dieses Diagramm an den übergeordneten "Besucher". Rein unabhängige Besucher werden nicht arbeiten, weil Sie Informationen an die Eltern weitergeben müssen. [Sie könnten jedem Knoten, der vom Besucher eingestellt wird, Eintritts-/Austrittsbögenschlitze hinzufügen und von dem Elternteil inspiziert werden.]

Einige Knoten (z. B. für "assignestmt") stellen einen Aktionsknoten her, der sich auf den AST bezieht die Zuordnung (denke "Rechteck" in einem Flussdiagramm); Es gibt keine Untergraphenbögen, um die Sie sich kümmern müssen. Einige Knoten (z. B. für "if") stellen einen bedingten Verzweigungsknoten her (der den AST-Knoten für den Bedingungsausdruck referenziert), (in einem Flussdiagramm als "Diamant" bezeichnet), einen Flow-Join-Knoten und einen strukturierten (wenn then-else) subgraph durch Kombinieren dieses bedingten Verzweigungsknotens mit den Untergraphen für die then- und else-Klauseln (die dann nur durch Eintritts- und Austrittsbögen dargestellt werden) mit dem Flussverbindungsknoten. Dann übergeben Sie die Eintritts- und Austrittslichtbögen an diesen zusammengesetzten Teilgraphen an den Elternteil.

Dieses Schema funktioniert mit strukturiertem Kontrollfluss. Unstrukturierter Kontrollfluss (z. B. "GOTO x") erfordert einige witzige Anpassungen, z. B. zuerst den strukturierten Teil des Graphen erstellen, generierten Kontrollfluss mit Labels assoziieren und dann zurückgehen und die GOTO-Aktionen patchen, um einen Bogen zum assoziierten zu haben Etikette.

Denken Sie daran, sich über Ausnahmen Gedanken zu machen; sie sind auch GOTOs, aber im allgemeinen zu einem höheren Punkt in dem strukturierten Kontrollflußgraphen. Diese werden oft behandelt, indem der innerste Ausnahme-Handler-Knoten nach unten der Baum übergeben wird; Jetzt müssen Ihre Besucher sehen bis der Baum, um diese neueste Ausnahme Handler zu sehen.

Ein ausgefeilteres Schema, das generierte Besucher verwendet, heißt eine http://en.wikipedia.org/wiki/Attribute_grammar">Attributgrammatik, die im Wesentlichen alle Informationsflüsse für Sie verwaltet, indem sie die Werte von Interesse (In diesem Fall sind Eingabe-/Exit-/Exception-Flussbögen die Struktur als Parameter und Ergebnisse auf und ab. Dazu benötigen Sie ein Attributgrammatik-Tool, und Sie müssen noch die Knotenaufbaulogik angeben.Wir verwenden Attributgrammatiken und im Wesentlichen die obige Kontrollflussdiagrammkonstruktion nach Stücken mit unserer DMS Software Reengineering Toolkit, um generische Kontrollflussanalysefunktionen für viele Sprachen bereitzustellen.

Sobald Sie das Kontrollflussdiagramm haben, können Sie einen Datenflusslöser des beschriebenen Typs implementieren, indem Sie über das Kontrollflussdiagramm gehen. Sie müssen die ASTs erneut aufrufen, auf die die CF-Knoten zeigen, um die Informationen rough use/raw def zu sammeln.

Wenn Ihre Sprache nur strukturierten Kontrollfluss hat, können Sie die AST-Knoten zur Darstellung der Kontrollflussknoten verwenden und den Datenfluss direkt berechnen.

Weitere Details zum allgemeinen Prozess finden Sie unter here.