Für die Implementierung eines Interpreters in C/C++ benötigte Referenzen

Question

Ich bin an ein Projekt gebunden, um einen Interpreter in eine vorhandene Anwendung zu integrieren. Die zu interpretierende Sprache ist eine Ableitung von Lisp mit anwendungsspezifischen Builtins. Einzelne 'Programme' werden im Batch-Stil in der Anwendung ausgeführt.

Ich bin überrascht, dass ich im Laufe der Jahre ein paar Compiler und mehrere datensprachliche Übersetzer/Parser geschrieben habe, aber ich habe noch nie einen Interpreter geschrieben. Der Prototyp ist ziemlich weit, implementiert als Syntax-Baum-Walker, in C++. Ich kann wahrscheinlich die Architektur jenseits des Prototyps beeinflussen, aber nicht die Implementierungssprache (C++). So, Einschränkungen:

• Implementierung in C++
• Parsing wird wahrscheinlich mit einer yacc/Bison Grammatik behandelt werden (es ist jetzt) ​​
• Vorschläge von vollständigen VM/Dolmetscher ecologies wie NekoVM und LLVM sind wahrscheinlich nicht praktisch für dieses Projekt. Self-contained ist besser, auch wenn dies wie NIH klingt.

Was ich wirklich suche, liest Material über die Grundlagen der Implementierung von Dolmetschern. Ich habe ein wenig über SO geblättert und eine andere Seite, die als Lambda the Ultimate bekannt ist, obwohl sie mehr auf Programmiersprachen-Theorie ausgerichtet sind.

Einige der tidbits ich bisher gesammelt habe:

• Lisp in Small Pieces, von Christian Queinnec. Die Person, die es empfohlen hat, sagte, dass es "vom trivialen Interpreter zu fortgeschritteneren Techniken geht und die Darstellung von Bytecode und 'Scheme to C' Compilern beendet."

• NekoVM. Wie ich oben erwähnt habe, bezweifle ich, dass wir ein vollständiges VM-Framework zur Unterstützung dieses Projekts integrieren könnten.

• Structure and Interpretation of Computer Programs. Ursprünglich habe ich vorgeschlagen, dass dies vielleicht zu viel ist, aber nachdem ich einen gesunden Brocken durchgearbeitet habe, stimme ich @JBF zu. Sehr informativ und bewusstseinserweiternd.

• On Lisp von Paul Graham. Ich habe das gelesen, und obwohl es eine informative Einführung in Lisp-Prinzipien ist, reicht das nicht aus, um mit der Konstruktion eines Interpreters zu beginnen.

• Parrot Implementation. Das scheint eine lustige Lektüre zu sein. Nicht sicher, dass es mir die Grundlagen liefern wird.

• Scheme from Scratch. Peter Michaux greift verschiedene Implementierungen von Scheme an, von einem schnellen, in C geschriebenen Scheme-Interpreter (zur Verwendung als Bootstrap in späteren Projekten) bis zum kompilierten Scheme-Code. Sehr interessant bis jetzt.

• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, empfohlen im Kommentar-Thread für Books On Creating Interpreted Languages. Das Buch enthält zwei Kapitel, die sich mit der Praxis befassen, Dolmetscher zu bauen, also füge ich es meiner Leseschleife hinzu.

• New (und noch Old, das heißt 1979): Writing Interactive Compilers and Interpreters von P. J. Brown. Dies ist lange nicht mehr möglich, aber es ist interessant, einen Überblick über die verschiedenen Aufgaben zu geben, die mit der Implementierung eines Basic-Interpreters verbunden sind.Ich habe gemischte Kritiken für dieses Thema gesehen, aber da es billig ist (ich habe es auf Bestellung für ca. $ 3.50 verwendet), werde ich es drehen.

Wie wäre es damit? Gibt es ein gutes Buch, das den Neuling an die Hand nimmt und zeigt, wie man einen Interpreter in C/C++ für eine Lisp-ähnliche Sprache erstellt? Haben Sie eine Präferenz für Syntax-Tree-Walker oder Bytecode-Interpreter?

@JBF zu beantworten:

• der aktuelle Prototyp ist ein Interpreter, und es macht Sinn für mich, wie wir einen Pfad zu einer beliebigen Code-Datei zu akzeptieren und sie in unserer Anwendungsumgebung ausgeführt wird. Die Builtins werden verwendet, um unsere In-Memory-Datendarstellung zu beeinflussen.

