Wie erzeugt man Code für einen AST-Baum, der aus einer fiktiven Sprache geparst wurde?

Question

Ich habe den Artikel auf der Website http://parsingintro.sourceforge.net/ und beschloss, es als Übung in Ruby umzuschreiben. Dafür gab es zwei Gründe: Ich wollte mehr darüber lernen, wie man Ruby programmiert (ich kenne mich mit Java, PHP, C und etwas Python aus), und ich wollte mehr über Parser/Compiler lernen.

Ich habe den gesamten Code unter https://github.com/parse/boatcaptain . Der AST-Baum wird generiert, leider geht der Autor des Artikels nicht auf Konzepte wie Codegenerierung und Optimierungen ein.

Kann mir jemand helfen, indem er mir die richtige Richtung zeigt, wie ich diesen AST-Baum in "Code" umsetzen kann? Dies ist der AST-Baum, der erzeugt wird

Ich habe vor einigen Jahren einen Rechner in Java geschrieben, der viele ähnliche Begriffe und Techniken verwendet, wie ich sie in diesem Parser benutzt habe. Aber in dem Taschenrechner hatte ich Methoden für eval()-ing meine "Klassen" und daher erhalten Ausgabe, sollte ich für etwas ähnliches hier zu tun Ziel? Quelle für den Rechner: https://github.com/parse/Uppsala-University-Courses/blob/master/ImpOOP-Calculator/src/Calculator.java

Ich würde mich auch über Feedback zu meiner Art, Ruby zu schreiben, freuen. Ich glaube, ich schreibe Ruby immer noch so, wie ich Python schreiben würde, und verpasse dabei einige schöne Vorteile von Ruby.

Answer 1

Die Codegenerierung in ihrer einfachsten Form besteht darin, Ihre Zwischenform - den AST - zu durchlaufen und die entsprechenden Anweisungen in Ihrer Zielsprache auszugeben.

Zunächst müssen Sie sich für eine Zielsprache entscheiden. Auf welcher Plattform soll Ihre Eingabedatei laufen? Die wichtigsten Optionen, die Sie haben, sind:

• Ein Quelle-zu-Quelle-Übersetzer
• Ein Compiler für nativen Code
• Ein Compiler für Bytecode (der just-in-time auf einer VM ausgeführt werden kann)

Die Wahl der Zielsprache kann darüber entscheiden, wie viel Arbeit Sie für die Zuordnung zwischen den Sprachen aufwenden müssen. Die Abbildung objektorientierter Klassen auf ASM könnte/würde zum Beispiel schwierig sein. Auch die Abbildung von inhärent prozeduralem Code auf stapelbasierten Code könnte eine Herausforderung darstellen.

Unabhängig davon, welche Sprache Sie wählen, wird das Problem zweifellos auf folgende Prozedur hinauslaufen: Besuchen Sie die Knoten Ihres Baums und geben Sie je nach Typ die entsprechende Anweisung aus.

Angenommen, Sie stoßen in Ihrem AST auf den folgenden Knoten (wie in dem von Ihnen verlinkten):

        =
delta       /
      alpha   beta

Da es sich um einen Zuweisungsknoten handelt, weiß der Codegenerator, dass er die rechte Seite des Baums auswerten muss, bevor er den Wert in die linke Seite einfügt: "delta". Wir folgen also dem RHS-Knoten nach unten und sehen, dass es sich um eine Divisionsoperation handelt. Wir wissen dann, dass wir sowohl das LHS als auch das RHS dieses Knotens auswerten müssen, bevor wir sie dividieren und das Ergebnis in "delta" einfügen.

Jetzt bewegen wir uns auf der linken Seite nach unten, sehen, dass es sich um eine Variable handelt, und geben einen "Lade"-Befehl aus. Wir gehen zurück nach oben und dann nach unten auf der rechten Seite und geben ebenfalls eine "load"-Anweisung für "beta" aus. Dann gehen wir den Baum wieder hinauf (wobei wir sowohl Alpha als auch Beta mitnehmen), emittieren die Divisionsanweisung für beide Operanden, speichern das Ergebnis, geben es den Baum hinauf an den Zuweisungsemitter weiter und lassen es von diesem in "delta" speichern.

Der resultierende Code für dieses Snippet könnte also lauten:

load alpha
load beta
tmp = div alpha beta
store delta tmp

Was bereits existierende Ruby Code Generator-Bibliotheken angeht, so sind mir keine bekannt, tut mir leid. Ich hoffe, diese Antwort war nicht zu allgemein oder zu vereinfachend für Sie.