Wie erstelle ich meine eigene Programmiersprache und einen Compiler dafür?

427

Ich bin gründlich in der Programmierung und bin auf Sprachen gestoßen, einschließlich BASIC, FORTRAN, COBOL, LISP, LOGO, Java, C ++, C, MATLAB, Mathematica, Python, Ruby, Perl, JavaScript, Assembler und so weiter. Ich kann nicht verstehen, wie Leute Programmiersprachen erstellen und Compiler dafür entwickeln. Ich konnte auch nicht verstehen, wie Leute Betriebssysteme wie Windows, Mac, UNIX, DOS und so weiter erstellen. Das andere, was mir rätselhaft ist, ist, wie Leute Bibliotheken wie OpenGL, OpenCL, OpenCV, Cocoa, MFC usw. erstellen. Das Letzte, was ich nicht herausfinden kann, ist, wie Wissenschaftler eine Assemblersprache und einen Assembler für einen Mikroprozessor entwickeln. Ich würde wirklich gerne all diese Sachen lernen und ich bin 15 Jahre alt. Ich wollte schon immer Informatiker sein, wie Babbage, Turing, Shannon oder Dennis Ritchie.


Ich habe bereits Ahos Compiler Design und Tanenbaums OS-Konzeptbuch gelesen, und alle behandeln Konzepte und Code nur auf hohem Niveau. Sie befassen sich nicht mit Details und Nuancen sowie mit der Entwicklung eines Compilers oder Betriebssystems. Ich möchte ein konkretes Verständnis, damit ich eines selbst erstellen kann und nicht nur ein Verständnis dafür, was ein Thread, eine Semaphore, ein Prozess oder ein Parsing ist. Ich habe meinen Bruder danach gefragt. Er ist ein SB-Student in EECS am MIT und hat keine Ahnung, wie man all diese Dinge in der realen Welt erschafft. Alles, was er weiß, ist nur ein Verständnis für Compiler-Design und Betriebssystemkonzepte wie die, die Sie erwähnt haben (z. B. Thread, Synchronisation, Parallelität, Speicherverwaltung, Lexikalische Analyse, Zwischencode-Generierung usw.).

abdul wakeel
quelle
Wenn Sie auf Unix / Linux sind, können Sie Informationen über spezielle Werkzeuge bekommen: lex, yaccund bison.
Mouviciel
Mein erster Vorschlag wäre, das Drachenbuch von Aho zu lesen. amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/…
Julian
1
Vielleicht nicht allzu hilfreich, aber ich empfehle, sites.google.com/site/steveyegge2/blog-rants (Steve Yegges Blog) und steve-yegge.blogspot.com/ (Steve Yegges anderes Blog) zu durchsuchen.
KK.
3
Lerne so viele Programmiersprachen wie möglich. Auf diese Weise lernen Sie sowohl aus ihren Konzepten als auch aus ihren Fehlern. Warum mit Zwergen zufrieden sein, wenn man Riesen auf der Schulter stehen kann?
sbi
1
Hinweis: Ein Interpreter ist einfacher als ein Compiler. Es ist nur eine Klasse, die etwas "tut", basierend auf dem eingegebenen Text, den sie Zeile für Zeile liest. ein weiterer tipp: binde dies an reflexion und du kannst beliebige objekte mit deinem script steuern.
Dave Cousineau

Antworten:

407

Grundsätzlich lautet Ihre Frage: "Wie werden Computerchips, Befehlssätze, Betriebssysteme, Sprachen, Bibliotheken und Anwendungen entworfen und implementiert?" Das ist eine weltweite Multi-Milliarden-Dollar-Branche, in der Millionen von Menschen beschäftigt sind, von denen viele Spezialisten sind. Vielleicht möchten Sie Ihre Frage ein bisschen mehr konzentrieren.

Das heißt, ich kann eine Pause machen bei:

Ich kann nicht verstehen, wie Leute Programmiersprachen erstellen und Compiler dafür entwickeln.

Es ist überraschend für mich, aber viele Leute betrachten Programmiersprachen als magisch. Wenn ich Leute auf Partys treffe oder was auch immer, wenn sie mich fragen, was ich tue, sage ich ihnen, dass ich Programmiersprachen entwerfe und die Compiler und Tools implementiere, und es ist überraschend, wie oft Leute - wohlgemerkt professionelle Programmierer - sagen "Wow, ich habe nie darüber nachgedacht, aber ja, jemand muss diese Dinge entwerfen." Es ist, als ob sie dachten, dass Sprachen nur entstehen, wenn sie bereits von Tool-Infrastrukturen umgeben sind.

Sie erscheinen nicht nur. Sprachen werden wie jedes andere Produkt entworfen: indem sorgfältig eine Reihe von Kompromissen zwischen konkurrierenden Möglichkeiten geschlossen werden. Die Compiler und Tools werden wie jedes andere professionelle Softwareprodukt erstellt: indem das Problem aufgeschlüsselt wird, eine Codezeile nach der anderen geschrieben wird und dann das daraus resultierende Programm auf den Prüfstand gestellt wird.

Sprachgestaltung ist ein großes Thema. Wenn Sie daran interessiert sind, eine Sprache zu entwerfen, sollten Sie sich zunächst überlegen, welche Mängel in einer Sprache vorliegen, die Sie bereits kennen. Konstruktionsentscheidungen ergeben sich häufig aus der Berücksichtigung eines Konstruktionsfehlers in einem anderen Produkt.

Stellen Sie sich alternativ eine Domain vor, an der Sie interessiert sind, und entwerfen Sie dann eine domänenspezifische Sprache (DSL), die Lösungen für Probleme in dieser Domain angibt. Sie erwähnten LOGO; Das ist ein großartiges Beispiel für eine DSL für die "Strichzeichnung" -Domäne. Reguläre Ausdrücke sind eine DSL für die Domäne "Finde ein Muster in einer Zeichenfolge". LINQ in C # / VB ist eine DSL für die Domäne "Daten filtern, zusammenführen, sortieren und projizieren". HTML ist eine DSL für die Domäne "Beschreiben des Layouts von Text auf einer Seite" usw. Es gibt viele Domänen, die für sprachbasierte Lösungen zugänglich sind. Einer meiner Favoriten ist Inform7, eine DSL für die Domain "textbasiertes Abenteuerspiel". Es ist wahrscheinlich die seriöseste Programmiersprache, die ich je gesehen habe.

Wenn Sie festgelegt haben, wie Ihre Sprache aussehen soll, notieren Sie sich genau, nach welchen Regeln ein legales und illegales Programm ermittelt werden soll. Normalerweise möchten Sie dies auf drei Ebenen tun:

  1. lexikalisch : Wie lauten die Regeln für Wörter in der Sprache, welche Zeichen sind zulässig, wie sehen Zahlen aus und so weiter?
  2. syntaktisch : wie verbinden sich wörter der sprache zu größeren einheiten? In C # sind größere Einheiten Ausdrücke, Anweisungen, Methoden, Klassen usw.
  3. semantisch : Wie finden Sie bei einem syntaktisch legalen Programm heraus, was das Programm tut ?

Schreiben Sie diese Regeln so genau wie möglich auf . Wenn Sie gute Arbeit leisten, können Sie dies als Grundlage für das Schreiben eines Compilers oder Interpreters verwenden. Schauen Sie sich die C # -Spezifikation oder die ECMAScript-Spezifikation an, um zu sehen, was ich meine. Sie stecken voller sehr präziser Regeln, die beschreiben, was ein Rechtsprogramm ausmacht und wie man herausfindet, was es tut.

Eine der besten Möglichkeiten, um mit dem Schreiben eines Compilers zu beginnen, ist das Schreiben eines Compilers für eine Hochsprache zu einer Hochsprache . Schreiben Sie einen Compiler, der Zeichenfolgen in Ihrer Sprache aufnimmt und Zeichenfolgen in C # oder JavaScript oder in einer anderen Sprache ausgibt. Lassen Sie den Compiler für diese Sprache sich dann darum kümmern, dass daraus ausführbarer Code wird.

Ich schreibe einen Blog über das Design von C #, VB, VBScript, JavaScript und anderen Sprachen und Tools. Wenn Sie dieses Thema interessiert, probieren Sie es aus. http://blogs.msdn.com/ericlippert (historisch) und http://ericlippert.com (aktuell)

Insbesondere könnte dieser Beitrag für Sie interessant sein. Hier liste ich die meisten Aufgaben auf, die der C # -Compiler während seiner semantischen Analyse für Sie ausführt. Wie Sie sehen, gibt es viele Stufen. Wir unterteilen das große Analyseproblem in eine Reihe von Problemen, die wir individuell lösen können.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/04/how-many-passes.aspx

Wenn Sie auf der Suche nach einem Job sind, der diese Dinge erledigt, wenn Sie älter sind, sollten Sie als Praktikant zu Microsoft kommen und versuchen, in die Entwicklerabteilung einzusteigen. So bin ich heute zu meiner Arbeit gekommen!

