Kompilieren eines AST zurück in den Quellcode

Question 1

Ich bin gerade dabei, einen in PHP geschriebenen PHP-Parser zu erstellen, da in meiner vorherigen Frage kein vorhandener Parser auftauchte. Die Parser selbst funktioniert ziemlich gut.

Nun bringt ein Parser selbst offensichtlich wenig (abgesehen von der statischen Analyse). Ich möchte Transformationen auf den AST anwenden und ihn dann wieder in den Quellcode kompilieren. Das Anwenden der Transformationen ist kein großes Problem, ein normales Besuchermuster sollte ausreichen.

Was mein Problem derzeit ist, ist, wie ich den AST zurück in den Quellcode kompiliere. Grundsätzlich sehe ich zwei Möglichkeiten:

Kompilieren Sie den Code mithilfe eines vordefinierten Schemas
Behalten Sie die Formatierung des Originalcodes bei und wenden Sie 1. nur auf Knoten an, die geändert wurden.

Im Moment möchte ich mich auf 1. konzentrieren, da 2. ziemlich schwer zu bewerkstelligen scheint (aber wenn Sie diesbezüglich Tipps haben, würde ich sie gerne hören).

Aber ich bin mir nicht sicher, welches Entwurfsmuster verwendet werden kann, um den Code zu kompilieren. Der einfachste Weg, dies zu implementieren, besteht darin, a hinzuzufügen ->compile Methode für alle Knoten. Der Nachteil, den ich hier sehe, ist, dass es ziemlich schwierig wäre, die Formatierung der generierten Ausgabe zu ändern. Dazu müssten die Knoten selbst geändert werden. Daher suche ich nach einer anderen Lösung.

Ich habe gehört, dass das Visitor-Pattern auch dafür verwendet werden kann, aber ich kann mir nicht wirklich vorstellen, wie das funktionieren soll. Wie ich das Besuchermuster verstehe, haben Sie einige NodeTraverser die rekursiv über alle Knoten iteriert und a aufruft ->visit Methode von a Visitor. Das klingt ziemlich vielversprechend für die Node-Manipulation, wo die Visitor->visit -Methode könnte einfach den Knoten ändern, an den sie übergeben wurde, aber ich weiß nicht, wie sie zum Kompilieren verwendet werden kann. Eine naheliegende Idee wäre, den Knotenbaum von den Blättern bis zur Wurzel zu iterieren und die besuchten Knoten durch Quellcode zu ersetzen. Aber das scheint irgendwie keine sehr saubere Lösung zu sein?

Question 2

Das Problem, einen AST wieder in Quellcode umzuwandeln, wird allgemein als “Prettyprinting” bezeichnet. Es gibt zwei subtile Variationen: Regenerieren des Textes, der so weit wie möglich mit dem Original übereinstimmt (ich nenne das “treues Drucken”), und (schönes) Hübsches Drucken, das schön formatierten Text erzeugt. Und wie Sie drucken, hängt davon ab, ob Programmierer an dem neu generierten Code arbeiten (sie wollen oft originalgetreues Drucken) oder ob Sie nur die Absicht haben, ihn zu kompilieren (an diesem Punkt ist jedes legale Schöndrucken in Ordnung).

Um Prettyprinting gut zu machen, sind normalerweise mehr Informationen erforderlich, als ein klassischer Parser sammelt, was durch die Tatsache erschwert wird, dass die meisten Parser-Generatoren diese Sammlung zusätzlicher Informationen nicht unterstützen. Ich nenne Parser, die genügend Informationen sammeln, um dies gut zu tun, “Re-Engineering-Parser”. Weitere Details unten.

