Références nécessaires pour implémenter un interpréteur en C / C ++

Question

Je me trouve attaché à un projet de integerate un interprète dans une application existante. La langue d'interprétation est un dérivé de Lisp, à des applications spécifiques, les builtins. Personne des "programmes" sera exécuté par lots de style dans l'application.

Je suis surpris de voir qu'au fil des années, j'ai écrit un couple de compilateurs, et plusieurs de données de traducteurs en langues/analyseurs, mais je n'ai jamais écrit un interprète avant. Le prototype est assez loin le long, mis en œuvre comme un arbre de syntaxe walker, en C++. Je peux probablement l'influence de l'architecture au-delà du prototype, mais pas la mise en œuvre du langage (C++). Ainsi, les contraintes:

• la mise en œuvre sera en C++
• l'analyse sera probablement traitée avec un yacc/bison de la grammaire (c'est maintenant)
• suggestions de plein VM/Interprète écologies comme NekoVM et LLVM sont probablement pas pratique pour ce projet. Autonomes est mieux, même si cela sonne comme le NIH.

Ce que je suis à la recherche de matériel de lecture sur les principes fondamentaux de la mise en œuvre des interprètes. J'ai fait un peu de navigation de la SORTE, et un autre site appelé Lambda Ultime, même s'ils sont plus orientés vers la programmation de la théorie des langages.

Certains des friandises j'ai réuni ce jour:

• Lisp en Petits Morceaux, par Christian Queinnec. La personne qui recommande, il a déclaré qu'il "va de la simple interprète à des techniques plus avancées et des finitions de la présentation de "bytecode" et "Régime de C compilateurs"."

• NekoVM. Comme je l'ai mentionné ci-dessus, je doute que nous serions autorisés à intégrer un ensemble de VM cadre à l'appui de ce projet.

• La Structure et l'Interprétation des Programmes d'Ordinateur. À l'origine, j'ai suggéré que ce serait peut-être exagéré, mais, ayant travaillé une bonne partie, je suis d'accord avec @JBF. Très instructif, et l'esprit en expansion.

• Sur Lisp par Paul Graham. J'ai lu cela, et alors qu'il est une introduction utile à Lisp principes, n'est pas suffisant pour relancer la construction d'un interprète.

• Parrot Mise En Œuvre. Cela semble être un plaisir à lire. Pas sûr que ça va me fournir les principes de base.

• Régime à partir de Zéro. Pierre Michaux est d'attaquer les différentes implémentations de Système, à partir d'un rapide et sale interpréteur Scheme écrit en C (pour une utilisation en tant que bootstrap dans des projets ultérieurs) compilé Régime de code. Très intéressant jusqu'à présent.

• La langue mise en Œuvre des Schémas: Créer Votre Propre nom de Domaine Spécifique et Générale des Langages de Programmation, recommandé dans le fil de commentaires de Livres Sur la Création de Langages Interprétés. Le livre contient deux chapitres consacrés à la pratique de la construction des interprètes, je suis donc de l'ajouter à ma lecture de la file d'attente.

• Nouveau (et encore Vieux, c'est à dire de 1979): l'Écriture Interactive Compilateurs et Interprètes par P. J. Brown. C'est épuisées depuis longtemps, mais il est intéressant de fournir un aperçu des différentes tâches associées à la mise en œuvre d'un interpréteur Basic. J'ai vu des critiques mitigées pour celui-ci, mais comme il est pas cher (je l'ai sur ordonnance utilisé pour autour de $3.50) je vais lui donner un spin.

Alors, comment à ce sujet? Est-il un bon livre qui prend le néophyte par la main et montre comment construire un interprète en C/C++ pour un Lisp comme langue? Avez-vous une préférence pour la syntaxe de l'arbre-les marcheurs ou bytecode interprètes?

Pour répondre à @JBF:

• le prototype actuel est un interprète, et il fait sens pour moi que nous sommes en acceptant un chemin d'accès à un code arbitraire de fichier et de l'exécuter dans notre environnement d'application. Les objets internes sont utilisés pour affecter notre en mémoire de représentation des données.

• il ne devrait pas être affreusement lent. L'arborescence actuelle walker semble tout à fait acceptable.

• La langue est basée sur le langage Lisp, mais n'est pas Lisp, donc pas de respect des normes requises.

• Comme mentionné ci-dessus, il est peu probable que nous serons autorisés à ajouter un externe VM/interprète projet visant à résoudre ce problème.

Pour les autres affiches, je vais vérifier vos citations ainsi. Merci à tous!

Answer 1

Réponse courte:

Les fondamentaux de la liste de lecture pour un interpréteur lisp est SICP. Je ne serais pas à tous l'appellent excessif, si vous sentez que vous êtes surqualifié pour les premières parties du livre sauter au chapitre 4 et au début de l'interprétation de suite (bien que je crois que ce serait une perte puisque les chapitres 1 à 3 sont vraiment que du bon!).

Ajouter LISP en Petits Morceaux (LISP à partir de maintenant), les chapitres 1 à 3. En particulier le chapitre 3 si vous avez besoin de mettre en œuvre toute non-trivial formulaires de contrôle.

Voir ce post par Jens Axel Søgaard sur un minimum d'auto-hébergement Schéma: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html .

Réponse un peu plus longue:

Il est difficile de donner des conseils sans savoir ce que vous avez besoin de votre interprète.

• est-il vraiment vraiment besoin d'être un interprète, ou avez-vous réellement besoin d'être en mesure d'exécuter du code lisp?
• est-il besoin d'être rapide?
• faut-il le respect des normes? Commune Lèvres? R5RS? R6RS? Tout SFRIs-vous besoin?