Eric Lippert
quelle
Haben Sie darüber geschrieben, inwieweit Compiler-Optimierungen nicht mehr durchgeführt werden, da die CLR sie automatisch durchführen kann?
6
@ Thorbjørn: Lassen Sie uns die Terminologie klarstellen. Ein "Compiler" ist ein Gerät, das von einer Programmiersprache in eine andere übersetzt. Das Schöne an einem C # -Compiler, der C # in IL umwandelt, und einem IL-Compiler (der "Jitter"), der IL in Maschinencode umwandelt, ist, dass Sie den C # -Compiler in IL schreiben können (einfach!) Und Setzen Sie die prozessorspezifischen Optimierungen in den Jitter. Es ist nicht so, dass Compiler-Optimierungen "nicht durchgeführt werden", sondern dass das JIT-Compiler-Team sie für uns erledigt. Siehe blogs.msdn.com/b/ericlippert/archive/2009/06/11/…
Eric Lippert
6
@ Cyclotis04: Inform6 wird in Z-Code kompiliert. Dies ist ein berühmtes, sehr frühes Beispiel für eine bytecode-basierte virtuelle Maschine. So könnten all diese Infocom-Spiele in den 1980er Jahren sowohl größer als der Speicher sein als auch auf mehrere Architekturen portierbar sein. Die Spiele wurden zu Z-Code kompiliert und anschließend wurden Z-Code-Interpreter mit Codespeicher-Paging für mehrere Computer implementiert. Heutzutage kann man natürlich einen Zcode-Interpreter auf einer Armbanduhr laufen lassen, aber damals war das Hightech . Einzelheiten finden Sie unter en.wikipedia.org/wiki/Z-machine .
Eric Lippert
@EricLippert Compiler ist kein Gerät, Gerät ist etwas, das Hardware enthält. Wir können sagen, ein vordefiniertes Programm, das einen Satz von Regeln hat, um Eingabedaten in Maschinencode umzuwandeln
dharam
2
@dhams: Ein Gerät ist alles, was für einen bestimmten Zweck gemacht wurde. Jeder Compiler, den ich jemals geschrieben habe, wurde auf einer Hardware ausgeführt, die speziell dafür entwickelt wurde, dass Compiler existieren können.
Eric Lippert
127

Vielleicht finden Sie in Lets Build a Compiler von Jack Crenshaw eine interessante Einführung in das Schreiben von Compilern und Assemblersprachen.

Der Autor hielt es sehr einfach und konzentrierte sich auf die Erstellung der tatsächlichen Funktionalität.

user1249
quelle
2
Das Interessante an Crenshaws Intro ist, dass es endet (Spoiler: Es ist unvollständig), genau zu dem Zeitpunkt, an dem Sie sich mit den Problemen befassen würden, die Ihnen klar werden würden, hey, ich hätte meine Sprache wirklich vollständig entwerfen sollen, bevor ich mit der Implementierung beginne. Und dann sagen Sie, hey, wenn ich eine vollständige Sprachspezifikation schreiben muss, warum nicht in einer formalen Notation, die ich dann in ein Tool einspeisen kann, um einen Parser zu generieren? Und dann machst du es wie alle anderen.
Irgendwann am
3
@kindall, du musst es von Hand gemacht haben, um zu erkennen, dass es einen Grund gibt, die Werkzeuge zu benutzen.
72

"Ich würde dieses Zeug wirklich gerne lernen". Wenn Sie langfristig ernst sind:

  • Gehen Sie aufs College und spezialisieren Sie sich auf Software-Engineering. Nehmen Sie jede Compiler-Klasse, die Sie bekommen können. Diejenigen, die den Unterricht anbieten, sind besser ausgebildet und erfahrener als Sie. Es ist gut, wenn ihre Expertenperspektiven verwendet werden, um die Informationen so darzustellen, wie Sie es niemals durch das Lesen von Code bekommen.

  • Bleib beim Matheunterricht durch die High School und mache für alle 4 Jahre weiter am College. Schwerpunkt Nicht-Standard-Mathematik: Logik, Gruppentheorie, Metamathematik. Dies wird Sie zwingen, abstrakt zu denken. Es wird Ihnen ermöglichen, die fortgeschrittenen Theoriepapiere zum Kompilieren zu lesen und zu verstehen, warum diese Theorien interessant und nützlich sind. Sie können diese fortgeschrittenen Theorien ignorieren, wenn Sie für immer hinter dem Stand der Technik stehen wollen.

  • Sammeln / Lesen Sie die Standard-Compilertexte: Aho / Ullman usw. Sie enthalten grundlegende Informationen, denen die Community im Allgemeinen zustimmt. Möglicherweise verwenden Sie nicht alles aus diesen Büchern, aber Sie sollten wissen, dass es es gibt, und Sie sollten wissen, warum Sie es nicht verwenden. Ich fand Muchnick großartig, aber es ist für ziemlich fortgeschrittene Themen.

  • Erstellen Sie einen Compiler. Beginnen Sie JETZT, indem Sie eine faule bauen. Dies wird Ihnen einige Probleme beibringen. Baue eine zweite. Wiederholen. Diese Erfahrung schafft enorme Synergien mit Ihrem Buchlernen.

  • Ein guter Einstieg ist das Erlernen von BNF (Backus Naur Form), Parsern und Parser-Generatoren. BNF wird praktisch überall im Compiler-Land verwendet, und Sie können nicht realistisch mit Ihren Compiler-Kollegen sprechen, wenn Sie es nicht wissen.