PrettyPrinting wird im Grunde dadurch erreicht, dass der AST durchlaufen wird (“Besuchermuster”, wie Sie es ausdrücken) und Text basierend auf dem Inhalt des AST-Knotens generiert wird. Der grundlegende Trick ist: Rufen Sie untergeordnete Knoten von links nach rechts auf (vorausgesetzt, dies ist die Reihenfolge des ursprünglichen Textes), um den Text zu generieren, den sie darstellen, und fügen Sie zusätzlichen Text ein, der für diesen AST-Knotentyp geeignet ist. Um einen Block von Anweisungen zu verschönern, haben Sie möglicherweise den folgenden Pseudocode:

 PrettyPrintBlock:
     Print("{"}; PrintNewline();
     Call PrettyPrint(Node.children[1]); // prints out statements in block
     Print("}"); PrintNewline();
     return;


 PrettyPrintStatements:
     do i=1,number_of_children
         Call PrettyPrint(Node.children[i]); Print(";"); PrintNewline(); // print one statement
     endo
     return;

Beachten Sie, dass dies spontan Text ausspuckt, wenn Sie den Baum besuchen.

Es gibt eine Reihe von Details, die Sie verwalten müssen:

Für AST-Knoten, die Literale darstellen, müssen Sie den Literalwert neu generieren. Dies ist schwieriger, als es aussieht, wenn Sie möchten, dass die Antwort korrekt ist. Das Drucken von Fließkommazahlen ohne Genauigkeitsverlust ist a viel schwieriger als es aussieht (Wissenschaftler hassen es, wenn Sie den Wert von Pi beschädigen). Für Zeichenfolgenliterale müssen Sie die Anführungszeichen und den Inhalt der Zeichenfolgenliterale neu generieren; Sie müssen darauf achten, Escape-Sequenzen für Zeichen, die mit Escapezeichen versehen werden müssen, neu zu generieren. PHP-String-Literale in doppelten Anführungszeichen können etwas schwieriger sein, da sie im AST nicht durch einzelne Token dargestellt werden. (Unsere PHP-Frontend (Ein Reengineering-Parser/Prettyprinter stellt sie im Wesentlichen als einen Ausdruck dar, der die Zeichenfolgenfragmente verkettet, sodass Transformationen innerhalb der Zeichenfolge „literal“ angewendet werden können).

Abstand: Einige Sprachen erfordern an kritischen Stellen Leerzeichen. Die Token ABC17 42 sollten besser nicht als ABC1742 gedruckt werden, aber es ist in Ordnung, wenn die Token ( ABC17 ) als (ABC17) gedruckt werden. Eine Möglichkeit, dieses Problem zu lösen, besteht darin, überall dort, wo es erlaubt ist, ein Leerzeichen einzufügen, aber das Ergebnis wird den Leuten nicht gefallen: zu viel Leerzeichen. Kein Problem, wenn Sie nur das Ergebnis kompilieren.
Newlines: Sprachen, die beliebige Leerzeichen zulassen, können technisch als einzelne Textzeile neu generiert werden. Die Leute hassen das, selbst wenn Sie das Ergebnis zusammenstellen; manchmal …… du verfügen über sich den generierten Code anzusehen und dies macht es unmöglich. Sie brauchen also eine Möglichkeit, Zeilenumbrüche für AST-Knoten einzuführen, die wichtige Sprachelemente darstellen (Anweisungen, Blöcke, Methoden, Klassen usw.). Das ist normalerweise nicht schwer; Wenn Sie einen Knoten besuchen, der ein solches Konstrukt darstellt, drucken Sie das Konstrukt aus und hängen Sie einen Zeilenumbruch an.
Wenn Sie möchten, dass Benutzer Ihr Ergebnis akzeptieren, werden Sie feststellen, dass Sie einige Eigenschaften des Quelltexts beibehalten müssen, die Sie normalerweise nicht speichern würden. Für Literale müssen Sie möglicherweise die Basis des Literals neu generieren. Programmierer, die eine Zahl als Hex-Literal eingegeben haben, sind nicht glücklich, wenn Sie das Dezimaläquivalent regenerieren, obwohl es genau dasselbe bedeutet. Ebenso müssen Strings die “ursprünglichen” Anführungszeichen haben; Die meisten Sprachen erlauben entweder ” oder ‘ als String-Anführungszeichen und die Leute wollen, was sie ursprünglich verwendet haben. Für PHP ist es wichtig, welches Anführungszeichen Sie verwenden, und bestimmt, welche Zeichen im String-Literal maskiert werden müssen. Einige Sprachen erlauben Schlüsselwörter in Groß- oder Kleinschreibung ( oder sogar Abkürzungen) und Groß- und Kleinbuchstaben von Variablennamen, die dieselbe Variable bedeuten; wieder wollen die ursprünglichen Autoren normalerweise ihre ursprüngliche Schreibweise zurück. PHP hat komische Zeichen in verschiedenen Arten von Bezeichnern (z. B. “$”), aber das werden Sie entdecken es ist nicht immer da (siehe $-Variablen in Literal-Strings).Oft möchten die Leute ihre ursprüngliche Layout-Formatierung;um dies zu tun, müssen Sie Informationen zur Spaltennummer für konkrete Token speichern und hübsche Druckregeln darüber haben, wann diese Spalte verwendet werden soll. Zahlendaten, um hübsch gedruckten Text nach Möglichkeit an der gleichen Spalte zu positionieren, und was zu tun ist, wenn die bisher hübsch gedruckte Zeile über diese Spalte hinaus gefüllt ist.

Kommentare: Die meisten Standard-Parser (darunter der, den Sie mit dem Zend-Parser implementiert haben, da bin ich mir ziemlich sicher) werfen Kommentare komplett weg. Auch hier hassen die Leute das und werden eine hübsch gedruckte Antwort ablehnen, in der Kommentare verloren gehen. Dies ist der Hauptgrund, warum einige Prettyprinter versuchen, Code unter Verwendung des Originaltexts neu zu generieren (der andere ist, das ursprüngliche Codelayout für originalgetreuen Druck zu kopieren, wenn Sie keine Spaltennummerinformationen erfasst haben). Meiner Meinung nach besteht der richtige Trick darin, die Kommentare im AST zu erfassen, damit AST-Transformationen auch Kommentare prüfen/generieren können, aber jeder trifft seine eigene Designentscheidung.

Alle diese “zusätzlichen” Informationen werden von einem guten Reengineering-Parser gesammelt. Herkömmliche Parser sammeln normalerweise nichts davon, was das Drucken akzeptabler ASTs erschwert.

Ein prinzipiellerer Ansatz unterscheidet das hübsche Drucken, dessen Zweck eine schöne Formatierung ist, vom originalgetreuen Drucken, dessen Zweck es ist, den Text so zu regenerieren, dass er so weit wie möglich mit der ursprünglichen Quelle übereinstimmt. Es sollte klar sein, dass Sie auf der Ebene der Terminals so ziemlich originalgetreues Drucken wünschen. Abhängig von Ihrem Zweck können Sie mit schöner Formatierung oder originalgetreuem Druck hübsch drucken. Eine Strategie, die wir verwenden, besteht darin, standardmäßig originalgetreu zu drucken, wenn die AST nicht geändert wurde, und Prettyprinting dort, wo sie geändert wurde (weil die Änderungsmaschinerie häufig keine Informationen über Spaltennummern oder Zahlenwurzeln usw. hat). Die Transformationen stempeln die neu generierten AST-Knoten als “keine Fidelity-Daten vorhanden”.

Ein organisierter Ansatz zum hübschen Drucken ist, zu verstehen, dass praktisch alle textbasierten Programmiersprachen in Bezug auf gut gerendert werden rechteckig Textblöcke. (Knuths TeX-Dokumentgenerator hat diese Idee auch). Wenn Sie eine Reihe von Textfeldern haben, die Teile des neu generierten Codes darstellen (z. B. primitive Felder, die direkt für die Terminal-Tokens generiert wurden), können Sie sich Operatoren zum Zusammensetzen dieser Felder vorstellen: Horizontale Komposition (stapeln Sie ein Feld rechts neben einem anderen), Vertikal (Boxen übereinander stapeln; dies ersetzt praktisch das Drucken von Zeilenumbrüchen), Einrücken (Horizontale Komposition mit einer Box voller Leerzeichen) usw. Dann können Sie Ihren Prettyprinter konstruieren, indem Sie Textboxen erstellen und zusammenstellen:

 PrettyPrintBlock:
     Box1=PrimitiveBox("{"); Box2=PrimitiveBox("}");
     ChildBox=PrettyPrint(Node.children[1]); // gets box for statements in block
     ResultBox=VerticalBox(Box1,Indent(3,ChildBox),Box2);
     return ResultBox;

PrettyPrintStatements:
     ResultBox=EmptyBox();
     do i=1,number_of_children
         ResultBox=VerticalBox(ResultBox,HorizontalBox(PrettyPrint(Node.children[i]); PrimitiveBox(";")
     endo
     return;

Der wirkliche Wert dabei ist, dass jeder Knoten die von seinen Kindern erzeugten Textfelder in beliebiger Reihenfolge mit beliebigem dazwischenliegendem Text zusammensetzen kann. Auf diese Weise können Sie riesige Textblöcke neu anordnen (stellen Sie sich vor, VBox ordnet die Methoden der Klasse in der Reihenfolge der Methodennamen an). Kein Text wird wie angetroffen ausgespuckt; nur wenn die Wurzel erreicht ist, oder irgendein AST-Knoten, wo bekannt ist, dass alle untergeordneten Kästchen korrekt erzeugt wurden.

Unsere DMS-Software-Reengineering-Toolkit verwendet diesen Ansatz, um alle Sprachen, die es parsen kann (einschließlich PHP, Java, C# usw.), zu verschönern. Anstatt die Box-Berechnungen über Besucher an AST-Knoten anzuhängen, hängen wir die Box-Berechnungen in einer domänenspezifischen Textbox-Notation an

H(…) für horizontale Boxen
V(….) für vertikale Kästchen

I(…) für eingerückte Kästchen)

direkt zu den Grammatikregeln, wodurch wir die Grammatik (Parser) und den Prettyprinter (“Anti-Parser”) kurz und bündig an einer Stelle ausdrücken können. Die Regeln der prettyprinter-Box werden automatisch von DMS in einen Besucher kompiliert. Die Prettyprinter-Maschinerie muss schlau genug sein, um zu verstehen, wie Kommentare dazu beitragen, und das ist ehrlich gesagt ein bisschen geheimnisvoll, aber Sie müssen es nur einmal tun. Ein DMS-Beispiel:

block = '{' statements '}' ; -- grammar rule to recognize block of statements
<<PrettyPrinter>>: { V('{',I(statements),'}'); };

Sie können ein größeres Beispiel dafür sehen, wie dies gemacht wird Wirths Oberon-Programmiersprache PrettyPrinter zeigt, wie Grammatikregeln und Prettyprinting-Regeln kombiniert werden. Das PHP-Frontend sieht so aus, ist aber offensichtlich viel größer.

Eine komplexere Art, Prettyprinting durchzuführen, besteht darin, einen syntaxgesteuerten Übersetzer zu erstellen (dh durch den Baum zu gehen und Text oder andere Datenstrukturen in baumstrukturierter Reihenfolge zu erstellen), um Textfelder in einem speziellen Textfeld-AST zu erzeugen. Die Textbox AST wird dann von einem anderen Treewalk schön gedruckt, aber die Aktionen dafür sind im Grunde trivial: Textboxen drucken. Siehe dieses technische Dokument: Pretty-Printing für Software-Reengineering

Ein weiterer Punkt: Sie können natürlich alle diese Maschinen selbst bauen. Aber derselbe Grund, warum Sie sich für die Verwendung eines Parser-Generators entscheiden (es ist eine Menge Arbeit, einen zu erstellen, und diese Arbeit trägt nicht auf interessante Weise zu Ihrem Ziel bei), ist derselbe Grund, warum Sie einen Off-the- Regal-Prettyprinter-Generator. Es gibt viele Parser-Generatoren. Nicht viele Prettyprinter-Generatoren. [DMS is one of the few that has both built in.]