Warum speichern wir nicht den Syntaxbaum anstelle des Quellcodes?

Wir haben viele Programmiersprachen. Jede Sprache wird analysiert und die Syntax überprüft, bevor sie in Code übersetzt wird, sodass ein abstrakter Syntaxbaum (AST) erstellt wird.

Wir haben diesen abstrakten Syntaxbaum. Warum speichern wir diesen Syntaxbaum nicht anstelle des Quellcodes (oder neben dem Quellcode)?

Durch die Verwendung eines AST anstelle des Quellcodes. Jeder Programmierer in einem Team kann diesen Baum in jede gewünschte Sprache serialisieren (mit der entsprechenden kontextfreien Grammatik) und nach Abschluss des Vorgangs wieder zu AST analysieren. Dies würde also die Debatte über die Codierungsstil-Fragen beseitigen (wo die {und} zu setzen sind, wo Whitespace, Einrückung usw. zu setzen sind).

Was sind die Vor- und Nachteile dieses Ansatzes?

Leerzeichen und Kommentare

Im Allgemeinen enthält ein AST keine Leerzeichen, Zeilenabschlusszeichen und Kommentare.

Sinnvolle Formatierung

Sie haben Recht, dass dies in den meisten Fällen positiv ist (wodurch heilige Kriege beseitigt werden), und dass die Formatierung des Originalcodes in vielen Fällen eine gewisse Bedeutung hat, z Anweisungen mit einer Leerzeile).

Code, der nicht kompiliert werden kann

Während viele Parser sehr widerstandsfähig gegen fehlende Syntax sind, führt fehlerhafter Code häufig zu einem sehr seltsamen Syntaxbaum, der bis zu dem Punkt, an dem der Benutzer die Datei neu lädt, in Ordnung und fehlerfrei ist. Haben Sie jemals einen Fehler in Ihrer IDE gemacht und plötzlich hat die gesamte Datei "Squigglies"? Stellen Sie sich vor, wie das in einer anderen Sprache nachgeladen würde.

Möglicherweise schreiben Benutzer keinen nicht analysierbaren Code ein, aber sie müssen auf jeden Fall lokal speichern.

Keine zwei Sprachen passen perfekt zusammen

Wie andere betont haben, gibt es fast keine zwei Sprachen, die eine perfekte Feature-Parität aufweisen. Ich kann mir vorstellen, dass VB und C # oder JavaScript und CoffeeScript am nächsten kommen, aber selbst dann verfügt VB über Funktionen wie XML-Literale, die in C # keine Entsprechungen aufweisen, und die Konvertierung von JavaScript in CoffeeScript führt möglicherweise zu vielen JavaScript-Literalen.

In einer Softwareanwendung, die ich schreibe, müssen wir dies tatsächlich tun, da von den Benutzern erwartet wird, dass sie "normales Englisch" eingeben, das im Hintergrund in JS konvertiert wird. Wir haben erwogen, nur die JS-Version zu speichern, aber kaum eine akzeptable Möglichkeit gefunden, um diese zuverlässig zu laden und zu entladen. Daher haben wir immer sowohl den Benutzertext als auch die JS-Version sowie ein Flag gespeichert, das angibt, ob "normales Englisch" vorliegt msgstr "Version wurde perfekt analysiert oder nicht.

Warum speichern wir diesen Syntaxbaum nicht anstelle des Quellcodes? Jeder Programmierer in einem Team kann diesen Baum in jede Sprache serialisieren, die er möchte, und nach Abschluss des Vorgangs zu AST zurückkehren.

Das ist in der Tat eine vernünftige Idee. Microsoft hatte in den neunziger Jahren ein Forschungsprojekt, um genau das zu erreichen .

Es kommen mehrere Szenarien in den Sinn.

Das erste ist eher trivial; Wie Sie sagen, könnte der AST in Abhängigkeit von den Vorlieben verschiedener Programmierer für Dinge wie Abstand usw. in verschiedene Ansichten gerendert werden. Das Speichern eines AST ist für dieses Szenario jedoch zu teuer. schreib dir einfach einen hübschen Drucker. Wenn Sie eine Datei in Ihren Editor laden, führen Sie den Pretty-Printer aus, um sie in Ihr bevorzugtes Format und beim Speichern wieder in das ursprüngliche Format zu bringen.