• sollte es nicht schrecklich langsam sein. Der aktuelle Baumläufer scheint akzeptabel.

• Die Sprache ist basiert auf Lisp, ist aber nicht Lisp, also keine Einhaltung der Standards erforderlich.

• Wie oben erwähnt, ist es unwahrscheinlich, dass wir ein vollständiges externes VM/Interpreter-Projekt hinzufügen können, um dieses Problem zu lösen.

Zu den anderen Plakaten werde ich auch Ihre Zitate überprüfen. Danke, alles!

Answer 1

Kurze Antwort:

Die grundlegende Leseliste für ein Lisp-Interpreter ist SICP. Ich würde es gar nicht als Overkill bezeichnen, wenn Sie das Gefühl haben, für die ersten Teile des Buches überqualifiziert zu sein, springen Sie zu Kapitel 4 und fangen Sie an zu interpretieren (obwohl ich denke, dass dies ein Verlust wäre, da die Kapitel 1-3 wirklich so gut sind!) .

Hinzufügen LISP in kleinen Stücken (LISP von jetzt an), Kapitel 1-3. Vor allem Kapitel 3, wenn Sie nicht-triviale Kontrollformulare implementieren müssen.

Siehe diesen Beitrag von Jens Axel Søgaard auf einem minimalen Selbst-Hosting-Schema: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html.

Eine etwas längere Antwort:

Es ist schwer, Ratschläge zu geben, ohne zu wissen, was Sie von Ihrem Dolmetscher benötigen.

muss es wirklich ein Interpreter sein, oder müssen Sie tatsächlich Lisp-Code ausführen können?

muss es schnell sein?

braucht es die Einhaltung von Normen? Gemeinsame Lippen? R5RS? R6RS? Irgendwelche SFRIs benötigen Sie?

Wenn Sie etwas mehr Phantasie als eine einfache Syntax Tree Walker benötigen, würde ich dringend die Einbettung eines schnellen Schema-Subsystem empfehlen. Gambit-Schema kommt in den Sinn: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page.

Wenn dies keine Option Kapitel 5 in SICP und Kapitel 5 - in LISP Ziel Kompilierung für schnellere Ausführung ist.

Für eine schnellere Interpretation würde ich mir die neuesten JavaScript-Interpreter/Compiler ansehen. Es scheint eine Menge Überlegung in die schnelle Ausführung von JavaScript zu gehen, und Sie können wahrscheinlich von ihnen lernen. V8 zitiert zwei wichtige Papiere: http://code.google.com/apis/v8/design.html und Squirrelfish zitiert ein Paar: http://webkit.org/blog/189/announcing-squirrelfish/.

Es gibt auch die kanonischen Schema Papiere: http://library.readscheme.org/page1.html für den RABBIT-Compiler.

Wenn ich ein wenig vorzeitige Spekulation betreibe, könnte Speicherverwaltung die harte Nuss zu knacken sein. Nils M Holm hat ein Buch "Scheme 9 from empty space" http://www.t3x.org/s9fes/ veröffentlicht, das eine einfache Stop-the-World-Markierung und Sweep Garbage Collector enthält. Quelle enthalten.

John Rose (neuere JVM Berühmtheit) hat eine Arbeit über die Integration von Scheme zu C geschrieben: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92.

Answer 2

Auschecken JScheme from Peter Norvig. Ich fand das erstaunlich einfach zu verstehen und nach C++ zu portieren. Äh, ich weiß nicht, wie ich Schema als Skriptsprache benutze - es jrs zu lehren ist mühsam und fühlt sich altmodisch an (helloooo 1980).

Answer 3

The Kamin Interpreters aus Samuel Kamin's Buch Programmiersprachen, ein Interpreter-basierter Ansatz, übersetzt in C++ von Timothy Budd. Ich bin nicht sicher, wie nützlich der blanke Quellcode sein wird, wie es eigentlich mit dem Buch gemeint war, aber es ist ein gutes Buch, das die Grundlagen der Implementierung von Lisp in einer niedrigeren Sprache behandelt, einschließlich Müllsammlung usw. (Das ist nicht der Fokus des Buches, das Programmiersprachen im Allgemeinen ist, aber es ist abgedeckt.)

Lisp in kleinen Stücken geht in die Tiefe, aber das ist sowohl gut als auch schlecht für Ihren Fall. Es gibt viel Material zum Kompilieren und so, das wird für Sie nicht relevant sein, und seine einfacheren Interpreter sind in Scheme, nicht in C++.