Wenn Sie eine großartige erste Einführung in das Kompilieren und den direkten Nutzen von BNF nicht nur für die Dokumentation, sondern auch als toolverarbeitbare Metasprache wünschen, lesen Sie dieses Tutorial (nicht meins) zum Erstellen von "Meta" -Compilern (Compiler, die Compiler erstellen) auf der Basis von a Artikel von 1964 (ja, Sie haben das richtig gelesen) ["META II eine syntaxorientierte Compiler-Schriftsprache" von Val Schorre. (http://doi.acm.org/10.1145/800257.808896)] Dieser IMHO ist einer der besten Comp-Sci-Artikel, die jemals geschrieben wurden: Er lehrt Sie, Compiler-Compiler auf 10 Seiten zu erstellen. Ich habe anfangs aus dieser Arbeit gelernt.

Was ich oben geschrieben habe, ist viel aus persönlicher Erfahrung, und ich denke, es hat mir ziemlich gute Dienste geleistet. YMMV, aber meiner Meinung nach nicht viel.

Ira Baxter
quelle
54
-1 Keines der oben genannten ist notwendig.
Neil Butter
77
@nbt Keines der oben genannten ist notwendig. Aber all das hilft. Wirklich viel.
Konrad Rudolph
1
Ich bin insbesondere anderer Meinung als "Mathematik lernen, um abstrakt zu denken!" Vorschlag. Auch wenn Sie der Meinung sind, dass "Lernen, abstrakt zu denken" beim Erstellen Ihrer eigenen Programmiersprache und Ihres Compilers besonders hilfreich ist (ich nicht - ich finde es viel nützlicher, wenn Sie lernen, indem Sie diese unglaublich indirekten Umwege gehen) Mathematik ist nicht der einzige Bereich mit abstrakten Gedanken! (Ich bin übrigens ein Mathematiker, also lehne ich die Verwendung von Mathematik im Allgemeinen nicht ab, nur die Anwendbarkeit in diesem speziellen Fall ...)
grautur
26
Wenn Sie die fortgeschrittenen technischen Artikel zur Compilertheorie lesen möchten, sollten Sie besser mathematisch kompetent sein. Sie können sich dafür entscheiden, diese Literatur zu ignorieren, und Ihre Theorie und damit die Compiler werden dafür ärmer sein. Die Neinsager hier machen alle den Punkt, dass Sie einen Compiler ohne viel formale Ausbildung bauen können, und ich stimme zu. Sie scheinen zu implizieren, dass man ohne sie wirklich gute Compiler bauen kann. Das ist keine Wette, die ich gerne annehmen würde.
Ira Baxter
7
CS ist eine Disziplin, die für das Design und die Implementierung von Sprachen von großem Nutzen ist. Natürlich nicht zwingend, aber es gibt Jahrzehnte der Forschung, die genutzt werden kann und sollte , und es gibt überhaupt keinen Grund, andere Fehler zu wiederholen.
Donal Fellows
46

Im Folgenden finden Sie ein Online-Buch / einen Online-Kurs mit dem Titel „ Die Elemente von Computersystemen: Aufbau eines modernen Computers aus ersten Prinzipien“ .

Mit Hilfe von Simulatoren bauen Sie ein komplettes Computersystem von Grund auf auf. Während viele Kommentatoren angegeben haben, dass Ihre Frage zu weit gefasst ist, beantwortet dieses Buch sie tatsächlich und bleibt dabei sehr überschaubar. Wenn Sie fertig sind, haben Sie ein Spiel in einer höheren Sprache (die Sie entworfen haben) geschrieben, das die Funktionalität Ihres eigenen Betriebssystems verwendet und das von Ihrem Compiler in eine VM-Sprache (die Sie entworfen haben) kompiliert wird Übersetzt in eine Assemblersprache (die Sie entworfen haben) von Ihrem VM-Übersetzer, die von Ihrem Assembler zu Maschinencode (der von Ihnen entworfen wurde) zusammengesetzt wird, der auf Ihrem Computersystem ausgeführt wird, das Sie aus Chips zusammensetzen, die Sie unter Verwendung der booleschen Logik und erstellt haben eine einfache Hardware-Beschreibungssprache.

Die Kapitel:

  1. Kursüberblick
  2. Boolesche Logik
  3. Kombinatorische Chips
  4. Sequenzielle Chips
  5. Maschinensprache
  6. Rechnerarchitektur
  7. Assembler
  8. Virtuelle Maschine I: Arithmetik
  9. Virtuelle Maschine II: Steuerung
  10. Programmiersprache
  11. Compiler I: Syntaxanalyse
  12. Compiler II: Codegenerierung
  13. Betriebssystem
  14. Listenpunkt

Mehr Spaß zum Mitnehmen

Colithium
quelle
Vielen Dank für die Änderungen, unbekannte Person. Ich habe es ein paar Mal versucht, konnte mich aber nicht genug auf die Beschreibung konzentrieren, wollte das Buch aber nicht erwähnen. Das Buch ist jetzt online unter dem Link zum Studienplan: www1.idc.ac.il/tecs/plan.html . Es ist auch sehr günstig online. Genießt alle.
Joe Internet
Ich wollte das selbst vorschlagen ... für die Faulen, schauen Sie sich das 10-minütige Intro an: Von NAND zu Tetris in 12 Schritten @ youtube.com/watch?v=JtXvUoPx4Qs
Richard Anthony Hein
46

Geh einen Schritt zurück. Ein Compiler ist einfach ein Programm, das ein Dokument in einer Sprache in ein Dokument in einer anderen Sprache übersetzt. Beide Sprachen sollten klar definiert und spezifisch sein.

Die Sprachen müssen keine Programmiersprachen sein. Dies kann jede Sprache sein, deren Regeln niedergeschrieben werden können. Sie haben wahrscheinlich Google Translate gesehen . Das ist ein Compiler, weil er eine Sprache (etwa Deutsch) in eine andere (vielleicht Japanisch) übersetzen kann.

Ein weiteres Beispiel für einen Compiler ist eine HTML-Rendering-Engine. Die Eingabe ist eine HTML-Datei und die Ausgabe ist eine Reihe von Anweisungen zum Zeichnen der Pixel auf dem Bildschirm.

Wenn die meisten Leute über einen Compiler sprechen, beziehen sie sich normalerweise auf ein Programm, das eine höhere Programmiersprache (wie Java, C, Prolog) in eine niedrigere Programmiersprache (Assembly oder Maschinencode) übersetzt. Das kann entmutigend sein. Aber es ist nicht so schlimm, wenn Sie die Ansicht eines Generalisten vertreten, dass ein Compiler ein Programm ist, das eine Sprache in eine andere übersetzt.

Können Sie ein Programm schreiben, das jedes Wort in einer Zeichenfolge umkehrt? Zum Beispiel:

When the cat's away, the mice will play.

wird

nehW eht s'tac yawa, eht ecim lliw yalp.

Das ist kein schwieriges Programm, aber Sie müssen über einige Dinge nachdenken:

  • Was ist ein "Wort"? Können Sie definieren, aus welchen Zeichen ein Wort besteht?
  • Wo beginnen und enden Wörter?
  • Werden Wörter nur durch ein Leerzeichen getrennt oder kann es mehr oder weniger geben?
  • Muss die Zeichensetzung auch umgekehrt werden?
  • Was ist mit Interpunktion in einem Wort?
  • Was passiert mit Großbuchstaben?

Die Antworten auf diese Fragen helfen, die Sprache klar zu definieren. Jetzt mach weiter und schreibe das Programm. Herzlichen Glückwunsch, Sie haben gerade einen Compiler geschrieben.

Wie wäre es damit: Können Sie ein Programm schreiben, das eine Reihe von Zeichenanweisungen übernimmt und eine PNG- (oder JPEG-) Datei ausgibt? Vielleicht so etwas:

image 100 100
background black
color red
line 20 55 93 105
color green
box 0 0 99 99

Auch hier müssen Sie einige Überlegungen anstellen, um die Sprache zu definieren:

  • Was sind die primitiven Anweisungen?
  • Was kommt nach dem Wort "Linie"? Was kommt nach "Farbe"? Ebenso für "Hintergrund", "Box" usw.
  • Was ist eine Nummer?
  • Ist eine leere Eingabedatei erlaubt?
  • Ist es in Ordnung, die Wörter groß zu schreiben?
  • Sind negative Zahlen erlaubt?
  • Was passiert, wenn Sie die "Bild" -Richtlinie nicht angeben?
  • Darf keine Farbe angegeben werden?

Natürlich gibt es noch weitere Fragen zu beantworten, aber wenn Sie sie richtig beantworten können, haben Sie eine Sprache definiert. Das Programm, das Sie für die Übersetzung schreiben, ist vermutlich ein Compiler.

Sie sehen, einen Compiler zu schreiben ist nicht so schwierig. Die Compiler, die Sie in Java oder C verwendet haben, sind nur größere Versionen dieser beiden Beispiele. Also los! Definieren Sie eine einfache Sprache und schreiben Sie ein Programm, mit dem diese Sprache etwas bewirkt. Früher oder später möchten Sie Ihre Sprache erweitern. Sie möchten beispielsweise Variablen oder arithmetische Ausdrücke hinzufügen. Ihr Compiler wird komplexer, aber Sie werden alles verstehen, weil Sie es selbst geschrieben haben. So entstehen Sprachen und Compiler.

Barry Brown
quelle
7
myFirstCompiler = (str) -> ("" + (str || "")). split (''). reverse (). join (''); jsfiddle.net/L7qSr
Larry Battle
21

Wenn Sie sich für das Compiler-Design interessieren, lesen Sie das Dragon Book (offizieller Titel: Compiler: Prinzipien, Techniken und Werkzeuge). Es wird allgemein als klassisches Buch zu diesem Thema angesehen.

Brian Agnew
quelle
4
Beachten Sie, dass Sie möglicherweise etwas mehr Erfahrung benötigen, um dieses Buch optimal nutzen zu können. Eine großartige Referenz.
13
-1 Nur wer es nicht gelesen hat, kann das Drachenbuch für gut halten. und es geht insbesondere nicht auf die Frage ein.
Neil Butterworth
33
Das Drachenbuch? Für einen begeisterten Fünfzehnjährigen? Ich möchte lieber, dass er seine Begeisterung noch eine Weile behält.
David Thornley
1
Eine leichter zugängliche Alternative: 'Programmiersprache Pragmatik' 3e .
Willjcroz
@DavidThornley Zähle ihn nicht vollständig aus (Ja, mir ist klar, dass dies ein sehr alter Beitrag ist). Mit 15 Jahren begann ich zu untersuchen, wie Sprachen funktionieren, und konzentrierte mich speziell auf virtuelle Maschinen. Jetzt bin ich 16 und nach Monaten der Recherche, des Schreibens und des Umschreibens habe ich einen funktionierenden Interpreter und Compiler, mit dem ich zufrieden bin.
David
10

Glauben Sie nicht, dass ein Compiler oder ein Betriebssystem etwas Magisches ist. Erinnern Sie sich an die Programme, die Sie geschrieben haben, um alle Vokale in einer Zeichenfolge zu zählen, oder addieren Sie die Zahlen in einem Array? Ein Compiler unterscheidet sich nicht im Konzept. es ist nur viel größer.

Jedes Programm besteht aus drei Phasen:

  1. Lies ein paar Sachen
  2. Verarbeiten Sie das Zeug: Übersetzen Sie die Eingabedaten in die Ausgabedaten
  3. schreibe ein paar andere Sachen - die Ausgangsdaten

Denken Sie darüber nach: Was wird in den Compiler eingegeben? Eine Zeichenfolge aus einer Quelldatei.

Was wird vom Compiler ausgegeben? Eine Folge von Bytes, die Computeranweisungen an den Zielcomputer darstellen.

Was ist also die "Prozess" -Phase des Compilers? Was macht diese Phase?

Wenn man bedenkt , dass der Compiler - wie jedes andere Programm - hat diese drei Phasen umfassen, erhalten Sie eine gute Vorstellung davon, wie ein Compiler aufgebaut ist.

Pete Wilson
quelle
3
Wie Neil sagte, wahr, aber nicht nützlich. Grundlegende Compiler-Aspekte wie eine rekursive Grammatik und Symboltabellen sind nicht intuitiv ersichtlich.
Mason Wheeler
1
@Mason Wheeler: Ich denke, jeder, der realistisch einen Compiler schreiben möchte (und die Zielsprache entwirft?), Würde höchstwahrscheinlich rekursive Grammatik- und Symboltabellen für ziemlich grundlegende Konzepte halten.
FumbleFingers
8

Ich bin kein Experte, aber hier ist mein Stich:

Sie scheinen nicht nach einem Compiler zu fragen, sondern nach einem Assembler. Das ist nicht wirklich magisch.

Wenn Sie jemand anderem die Antwort von SO stehlen ( https://stackoverflow.com/questions/3826692/how-do-i-translate-assembly-to-binary ), sieht die Assembly folgendermaßen aus:

label:  LDA #$00
        JMP label

Dann führen Sie es durch einen Assembler und verwandeln sich in so etwas:

$A9 $00
$4C $10 $00

Nur, dass alles so zusammengedrückt ist:

$A9 $00 $4C $10 $00

Es ist wirklich keine Magie.

Sie können das nicht in Editor schreiben, da Editor ASCII (nicht hex) verwendet. Sie würden einen Hex-Editor verwenden oder einfach die Bytes programmatisch ausschreiben. Sie schreiben dieses Hex in eine Datei, nennen es "a.exe" oder "a.out" und weisen das Betriebssystem an, es auszuführen.

Natürlich sind moderne CPUs und Betriebssysteme sehr kompliziert, aber das ist die Grundidee.

Wenn Sie einen neuen Compiler schreiben möchten, gehen Sie wie folgt vor:

1) Schreiben Sie eine interpretierte Sprache mit etwas wie dem Taschenrechner-Beispiel in Pyparsing (oder einem anderen guten Parsing-Framework). Damit sind Sie mit den Grundlagen des Parsens vertraut.

2) Schreiben Sie einen Übersetzer. Übersetzen Sie Ihre Sprache beispielsweise in Javascript. Jetzt läuft Ihre Sprache in einem Browser.

3) Schreiben Sie einen Übersetzer auf eine niedrigere Ebene, z. B. LLVM, C oder Assembly.

