Ich habe eine Programmiersprache geschrieben. So können Sie auch.

In den letzten 6 Monaten habe ich an einer Programmiersprache namens Pinecone gearbeitet. Ich würde es noch nicht als ausgereift bezeichnen, aber es verfügt bereits über genügend Funktionen, um verwendet werden zu können, wie z.

  • Variablen
  • Funktionen
  • benutzerdefinierte Strukturen

Wenn Sie daran interessiert sind, besuchen Sie die Zielseite von Pinecone oder das GitHub-Repo.

Ich bin kein Experte. Als ich dieses Projekt startete, hatte ich keine Ahnung, was ich tat, und ich weiß es immer noch nicht. Ich habe keine Unterrichtsstunden zur Erstellung von Sprachen belegt, online nur ein wenig darüber gelesen und bin nicht viel von den Ratschlägen gefolgt, die mir gegeben wurden.

Und trotzdem habe ich eine völlig neue Sprache gemacht. Und es funktioniert. Also muss ich etwas richtig machen.

In diesem Beitrag werde ich unter die Haube tauchen und Ihnen die Pipeline zeigen, mit der Pinecone (und andere Programmiersprachen) Quellcode in Magie verwandeln.

Ich werde auch auf einige der Kompromisse eingehen, die ich gemacht habe, und warum ich die Entscheidungen getroffen habe, die ich getroffen habe.

Dies ist keineswegs ein vollständiges Tutorial zum Schreiben einer Programmiersprache, aber es ist ein guter Ausgangspunkt, wenn Sie neugierig auf die Sprachentwicklung sind.

Loslegen

„Ich habe absolut keine Ahnung, wo ich überhaupt anfangen würde“, höre ich oft, wenn ich anderen Entwicklern sage, dass ich eine Sprache schreibe. Falls dies Ihre Reaktion ist, werde ich jetzt einige erste Entscheidungen und Schritte durchgehen, die beim Starten einer neuen Sprache unternommen werden.

Kompiliert vs interpretiert

Es gibt zwei Haupttypen von Sprachen: kompiliert und interpretiert:

  • Ein Compiler findet heraus, was ein Programm tun wird, wandelt es in „Maschinencode“ um (ein Format, das der Computer sehr schnell ausführen kann) und speichert es dann, um es später auszuführen.
  • Ein Interpreter geht zeilenweise durch den Quellcode und findet heraus, was er tut.

Technisch könnte jede Sprache kompiliert oder interpretiert werden, aber die eine oder andere ist normalerweise für eine bestimmte Sprache sinnvoller. Im Allgemeinen ist das Dolmetschen flexibler, während das Kompilieren tendenziell eine höhere Leistung aufweist. Dies kratzt jedoch nur an der Oberfläche eines sehr komplexen Themas.

Ich schätze die Leistung sehr und habe einen Mangel an Programmiersprachen festgestellt, die sowohl leistungsstark als auch auf Einfachheit ausgerichtet sind. Deshalb habe ich mich für die Kompilierung für Pinecone entschieden.

Dies war eine wichtige Entscheidung, die frühzeitig getroffen werden musste, da viele Entscheidungen zum Sprachdesign davon betroffen sind (z. B. ist statische Typisierung ein großer Vorteil für kompilierte Sprachen, für interpretierte Sprachen jedoch weniger).

Trotz der Tatsache, dass Pinecone für das Kompilieren entwickelt wurde, verfügt es über einen voll funktionsfähigen Interpreter, der die einzige Möglichkeit war, ihn für eine Weile auszuführen. Dafür gibt es eine Reihe von Gründen, die ich später erläutern werde.

Eine Sprache auswählen

Ich weiß, dass es ein bisschen meta ist, aber eine Programmiersprache ist selbst ein Programm, und daher müssen Sie es in einer Sprache schreiben. Ich habe mich wegen der Leistung und des großen Funktionsumfangs für C ++ entschieden. Außerdem arbeite ich sehr gerne in C ++.

Wenn Sie eine interpretierte Sprache schreiben, ist es sehr sinnvoll, sie in einer kompilierten Sprache (wie C, C ++ oder Swift) zu schreiben, da sich die in der Sprache Ihres Dolmetschers und des Dolmetschers, der Ihren Dolmetscher dolmetscht, verlorene Leistung zusammensetzt.

Wenn Sie kompilieren möchten, ist eine langsamere Sprache (wie Python oder JavaScript) akzeptabler. Die Kompilierungszeit mag schlecht sein, aber meiner Meinung nach ist das nicht annähernd so wichtig wie die schlechte Laufzeit.

Hochwertiges Design