Der zweite ist interessanter. Wenn Sie den abstrakten Syntaxbaum speichern können, wird eine Änderung, die sich vom Code unterscheidet, nicht textuell, sondern syntaktisch. Refactorings, bei denen Code verschoben wird, sind viel einfacher zu verstehen. Der Nachteil ist natürlich, dass das Schreiben der Tree-Diff-Algorithmen nicht gerade trivial ist und oft pro Sprache erfolgen muss. Text Diff funktioniert für fast jede Sprache.

Das dritte ist eher das, was Simonyi sich für die absichtliche Programmierung vorgestellt hat: Die grundlegenden Konzepte, die Programmiersprachen gemeinsam haben, sind serialisiert, und dann haben Sie unterschiedliche Ansichten dieser Konzepte, die in verschiedenen Sprachen wiedergegeben werden. Obwohl es eine schöne Idee ist, ist die hässliche Tatsache, dass Sprachen in ihren Details so unterschiedlich sind, dass ein Ansatz mit dem kleinsten gemeinsamen Nenner nicht wirklich funktioniert.

Kurz gesagt, es ist eine schöne Idee, aber es ist eine enorme Menge an zusätzlicher Arbeit für einen vergleichsweise geringen Nutzen. Deshalb tut es kaum jemand.

Sie könnten argumentieren, dass dies genau der Bytecode in .NET ist. Das Reflektorprogramm von Infact redgate übersetzt Byte-Code zurück in eine Reihe von .NET-Programmiersprachen.

Es gibt jedoch Probleme. Syntax ist sprachspezifisch, da es Dinge gibt, die Sie in einer Sprache darstellen können, die in anderen Sprachen nicht dargestellt sind. Dies tritt in .NET auf, wobei C ++ die einzige .NET-Sprache ist, die Zugriff auf alle sieben Zugriffsebenen hat.

Außerhalb der .NET-Umgebung wird es viel kniffliger. Jede Sprache verfügt dann über einen eigenen Satz zugeordneter Bibliotheken. Es wäre nicht möglich, sowohl in C als auch in Java eine generische Syntax wiederzugeben, die die gleiche Ausführung von Befehlen widerspiegelt, da sie ähnliche Probleme auf sehr unterschiedliche Weise lösen.

Ich mag einige Ihrer Ideen, aber Sie überschätzen deutlich, wie einfach es ist, Sprache in Sprache zu übersetzen. Wenn es so einfach wäre, müssten Sie den AST nicht einmal speichern, da Sie immer die Sprache X in den AST analysieren und dann von AST zu Sprache Y wechseln könnten.

Ich wünsche mir jedoch, dass die Compilerspezifikationen ein bisschen mehr darüber nachdenken, einen Teil des AST durch eine Art API verfügbar zu machen. Dinge wie aspektorientiertes Programmieren, Refactoring und statische Programmanalyse könnten über eine solche API implementiert werden, ohne dass der Implementierer dieser Funktionen so viel von der Arbeit wiederholen muss, die bereits von Compiler-Autoren implementiert wurde.

Es ist merkwürdig, wie oft die Datenstruktur eines Programmierers zur Darstellung eines Programms aus einer Reihe von Dateien besteht, die Zeichenfolgen enthalten.

Ich denke, die wichtigsten Punkte sind folgende:

• Es gibt keinen Vorteil. Sie sagten, das würde bedeuten, dass jeder seine Haustiersprache benutzen könnte. Dies ist jedoch nicht der Fall - bei Verwendung einer Syntaxbaumdarstellung würden nur syntaktische, nicht jedoch semantische Unterschiede beseitigt. Es funktioniert bis zu einem gewissen Grad für sehr ähnliche Sprachen - wie VB und C # oder Java und Scala. Aber auch da nicht ganz.

