Allgemeine Regeln zum Schreiben eines X-Compilers nach Z in Y.

Angenommen, X ist die Eingabesprache, Z ist die Ausgabesprache, dann ist f der Compiler, der in Sprache Y geschrieben ist.

f = X -> Z

Da f nur ein Programm ist, denke ich, dass Y jede Sprache sein kann, oder? Wir können also Compiler f1, f2 haben, die jeweils in Y1, Y2 geschrieben sind.

f1 = f Y1    
f2 = f Y2

g = Z -> M
h = g . f    # We get a compiler X -> M

Nehmen wir zum Beispiel den cpython-Compiler: X ist Python, Z ist der Python-VM-Code, Y ist C.

cpython = Python -> PythonVMCode C
interpreter = PythonVMCode -> Nothing
interpreter2 = PythonVMCode -> MachineCode

Python-Quellen werden aus dem Python-VM-Code, den .pyc-Dateien, kompiliert und dann vom Interpreter interpretiert. Es scheint möglich, dass es einen Compiler gibt, der Python -> MachineCode direkt ausführen kann, obwohl dies sehr schwer zu implementieren ist:

   hardpython = interpreter2 . cpython 

Wir können auch einen anderen Compiler schreiben, der die Arbeit Python -> PythonVMCode erledigt, in einer anderen Sprache, sagen wir Python selbst.

mypython = Python -> PythonVMCode Python
mypython2 = Python -> PythonVMCode Ruby

Hier ist das komplizierte Beispiel PyPy. Ich bin nur ein Neuling von PyPy. Korrigieren Sie mich, wenn ich falsch liege:

PyPy-Dokument http://doc.pypy.org/en/latest/architecture.html#pypy-the-translation-framework

Unser Ziel ist es, eine mögliche Lösung für das Problem der Sprachimplementierer zu finden: Wir müssen l * o * p-Interpreter für l dynamische Sprachen und p Plattformen mit o entscheidenden Entwurfsentscheidungen schreiben.

Wir können denken, l ist X, p ist Y. Es gibt ein Programm, das alle RPython-Programme in C übersetzt:

 rpython_compiler = RPython -> C  Python

 pypy = Python -> Nothing RPython

 translate = compile the program pypy written in RPython using rpython_compiler

 py2rpy = Python -> RPython  Python
 py2c = Python -> C Python 
 py2c = rpython_compiler . py2rpy

RPython-Programme sind genau wie VM-Anweisungen, rpython_compiler ist die VM.

q1. pypy ist der Interpreter, ein RPython-Programm, das Python-Code interpretieren kann. Es gibt keine Ausgabesprache, daher können wir ihn nicht als Compiler betrachten, oder?

Hinzugefügt:

• Ich habe gerade festgestellt, dass Pypy auch nach der Übersetzung noch Dolmetscher ist, nur diesmal in C.
• Wenn wir tief in die Interpreter-Pypy schauen, muss es meiner Meinung nach eine Art Compiler geben, der die Python-Quellen zu einem AST kompiliert und dann ausführt

so was:

compiler_inside_pypy = Python -> AST_or_so

q2. Kann der Compiler py2rpy existieren, der alle Python-Programme in RPython umwandelt? In welcher Sprache es geschrieben ist, spielt keine Rolle. Wenn ja, bekommen wir einen anderen Compiler py2c. Was ist der Unterschied zwischen pypy und py2rpy in der Natur? Ist py2rpy viel schwieriger zu schreiben als pypy?

q3. Gibt es dazu allgemeine Regeln oder Theorien?

Weitere Compiler:

gcc_c = C -> asm? C  # not sure, gimple or rtl?
g++ =   C++ -> asm? C
clang = C -> LLVM_IR  C++
jython = Python -> JVMCode java
ironpython = Python -> CLI C#

q4. Wenn f = X -> Z ist, ein in P geschriebenes Programm P. Was können wir tun, wenn wir P beschleunigen wollen? Mögliche Wege:

• Schreiben Sie P in einen effizienteren Algorithmus um

• schreibe f um, um besseres Z zu erzeugen

• Wenn Z interpretiert wird, schreiben Sie einen besseren Z-Interpreter (PyPy ist hier?)

• Beschleunigen Sie rekursiv in Z geschriebene Programme

• Holen Sie sich eine bessere Maschine

ps. Bei dieser Frage geht es nicht um die technischen Aspekte des Schreibens eines Compilers, sondern um die Machbarkeit und Komplexität des Schreibens eines bestimmten Compilers.

q1. pypy ist der Interpreter, ein RPython-Programm, das Python-Code interpretieren kann. Es gibt keine Ausgabesprache, daher können wir ihn nicht als Compiler betrachten, oder?

PyPy ähnelt CPython, beide haben einen Compiler + Interpreter. CPython hat einen in C geschriebenen Compiler, der Python zu Python VM-Bytecode kompiliert und dann den Bytecode in einem in C geschriebenen Interpreter ausführt. PyPy hat einen in RPython geschriebenen Compiler, der Python zu Python VM-Bytecode kompiliert, und führt ihn dann in PyPy Interpreter aus, der in RPython geschrieben ist.

q2. Kann der Compiler py2rpy existieren, der alle Python-Programme in RPython umwandelt? In welcher Sprache es geschrieben ist, spielt keine Rolle. Wenn ja, bekommen wir einen anderen Compiler py2c. Was ist der Unterschied zwischen pypy und py2rpy in der Natur? Ist py2rpy viel schwieriger zu schreiben als pypy?

Kann ein Compiler py2rpy existieren? Theoretisch ja. Die Vollständigkeit garantiert dies.

Eine zu konstruierende Methode py2rpybesteht darin, einfach den Quellcode eines in RPython geschriebenen Python-Interpreters in den generierten Quellcode aufzunehmen. Ein Beispiel für einen in Bash geschriebenen py2rpy-Compiler:

// suppose that /pypy/source/ contains the source code for pypy (i.e. Python -> Nothing RPython)
cp /pypy/source/ /tmp/py2rpy/pypy/

// suppose $inputfile contains an arbitrary Python source code
cp $inputfile /tmp/py2rpy/prog.py

// generate the main.rpy
echo "import pypy; pypy.execfile('prog.py')" > /tmp/py2rpy/main.rpy

cp /tmp/py2rpy/ $outputdir

Wenn Sie jetzt einen Python-Code in RPython-Code übersetzen müssen, rufen Sie dieses Skript auf, das im $ outputdir ein RPython main.rpy, den Python-Interpreter-Quellcode des RPython und einen binären Blob prog.py erzeugt. Anschließend können Sie das generierte RPython-Skript durch Aufrufen ausführen rpython main.rpy.

(Hinweis: Da ich mit dem rpython-Projekt nicht vertraut bin, ist die Syntax zum Aufrufen des rpython-Interpreters, die Möglichkeit, pypy zu importieren und pypy.execfile auszuführen, und die Erweiterung .rpy nur erfunden, aber ich denke, Sie verstehen es.)

q3. Gibt es dazu allgemeine Regeln oder Theorien?

Ja, jede Turing Complete-Sprache kann theoretisch in jede Turing Complete-Sprache übersetzt werden. Einige Sprachen sind möglicherweise viel schwieriger zu übersetzen als andere Sprachen. Wenn die Frage jedoch "Ist es möglich?" Lautet, lautet die Antwort "Ja".

q4. ...

Hier gibt es keine Frage.

Um nur q2 zu beantworten, gibt es ein Compiler-Buch von William McKeeman, in dem die Theorie der Compiler für Sprache X, die in Sprache Y geschrieben ist und die Ausgabesprache Z erzeugt, über ein System von T-Diagrammen untersucht wird. Veröffentlicht in den 1970er Jahren, Titel nicht zur Hand, sorry.

