Règles générales pour écrire un compilateur X sur Z en Y

Supposons que X est la langue d'entrée, Z est la langue de sortie, puis f est le compilateur, qui est écrit dans la langue Y.

f = X -> Z

Puisque f n'est qu'un programme, je pense que Y peut être n'importe quelle langue, non? Nous pouvons donc avoir des compilateurs f1, f2, chacun écrit en Y1, Y2.

f1 = f Y1    
f2 = f Y2

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

Prenez le compilateur cpython par exemple, X est Python, Z est le code VM Python, Y est C.

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

Les sources Python sont compilées dans le code Python VM, les fichiers .pyc, puis interprétées par l'interpréteur. On dirait qu'il est possible qu'il existe un compilateur qui peut directement faire Python -> MachineCode, bien que beaucoup difficile à implémenter:

   hardpython = interpreter2 . cpython 

Nous pouvons également écrire un autre compilateur faire le travail Python -> PythonVMCode, dans une autre langue, dit Python lui-même.

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

Maintenant, voici l'exemple compliqué PyPy. Je suis juste un débutant de PyPy, corrigez-moi si je me trompe:

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

Notre objectif est de fournir une solution possible au problème des implémenteurs de langage: avoir à écrire l * o * p interprètes pour l langages dynamiques et p plateformes avec o des décisions de conception cruciales.

On peut penser que l est X, p est Y. Il existe un programme qui traduit tous les programmes RPython en C:

 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

Les programmes RPython sont comme les instructions VM, rpython_compiler est la VM.

q1. pypy est l'interpréteur, un programme RPython qui peut interpréter le code Python, il n'y a pas de langage de sortie, donc nous ne pouvons pas le considérer comme un compilateur, non?

Ajoutée:

• Je viens de découvrir que même si après la traduction, pypy est toujours un interprète, mais cette fois écrit en C.
• Si nous regardons profondément dans le pypy interprète, je crois qu'il doit exister une sorte de compilateur, qui compile les sources Python en AST, puis exécute

comme ça:

compiler_inside_pypy = Python -> AST_or_so

q2. Le compilateur py2rpy peut-il exister, transformant tous les programmes Python en RPython? Dans quelle langue il est écrit n'a pas d'importance. Si oui, nous obtenons un autre compilateur py2c. Quelle est la différence entre pypy et py2rpy dans la nature? Py2rpy est-il beaucoup plus difficile à écrire que pypy?

q3. Existe-t-il des règles générales ou une théorie à ce sujet?

Plus de compilateurs:

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. Étant donné f = X -> Z, un programme P écrit en X. Lorsque nous voulons accélérer P, que pouvons-nous faire? Voies possibles:

• réécrire P dans un algorithme plus efficace

• réécrire f pour générer un meilleur Z

• si Z est interprété, écrivez un meilleur interprète Z (PyPy est ici?)

• accélérer les programmes écrits en Z récursivement

• obtenir une meilleure machine

ps. Cette question ne concerne pas les aspects techniques de la façon d'écrire un compilateur, mais la faisabilité et la complexité de l'écriture d'un certain type de compilateur.

q1. pypy est l'interpréteur, un programme RPython qui peut interpréter le code Python, il n'y a pas de langage de sortie, donc nous ne pouvons pas le considérer comme un compilateur, non?

PyPy est similaire à CPython, les deux ont un compilateur + interprète. CPython a un compilateur écrit en C qui compile le bytecode Python en Python VM puis exécute le bytecode dans un interpréteur écrit en C.PyPy a un compilateur écrit en RPython qui compile le bytecode Python en Python VM, puis l'exécute en PyPy Interpreter écrit en RPython.

q2. Le compilateur py2rpy peut-il exister, transformant tous les programmes Python en RPython? Dans quelle langue il est écrit n'a pas d'importance. Si oui, nous obtenons un autre compilateur py2c. Quelle est la différence entre pypy et py2rpy dans la nature? Py2rpy est-il beaucoup plus difficile à écrire que pypy?

Un compilateur py2rpy peut-il exister? Théoriquement oui. Turing l'exhaustivité le garantit.