• Das ist problematisch. Sie haben die Freiheit der Sprache gewonnen, aber die Freiheit der Werkzeuge verloren. Sie können den Code nicht mehr in einem Texteditor oder in einer beliebigen IDE lesen und bearbeiten. Sie sind zum Lesen und Bearbeiten des Codes auf ein bestimmtes Tool angewiesen , das Ihre AST-Darstellung spricht. Hier ist nichts gewonnen.

  Um diesen letzten Punkt zu veranschaulichen, werfen Sie einen Blick auf RealBasic, eine proprietäre Implementierung eines leistungsstarken BASIC-Dialekts. Eine Zeitlang sah es fast so aus, als ob die Sprache abheben könnte, aber es war vollständig herstellerabhängig, bis zu dem Punkt, dass Sie den Code nur in ihrer IDE anzeigen konnten, da er in einem proprietären Nicht-Text-Format gespeichert war. Großer Fehler.

Ich denke, wenn Sie sowohl den Text als auch den AST speichern, haben Sie nichts wirklich Nützliches hinzugefügt, da der Text bereits in einer Sprache vorhanden ist und der AST schnell aus dem Text rekonstruiert werden kann.

Wenn Sie dagegen nur den AST speichern, verlieren Sie Dinge wie Kommentare, die nicht wiederhergestellt werden können.

Ich glaube, die Idee ist theoretisch interessant, aber nicht sehr praktisch, da verschiedene Programmiersprachen verschiedene Konstrukte unterstützen, von denen einige keine Entsprechungen in anderen Sprachen haben.

Zum Beispiel hat X ++ eine 'while select'-Anweisung, die ohne viel zusätzlichen Code (zusätzliche Klassen, zusätzliche Logik usw.) nicht in C # geschrieben werden kann. http://msdn.microsoft.com/en-us/library/aa558063.aspx

Ich sage hier, dass viele Sprachen syntaktische Zucker haben, die in großen Codeblöcken derselben Sprache übersetzt werden, oder sogar Elemente, die in anderen überhaupt nicht existieren. Hier ist ein Beispiel, warum der AST-Ansatz nicht funktioniert:

Die Sprache X hat ein Schlüsselwort K, das in AST in 4 Anweisungen übersetzt wird: S1, S2, S3 und S4. Der AST ist jetzt in die Sprache Y übersetzt und ein Programmierer ändert S2. Was passiert nun mit der Übersetzung zurück nach X? Der Code wird als 4 Anweisungen anstelle eines einzelnen Schlüsselworts übersetzt ...

Das letzte Argument gegen den AST-Ansatz sind die Plattformfunktionen: Was passiert, wenn eine Funktion in die Plattform eingebettet ist? Wie bei .NET Environment.GetEnvironmentVariable. Wie übersetzen Sie das?

Um diese Idee herum gibt es ein System: JetBrains MPS . Ein Editor ist ein bisschen seltsam oder einfach anders, aber im Allgemeinen ist es kein so großes Problem. Das größte Problem ist, na ja, dass es kein Text mehr ist, so dass Sie keine der normalen textbasierten Tools verwenden können - andere Editoren grep, sedverschmelzen und diff Werkzeuge usw.

Tatsächlich gibt es mehrere Produkte, die allgemein als "Sprachwerkbänke" bekannt sind, die ASTs speichern und in ihren Editoren eine "Projektion" des AST in eine bestimmte Sprache zurückgeben. Wie @ sk-logic sagte, ist das MPS von JetBrains ein solches System. Ein weiteres Beispiel ist die Intentional Workbench von Intentional Software.

Das Potenzial für Sprachwerkbänke scheint insbesondere im Bereich domänenspezifischer Sprachen sehr hoch zu sein, da Sie eine domänenspezifische Projektion erstellen können. Beispiel: Intentional demonstriert eine DSL in Bezug auf Elektrizität, die als Schaltplan projiziert wird - viel einfacher und genauer als eine Schaltung, die in einer textbasierten Programmiersprache beschrieben wird.

In der Praxis haben sich Sprach-Workbenches nur langsam durchgesetzt, da Entwickler neben der DSL-Arbeit wahrscheinlich lieber in einer vertrauten, allgemeinen Programmiersprache arbeiten würden. Im direkten Vergleich mit einem Texteditor oder einer Programmier-IDE sind die Sprach-Workbenches mit einem enormen Aufwand verbunden, und ihre Vorteile sind bei weitem nicht so deutlich. Keine der Sprach-Workbenches, die ich gesehen habe, hat sich so weit selbst gebootet, dass sie ihre eigenen IDEs problemlos erweitern können. Wenn Sprach-Workbenches also die Produktivität steigern, warum wurden die Tools der Sprach-Workbench nicht besser? -und-besser bei immer schnelleren Raten?