q1. Im Allgemeinen ist ein Interpreter kein Compiler. Der Hauptunterschied zwischen einem Compiler und einem Interpreter besteht darin, dass ein Interpreter jedes Mal neu mit Quellcode in der Quellsprache startet. Wenn Ihr Pypy stattdessen pyAST oder pyP-Code war und Sie dann einen AST- oder P-Code-Interpreter hatten, können Sie pyAST als Compiler bezeichnen. So funktionierte der alte UCSD PASCAL-Compiler (wie auch einige andere): Sie wurden zu einem P-Code kompiliert, der beim Ausführen des Programms interpretiert wurde. (Sogar .NET bietet so etwas, wenn die Kompaktheit des generierten Objektcodes weitaus wichtiger ist als die Geschwindigkeit.)

q2. Ja, sicher. Siehe UCSD PASCAL (und einige andere).

q3. Stöbern Sie in den klassischen Texten der Informatik. Lesen Sie mehr über Concurrent PASCAL von Per Brinch-Hansen (wenn mir die Erinnerung dient). Es wurde viel über Compiler und Codegenerierung geschrieben. Das Generieren eines maschinenunabhängigen Pseudocodes ist normalerweise viel einfacher als das Generieren von Maschinencode: Der Pseudocode ist normalerweise frei von den Macken, die echte Maschinen ausnahmslos enthalten.

q4. Wenn Sie möchten, dass Ihr generiertes Objekt schneller ausgeführt wird, machen Sie den Compiler intelligenter, um eine bessere Optimierung zu erzielen. Wenn Ihr Objekt interpretiert wird, ziehen Sie in Betracht, komplexere Operationen in primitive Pseudoinstruktionen zu verschieben (CISC vs. RISC ist die Analogie), und Sie tun Ihr Bestes, um den Frack aus Ihrem Interpreter heraus zu optimieren.

