Elegantes AST Modell

Question

Ich schreibe gerade einen Spielzeug Compiler in Scala. Die Zielsprache selbst sieht wie eine Skala aus, ist aber ein offenes Feld für Experimente.

Nach mehreren großen Refactorings kann ich keinen guten Weg finden, meinen abstrakten Syntaxbaum zu modellieren. Ich würde gerne die Möglichkeiten von scalas Musterabgleich nutzen, das Problem ist, dass der Baum während des Kompilierungsprozesses bewegte Informationen (wie Typen, Symbole) mit sich führt.

ich ein paar Lösungen sehen, von denen keines Mir mag:

• Fallklassen mit veränderbaren Feldern (ich glaube, der scala Compiler dies der Fall ist): Das Problem ist, dass diese Felder keine präsentieren Jede Stufe der Kompilierung und muss daher nulled (oder Option) und es wird wirklich schwer zu debuggen/schreiben Code. Wenn ich zum Beispiel nach der Typisierungsphase einen Knoten mit Null-Typ finde, fällt es mir sehr schwer, die Ursache des Fehlers zu finden.

• große Zug/Fallklassenhierarchie: so etwas wie Knoten, NodeWithSymbol, NodeWithType, ... Scheint wie ein Schmerz mit

• etwas komplett von Hand mit Extraktoren gefertigt zu schreiben und arbeiten

Ich bin mir auch nicht sicher, ob es eine gute Übung ist, mit einem vollständig unveränderlichen AST zu gehen, besonders in Scala, wo es keine implizite Freigabe gibt (weil der Compiler sich der Unveränderlichkeit nicht bewusst ist) und es Performances könnte den Baum die ganze Zeit zu kopieren .

Können Sie sich ein elegantes Muster vorstellen, um meinen Baum mit dem leistungsfähigen Typensystem von scala zu modellieren?

Answer 1

Ich habe vor kurzem angefangen, einen Spielzeug-Verifier für eine kleine Sprache zu schreiben, und ich verwende die Kiama-Bibliothek für die Phasen Parser, Resolver und Type Checker.

Kiama ist eine Scala-Bibliothek für die Sprachverarbeitung. Es ermöglicht eine komfortable Analyse und Transformation von strukturierten Daten. Die von der Bibliothek unterstützten Programmierstile basieren auf bekannten formalen Sprachverarbeitungsparadigmen, einschließlich attribute grammars, tree rewriting, abstract state machines und pretty printing.

Ich werde versuchen, meine (ziemlich begrenzt) Erfahrung zusammenfassen:

• [+] Kiama kommt mit einigen Beispielen und der wichtigste Faktor reagiert in der Regel schnell auf Fragen auf der Mailingliste fragte

• [+] Das Attribut-Grammatik-Paradigma ermöglicht eine schöne Trennung in „unveränderliche Komponenten“ des Knoten, zum Beispiel Namen und Unterknoten, und „wandelbar Komponenten“, zB Typinformation

• [+] Die Bibliothek kommt mit einem vielseitigen Umschreibsystem, das - soweit - alle meine Anwendungsfälle abdeckt

• [+] Die Bibliothek, z.B., Die ziemlich Drucker, schöne Beispiele von DSLs und verschiedenen funktionellen Muster/Ansätze/Ideen

• machen [-] Die Lernkurve es auf jeden Fall steil, auch mit Beispielen und der Mailingliste zur Hand

• [- ] Scheint die Umsetzung der Auflösungsphase in einem "rein funktionalen" Stil (vgl. my question) schwierig zu sein, aber ein hybrider Ansatz (den ich noch nicht ausprobiert habe) scheint möglich zu sein [-] Das Attribut Grammatik Paradigma und Die daraus resultierende Trennung der Belange macht es nicht offensichtlich, wie die Eigenschaften der Knoten am Ende zu dokumentieren sind (vgl. my question)

• [-] Es wird gemunkelt,, dass das Attribut-Grammatik-Paradigma

zusammenfassend meine Zusammenfassung nicht die schnellsten Implementierungen hat ergeben, ich viel Kiama viel Freude mit und ich empfehle dringend, dass Sie es versuchen oder sehen Sie sich zumindest die Beispiele an.

(PS Ich bin nicht mit Kiama dem Unternehmen assoziiert.)

Answer 2

TL; DR Ich ziehe das AST unveränderlich und tragen Dinge wie Typinformationen in einer separaten Struktur zu halten, z.B. eine Map, die durch im AST gespeicherte IDs referenziert werden kann. Aber es gibt keine perfekte Antwort.

Sie sind keineswegs der Erste, der sich mit dieser Frage abmüht. Lassen Sie mich einige Optionen auflisten:

1) Veränderliche Strukturen, die in jeder Phase aktualisiert werden. Alle Auf und Ab, die Sie erwähnen.

2) Merkmale/Kuchenmuster. Machbar, aber teuer (es gibt kein Teilen) und irgendwie hässlich.

3) Ein neuer Baumtyp in jeder Phase. In gewisser Hinsicht ist dies der theoretisch sauberste. Jede Phase kann nur mit einer Struktur arbeiten, die in der vorherigen Phase für sie erzeugt wurde. Derselbe Ansatz erstreckt sich vom Frontend bis zum Backend. Zum Beispiel können Sie zu einem bestimmten Zeitpunkt "entziehen" und einen neuen Baumtyp haben bedeutet, dass die nachgelagerten Phasen nicht einmal die Möglichkeit von Knotentypen berücksichtigen müssen, die durch Entzundern eliminiert werden. Außerdem benötigen Low-Level-Optimierungen in der Regel IRs, die deutlich niedriger als der ursprüngliche AST sind. Aber das ist auch eine Menge Code, da bei jedem Schritt fast alles neu erstellt werden muss. Dieser Ansatz kann auch langsam sein, da fast keine Daten zwischen den Phasen ausgetauscht werden müssen.

4) Beschriften Sie jeden Knoten im AST mit einer ID und verwenden Sie diese ID, um Informationen in anderen Datenstrukturen (Karten und Vektoren usw.) zu referenzieren, die für jede Phase berechnete Informationen enthalten. In vielerlei Hinsicht ist das mein Favorit. Es behält die Unveränderlichkeit bei, maximiert das Teilen und minimiert den "überschüssigen" Code, den Sie schreiben müssen. Aber Sie müssen immer noch mit dem Potenzial für "fehlende" Informationen umgehen, die schwierig zu debuggen sein können. Es ist auch nicht so schnell wie die veränderbare Option, aber schneller als jede Option, die das Erzeugen eines neuen Baums in jeder Phase erfordert.