Une méthode à construire py2rpyconsiste simplement à inclure le code source d'un interpréteur Python écrit en RPython dans le code source généré. Un exemple de compilateur py2rpy, écrit en Bash:

// 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

maintenant, chaque fois que vous avez besoin de traduire un code Python en code RPython, vous appelez ce script, qui produit - dans le $ outputdir - un RPython main.rpy, le code source de Python Interpreter de RPython et un prog.py blob binaire. Et puis vous pouvez exécuter le script RPython généré en appelant rpython main.rpy.

(note: puisque je ne connais pas le projet rpython, la syntaxe pour appeler l'interpréteur rpython, la possibilité d'importer pypy et de faire pypy.execfile, et l'extension .rpy est purement inventée, mais je pense que vous comprenez)

q3. Existe-t-il des règles générales ou une théorie à ce sujet?

Oui, n'importe quelle langue Turing Complete peut théoriquement être traduite dans n'importe quelle langue Turing Complete. Certaines langues peuvent être beaucoup plus difficiles à traduire que d'autres langues, mais si la question est "est-ce possible?", La réponse est "oui"

q4. ...

Il ne fait aucun doute ici.

Pour répondre uniquement au q2, il existe un livre de compilation de William McKeeman dans lequel la théorie des compilateurs pour le langage X écrite dans le langage Y produisant le langage de sortie Z est explorée via un système de diagrammes en T. Publié dans les années 1970, titre non disponible, désolé.

q1. Généralement, un interpréteur n'est pas un compilateur. La principale différence entre un compilateur et un interprète est qu'un interprète démarre à chaque fois avec du code source dans la langue source. Si votre pypy était à la place pyAST, ou pyP-code, et que vous aviez alors un interpréteur AST ou P-code, alors vous pourriez appeler pyAST un compilateur. C'est ainsi que l'ancien compilateur UCSD PASCAL fonctionnait (ainsi que plusieurs autres): ils ont compilé en un certain code P, qui a été interprété lors de l'exécution du programme. (Même .NET fournit quelque chose comme ça, lorsque la compacité du code objet généré est beaucoup plus importante que la vitesse.)

q2. Oui bien sûr. Voir UCSD PASCAL (et un tas d'autres).

q3. Parcourez les textes classiques de l'informatique. Lisez sur PASCAL simultané, par Per Brinch-Hansen (si ma mémoire est bonne). Beaucoup a été écrit sur les compilateurs et la génération de code. Générer un pseudocode indépendant de la machine est généralement beaucoup plus facile que de générer du code machine: le pseudocode est généralement exempt des caprices que les machines réelles contiennent invariablement.

q4. Si vous voulez que votre objet généré s'exécute plus rapidement, vous rendez le compilateur plus intelligent, pour une meilleure optimisation. Si votre objet est interprété, vous envisagez de pousser des opérations plus complexes vers le bas dans des pseudoinstructions primitives (CISC vs RISC est l'analogie), alors vous faites de votre mieux pour optimiser la fracturation de votre interprète.

Si vous voulez que votre compilateur s'exécute plus rapidement, vous devez regarder TOUT ce qu'il fait, y compris repenser votre code source. Après avoir chargé le compilateur lui-même, la partie la plus longue de la compilation est TOUJOURS de lire le code source dans le compilateur. (Considérez C ++ par exemple. Toutes autres choses étant relativement égales par ailleurs, un compilateur qui doit réduire 9 000 (ou peut-être 50 000) lignes de fichiers #include pour compiler un simple programme "Hello, World" ne sera jamais aussi rapide qu'un qui n'a qu'à lire quatre ou cinq lignes.)

Je ne me souviens pas où je l'ai lu, mais le compilateur Oberon original de l'ETH-Zurich avait un mécanisme de table de symboles très sophistiqué, assez élégant. La référence de Wirth pour les performances du compilateur était le temps nécessaire au compilateur pour se compiler. Un matin, il est entré, a arraché la magnifique table de symboles ultra-liée à plusieurs arbres et l'a remplacée par un simple tableau linéaire et des recherches linéaires droites. Les étudiants diplômés de son groupe ont été choqués. Après le changement, le compilateur était plus rapide, car les modules qu'il compilait étaient toujours suffisamment petits pour que l'élégant monstre impose un surcoût total plus important que le tableau linéaire et la recherche linéaire.

Vos questions, comme indiqué, me font croire que ce que vous voulez / avez vraiment besoin est une explication de ce qu'est un compilateur, de ce qu'est un interprète et des différences entre les deux.

Un compilateur mappe un programme écrit en langage X à un programme fonctionnellement équivalent écrit en langage Y. Par exemple, un compilateur de Pascal à C peut compiler

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

à

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

La plupart des compilateurs compilent «vers le bas», donc ils compilent des langages de programmation de niveau supérieur en langages de niveau inférieur, le langage de niveau inférieur ultime étant le code machine.

La plupart des compilateurs compilent directement en code machine, mais certains (notamment les langages Java et .NET) se compilent en «bytecode» ( Java bytecode et CIL ). Considérez le bytecode comme un code machine pour un ordinateur hypothétique. Ce bytecode est ensuite interprété ou JITted lors de son exécution (plus d'informations à ce sujet plus tard).

Un interprète exécute un programme écrit dans une langue Z. Un interprète lit un programme petit à petit et l'exécute au fur et à mesure. Par exemple:

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

Imaginez que l'interprète regarde cette ligne de programme pour la ligne, examine la ligne, exécute ce qu'elle fait, regarde la ligne suivante et ainsi de suite.

Le meilleur exemple d'interpréteur est le processeur de votre ordinateur. Il interprète le code machine et l'exécute. Le fonctionnement du CPU est spécifié par sa construction physique. Le fonctionnement d'un programme interpréteur est déterminé par l'apparence de son code. La CPU interprète et exécute donc le programme interpréteur, qui à son tour interprète et exécute son entrée. Vous pouvez chaîner des interprètes de cette façon.

Un JITter est un compilateur Just-In-Time. Un JITter est un compilateur. La seule différence est le moment où il est exécuté: la plupart des programmes sont écrits, compilés, expédiés à leurs utilisateurs puis exécutés, mais le bytecode Java et CIL sont expédiés à leurs utilisateurs en premier, puis juste avant leur exécution, ils sont compilés sur la machine code de leurs utilisateurs.

C # -> (compiler) -> CIL -> expédié au client -> (compiler juste avant l'exécution) -> code machine -> (exécuter)

La dernière chose que vous voudrez savoir est l' exhaustivité de Turing ( lien ). Un langage de programmation est Turing Complete s'il peut calculer tout ce qu'une « machine de Turing » peut, c'est-à-dire qu'il est au moins aussi «puissant» qu'une machine de Turing. La thèse de Church-Turing déclare qu'une machine de Turing est au moins aussi puissante que n'importe quelle machine que nous pouvons jamais construire. Il s'ensuit que chaque langage complet Turing est exactement aussi puissant que la machine Turing, et donc tous les langages complets Turing sont tout aussi puissants.

En d'autres termes, tant que votre langage de programmation est Turing complet (presque tous), peu importe le langage que vous choisissez, car ils peuvent tous calculer les mêmes choses. Cela signifie également qu'il n'est pas très pertinent de savoir quel langage de programmation vous choisissez pour écrire votre compilateur ou votre interprète. Enfin, cela signifie que vous pouvez toujours écrire un compilateur du langage X vers Y si X et Y sont tous les deux Turing terminés.

Notez qu'être Turing complet ne dit rien sur l'efficacité de votre langue, ni sur tous les détails d'implémentation de votre CPU et autre matériel, ni sur la qualité du compilateur que vous utilisez pour la langue. De plus, votre système d'exploitation peut décider que votre programme n'a pas les droits pour ouvrir un fichier, mais cela n'empêche pas votre capacité de calculer quoi que ce soit - je n'ai délibérément pas défini l'informatique, car cela prendrait un autre mur de texte.