Eine Programmiersprache ist im Allgemeinen als Pipeline strukturiert. Das heißt, es hat mehrere Stufen. In jeder Phase sind Daten auf eine bestimmte, genau definierte Weise formatiert. Es hat auch Funktionen zum Transformieren von Daten von jeder Stufe zur nächsten.

Die erste Stufe ist eine Zeichenfolge, die die gesamte Eingabequelldatei enthält. Die letzte Phase kann ausgeführt werden. Dies alles wird deutlich, wenn wir Schritt für Schritt die Pinecone-Pipeline durchlaufen.

Lexing

Der erste Schritt in den meisten Programmiersprachen ist das Lexen oder Tokenisieren. 'Lex' ist die Abkürzung für lexikalische Analyse, ein sehr ausgefallenes Wort, um eine Menge Text in Token aufzuteilen. Das Wort "Tokenizer" macht viel mehr Sinn, aber "Lexer" macht so viel Spaß zu sagen, dass ich es trotzdem benutze.

Token

Ein Token ist eine kleine Einheit einer Sprache. Ein Token kann ein Variablen- oder Funktionsname (AKA eine Kennung), ein Operator oder eine Zahl sein.

Aufgabe des Lexers

Der Lexer soll eine Zeichenfolge aufnehmen, die einen ganzen Quellcode enthält, und eine Liste mit jedem Token ausspucken.

Zukünftige Phasen der Pipeline beziehen sich nicht auf den ursprünglichen Quellcode, daher muss der Lexer alle von ihm benötigten Informationen produzieren. Der Grund für dieses relativ strenge Pipeline-Format ist, dass der Lexer Aufgaben wie das Entfernen von Kommentaren oder das Erkennen, ob etwas eine Nummer oder eine Kennung ist, ausführen kann. Sie möchten diese Logik im Lexer gesperrt halten, damit Sie beim Schreiben der restlichen Sprache nicht über diese Regeln nachdenken müssen und diese Art von Syntax an einem Ort ändern können.

Biegen

An dem Tag, an dem ich mit der Sprache anfing, schrieb ich als erstes einen einfachen Lexer. Bald darauf lernte ich Tools kennen, die das Lexen angeblich einfacher und weniger fehlerhaft machen würden.

Das vorherrschende Tool dieser Art ist Flex, ein Programm, das Lexer generiert. Sie geben ihm eine Datei mit einer speziellen Syntax zur Beschreibung der Grammatik der Sprache. Daraus wird ein C-Programm generiert, das einen String lexiert und die gewünschte Ausgabe erzeugt.

Meine Entscheidung

Ich entschied mich dafür, den Lexer zu behalten, den ich vorerst geschrieben hatte. Am Ende sah ich keine signifikanten Vorteile der Verwendung von Flex, zumindest nicht genug, um das Hinzufügen einer Abhängigkeit und das Komplizieren des Erstellungsprozesses zu rechtfertigen.

Mein Lexer ist nur ein paar hundert Zeilen lang und bereitet mir selten Probleme. Das Rollen meines eigenen Lexers bietet mir auch mehr Flexibilität, z. B. die Möglichkeit, der Sprache einen Operator hinzuzufügen, ohne mehrere Dateien zu bearbeiten.

Parsing

Die zweite Stufe der Pipeline ist der Parser. Der Parser wandelt eine Liste von Token in einen Baum von Knoten um. Ein Baum, der zum Speichern dieses Datentyps verwendet wird, wird als abstrakter Syntaxbaum oder AST bezeichnet. Zumindest in Pinecone hat der AST keine Informationen über Typen oder welche Bezeichner welche sind. Es sind einfach strukturierte Token.

Parser Pflichten

Der Parser fügt der geordneten Liste der vom Lexer erzeugten Token Struktur hinzu. Um Mehrdeutigkeiten zu vermeiden, muss der Parser Klammern und die Reihenfolge der Operationen berücksichtigen. Das einfache Parsen von Operatoren ist nicht besonders schwierig, aber wenn mehr Sprachkonstrukte hinzugefügt werden, kann das Parsen sehr komplex werden.

Bison

Es gab erneut die Entscheidung, eine Bibliothek eines Drittanbieters einzubeziehen. Die vorherrschende Analysebibliothek ist Bison. Bison funktioniert sehr ähnlich wie Flex. Sie schreiben eine Datei in einem benutzerdefinierten Format, in dem die Grammatikinformationen gespeichert sind, und Bison generiert daraus ein C-Programm, das Ihre Analyse durchführt. Ich habe mich nicht für Bison entschieden.

Warum Custom besser ist

Mit dem Lexer war die Entscheidung, meinen eigenen Code zu verwenden, ziemlich offensichtlich. Ein Lexer ist ein so triviales Programm, dass es sich fast so albern anfühlte, wenn ich nicht mein eigenes "linkes Pad" schrieb.

