Zephyr ASDL (abstrakte Syntaxbeschreibungssprache)

Lexer und Parser-Generatoren akzeptieren Beschreibungen von Lexemen und Grammatiken und erzeugen Code, der das entsprechende Artefakt implementiert. Lex benötigt einen regulären Ausdruck, um Tokens zu beschreiben. Parser-Generatoren verwenden verschiedene Arten von erweiterten BNF-Notationen.

Das Papier, auf das Sie verweisen, ist ziemlich klar. IMHO: ASDL ist eine kleine Sprache, um abstrakt eine Menge von Baumknoten (ihre Typen und Signaturen) zu beschreiben. Mit dieser Sprache kann man (und die Autoren des Papiers) ein Werkzeug schreiben, das diese Beschreibungen in die Menge von Datensatztypen umwandelt, die Sie zum Implementieren von Bäumen für die Verwendung mit einem Parser benötigen. ADSL ist also wie Regexes und BNF, da es einem Codegenerator zugeführt werden soll, der einen Teil eines Compilers erzeugt.

Eine expansive Ansicht ist, dass Compiler eine ziemlich gut verstandene Technologie sind, und dass man sie aus Beschreibungen verschiedener Stücke generieren könnte. Regex / BNF / ADSL sind die wesentlichen Schlüssel für die Parsing-Phase.

Sie würden im Idealfall die Beschreibungssprachen für Zielinstruktionssätze, Flussanalysen, Übersetzungen (Sie erwähnten maximalen Munch) von den abstrakten Bäumen zum Zielbefehlssatz und eine Möglichkeit, Optimierungen zu beschreiben, mögen. Dann mit entsprechenden Werkzeugen für jedes Stück, könnten Sie den gesamten Compiler aus "Spezifikationen" erstellen. Da ist tatsächlich war viel Arbeit in diesem Bereich; Menschen haben all diese Dinge getrennt und zusammen getan. Es überrascht nicht, dass ein Teil davon aus dem "Zephyr" -Projekt stammt, das ursprünglich aus Princeton stammte (scheint, dass die Zephyr-Website dort jetzt tot ist), deren Ziel es war, genau diese Art von Ding zu machen.

Wie auch immer, suchen Sie unter Google Scholar nach "Compiler-Generator".

ASDL wird verwendet, wenn Sie einen Baum in einem Modul erstellen und denselben Baum in einem anderen Modul (oder fast demselben Baum, irgendwie optimiert) eingeben müssen.

Dazu müssen Sie Funktionen der Konstruktion haben (idealerweise mit Typ-Checker), die Funktion, den Baum so zu drucken, dass Sie ihn sicher visualisieren, dass Sie ihn korrekt erzeugt haben.

ASDL nimmt als Eingabe einen Baum, der in einer Syntax geschrieben ist, die fast identisch mit der Syntax des algebraischen Datentyps ist (wie in Haskell oder ml), oder die Syntax in BNF, aber viel einfacher, und generiert automatisch alle Konstruktoren, Druckfunktionen beginnend mit der einfachen Beschreibung eines Baumes.

Wenn Sie beispielsweise einen Lexer haben, müssen Sie Lexeme generieren, die einen Typ haben. Sie müssen auch den Ausgabestrom von Lexemen sehen (das ist in linearer Form, also ein sehr einfacher Baum). Anstatt Funktionen zum Drucken zu schreiben und Lexeme zu konstruieren, definierst du sie in etwa so

und Sie rufen Konstruktoren ID, INT, FLOAT usw. von Ihrem Lexer. ASDL konvertiert diese einfache Syntax in alle Funktionen, die Sie benötigen, um Knoten für AST zu konstruieren oder um zu drucken, oder was auch immer Sie brauchen. ASDL auferlegt dem generierten Code keine Einschränkungen.

Wenn Sie attributes zu einem Typ hinzufügen, z. B. die Koordinaten eines Tokens, werden solche Attribute an die Parameter jedes Konstruktors von diesem Typ angehängt.

Ein komplexerer Baum, der von einem Parser erstellt wurde, würde so aussehen

In diesem Fall wird asdl prüfen, ob der vom Parser gemachte Aufruf von SUM (_ _) an die mit einem Konstruktor von expr erstellten Knoten übergeben wird. num_integer wird extern definiert, möglicherweise durch eine asdl-Struktur für den Lexer.

Beachten Sie, dass Sie keine Konstruktoren mit regulären Ausdrücken wie number: [0-9]+ definieren dürfen. ASDL ist einfacher als EBNF.

Diese Konstruktoren werden so definiert, dass sie, um das zu erstellen, was Sie brauchen, check eingeben, um sicherzustellen, dass Ihr Lexer / Parser / Code-Generator Bäume ausgibt, die der von asdl definierten Sprache entsprechen.

Um ASDL gut zu verstehen, müssen Sie 3-4 Parser schreiben und sehen, was in dem von ihnen generierten Code üblich ist. Dieser gemeinsame Teil ist tatsächlich ASDL, also ist dies eine Abstraktion für die Ausgabe der Parser im Besonderen.