Programmiersprachen scheinen mehrere Stufen zu durchlaufen. Erstens, jemand träumt eine neue Sprache, Foo Language. Der Compiler / Interpreter wird in einer anderen Sprache geschrieben, in der Regel C oder einer anderen Low-Level-Sprache. Irgendwann reift Fool und wächst, und irgendwann wird irgendwo jemand einen Compiler und / oder einen Interpreter für Fool in Fool selbst schreiben.
Meine Frage ist: Was ist die minimale Untermenge von Sprachfeatures, so dass jemand diese Sprache selbst implementieren könnte?
Compiler kann sogar mit einer Turing-Maschine geschrieben werden - a Universal Turing Machine ist im Grunde ein Compiler / Interpreter einer beliebigen Turing-Maschine, also Turing- Vollständige Sprache sollte genug sein:)
In der Theorie überraschend wenig. Ein Computational Theoretiker würde sagen, dass alles, was Sie brauchen, mu-recursion oder eine Turing-Maschine oder dergleichen.
Aus praktischer Sicht werden Sie jedoch nicht sehr glücklich sein, wenn Sie versuchen, eine Programmiersprache in einer Turing-Maschine zu implementieren. Ich würde sagen, dass Sie zumindest alle üblichen Control-Flow-Konstrukte, die primitiven Datentypen, Subroutinen sowie Arrays und Strukturen haben möchten. Das sollte ausreichen, damit Sie diese Teilmenge der Sprache in der Sprache selbst implementieren können - und Sie können sich dann von dort aus booten.
Eine Option ist eine Lese-Test-Schleife . Dies kann verwendet werden, um viele übergeordnete Konstrukte zu erstellen. Ich glaube, dies ist der Weg, den LISP eingeschlagen hat.
Ich bin unsicher über die Anfänge von C, aber ich denke, es begann mit ein paar Systemaufrufen, um Verzweigungen, Schleifen, Zuweisung und Einzelzeichen-I / O zu implementieren, und baute von dort aus.
Meine Frage ist: Was ist die minimale Untermenge von Sprachfeatures, so dass jemand diese Sprache selbst implementieren könnte?
Es ist nicht erforderlich, dass die Sprache für etwas anderes als das Kompilieren nützlich ist. Ich präsentiere Ihnen Useless , die Sprache, in der jeder Text ein richtiges Programm ist und bedeutet "ein Programm, das jede Eingabe nimmt und sich selbst produziert" (dies wird auch als Useless compiler bezeichnet).
Tags und Links language-agnostic compiler-theory