Si vous besoin de quelque chose de plus classe qu'un simple arbre de syntaxe walker je vous recommande fortement de l'incorporation d'un rapide schéma de sous-système. Gambit régime vient à l'esprit: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page .

Si ce n'est pas une option au chapitre 5 dans SICP et les chapitres 5-- en LISP de la cible de compilation pour une exécution plus rapide.

Pour accélérer l'interprétation, je voudrais prendre un coup d'oeil à la plus récente JavaScript interpréteurs et des compilateurs. Il semble y avoir beaucoup de réflexion va dans rapide d'exécution de JavaScript, et vous pouvez probablement apprendre d'eux. V8 cites deux documents importants: http://code.google.com/apis/v8/design.html et squirrelfish cite un couple: http://webkit.org/blog/189/announcing-squirrelfish/ .

Il y a aussi le schéma canonique de papiers: http://library.readscheme.org/page1.html pour le LAPIN compilateur.

Si je m'engage dans un peu prématuré de la spéculation, de la gestion de la mémoire pourrait être la noix dure à casser. Nils M Holm a publié un livre intitulé "Schéma 9 à partir de l'espace vide" http://www.t3x.org/s9fes/ qui inclut un simple cessez-le-monde marque et de balayage garbage collector. Source inclus.

John Rose (de la plus récente de la JVM de la gloire) a écrit un papier sur l'intégration du Système sur C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92 .

Answer 2

Oui sur SICP.

J'ai fait cette tâche plusieurs fois et voici ce que je ferais si j'étais vous:

La conception de votre modèle de mémoire de la première. Vous aurez besoin d'un GC système d'une certaine sorte. C'est WAAAAY plus facile de le faire d'abord que les visser sur le tard.

La conception de vos structures de données. Dans mon implémentations, j'ai eu une base inconvénients de la boîte avec un certain nombre de types de base: l'atome, chaîne de caractères, nombre, liste, bool, primitive de la fonction.

La conception de votre VM et de veiller à garder l'API propre. Ma dernière œuvre se présente comme une API de niveau supérieur (pardon pour la mise en forme est pooching mon extrait)

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

RunProgram n'est pas nécessaire - il est mis en œuvre en termes de Lire, Eval, et de les Imprimer. REPL est un modèle commun pour les interprètes, en particulier LISP.

Un ConsBoxFactory est disponible pour faire de nouveaux inconvénients des boîtes et de les manipuler. Un AtomFactory est utilisé de sorte que l'équivalent symbolique d'atomes de carte à un seul objet. Un Environnement est utilisé pour maintenir la liaison de symboles à contre-boîtes.

La plupart de votre travail devrait aller dans ces trois étapes. Ensuite, vous trouverez que votre code client et le code de prise en charge commence à sembler beaucoup comme LISP trop:

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

Vous pouvez écrire le parser en yacc/lex, mais pourquoi s'embêter? Lisp est un outil très simple de la grammaire et de scanner/récursive de la descente de l'analyseur paire pour il est environ deux heures de travail. Le pire, c'est écrit prédicats d'identifier les jetons (c'est à dire, IsString, IsNumber, IsQuotedExpr, etc) et puis l'écriture de routines pour convertir les tokens dans les inconvénients des boîtes.

Rendre plus facile l'écriture de la colle dans et hors de code en C et de le rendre facile à déboguer les problèmes quand les choses vont mal.

Answer 3

Le Kamin Interprètes de Samuel Kamin le livre de Langages de Programmation, les services d'Un Interprète Approche Fondée sur les, traduit en C++ par Timothy Budd. Je ne suis pas sûr de l'utilité de la nue-code source sera, comme il était censé aller avec le livre, mais c'est un bel ouvrage qui couvre les bases de la mise en œuvre de Lisp dans un langage de bas niveau, y compris la collecte des ordures, etc. (Qui n'est pas le propos du livre, qui est des langages de programmation en général, mais il est couvert.)

Lisp en Petits Morceaux va en profondeur, mais c'est à la fois bon et mauvais pour votre cas. Il y a beaucoup de matière sur la compilation et à ces qui ne sont pas utiles pour vous, et à sa plus simple interprètes sont dans le Schéma, pas du C++.

SICP est bon, certainement. Pas surpuissant, mais bien sûr l'écriture des interprètes n'est qu'une petite fraction de l'ouvrage.

Le JScheme suggestion est bonne, trop (et il intègre un code par moi), mais ne sera pas vous aider avec des choses comme la GC.

Je pourrais chair avec plus de suggestions plus tard.

Edit: quelques personnes ont dit qu'ils ont appris de mon awklisp. C'est certes une sorte de bizarre suggestion, mais il est très petit, lisible, réellement utilisable, et contrairement à d'autres petits encore lisible jouet Lisps il met en œuvre ses propres garbage collector et de représentation des données au lieu de s'appuyer sur un sous-jacent de haut niveau langage de mise en œuvre de leur fournir.

Answer 4

Découvrez JScheme de Peter Norvig . J'ai trouvé cela incroyablement simple à comprendre et à transférer en C ++. Euh, je ne sais pas comment utiliser le schéma comme langage de script - l'enseigner à jnrs est lourd et semble désuet (helloooo 1980).

Answer 5

Je tiens à exprimer ma recommandation pour les Langages de Programmation: Application et de l'Interprétation. Si vous voulez écrire un interprète, ce livre vous emmène dans un très court chemin. Si vous lisez à travers l'écriture de code vous de lire et de faire l'exercice, vous vous retrouvez avec un tas de similaire des interprètes, mais différents (l'un est impatient, l'autre est paresseux, on est dynamique, l'autre a un peu de temps, une dynamique portée, l'autre de portée lexicale, etc).