Sie können hier aufhören, dies ist ein Compiler. Es ist kein optimierender Compiler, aber das war nicht die Frage. Möglicherweise müssen Sie auch einen Linker und Assembler schreiben, aber möchten Sie das wirklich?

4) (Wahnsinnig) Schreiben Sie einen Optimierer. Große Teams arbeiten seit Jahrzehnten daran.

4) (Gesund) Engagieren Sie sich in einer bestehenden Community. GCC, LLVM, PyPy, das Kernteam, das an jedem Dolmetscher arbeitet.

wisty
quelle
8

Mehrere andere haben hervorragende Antworten gegeben. Ich werde nur noch ein paar Vorschläge hinzufügen. Ein gutes Buch für das, was Sie tun möchten, sind Appels Modern Compiler-Implementierungstexte (wählen Sie zwischen C , Java oder Standard ML ). Dieses Buch führt Sie durch die vollständige Implementierung eines Compilers für eine einfache Sprache, Tiger, zur MIPS-Assembly, die in einem Emulator ausgeführt werden kann, zusammen mit einer minimalen Laufzeit-Unterstützungsbibliothek. Für einen einzelnen Durchgang durch alles, was für die Kompilierung einer Sprache erforderlich ist, ist es ein ziemlich gutes Buch 1 .

Appel zeigt Ihnen, wie Sie eine Sprache kompilieren, die im Voraus entworfen wurde, aber nicht viel Zeit damit verbringt, was verschiedene Sprachfunktionen bedeuten, oder wie Sie darüber nachdenken, welche relativen Vorzüge sie haben, um Ihre eigene Sprache zu entwerfen. Für diesen Aspekt ist Programming Languages: Concepts & Constructs anständig. Konzepte, Techniken und Modelle der Computerprogrammierung sind auch ein gutes Buch zum gründlichen Nachdenken über Sprachdesign, obwohl dies im Kontext einer einzelnen Sprache ( Oz ) geschieht .

Schließlich erwähnte ich, dass Appel seinen Text in C, Java und Standard ML hat. Wenn Sie es mit der Compilerkonstruktion und den Programmiersprachen ernst meinen, empfehle ich, ML zu lernen und diese Version von Appel zu verwenden. Die Sprachen der ML-Familie haben starke Typsysteme, die vorwiegend funktional sind - Funktionen, die sich von vielen anderen Sprachen unterscheiden. Wenn Sie sie also nicht bereits in einer funktionalen Sprache beherrschen, verbessern Sie Ihr Sprachhandwerk. Darüber hinaus sind ihre Pattern-Matching- und Functional-Mindsets hervorragend für die Arten von Manipulationen geeignet, die Sie häufig in einem Compiler ausführen müssen. Daher sind Compiler, die in ML-basierten Sprachen geschrieben sind, in der Regel viel kürzer und verständlicher als Compiler, die in C geschrieben sind. Java oder ähnliche Sprachen. Harpers Buchon Standard ML ist ein ziemlich guter Leitfaden für den Einstieg. Wenn Sie das durcharbeiten, sollten Sie sich auf das Implementierungshandbuch für den Standard ML-Compiler von Appel vorbereiten. Wenn Sie Standard ML lernen, ist es auch ziemlich einfach, OCaml für die spätere Arbeit zu erwerben. IMO hat es bessere Tools für den funktionierenden Programmierer (lässt sich sauberer in die umgebende Betriebssystemumgebung integrieren, erstellt leicht ausführbare Programme und verfügt über einige spektakuläre Tools zum Erstellen von Compilern wie ulex und Menhir).


1 Als langfristige Referenz bevorzuge ich das Drachenbuch, da es mehr Details zu den Dingen enthält, auf die ich mich wahrscheinlich beziehe, z für einen ersten Durchgang. Grundsätzlich bringt Appel Ihnen eine Methode bei, mit der Sie den gesamten Compiler durcharbeiten können, und führt Sie durch den Compiler. Das Drachenbuch behandelt verschiedene Designalternativen ausführlicher, bietet jedoch weitaus weniger Anleitungen, wie etwas funktioniert.


Bearbeitet : Ersetze eine falsche Aho-Referenz durch Sethi, erwähne CTMCP.

Michael Ekstrand
quelle
Ugh, ich hatte Grundlagen der Programmiersprachen für meine College-Dolmetscherklasse. Es war furchtbar. Ich mag sogar Schema persönlich und kümmere mich nicht um die Syntax, es waren die schlechten Erklärungen der Autoren der Konzepte, die es für mich ruinierten.
Greg Guida
Ich mag Appels Kompilieren mit Fortsetzungen, aber ich fand, dass seine Bücher viel Vorwissen voraussetzten.
Jon Harrop
6

Ich musste einen Compiler für den Collegeunterricht erstellen.

Die Grundlagen dafür sind nicht so kompliziert, wie man denkt. Der erste Schritt besteht darin, Ihre Grammatik zu erstellen. Denken Sie an die Grammatik der englischen Sprache. Auf die gleiche Weise können Sie einen Satz analysieren, wenn er einen Betreff und ein Prädikat enthält. Lesen Sie dazu mehr über kontextfreie Grammatiken .

Sobald Sie die Grammatik (die Regeln Ihrer Sprache) festgelegt haben, ist das Schreiben eines Compilers so einfach wie das Befolgen dieser Regeln. Compiler übersetzen normalerweise in den Maschinencode, aber wenn Sie nicht x86 lernen möchten, sollten Sie sich MIPS ansehen oder Ihre eigene virtuelle Maschine erstellen.

Compiler bestehen normalerweise aus zwei Teilen, einem Scanner und einem Parser. Grundsätzlich liest der Scanner den Code ein und teilt ihn in Token auf. Der Parser untersucht die Struktur dieser Token. Anschließend durchläuft der Compiler einige recht einfache Regeln, um ihn in den Code zu konvertieren, in dem er enthalten sein muss (Assembly, Zwischencode wie Bytecode usw.). Wenn Sie es in immer kleinere Teile zerlegen, ist dies letztendlich überhaupt nicht entmutigend.

Viel Glück!

Jerr
quelle
8
Konzeptionell einfach? Ja. Eigentlich einfach? Nein
Neil Butter
7
Ähm. Der Compiler muss nach dem Scannen / Parsen Typüberprüfungen / Inferenzen, Optimierungen, Registerzuordnungen usw. durchführen. Diese Schritte sind alles andere als einfach. (Wenn Sie interpretierten Code verwenden, verschieben Sie diese Teile einfach auf die Laufzeitstufe.)
Macke,
Kein Votum von mir: Während Compiler zwei grundlegende Teile haben, besteht einer darin, eine abstrakte Beschreibung des Programms zu erstellen (die normalerweise in Scannen und Parsen unterteilt ist) und der andere darin, eine Version dieser abstrakten Beschreibung in einigen zu schreiben andere Form (zB Maschinencode). (Randnotiz: Optimierende Compiler versuchen normalerweise, die abstrakte Beschreibung vor dem Ausschreiben zu verbessern, aber das ist eine Verfeinerung.)
Donal Fellows,
6

Petzolds Buch- Code ist eine großartige Einführung für Nicht-Techniker und Techniker, beginnend mit den ersten Prinzipien. Es ist gut lesbar und in seinem Umfang riesig, ohne zu sehr ins Stocken zu geraten.

Jetzt, wo ich das geschrieben habe, muss ich es noch einmal lesen.

Kevin Won
quelle
5

Möglicherweise möchten Sie diese hervorragende Frage (und die Antworten) in StackOverflow: Lernen, einen Compiler zu schreiben überprüfen . Es enthält eine breite Liste von Ressourcen.

Wütender Salat
quelle
5

Es gibt ausgezeichnete Antworten in diesem Thread, aber ich wollte nur meine hinzufügen, da ich auch einmal die gleiche Frage hatte. (Außerdem möchte ich darauf hinweisen, dass das von Joe-Internet vorgeschlagene Buch eine hervorragende Ressource ist.)

Zunächst stellt sich die Frage, wie ein Computer funktioniert. So geht's: Eingabe -> Berechnen -> Ausgabe.

Betrachten Sie zuerst den Teil "Compute". Wir werden uns später ansehen, wie Input und Output funktionieren.

Ein Computer besteht im Wesentlichen aus einem Prozessor (oder einer CPU) und einem Speicher (oder RAM). Der Speicher ist eine Sammlung von Orten, von denen jeder eine endliche Anzahl von Bits speichern kann, und auf jeden solchen Speicherort kann selbst durch eine Zahl Bezug genommen werden, die als Adresse des Speicherorts bezeichnet wird. Der Prozessor ist ein Gerät, das Daten abrufen kann Führen Sie aus dem Speicher einige Operationen basierend auf den Daten aus und schreiben Sie einige Daten in den Speicher zurück. Wie findet der Prozessor heraus, was zu lesen ist und was zu tun ist, nachdem die Daten aus dem Speicher gelesen wurden?