Beim Parser ist das eine andere Sache. Mein Pinecone-Parser ist derzeit 750 Zeilen lang, und ich habe drei davon geschrieben, weil die ersten beiden Müll waren.

Ich habe meine Entscheidung ursprünglich aus mehreren Gründen getroffen, und obwohl sie nicht ganz reibungslos verlief, gelten die meisten davon. Die wichtigsten sind wie folgt:

  • Minimieren Sie die Kontextumschaltung im Workflow: Die Kontextumschaltung zwischen C ++ und Pinecone ist schon schlimm genug, ohne Bisons Grammatikgrammatik zu verwenden
  • Halten Sie den Build einfach: Jedes Mal, wenn sich die Grammatik ändert, muss Bison vor dem Build ausgeführt werden. Dies kann automatisiert werden, wird jedoch beim Umschalten zwischen Build-Systemen zu einem Problem.
  • Ich mag es, coole Scheiße zu bauen: Ich habe Pinecone nicht gemacht, weil ich dachte, es wäre einfach. Warum sollte ich dann eine zentrale Rolle delegieren, wenn ich es selbst tun könnte? Ein benutzerdefinierter Parser ist möglicherweise nicht trivial, aber vollständig machbar.

Am Anfang war ich mir nicht ganz sicher, ob ich einen tragfähigen Weg einschlagen würde, aber mir wurde Vertrauen gegeben, was Walter Bright (Entwickler einer frühen Version von C ++ und Schöpfer der D-Sprache) zu sagen hatte Thema:

„Etwas kontroverser würde ich keine Zeit mit Lexer- oder Parser-Generatoren und anderen sogenannten„ Compiler-Compilern “verschwenden. Sie sind Zeitverschwendung. Das Schreiben eines Lexers und Parsers ist ein winziger Prozentsatz der Aufgabe, einen Compiler zu schreiben. Die Verwendung eines Generators nimmt ungefähr so ​​viel Zeit in Anspruch wie das Schreiben eines Generators und heiratet Sie mit dem Generator (was wichtig ist, wenn Sie den Compiler auf eine neue Plattform portieren). Und Generatoren haben auch den unglücklichen Ruf, miese Fehlermeldungen auszusenden. “

Aktionsbaum

Wir haben jetzt den Bereich der allgemeinen Begriffe verlassen, oder zumindest weiß ich nicht mehr, was die Begriffe sind. Nach meinem Verständnis ähnelt das, was ich als "Aktionsbaum" bezeichne, am ehesten der IR (Zwischendarstellung) von LLVM.

Es gibt einen subtilen, aber sehr signifikanten Unterschied zwischen dem Aktionsbaum und dem abstrakten Syntaxbaum. Es hat eine ganze Weile gedauert, bis ich herausgefunden hatte, dass es sogar einen Unterschied zwischen ihnen geben sollte (was dazu beitrug, dass der Parser neu geschrieben werden musste).

Aktionsbaum gegen AST

Einfach ausgedrückt ist der Aktionsbaum der AST mit Kontext. Dieser Kontext enthält Informationen darüber, welchen Typ eine Funktion zurückgibt oder dass zwei Stellen, an denen eine Variable verwendet wird, tatsächlich dieselbe Variable verwenden. Da der gesamte Kontext herausgefunden und gespeichert werden muss, benötigt der Code, der den Aktionsbaum generiert, viele Namespace-Nachschlagetabellen und andere Dingsbums.

Ausführen des Aktionsbaums

Sobald wir den Aktionsbaum haben, ist es einfach, den Code auszuführen. Jeder Aktionsknoten hat eine Funktion 'Ausführen', die einige Eingaben entgegennimmt, alles tut, was die Aktion sollte (einschließlich möglicherweise des Aufrufs einer Unteraktion) und die Ausgabe der Aktion zurückgibt. Dies ist der Dolmetscher in Aktion.

Kompilierungsoptionen

"Aber warte!" Ich höre Sie sagen: "Soll Pinecone nicht kompiliert werden?" Ja ist es. Das Kompilieren ist jedoch schwieriger als das Interpretieren. Es gibt einige mögliche Ansätze.

Erstellen Sie meinen eigenen Compiler

Das klang für mich zunächst nach einer guten Idee. Ich liebe es, Dinge selbst zu machen, und ich habe mich nach einer Ausrede gesehnt, um bei der Montage gut zu werden.

Leider ist das Schreiben eines tragbaren Compilers nicht so einfach wie das Schreiben von Maschinencode für jedes Sprachelement. Aufgrund der Anzahl der Architekturen und Betriebssysteme ist es für jeden Einzelnen unpraktisch, ein plattformübergreifendes Compiler-Backend zu schreiben.