Du hast meine Gedanken gelesen.

Als ich vor ein paar Jahren an einem Compilerkurs teilgenommen habe, habe ich festgestellt, dass Sie Lisp erhalten, wenn Sie einen AST mit Präfixnotation anstelle der üblichen Infixnotation nehmen und Klammern verwenden, um ganze Anweisungen abzugrenzen. Während ich in meinem Grundstudium etwas über Scheme (ein Lisp-Dialekt) gelernt hatte, hatte ich nie wirklich eine Anerkennung dafür bekommen. Durch diesen Kurs habe ich definitiv eine Wertschätzung für Lisp und seine Dialekte gewonnen.

Probleme mit dem, was Sie vorschlagen:

1. Es ist schwierig / langsam, einen AST in einer grafischen Umgebung zu erstellen. Schließlich können die meisten von uns schneller tippen, als wir eine Maus bewegen können. Und dennoch stellt sich die Frage, wie man mit einem Tablet Programmcode schreibt. Das Tippen auf einem Tablet ist im Vergleich zu einer Tastatur / einem Laptop mit einer Hardwaretastatur langsam / umständlich. Wenn Sie einen AST erstellen könnten, indem Sie Komponenten von einer Palette auf eine Leinwand auf einem großen Touchscreen-Gerät ziehen und dort ablegen, könnte die Programmierung auf einem Tablet zu einer echten Sache werden.

2. nur wenige / keine unserer vorhandenen Tools unterstützen dies. Wir haben jahrzehntelange Entwicklungsarbeit in die Erstellung immer komplexerer IDEs und immer intelligenterer Editoren gesteckt. Wir haben all diese Tools zum Neuformatieren von Text, Vergleichen von Text und Durchsuchen von Text. Wo sind die Werkzeuge, die eine Suche nach regulären Ausdrücken über einen Baum hinweg durchführen können? Oder ein Unterschied von zwei Bäumen? All diese Dinge lassen sich leicht mit Text erledigen. Aber sie können nur die Wörter vergleichen. Ändern Sie einen Variablennamen so, dass die Wörter unterschiedlich sind, die semantische Bedeutung jedoch gleich ist und diese Diff-Tools Probleme bekommen. Mit solchen Tools, die entwickelt wurden, um ASTs anstelle von Text zu verarbeiten, können Sie die semantische Bedeutung besser vergleichen. Das wäre eine gute Sache.

3. Während das Umwandeln von Programm-Quellcode in einen AST relativ gut verstanden ist (wir haben Compiler und Interpreter, nicht wahr?), ist das Umwandeln eines AST in Programmcode nicht so gut verstanden. Das Multiplizieren von zwei Primzahlen, um eine große, zusammengesetzte Zahl zu erhalten, ist relativ einfach, aber das Zurückrechnen einer großen, zusammengesetzten Zahl in Primzahlen ist viel schwieriger; Das ist der Punkt, an dem wir uns mit dem Parsen und Dekompilieren von ASTs befassen. Hier werden die Unterschiede zwischen den Sprachen zum Problem. Selbst innerhalb einer bestimmten Sprache gibt es mehrere Möglichkeiten, einen AST zu dekompilieren. Zum Beispiel durch eine Sammlung von Objekten iterieren und ein Ergebnis erhalten. Verwenden Sie eine for-Schleife, die ein Array durchläuft? Das wäre kompakt und schnell, aber es gibt Einschränkungen. Verwenden Sie einen Iterator, Arbeiten an einer Sammlung? Diese Sammlung kann eine variable Größe haben, was die Flexibilität auf (mögliche) Kosten der Geschwindigkeit erhöht. Karte verkleinern? Komplexer, aber implizit parallelisierbar. Und das nur für Java, abhängig von Ihren Vorlieben.

Mit der Zeit wird der Entwicklungsaufwand erhöht und wir werden mit Touchscreens und ASTs entwickeln. Tippen wird weniger notwendig. Ich sehe das als logische Weiterentwicklung von unserem derzeitigen Stand an, wenn wir uns ansehen, wie wir heute mit Computern umgehen. Das wird die erste Aufgabe lösen.