Um dies zu beantworten, müssen wir die Struktur eines Prozessors verstehen. Das Folgende ist eine ziemlich einfache Ansicht. Ein Prozessor besteht im Wesentlichen aus zwei Teilen. Eine ist eine Reihe von Speicherplätzen im Prozessor, die als Arbeitsspeicher dienen. Diese werden als "Register" bezeichnet. Die zweite ist ein Bündel von elektronischen Maschinen, die zur Ausführung bestimmter Operationen unter Verwendung der Daten in den Registern gebaut wurden. Es gibt zwei spezielle Register, die als "Programmzähler" oder "PC" und "Befehlsregister" oder "IR" bezeichnet werden. Der Prozessor betrachtet den Speicher als in drei Teile unterteilt. Der erste Teil ist der „Programmspeicher“, in dem das ausgeführte Computerprogramm gespeichert ist. Der zweite ist der "Datenspeicher". Der dritte wird für spezielle Zwecke verwendet, wir werden später darüber sprechen. Der Programmzähler enthält die Position der nächsten Anweisung, die aus dem Programmspeicher gelesen werden soll. Der Befehlszähler enthält eine Zahl, die sich auf die aktuell ausgeführte Operation bezieht. Jede Operation, die ein Prozessor ausführen kann, wird durch eine Nummer bezeichnet, die als Operationscode der Operation bezeichnet wird. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Der Befehlszähler enthält eine Zahl, die sich auf die aktuell ausgeführte Operation bezieht. Jede Operation, die ein Prozessor ausführen kann, wird durch eine Nummer bezeichnet, die als Operationscode der Operation bezeichnet wird. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Der Befehlszähler enthält eine Zahl, die sich auf die aktuell ausgeführte Operation bezieht. Jede Operation, die ein Prozessor ausführen kann, wird durch eine Nummer bezeichnet, die als Operationscode der Operation bezeichnet wird. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Jede Operation, die ein Prozessor ausführen kann, wird durch eine Nummer bezeichnet, die als Operationscode der Operation bezeichnet wird. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Jede Operation, die ein Prozessor ausführen kann, wird durch eine Nummer bezeichnet, die als Operationscode der Operation bezeichnet wird. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben. Grundsätzlich arbeitet ein Computer so, dass er den vom Programmzähler referenzierten Speicherplatz in das Befehlsregister einliest (und den Programmzähler inkrementiert, sodass er auf den Speicherplatz des nächsten Befehls zeigt). Als nächstes liest es das Befehlsregister und führt die gewünschte Operation aus. Beispielsweise könnte der Befehl darin bestehen, einen bestimmten Speicherort in ein Register zu lesen oder in ein Register zu schreiben oder eine Operation unter Verwendung der Werte von zwei Registern durchzuführen und die Ausgabe in ein drittes Register zu schreiben.

Wie führt der Computer nun die Ein- / Ausgabe durch? Ich werde eine sehr vereinfachte Antwort geben. Siehe http://en.wikipedia.org/wiki/Input/output und http://en.wikipedia.org/wiki/Interrupt. für mehr. Es verwendet zwei Dinge, den dritten Teil des Speichers und etwas, das Interrupts genannt wird. Jedes an einen Computer angeschlossene Gerät muss Daten mit dem Prozessor austauschen können. Dabei wird der zuvor erwähnte dritte Teil des Speichers verwendet. Der Prozessor weist jedem Gerät eine Speicherscheibe zu, und das Gerät und der Prozessor kommunizieren über diese Speicherscheibe. Aber woher weiß der Prozessor, welcher Standort sich auf welches Gerät bezieht und wann ein Gerät Daten austauschen muss? Hier kommen Interrupts ins Spiel. Ein Interrupt ist im Wesentlichen ein Signal an den Prozessor, die aktuelle Position anzuhalten, alle Register an einem bekannten Ort zu speichern und dann etwas anderes zu tun. Dort gibt es viele Interrupts, die jeweils durch eine eindeutige Nummer gekennzeichnet sind. Für jeden Interrupt ist ein spezielles Programm zugeordnet. Wenn der Interrupt auftritt, der Prozessor führt das dem Interrupt entsprechende Programm aus. Abhängig vom BIOS und davon, wie die Hardwaregeräte mit der Hauptplatine des Computers verbunden sind, erhält jedes Gerät einen eindeutigen Interrupt und eine Speicherscheibe. Während des Startvorgangs ermittelt das Betriebssystem mithilfe des BIOS den Interrupt und den Speicherort jedes Geräts und richtet die speziellen Programme für den Interrupt ein, um die Geräte ordnungsgemäß zu behandeln. Wenn ein Gerät also Daten benötigt oder Daten senden möchte, signalisiert es einen Interrupt. Der Prozessor pausiert, was er tut, behandelt den Interrupt und kehrt dann zu dem zurück, was er tut. Es gibt viele Arten von Interrupts, z. B. für die Festplatte, die Tastatur usw. Ein wichtiger ist der System-Timer, der in regelmäßigen Abständen einen Interrupt auslöst. Es gibt auch Opcodes, die Interrupts auslösen können, sogenannte Software-Interrupts.

Jetzt können wir fast verstehen, wie ein Betriebssystem funktioniert. Beim Hochfahren richtet das Betriebssystem einen Timer-Interrupt ein, damit das Betriebssystem in regelmäßigen Abständen die Kontrolle erhält. Es werden auch andere Interrupts für die Verarbeitung anderer Geräte usw. eingerichtet. Wenn nun auf dem Computer eine Reihe von Programmen ausgeführt wird und der Timer-Interrupt auftritt, erlangt das Betriebssystem die Kontrolle und führt wichtige Aufgaben wie die Prozessverwaltung, die Speicherverwaltung usw. aus Eine abstrakte Möglichkeit für die Programme, auf die Hardwaregeräte zuzugreifen, anstatt sie direkt auf die Geräte zugreifen zu lassen. Wenn ein Programm auf ein Gerät zugreifen möchte, ruft es einen vom Betriebssystem bereitgestellten Code auf, der dann mit dem Gerät kommuniziert. Darin ist eine Menge Theorie enthalten, die sich mit Parallelität, Threads, Sperren, Speicherverwaltung usw. befasst.

Nun kann man theoretisch ein Programm direkt mit Opcodes schreiben. Dies wird als Maschinencode bezeichnet. Das ist offensichtlich sehr schmerzhaft. Jetzt ist eine Assemblersprache für den Prozessor nichts anderes als eine Mnemonik für diese Opcodes, was das Schreiben von Programmen erleichtert. Ein einfacher Assembler ist ein Programm, das ein in Assembly geschriebenes Programm verwendet und die Mnemonik durch die entsprechenden Opcodes ersetzt.

Wie gestaltet man einen Prozessor und eine Assemblersprache? Um zu wissen, dass Sie einige Bücher über Computerarchitektur lesen müssen. (siehe kapitel 1-7 des buches von joe-internet). Dazu gehört das Erlernen der Booleschen Algebra, das Erstellen einfacher kombinatorischer Schaltkreise zum Addieren, Multiplizieren usw., das Erstellen von Speicher- und sequentiellen Schaltkreisen, das Erstellen eines Mikroprozessors usw.

Nun, wie schreibt man Computer-Sprachen? Man könnte damit beginnen, einen einfachen Assembler in Maschinencode zu schreiben. Verwenden Sie dann diesen Assembler, um einen Compiler für eine einfache Teilmenge von C zu schreiben. Verwenden Sie dann diese Teilmenge von C, um eine vollständigere Version von C zu schreiben. Verwenden Sie schließlich C, um eine kompliziertere Sprache wie Python oder C ++ zu schreiben. Um eine Sprache zu schreiben, müssen Sie sie natürlich zuerst entwerfen (so wie Sie einen Prozessor entwerfen). Schauen Sie sich noch einmal einige Lehrbücher dazu an.

Und wie schreibt man ein os. Zuerst zielen Sie auf eine Plattform wie x86. Dann finden Sie heraus, wie es startet und wann Ihr Betriebssystem aufgerufen wird. Ein typischer PC bootet auf diese Weise. Es startet und BIOS führt einige Tests durch. Dann liest das BIOS den ersten Sektor der Festplatte und lädt den Inhalt an eine bestimmte Stelle im Speicher. Dann richtet es die CPU ein, um die Ausführung dieser geladenen Daten zu starten. Dies ist der Punkt, an dem Sie aufgerufen werden. Ein typisches Betriebssystem lädt an dieser Stelle den Rest seines Speichers. Anschließend werden die Geräte initialisiert und andere Einstellungen vorgenommen. Schließlich werden Sie mit dem Anmeldebildschirm begrüßt.

Um ein OS zu schreiben, müssen Sie den “Boot-Loader” schreiben. Dann müssen Sie Code schreiben, um die Interrupts und Geräte zu behandeln. Dann müssen Sie den gesamten Code für die Prozessverwaltung, die Geräteverwaltung usw. schreiben. Dann müssen Sie eine API schreiben, mit der die in Ihrem Betriebssystem ausgeführten Programme auf Geräte und andere Ressourcen zugreifen können. Und schließlich müssen Sie Code schreiben, der ein Programm von der Festplatte liest, als Prozess einrichtet und mit der Ausführung beginnt.

Natürlich ist meine Antwort deutlich vereinfacht und wahrscheinlich von geringem praktischen Nutzen. Zu meiner Verteidigung bin ich jetzt ein Doktorand in der Theorie, deshalb habe ich viele dieser Dinge vergessen. Aber Sie können eine Menge von diesen Sachen googeln und mehr herausfinden.

Dubyaman
quelle
4

Ich kann mich an einen Punkt in meiner Programmierkarriere erinnern, als ich in einem ähnlichen Zustand der Verwirrung war wie Sie: Ich hatte einiges über die Theorie gelesen, das Drachenbuch, das Tigerbuch (rot), aber immer noch nicht viel von eine Ahnung, wie man alles zusammensetzt.