Wenn Sie möchten, dass Ihr Compiler schneller ausgeführt wird, müssen Sie sich ALLES ansehen, einschließlich des Umdenkens Ihres Quellcodes. Nach dem Laden des Compilers selbst ist der zeitaufwändigste Teil der Kompilierung IMMER das Einlesen des Quellcodes in den Compiler. (Betrachten Sie zum Beispiel C ++. Wenn alle anderen Dinge relativ gleich sind, wird ein Compiler, der 9.000 (oder vielleicht 50.000) Zeilen # include-Dateien zerlegen muss, um ein einfaches "Hello, World" -Programm zu kompilieren, niemals so schnell sein wie eines das muss nur vier oder fünf Zeilen lesen.)

Ich erinnere mich nicht, wo ich es gelesen habe, aber der ursprüngliche Oberon-Compiler an der ETH-Zürich hatte einen sehr ausgeklügelten Symboltabellenmechanismus, ziemlich elegant. Wirths Benchmark für die Compilerleistung war die Zeit, die der Compiler brauchte, um sich selbst zu kompilieren. Eines Morgens ging er hinein, riss die wunderschöne mehrfach verknüpfte Ultra-Tree-Symboltabelle heraus und ersetzte sie durch ein einfaches lineares Array und gerade lineare Suchen. Die Doktoranden in seiner Gruppe waren geschockt. Nach der Änderung war der Compiler schneller, da die Module, die er kompilierte, immer klein genug waren, dass das elegante Monster mehr Gesamtaufwand verursachte als das lineare Array und die lineare Suche.

Ihre Fragen lassen mich glauben, dass das, was Sie wirklich wollen / brauchen, eine Erklärung dafür ist, was ein Compiler ist, was ein Interpreter ist und welche Unterschiede zwischen den beiden bestehen.

Ein Compiler ordnet ein in Sprache X geschriebenes Programm einem in Sprache Y geschriebenen funktional äquivalenten Programm zu. Beispielsweise könnte ein Compiler von Pascal nach C kompilieren

function Square(i: Integer)
begin
    Square := i * i
end

zu

int Square(int i)
{
    return i * i;
}

Die meisten Compiler kompilieren "abwärts", sodass sie übergeordnete Programmiersprachen in untergeordnete Sprachen kompilieren, wobei die ultimative untergeordnete Sprache Maschinencode ist.

Die meisten Compiler kompilieren direkt in Maschinencode, aber einige (insbesondere Java- und .NET-Sprachen) kompilieren in 'Bytecode' ( Java-Bytecode und CIL ). Stellen Sie sich Bytecode als Maschinencode für einen hypothetischen Computer vor. Dieser Bytecode wird dann beim Ausführen interpretiert oder JITted (dazu später mehr).

Ein Interpreter führt ein Programm aus, das in einer Sprache Z geschrieben ist. Ein Interpreter liest ein Programm Stück für Stück und führt es dabei aus. Zum Beispiel:

int i = 0;
while (i < 1)
{
    i++
}
return i;

Stellen Sie sich vor, der Interpreter betrachtet diese Programmzeile Zeile für Zeile, untersucht die Zeile, führt aus, was sie tut, schaut auf die nächste Zeile und so weiter.

Das beste Beispiel für einen Interpreter ist die CPU Ihres Computers. Es interpretiert Maschinencode und führt ihn aus. Wie die CPU funktioniert, hängt davon ab, wie sie physisch aufgebaut ist. Wie ein Interpreter-Programm funktioniert, hängt davon ab, wie sein Code aussieht. Die CPU interpretiert und führt daher das Interpreterprogramm aus, das seinerseits seine Eingabe interpretiert und ausführt. Auf diese Weise können Sie Dolmetscher verketten.

Ein JITter ist ein Just-In-Time-Compiler. Ein JITter ist ein Compiler. Der einzige Unterschied besteht in der Ausführungszeit: Die meisten Programme werden geschrieben, kompiliert, an ihre Benutzer gesendet und dann ausgeführt, aber Java-Bytecode und CIL werden zuerst an ihre Benutzer gesendet, und kurz bevor sie ausgeführt werden, werden sie auf den Computer kompiliert Code ihrer Benutzer.

C # -> (kompilieren) -> CIL -> an Kunden versendet -> (kurz vor der Ausführung kompilieren) -> Maschinencode -> (ausführen)

Das Letzte, was Sie wissen möchten, ist die Vollständigkeit von Turing ( Link ). Eine Programmiersprache ist Turing Complete, wenn sie alles berechnen kann, was eine ' Turing-Maschine ' kann, dh mindestens so 'leistungsfähig' wie eine Turing-Maschine. Die Church-Turing-These besagt, dass eine Turing-Maschine mindestens so leistungsfähig ist wie jede Maschine, die wir jemals bauen können. Daraus folgt, dass jede vollständige Turing-Sprache genauso leistungsfähig ist wie die Turing-Maschine, und daher sind alle vollständigen Turing-Sprachen gleich leistungsfähig.

Mit anderen Worten, solange Ihre Programmiersprache Turing vollständig ist (fast alle), spielt es keine Rolle, welche Sprache Sie auswählen, da sie alle die gleichen Dinge berechnen können. Dies bedeutet auch, dass es nicht sehr relevant ist, welche Programmiersprache Sie auswählen, um Ihren Compiler oder Ihren Interpreter zu schreiben. Last but not least bedeutet dies, dass Sie jederzeit einen Compiler von Sprache X nach Y schreiben können, wenn X und Y beide vollständig sind.

Beachten Sie, dass die Vollständigkeit von Turing nichts darüber aussagt, ob Ihre Sprache effizient ist, noch über alle Implementierungsdetails Ihrer CPU und anderer Hardware oder über die Qualität des Compilers, den Sie für die Sprache verwenden. Möglicherweise entscheidet Ihr Betriebssystem auch, dass Ihr Programm nicht über die Rechte zum Öffnen einer Datei verfügt. Dies beeinträchtigt jedoch nicht Ihre Fähigkeit, etwas zu berechnen. Ich habe das Rechnen absichtlich nicht definiert, da dies eine weitere Textwand erfordern würde.