SICP ist gut, definitiv. Nicht übertrieben, aber natürlich Dolmetscher zu schreiben ist nur ein Bruchteil des Buches.

Der JScheme-Vorschlag ist auch ein guter (und enthält einen Code von mir), aber wird Ihnen mit Dingen wie GC nicht helfen.

Ich könnte das später mit weiteren Vorschlägen ausstatten.

Bearbeiten: Ein paar Leute haben gesagt, dass sie von meinem awklisp gelernt haben. Dies ist zugegebenermaßen ein merkwürdiger Vorschlag, aber er ist sehr klein, lesbar, tatsächlich verwendbar und im Gegensatz zu anderen winzigen, noch lesbaren Spielzeug-Lisps implementiert er seinen eigenen Garbage Collector und seine Datenrepräsentation anstatt sich auf eine zugrundeliegende High-Level-Implementierungssprache zu verlassen stelle sie zur Verfügung.

Answer 4

Ja auf SICP.

ich diese Aufgabe mehrmals getan haben und hier ist was ich tun würde, wenn ich Sie wäre:

zuerst Ihre Speichermodell entwerfen. Sie werden ein GC-System irgendeiner Art wollen. Es ist WAAAAY einfacher, dies zuerst zu tun, als später anzuschrauben.

Entwerfen Sie Ihre Datenstrukturen. In meinen Implementierungen hatte ich eine Basis-Cons-Box mit einer Anzahl von Basistypen: Atom, String, Zahl, Liste, Bool, Primitiv-Funktion.

Entwerfen Sie Ihre VM und achten Sie darauf, die API sauber zu halten.Meine letzte Implementierung hatte dies als Top-Level-API (die Formatierung vergeben - so meine Vorschau ist pooching)

ConsBoxFactory &GetConsBoxFactory() { return mConsFactory; } 
AtomFactory &GetAtomFactory() { return mAtomFactory; } 
Environment &GetEnvironment() { return mEnvironment; } 
t_ConsBox *Read(iostream &stm); 
t_ConsBox *Eval(t_ConsBox *box); 
void Print(basic_ostream<char> &stm, t_ConsBox *box); 
void RunProgram(char *program); 
void RunProgram(iostream &stm); 

RunProgram nicht benötigt wird - es in Bezug auf Lesen, Eval und Druck umgesetzt wird. REPL ist ein gängiges Muster für Dolmetscher, insbesondere LISP.

Eine ConsBoxFactory ist verfügbar, um neue Boxen zu erstellen und mit ihnen zu arbeiten. Eine AtomFactory wird verwendet, damit äquivalente symbolische Atome genau einem Objekt zugeordnet werden. Eine Umgebung wird verwendet, um die Bindung von Symbolen an Datensicherungsboxen aufrechtzuerhalten.

Die meisten Ihrer Arbeit sollten in diese drei Schritte gehen. Dann werden Sie feststellen, dass Ihr Client-Code und Support-Code sehr ähnlich wie LISP zu schauen beginnt:

t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list) 
{ 
    return Car(Cdr(list)); 
} 

Sie können den Parser in yacc/lex schreiben, aber warum die Mühe? Lisp ist ein unglaublich einfaches Grammatik- und Scanner/Recursive-Descent-Parser-Paar, denn es sind ungefähr zwei Stunden Arbeit. Der schlimmste Teil besteht darin, Prädikate zu schreiben, um die Token zu identifizieren (dh IsString, IsNumber, IsQuotedExpr usw.) und dann Routinen zu schreiben, um die Token in Con-Boxen umzuwandeln.

Machen Sie es einfach, Leim in und aus C-Code zu schreiben, und machen Sie es leicht, Probleme zu beheben, wenn etwas schief läuft.

Answer 5

Ich möchte meine Empfehlung für Programming Languages: Application and Interpretation erweitern. Wenn Sie einen Dolmetscher schreiben möchten, führt Sie dieses Buch auf einem sehr kurzen Weg dahin. Wenn du den Code liest, den du gelesen hast und die Übung gemacht hast, landest du mit einem Haufen ähnlicher Interpreten, die unterschiedlich sind (der eine ist eifrig, der andere ist faul, der andere dynamisch, der andere etwas schreibend, der andere dynamisch) andere haben lexikalischen Umfang, etc).