Was hat es zusammenbinden wurde ein konkretes Projekt zu finden , zu tun (und herauszufinden , dann , dass ich nur eine kleine Teilmenge aller Theorie erforderlich).

Die Java-VM bot mir einen guten Ausgangspunkt: Sie ist konzeptionell ein "Prozessor", aber stark von den unübersichtlichen Details der tatsächlichen CPUs abstrahiert. Es bietet auch einen wichtigen und oft übersehenen Teil des Lernprozesses: Dinge auseinander nehmen, bevor sie wieder zusammengesetzt werden (wie es Kinder früher mit Funkgeräten taten).

Spielen Sie mit einem Dekompiler und der Weltklasse von Hello in Java. Lesen Sie die JVM-Spezifikation und versuchen Sie zu verstehen, was los ist. Dies wird Ihnen geerdet Einblick in genau das, was der Compiler tun .

Spielen Sie dann mit Code, der die Hello World-Klasse erzeugt. (Tatsächlich erstellen Sie einen anwendungsspezifischen Compiler für eine hochspezialisierte Sprache, in der Sie nur Hallo, Welt sagen können.)

Versuchen Sie, Code zu schreiben, der Hello, World in einer anderen Sprache lesen und dieselbe Klasse ausgeben kann. Machen Sie es so, dass Sie die Zeichenfolge von "Hallo, Welt" in etwas anderes ändern können.

Versuchen Sie nun (in Java) eine Klasse zu kompilieren, die einen arithmetischen Ausdruck wie "2 * (3 + 4)" berechnet. Nehmen Sie diese Klasse auseinander, schreiben Sie einen "Toy Compiler", der sie wieder zusammensetzen kann.

Morendil
quelle
3

1) Tolle Videovorträge von der University of Washington:

CSE P 501 Compilerbau - Herbst 2009 www.cs.washington.edu/education/courses/csep501/09au/lectures/video.html *

2) SICP http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ Und das gleichnamige Buch. Dies ist eigentlich für jeden Softwareentwickler ein Muss.

3) Auch über funktionale Programmierung, Haskell, Lambda-Kalkül, Semantik (einschließlich denotational) und Compiler-Implementierung für funktionale Sprachen. Sie können ab 2005-SS-FP.V10.2005-05-24.HDV starten, wenn Sie Haskell bereits kennen. Uxx Videos sind Antworten. Bitte folge zuerst den Vxx- Videos.

http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung

(Videos sind in Englisch, andere Kurse in Deutsch.)

  • Neue Benutzer können maximal zwei Hyperlinks posten.
Zura
quelle
3

ANTLR ist ein guter Ausgangspunkt. Es ist ein Framework zur Sprachgenerierung, ähnlich wie Lex und Yacc. Es gibt eine GUI namens ANTLRWorks , die den Prozess vereinfacht.

In der .NET-Welt gibt es die Dynamic Language Runtime , mit der Code in der .NET-Welt generiert werden kann. Ich habe eine Ausdruckssprache namens Zentrum geschrieben , die mit dem DLR Code generiert. Hier erfahren Sie, wie Sie statisch und dynamisch typisierte Ausdrücke analysieren und ausführen.

Sean
quelle
2

Für eine einfache Einführung in die Funktionsweise von Compilern und das Erstellen Ihrer eigenen Programmiersprache würde ich das neue Buch http://createyourproglang.com empfehlen, das sich mehr auf die Theorie des Sprachdesigns konzentriert, ohne die OS / CPU-Interna, dh Lexer, Parser, kennen zu müssen , Dolmetscher usw.

Es werden die gleichen Tools verwendet, die zum Erstellen der kürzlich populären Programmiersprachen Coffee Script und Fancy verwendet wurden.

Mythos
quelle
2

Wenn alles, was Sie sagen, wahr ist, haben Sie das Profil eines vielversprechenden Forschers, und ein konkretes Verständnis kann nur auf eine Weise erreicht werden: durch Studieren. Und ich sage nicht " Lies all diese hochrangigen Informatikbücher (speziell diese ), die von diesem Genie geschrieben wurden !"; Ich meine: Sie müssen mit hochrangigen Leuten zusammen sein, um Informatiker wie Charles Babbage, Alan Turing, Claude Shannon oder Dennis Ritchie zu sein. Ich verachte keine Autodidakten (ich bin einer von ihnen), aber es gibt nicht viele Leute wie Sie da draußen. Ich kann das Symbolic Systems Program (SSP) an der Stanford University nur empfehlen . Wie ihre Website sagt:

Das Symbolic Systems Program (SSP) an der Stanford University konzentriert sich auf Computer und Geist: künstliche und natürliche Systeme, die Symbole zur Darstellung von Informationen verwenden. SSP bringt Studenten und Dozenten zusammen, die an verschiedenen Aspekten der Mensch-Computer-Beziehung interessiert sind, darunter ...

  • Kognitionswissenschaft : Studium der menschlichen Intelligenz, der natürlichen Sprachen und des Gehirns als Rechenprozesse;
  • Künstliche Intelligenz : Computer mit menschlichem Verhalten und Verständnis ausstatten; und
  • Mensch-Computer-Interaktion : Entwerfen von Computersoftware und Schnittstellen, die gut mit menschlichen Benutzern zusammenarbeiten.
quantme
quelle
2

Ich werde etwas außerhalb des linken Feldes vorschlagen: Python lernen (oder vielleicht Ruby, aber ich habe viel mehr Erfahrung in Python, also werde ich darüber diskutieren). Und nicht nur darin herumtollen, sondern es auf einer tiefen Ebene wirklich kennenlernen.

Ich schlage dies aus mehreren Gründen vor:

  1. Python ist eine außergewöhnlich gut gestaltete Sprache. Während es ein paar Warzen hat, hat es weniger IMHO als viele andere Sprachen. Wenn Sie ein angehender Sprachdesigner sind, ist es gut, sich so vielen guten Sprachen wie möglich auszusetzen.

  2. Die Standardimplementierung von Python (CPython) ist Open Source und gut dokumentiert, wodurch das Verständnis der Funktionsweise der Sprache unter der Haube erleichtert wird.

  3. Python wird zu einem einfachen Bytecode kompiliert, der einfacher zu verstehen ist als Assembly und auf allen Plattformen, auf denen Python ausgeführt wird, gleich funktioniert. So lernen Sie die Kompilierung (da Python den Quellcode in Byte-Code kompiliert) und die Interpretation (da dieser Byte-Code in der virtuellen Python-Maschine interpretiert wird).

  4. Python bietet zahlreiche neue Funktionen, die in nummerierten PEPs (Python Enhancement Proposals) dokumentiert sind. Interessante PEPs, um zu sehen, wie die Sprachentwickler eine Funktion implementiert haben, bevor sie entschieden haben, wie sie sie tatsächlich ausgeführt haben. (Besonders interessant sind in diesem Zusammenhang noch zu prüfende PEPs.)

  5. Python verfügt über eine Mischung von Funktionen aus verschiedenen Programmierparadigmen, sodass Sie verschiedene Lösungsansätze kennenlernen und eine größere Auswahl von Tools in Ihrer eigenen Sprache berücksichtigen können.

  6. Mit Python ist es ziemlich einfach, die Sprache mit Dekoratoren, Metaklassen, Import-Hooks usw. auf verschiedene Arten zu erweitern, sodass Sie in gewissem Umfang mit neuen Sprachfunktionen spielen können, ohne die Sprache tatsächlich zu verlassen. (Übrigens: Codeblöcke sind in Ruby erstklassige Objekte, sodass Sie tatsächlich neue Kontrollstrukturen wie Schleifen schreiben können. Ich habe den Eindruck, dass Ruby-Programmierer nicht unbedingt in Betracht ziehen, die Sprache zu erweitern, sondern nur, wie Sie programmieren in Ruby. Aber es ist ziemlich cool.)

  7. In Python können Sie den vom Compiler generierten Bytecode zerlegen oder sogar Ihren eigenen von Grund auf neu schreiben und ihn vom Interpreter ausführen lassen (das habe ich selbst gemacht, und es war umwerfend, hat aber Spaß gemacht).

  8. Python hat gute Bibliotheken zum Parsen. Sie können Python-Code in einem abstrakten Syntaxbaum analysieren und dann mit dem AST-Modul bearbeiten. Das PyParsing-Modul eignet sich zum Parsen beliebiger Sprachen, z. B. der von Ihnen entworfenen. Sie könnten theoretisch Ihren ersten Sprach-Compiler in Python schreiben, wenn Sie möchten (und es könnte C-, Assembly- oder sogar Python-Ausgabe erzeugen).

Dieser Untersuchungsansatz könnte zu einem formaleren Ansatz passen, da Sie anfangen, Konzepte zu erkennen, die Sie in der Sprache gelernt haben, mit der Sie arbeiten, und umgekehrt.

Habe Spaß!

irgendwie
quelle
Nicht in Python zu graben, aber es ist nebensächlich. Das Kind hat bereits N Sprachen für großes N; Das Inkrementieren von N macht keinen großen Unterschied. Nehmen Sie zum Beispiel C. Es ist Standard. Es hat viele Bibliotheken. Es ist plattformübergreifend (wenn Sie sich an den Standard halten). Sie können den Ausgang zerlegen. Sie können CFront schreiben. Usw. Also da.
Ian
1

Nun, ich denke, Ihre Frage könnte so umgeschrieben werden, dass sie lautet: "Was sind die wichtigsten praktischen Konzepte eines Informatik-Abschlusses", und die vollständige Antwort ist natürlich, einen eigenen Bachelor in Informatik zu machen.