Sogar die Teams hinter Swift, Rust und Clang wollen sich nicht alleine darum kümmern, also nutzen sie stattdessen alle…

LLVM

LLVM ist eine Sammlung von Compiler-Tools. Es ist im Grunde eine Bibliothek, die Ihre Sprache in eine kompilierte ausführbare Binärdatei verwandelt. Es schien die perfekte Wahl zu sein, also sprang ich sofort ein. Leider überprüfte ich nicht, wie tief das Wasser war und ertrank sofort.

LLVM ist zwar keine Assemblersprache, aber eine gigantische komplexe Bibliothek. Es ist nicht unmöglich zu verwenden, und sie haben gute Tutorials, aber mir wurde klar, dass ich etwas Übung brauchen würde, bevor ich bereit war, einen Pinecone-Compiler damit vollständig zu implementieren.

Transpiling

Ich wollte eine Art kompilierten Tannenzapfen und ich wollte es schnell, also wandte ich mich einer Methode zu, von der ich wusste, dass ich sie zum Laufen bringen könnte: dem Transpilieren.

Ich habe einen Pinecone to C ++ - Transpiler geschrieben und die Möglichkeit hinzugefügt, die Ausgabequelle automatisch mit GCC zu kompilieren. Dies funktioniert derzeit für fast alle Pinecone-Programme (obwohl es einige Randfälle gibt, die dies verhindern). Es ist keine besonders tragbare oder skalierbare Lösung, funktioniert aber vorerst.

Zukunft

Vorausgesetzt, ich entwickle Pinecone weiter, wird es früher oder später Unterstützung beim LLVM-Kompilieren erhalten. Ich vermute, egal wie viel ich daran arbeite, der Transpiler wird niemals vollständig stabil sein und die Vorteile von LLVM sind zahlreich. Es ist nur eine Frage der Zeit, wann ich Zeit habe, einige Beispielprojekte in LLVM zu erstellen und den Dreh raus zu bekommen.

Bis dahin eignet sich der Interpreter hervorragend für einfache Programme, und das C ++ - Transpiling funktioniert für die meisten Dinge, die mehr Leistung benötigen.

Fazit

Ich hoffe, ich habe Programmiersprachen für Sie etwas weniger mysteriös gemacht. Wenn Sie selbst eines machen möchten, kann ich es nur empfehlen. Es gibt eine Menge Implementierungsdetails, die herausgefunden werden müssen, aber die Gliederung hier sollte ausreichen, um Sie zum Laufen zu bringen.

Hier sind meine allgemeinen Ratschläge für den Einstieg (denken Sie daran, ich weiß nicht wirklich, was ich tue, nehmen Sie es also mit einem Körnchen Salz):

  • Wenn Sie Zweifel haben, gehen Sie interpretiert. Interpretierte Sprachen sind im Allgemeinen einfacher zu entwerfen, zu erstellen und zu lernen. Ich entmutige Sie nicht, eine kompilierte zu schreiben, wenn Sie wissen, dass Sie das tun möchten, aber wenn Sie auf dem Zaun stehen, würde ich dolmetschen.
  • Wenn es um Lexer und Parser geht, machen Sie, was Sie wollen. Es gibt gültige Argumente für und gegen das Schreiben eigener. Am Ende spielt es keine Rolle, ob Sie Ihr Design durchdenken und alles auf vernünftige Weise implementieren.
  • Lerne aus der Pipeline, mit der ich gelandet bin. Bei der Entwicklung der Pipeline, die ich jetzt habe, wurde viel versucht. Ich habe versucht, ASTs, ASTs, die sich in vorhandene Aktionsbäume verwandeln, und andere schreckliche Ideen zu eliminieren. Diese Pipeline funktioniert, ändern Sie sie also nur, wenn Sie eine wirklich gute Idee haben.
  • Wenn Sie nicht die Zeit oder Motivation haben, eine komplexe Allzwecksprache zu implementieren, versuchen Sie, eine esoterische Sprache wie Brainfuck zu implementieren. Diese Interpreten können nur einige hundert Zeilen lang sein.

Ich bereue die Entwicklung von Pinecone nur sehr wenig. Ich habe auf dem Weg eine Reihe von schlechten Entscheidungen getroffen, aber den größten Teil des von solchen Fehlern betroffenen Codes neu geschrieben.

Derzeit befindet sich Pinecone in einem Zustand, in dem es gut funktioniert und leicht verbessert werden kann. Das Schreiben von Pinecone war für mich eine äußerst lehrreiche und erfreuliche Erfahrung, und es fängt gerade erst an.