Wir arbeiten bereits mit Bäumen. Lisp ist lediglich serialisierte ASTs. XML (und HTML als Erweiterung) ist nur ein serialisierter Baum. Für die Suche haben wir bereits einige Prototypen: XPath und CSS (für XML bzw. HTML). Wenn grafische Werkzeuge erstellt werden, mit denen wir CSS-artige Selektoren und Modifikatoren erstellen können, haben wir einen Teil von # 2 gelöst. Wenn diese Selektoren erweitert werden können, um reguläre Ausdrücke zu unterstützen, sind wir näher dran. Ich suche noch ein gutes grafisches Diff-Tool zum Vergleichen von zwei XML- oder HTML-Dokumenten. Während die Leute diese Tools entwickeln, wird # 2 gelöst werden können. Die Leute arbeiten bereits an solchen Dingen; Sie sind einfach noch nicht da.

Die einzige Möglichkeit, diese ASTs in Programmiersprachentexte zu dekompilieren, wäre etwas Zielstrebendes. Wenn ich vorhandenen Code ändere, kann das Ziel durch einen Algorithmus erreicht werden, der meinen geänderten Code dem Startcode so ähnlich wie möglich macht (minimaler Textunterschied). Wenn ich Code von Grund auf neu schreibe, ist das Ziel möglicherweise der kleinste und engste Code (wahrscheinlich eine for-Schleife). Oder es könnte Code sein, der so effizient wie möglich parallelisiert (wahrscheinlich eine Karte / Verkleinerung oder etwas, das CSP einbezieht). Aus diesem Grund kann derselbe AST auch in derselben Sprache zu erheblich unterschiedlichem Code führen, je nachdem, wie die Ziele festgelegt wurden. Die Entwicklung eines solchen Systems würde # 3 lösen. Es wäre rechenintensiv, was bedeutet, dass wir wahrscheinlich eine Art Client-Server-Anordnung benötigen würden.

Wenn Sie die Debatte über Formatierungsstile beenden möchten, möchten Sie vielleicht einen Editor, der eine Quelldatei einliest und sie nach Ihren persönlichen Wünschen für die Anzeige und Bearbeitung formatiert. Wenn Sie sie jedoch speichern, formatieren Sie den ausgewählten Stil im Team neu Verwendet.

Es ist ganz einfach, wenn Sie einen Editor wie Emacs verwenden . Das Ändern des Formatierungsstils einer gesamten Datei erfolgt mit drei Befehlen.

Sie sollten auch in der Lage sein, die Hooks zu erstellen, um eine Datei beim Laden automatisch in Ihren eigenen Stil umzuwandeln und beim Speichern in den Teamstil umzuwandeln.

Es ist schwierig, einen AST anstatt des Quellcodes zu lesen und zu ändern.

Einige compilerbezogene Tools ermöglichen jedoch die Verwendung des AST. Java-Bytecode und .NET-Zwischencode funktionieren ähnlich wie ein AST.

es ist eine nette Idee; Das AST jeder Sprache unterscheidet sich jedoch von jedem anderen.

Die einzige mir bekannte Ausnahme betrifft VB.NET und C #, bei denen Microsoft argumentiert, dass es sich um "genau dieselbe Sprache mit unterschiedlicher Syntax" handelt. Sogar andere .NET-Sprachen (IronPython, F #, was auch immer) sind auf AST-Ebene unterschiedlich.

Dieselbe Sache mit JVM-Sprachen, alle zielen auf denselben Bytecode ab, aber die Sprachkonstrukte sind unterschiedlich, wodurch es unterschiedliche Sprachen und unterschiedliche ASTs gibt.

Selbst "Thin Layer" -Sprachen wie CoffeScript und Xtend teilen einen Großteil der Theorie der zugrunde liegenden Sprachen (JavaScript bzw. Java). Einführung von Konzepten auf höherer Ebene, die auf AST-Ebene beibehalten werden (oder sollten).

Wenn Xtend aus einem Java-AST rekonstruiert werden könnte, wäre es meiner Meinung nach als Java-to-Xtend-Uncompiler definiert worden, der auf magische Weise Abstraktionen auf höherer Ebene aus vorhandenem Java-Code erzeugt.