Grundsätzlich erstellen Sie Ihren eigenen Programmiersprachen-Compiler, indem Sie eine Textdatei lesen, Informationen daraus extrahieren und den Text anhand der gelesenen Informationen umwandeln, bis Sie ihn in lesbare Bytes umgewandelt haben der Loader (vgl. Linker und Loader von Levine). Ein trivialer Compiler ist ein ziemlich strenges Projekt, wenn es zum ersten Mal ausgeführt wird.

Das Herz eines Betriebssystems ist der Kernel, der Ressourcen verwaltet (z. B. Speicherzuweisung / Freigabe) und zwischen Aufgaben / Prozessen / Programmen wechselt.

Ein Assembler ist eine Text-> Byte-Transformation.

Wenn Sie sich für dieses Zeug interessieren, würde ich vorschlagen, einen X86-Assembler unter Linux zu schreiben, der eine Teilmenge der Standard-X86-Assembler unterstützt. Das ist ein ziemlich einfacher Einstiegspunkt und führt Sie in diese Themen ein. Es ist kein Babyprojekt und wird Ihnen viele Dinge beibringen.

Ich würde empfehlen, es in C zu schreiben; C ist die Verkehrssprache für diese Arbeitsstufe.

Paul Nathan
quelle
1
Auf der anderen Seite ist dies ein guter Ort für eine Sprache auf sehr hohem Niveau. Solange Sie die einzelnen Bytes in einer Datei diktieren können, können Sie einen Compiler / Assembler (was einfacher ist) in einer beliebigen Sprache erstellen. Sag mal, Perl. Oder VBA. Himmel, die Möglichkeiten!
Ian
1

Siehe Kenneth Loudens Buch "Compiler Construction"

http://www.cs.sjsu.edu/~louden/cmptext/

Es bietet einen besseren praktischen Ansatz für die Compiler-Entwicklung.

Die Menschen lernen dabei. Nur eine kleine Anzahl kann Symbole auf der Tafel sehen und sofort von der Theorie zur Praxis springen. Leider sind diese Leute oft dogmatisch, fundamentalistisch und am lautesten.

Jarvis Jones
quelle
1

Ich war gesegnet, mit dem PDP-8 als meiner ersten Assemblersprache konfrontiert zu sein. Der PDP-8 hatte nur sechs Befehle, die so einfach waren, dass man sich leicht vorstellen konnte, dass sie von ein paar diskreten Komponenten implementiert wurden, die es tatsächlich waren. Es entfernte wirklich die "Magie" von Computern.

Ein weiteres Tor zu derselben Enthüllung ist die Assemblersprache "mix", die Knuth in seinen Beispielen verwendet. "Mix" wirkt heute archaisch, hat aber immer noch den DE-mystifizierenden Effekt.

ddyer
quelle
0

Compiler und Programmiersprachen (und alles, was auch zum Erstellen einer solchen gehört - wie das Definieren einer endlichen Grammatik und das Konvertieren in Assembler) sind eine sehr komplexe Aufgabe, die viel Verständnis für das gesamte System erfordert. Diese Art von Kurs wird in der Regel als Comp Sci-Klasse im 3./4. Jahr an der Universität angeboten.

Ich würde Ihnen wärmstens empfehlen, zunächst ein besseres Verständnis der Betriebssysteme im Allgemeinen und der Kompilierung / Ausführung vorhandener Sprachen (dh nativ (C / C ++), in einer VM (Java) oder von einem Interpreter (Python / Javascript)) zu erlangen.

Ich glaube, wir haben das Buch Betriebssystemkonzepte von Abraham Silberschatz, Peter B. Galvin und Greg Gagne in meinem Betriebssystemkurs (im 2. Jahr) verwendet. Dies war ein exzellentes Buch, in dem jede Komponente eines Betriebssystems ausführlich beschrieben wurde - ein bisschen teuer, aber es lohnt sich und ältere / gebrauchte Kopien sollten im Umlauf sein.

plafond
quelle
OS-Konzepte? Davon wird sehr wenig benötigt, um einen Compiler zu erstellen. Was benötigt wird, ist das Verständnis von Software-Architekturen: Adressen, Stapel, Threads (wenn er Compiler lernen will, lernt er besser über Parallelität, seine Zukunft).
Ira Baxter
Unmittelbar nachdem er gesagt hatte, er wolle Sprachdesign und Compiler lernen, sagte er, er wolle etwas über Betriebssysteme lernen.
David Thornley
@Ira - einverstanden. Ich habe nie gesagt, dass das Verständnis des Betriebssystems erforderlich ist, um einen Compiler / eine Sprache zu erstellen. Ich habe lediglich erklärt, dass dies ein einfacherer Ausgangspunkt sein könnte. Jeder konzentriert sich auf den "Compiler" Aspekt seiner Frage, aber er erwähnte auch, dass er ein besseres Verständnis von Betriebssystemen und Bibliotheken haben möchte. Für einen 15-Jährigen, der noch etwas über Architekturen lernt, wäre es viel nützlicher, Speicherverwaltung, Threading, Sperren, E / A usw. zu verstehen, als zu lernen, wie man eine Grammatik mit yacc (IMHO) definiert
plafond
Entschuldigung ... habe den Punkt verpasst, in dem es darum geht, mehr über (Gebäude-?) Betriebssysteme zu erfahren. Mein Standpunkt lautet: Er benötigt nicht viel OS-Wissen für Compiler. Tatsächlich ist es ein völlig anderes Thema, es sei denn, der Compiler und das Betriebssystem interagieren, um einen gemeinsamen Zweck zu erreichen. (Multics forderte von seinen PL / 1-Compilern, Funktionsaufrufe auf bestimmte Weise zu erstellen, um beispielsweise eine globale VM zu aktivieren.)
Ira Baxter
0

Es ist ein großes Thema, aber anstatt dich mit einem pompösen "Geh, lies ein Buch, Junge" abzuwischen, gebe ich dir gerne Hinweise, die dir helfen, deinen Kopf darum zu wickeln.

Die meisten Compiler und / oder Interpreten arbeiten folgendermaßen:

Tokenize : Scannen Sie den Codetext und teilen Sie ihn in eine Liste von Token auf.

Dieser Schritt kann schwierig sein, da Sie die Zeichenfolge nicht einfach auf Leerzeichen aufteilen können. Sie müssen erkennen, dass if (bar) foo += "a string";es sich um eine Liste von 8 Token handelt: WORD, OPEN_PAREN, WORD, CLOSE_PAREN, WORD, ASIGNMENT_ADD, STRING_LITERAL, TERMINATOR. Wie Sie sehen, funktioniert es nicht, den Quellcode einfach in Leerzeichen aufzuteilen. Sie müssen jedes Zeichen als Sequenz lesen. Wenn Sie also auf ein alphanumerisches Zeichen stoßen, lesen Sie solange Zeichen, bis Sie ein nicht-alphanumerisches Zeichen und diese Zeichenfolge treffen Gerade gelesen ist ein Wort, das später weiter klassifiziert werden soll. Sie können selbst entscheiden, wie detailliert Ihr Tokenizer ist: ob er "a string"als ein Token namens STRING_LITERAL verschluckt wird, das später weiter analysiert wird, oder ob er dies sieht"a string" OPEN_QUOTE, UNPARSED_TEXT, CLOSE_QUOTE oder was auch immer, dies ist nur eine von vielen Möglichkeiten, die Sie beim Codieren für sich entscheiden müssen.

Lex : Nun haben Sie eine Liste von Token. Sie haben wahrscheinlich einige Token mit einer mehrdeutigen Klassifizierung wie WORD versehen, weil Sie beim ersten Durchgang nicht zu viel Mühe darauf verwenden, den Kontext der einzelnen Zeichenfolgen zu ermitteln. Lesen Sie nun Ihre Liste der Quell-Token erneut und klassifizieren Sie jeden der mehrdeutigen Token mit einem spezifischeren Token-Typ, basierend auf den Schlüsselwörtern in Ihrer Sprache. Sie haben also ein WORT wie "if" und "if" in Ihrer Liste der speziellen Schlüsselwörter, die als "Symbol IF" bezeichnet werden, sodass Sie den Symboltyp dieses Tokens von "WORD" in "IF" ändern und jedes WORT, das sich nicht in Ihrer Liste der speziellen Schlüsselwörter befindet , wie WORD foo, ist ein IDENTIFIER.

Parse : Sie haben jetzt if (bar) foo += "a string";eine Liste mit lexierten Token erstellt, die folgendermaßen aussieht: IF OPEN_PAREN IDENTIFER CLOSE_PAREN IDENTIFIER ASIGN_ADD STRING_LITERAL TERMINATOR. Der Schritt besteht darin, Folgen von Tokens als Anweisungen zu erkennen. Das ist Parsen. Dazu verwenden Sie eine Grammatik wie:

STATEMENT: = ASIGN_EXPRESSION | IF_STATEMENT

IF_STATEMENT: = IF, PAREN_EXPRESSION, STATEMENT

ASIGN_EXPRESSION: = IDENTIFIER, ASIGN_OP, VALUE

PAREN_EXPRESSSION: = OPEN_PAREN, VALUE, CLOSE_PAREN

VALUE: = IDENTIFIER | STRING_LITERAL | PAREN_EXPRESSION

ASIGN_OP: = EQUAL | ASIGN_ADD | ASIGN_SUBTRACT | ASIGN_MULT

Die Produktionen, die "|" zwischen Begriffen bedeutet "Übereinstimmung mit diesen", wenn es Kommas zwischen Begriffen gibt, bedeutet dies "Übereinstimmung mit dieser Abfolge von Begriffen"

Wie benutzt du das? Versuchen Sie, beginnend mit dem ersten Token, Ihre Token-Sequenz mit diesen Produktionen abzugleichen. Also versuchen Sie zuerst, Ihre Token-Liste mit STATEMENT abzugleichen, also lesen Sie die Regel für STATEMENT und es heißt "ein STATEMENT ist entweder ein ASIGN_EXPRESSION oder ein IF_STATEMENT", also versuchen Sie zuerst, ASIGN_EXPRESSION abzugleichen, also schlagen Sie die Grammatikregel für ASIGN_EXPRESSION nach und es heißt "ASIGN_EXPRESSION ist ein IDENTIFIER gefolgt von einem ASIGN_OP gefolgt von einem VALUE, so dass Sie die Grammatikregel für IDENTIFIER nachschlagen und sehen, dass es für IDENTIFIER keine Grammatiklücke gibt, was bedeutet, dass IDENTIFIER ein" Terminal "ist, was bedeutet, dass es nicht weiter benötigt Analysieren, um es abzugleichen, damit Sie versuchen können, es direkt mit Ihrem Token abzugleichen. Ihr erstes Quelltoken ist jedoch eine IF, und IF ist nicht dasselbe wie ein IDENTIFIER. Was jetzt? Sie kehren zur Regel STATEMENT zurück und versuchen, den nächsten Ausdruck zu finden: IF_STATEMENT. Sie suchen nach IF_STATEMENT, es beginnt mit IF, suchen nach IF, IF ist ein Terminal, vergleichen Sie das Terminal mit Ihrem ersten Token, IF-Token-Übereinstimmungen, sehen Sie nach PAREN_EXPRESSION, suchen Sie nach PAREN_EXPRESSION, es ist kein Terminal, was ist es, PAREN_EXPRESSION beginnt mit OPEN_PAREN, sucht nach OPEN_PAREN, ist ein Terminal, ordnet OPEN_PAREN Ihrem nächsten Token zu, stimmt überein, ... und so weiter.

Der einfachste Weg, sich diesem Schritt zu nähern, besteht darin, eine Funktion namens parse () zu verwenden, mit der Sie das Quelltext-Token, mit dem Sie übereinstimmen möchten, und den Grammatikbegriff übergeben, mit dem Sie übereinstimmen möchten. Wenn der Grammatikbegriff kein Terminal ist, verwenden Sie erneut: Sie rufen parse () auf und übergeben ihm erneut das gleiche Quell-Token und den ersten Begriff dieser Grammatikregel. Aus diesem Grund wird es als "rekursiver Abstiegsparser" bezeichnet. Die Funktion parse () gibt Ihre aktuelle Position beim Lesen der Quelltoken zurück (oder ändert sie). Sie gibt im Wesentlichen das letzte Token in der übereinstimmenden Sequenz zurück und Sie fahren mit dem nächsten Aufruf von fort parse () von dort.

Jedes Mal, wenn parse () mit einer Produktion wie ASIGN_EXPRESSION übereinstimmt, erstellen Sie eine Struktur, die diesen Code darstellt. Diese Struktur enthält Verweise auf die ursprünglichen Quelltoken. Sie beginnen mit der Erstellung einer Liste dieser Strukturen. Wir nennen diese gesamte Struktur den Abstract Syntax Tree (AST).

Kompilieren und / oder Ausführen : Für bestimmte Produktionen in Ihrer Grammatik haben Sie Handlerfunktionen erstellt, die bei einer AST-Struktur diesen AST-Block kompilieren oder ausführen.

Schauen wir uns also das Teil Ihres AST an, das den Typ ASIGN_ADD hat. Als Interpreter haben Sie also eine ASIGN_ADD_execute () -Funktion. Diese Funktion wird als Teil des AST übergeben, der dem Analysebaum für entspricht. Daher betrachtet foo += "a string"diese Funktion diese Struktur und weiß, dass der erste Term in der Struktur ein IDENTIFIER sein muss und der zweite Term der VALUE ist. ASIGN_ADD_execute () Übergibt den VALUE-Term an eine VALUE_eval () -Funktion, die ein Objekt zurückgibt, das den ausgewerteten Wert im Speicher darstellt. Dann sucht ASIGN_ADD_execute () in Ihrer Variablentabelle nach "foo" und speichert einen Verweis auf alles, was von eval_value () zurückgegeben wurde. Funktion.

Das ist ein Dolmetscher. Ein Compiler hätte stattdessen Handlerfunktionen, die den AST in Bytecode oder Maschinencode übersetzen, anstatt ihn auszuführen.

Die Schritte 1 bis 3 und einige 4 können mithilfe von Tools wie Flex und Bison vereinfacht werden. (aka. Lex und Yacc), aber selbst einen Dolmetscher zu schreiben, ist wahrscheinlich die stärkste Übung, die ein Programmierer erreichen kann. Alle anderen Programmierherausforderungen scheinen nach diesem Gipfel trivial zu sein.

Mein Rat ist, klein anzufangen: eine winzige Sprache mit einer winzigen Grammatik, und zu versuchen, ein paar einfache Aussagen zu analysieren und auszuführen, und von dort aus zu wachsen.

Lesen Sie diese und viel Glück!

http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c

http://en.wikipedia.org/wiki/Recursive_descent_parser

Schnorcheln
quelle
2
Sie machen das, was ich für einen klassischen Fehler halte, wenn die Leute über das Kompilieren nachdenken: Sie glauben, dass es sich bei dem Problem um das Parsen handelt. PARSING IST TECHNISCH EINFACH; Dafür gibt es großartige Technologien. Der schwierige Teil beim Kompilieren ist die semantische Analyse, die Optimierung auf hoher und niedriger Ebene der Programmrepräsentation und die Generierung von Code, wobei der Schwerpunkt heutzutage auf PARALLEL-Code liegt. Sie trivialisieren dies vollständig in Ihrer Antwort: "Ein Compiler hätte Handlerfunktionen, um den AST in Byte-Code zu übersetzen". Es gibt 50 Jahre verstrichene Compilertheorie und Technik, die sich darin verstecken.
Ira Baxter
0

Das Computerfeld ist nur deshalb kompliziert, weil es Zeit hatte, sich in viele Richtungen zu entwickeln. Im Kern geht es nur um Maschinen, die rechnen.

Mein sehr einfacher Lieblingscomputer ist Harry Porters Relay Computer . Es vermittelt einen Eindruck davon, wie ein Computer auf der Basisebene funktioniert. Dann können Sie anfangen zu verstehen, warum Dinge wie Sprachen und Betriebssysteme benötigt werden.

Die Sache ist, es ist schwer, etwas zu verstehen, ohne zu verstehen, was es braucht . Viel Glück und lese nicht nur Zeug. Haben Sachen.

Mike Dunlavey
quelle
-1

Schau mal bei http://mikeos.berlios.de/

In der x86-Assembly gibt es ein wirklich einfaches Betriebssystem.

Er hat ein nettes Tutorial, wie man ein einfaches OS von Grund auf neu schreibt.

Tim Williscroft
quelle
-1

Ein weiteres gutes Einführungsbuch ist das "Compilerbau" von N. Wirth aus dem Jahr 1986 (Compilerbau), das etwa 100 Seiten lang ist und prägnanten, gut gestalteten Code für die Spielzeugsprache PL / 0 einschließlich Parser, Codegenerator und virtueller Maschine erklärt. Es wird auch gezeigt, wie ein Parser geschrieben wird, der die Grammatik liest, um sie in EBNF-Notation zu analysieren. Das Buch ist auf Deutsch, aber ich habe eine Zusammenfassung geschrieben und den Code als Übung in Python übersetzt, siehe http://www.d12k.org/cmplr/w86/intro.html .

Daniel Storbeck
quelle
-1

Wenn Sie das Wesentliche von Programmiersprachen verstehen möchten, empfehle ich Ihnen, das PLAI-Buch (http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/) durchzuarbeiten, um die Konzepte und Funktionen zu verstehen ihre Umsetzung. Es hilft Ihnen auch bei der Gestaltung Ihrer eigenen Sprache.

Mansu
quelle
-1

Wenn Sie wirklich an Compiler interessiert sind und noch nie zuvor ein solches Interesse hatten, können Sie zunächst einen Taschenrechner für die Berechnung arithmetischer Formeln entwerfen (eine Art DSL, wie Eric es erwähnt hat). Es gibt viele Aspekte, die Sie für diese Art von Compiler berücksichtigen müssen:

  • Zulässige Nummern
  • Zulässige Operatoren
  • Die Betreiberprioritäten
  • Syntaxvalidierung
  • Variabler Suchmechanismus
  • Zykluserkennung
  • Optimierung

Wenn Sie beispielsweise die folgenden Formeln haben, sollte Ihr Rechner den Wert von x berechnen können:

a = 1
b = 2
c = a + b
d = (3 + b) * c
x = a - d / b

Zunächst ist es kein extrem schwieriger Compiler, aber Sie können sich ein paar grundlegende Vorstellungen darüber machen, was ein Compiler ist, und Sie können Ihre Programmierkenntnisse verbessern und die Qualität Ihres Codes kontrollieren (dies ist tatsächlich ein perfektes Problem, das es gibt) Test Driven Development (TDD könnte zur Verbesserung der Softwarequalität eingesetzt werden).

Sapience
quelle