Referencias necesarias para implementar un intérprete en C/C++

Question

Me encuentro adjunto a un proyecto para integrar un intérprete en una aplicación existente. El lenguaje que se debe interpretar es un derivado de Lisp, con builtins específicos de la aplicación. Los 'programas' individuales se ejecutarán por lotes en la aplicación.

Me sorprende que a lo largo de los años haya escrito un par de compiladores y varios traductores/analizadores de datos de idiomas, pero nunca antes he escrito un intérprete. El prototipo está bastante avanzado, implementado como un árbol de sintaxis en C++. Probablemente pueda influir en la arquitectura más allá del prototipo, pero no en el lenguaje de implementación (C++). Por lo tanto, las limitaciones:

• aplicación será en C++
• análisis probablemente será manejada con un yacc gramática/bisontes (que es ahora)
• sugerencias de completos ecologías VM/intérprete como NekoVM y LLVM son probablemente no es práctico para este proyecto. Independiente es mejor, incluso si esto suena como NIH.

Lo que realmente estoy buscando es material de lectura sobre los fundamentos de la implementación de intérpretes. Hice una navegación de SO, y otro sitio conocido como Lambda the Ultimate, aunque están más orientados hacia la teoría del lenguaje de programación.

Algunas de las cositas que he obtenido hasta ahora:

• Lisp in Small Pieces, por Christian Queinnec. La persona que lo recomendó dijo que "pasa del intérprete trivial a técnicas más avanzadas y termina presentando códigos de bytes y compiladores de 'Esquema a C'".

• NekoVM. Como mencioné anteriormente, dudo que se nos permita incorporar un marco VM completo para apoyar este proyecto.

• Structure and Interpretation of Computer Programs. Originalmente, sugerí que esto podría ser excesivo, pero después de haber trabajado en un segmento saludable, estoy de acuerdo con @JBF. Muy informativo y expansivo de la mente.

• On Lisp por Paul Graham. He leído esto, y si bien es una introducción informativa a los principios de Lisp, no es suficiente para comenzar a construir un intérprete.

• Parrot Implementation. Esto parece una lectura divertida. No estoy seguro de que me proporcione los fundamentos.

• Scheme from Scratch. Peter Michaux está atacando varias implementaciones de Scheme, desde un intérprete Scheme rápido y sucio escrito en C (para usarlo como un programa de arranque en proyectos posteriores) hasta el código compilado del Esquema. Muy interesante hasta ahora.

• Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages, se recomienda en la secuencia de comentarios para Books On Creating Interpreted Languages. El libro contiene dos capítulos dedicados a la práctica de la construcción de intérpretes, por lo que lo estoy agregando a mi cola de lectura.

• Nueva (y sin embargo antiguo, es decir, 1979): Writing Interactive Compilers and Interpreters por P. J. Brown. Esto está agotado por mucho tiempo, pero es interesante para proporcionar un resumen de las diversas tareas asociadas con la implementación de un intérprete básico.He visto críticas mixtas para este pero como es barato (lo tengo en orden usado por alrededor de $ 3.50) voy a darle un giro.

¿Qué tal? ¿Existe un buen libro que tome al neófito de la mano y muestre cómo construir un intérprete en C/C++ para un lenguaje parecido a Lisp? ¿Tiene preferencia por sintaxis-tree walkers o bytecode intérpretes?

Para responder @JBF:

• el prototipo actual es un intérprete, y tiene sentido para mí, ya que estamos aceptando una ruta a un archivo de código arbitrario y ejecutarlo en nuestro entorno de aplicación. Los builtins se usan para afectar nuestra representación de datos en memoria.

• no debe ser terriblemente lento. El árbol andador actual parece aceptable.

• El idioma es basado en en Lisp, pero no es Lisp, por lo que no se requiere el cumplimiento de las normas.

• Como se mencionó anteriormente, es poco probable que se nos permita agregar un proyecto de VM/intérprete externo completo para resolver este problema.

Para los otros carteles, también estaré revisando sus citas. ¡Gracias a todos!

Answer 1

Respuesta corta:

La lista de lectura fundamental para un intérprete de Lisp es SICP. No lo llamaría demasiado, si sientes que estás sobre calificado para las primeras partes del libro salta al capítulo 4 y comienzas a interpretar (¡aunque creo que esto sería una pérdida ya que los capítulos 1-3 realmente son tan buenos!) .

Agregue LISP en piezas pequeñas (LISP a partir de ahora), capítulos 1-3. Especialmente el capítulo 3 si necesita implementar formas de control no triviales.

Ver esta publicación de Jens Axel Søgaard en un esquema de auto-hosting mínimo: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html.

Una respuesta un poco más largo:

Es difícil dar consejos sin saber lo que requiere de su intérprete.

• ¿realmente necesita ser un intérprete, o realmente necesita ser capaz de ejecutar el código de lisp?
• ¿necesita ser rápido?
• ¿necesita cumplimiento de las normas? Labios comunes? R5RS? R6RS? ¿Qué SFRI necesitas?

Si necesita algo más elegante que un simple árbol de sintaxis, recomiendo incrustar un subsistema de esquema rápido. El esquema de Gambit viene a la mente: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page.

Si esa no es una opción, el capítulo 5 en SICP y los capítulos 5-- en la compilación de objetivos LISP para una ejecución más rápida.

Para una interpretación más rápida, echaré un vistazo a los intérpretes/compiladores de JavaScript más recientes. Parece que se está pensando mucho en la rápida ejecución de JavaScript, y probablemente puedas aprender de ellos. V8 cita dos documentos importantes: http://code.google.com/apis/v8/design.html y squirrelfish cita un par: http://webkit.org/blog/189/announcing-squirrelfish/.

También existe el documento de esquema canónico: http://library.readscheme.org/page1.html para el compilador RABBIT.

Si me dedico a un poco de especulación prematura, la gestión de la memoria puede ser la tuerca más difícil de romper. Nils M Holm ha publicado un libro "Esquema 9 del espacio vacío" http://www.t3x.org/s9fes/ que incluye una marca de stop-the-world y barredora de basura simple. Fuente incluida.

John Rose (de la nueva fama de JVM) ha escrito un documento sobre la integración de Scheme en C: http://library.readscheme.org/servlets/cite.ss?pattern=AcmDL-Ros-92.

Answer 2

Echa un vistazo JScheme from Peter Norvig. Encontré esto increíblemente simple de entender y portar a C++. Uh, no sé si usar el esquema como un lenguaje de scripting, enseñarlo a jnrs es engorroso y se siente anticuado (helloooo 1980's).

Answer 3

The Kamin Interpreters del libro de Samuel Kamin Lenguajes de programación, un enfoque basado en el intérprete, traducido a C++ por Timothy Budd. No estoy seguro de cuán útil será el código fuente simple, ya que estaba destinado a ir con el libro, pero es un buen libro que cubre los aspectos básicos de la implementación de Lisp en un lenguaje de nivel inferior, incluida la recolección de basura, etc. (Ese no es el enfoque del libro, que es el lenguaje de programación en general, pero está cubierto.)

Lisp en pequeñas piezas entra en más profundidad, pero eso es bueno y malo para su caso. Hay mucho material sobre la compilación y eso no será relevante para usted, y sus intérpretes más simples están en Scheme, no en C++.

SICP es bueno, definitivamente. No excesivo, pero por supuesto escribir intérpretes es solo una pequeña fracción del libro.

La sugerencia de JScheme también es buena (e incorpora algún código mío), pero no le ayudará con cosas como GC.

Podría completar esto con más sugerencias más adelante.

Editar: Algunas personas han dicho que aprendieron de mi awklisp. Esta es una especie de sugerencia extraña, pero es muy pequeña, legible, realmente utilizable y, a diferencia de otros diminutos Lisps de juguete, implementa su propio recolector de basura y representación de datos en lugar de confiar en un lenguaje subyacente de implementación de alto nivel para proveerles.

Answer 4

Sí en SICP.

que he hecho esta tarea varias veces y esto es lo que haría si yo fuera usted:

del diseño de su modelo de memoria primero. Querrás un sistema de GC de algún tipo. Es WAAAAY más fácil hacer esto primero que atornillarlo más tarde.

Diseña tus estructuras de datos. En mis implementaciones, he tenido un cuadro básico de contras con varios tipos básicos: átomo, cadena, número, lista, bool, función primitiva.

Diseña tu máquina virtual y asegúrate de mantener limpia la API.Mi última ejecución tuvo esto como una API de alto nivel (valga el formato - SO se pooching mi vista previa) no es necesaria

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 - se implementa en términos de lectura, Eval e Imprimir. REPL es un patrón común para intérpretes, especialmente LISP.

ConsBoxFactory está disponible para crear nuevos buzones y operarlos. Se usa una AtomFactory para que los átomos simbólicos equivalentes se asignen exactamente a un objeto. Un entorno se utiliza para mantener la unión de símbolos a cuadros de cons.

La mayor parte de su trabajo debe seguir estos tres pasos. A continuación, usted encontrará que su código de cliente y el código de soporte empieza a parecerse mucho a LISP también:

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

Usted puede escribir el analizador de yacc/lex, pero ¿por qué molestarse? Lisp es un par de analizadores gramaticales y escáner/recursivo-descendente increíblemente simples, ya que se trata de dos horas de trabajo. La peor parte es escribir predicados para identificar los tokens (es decir, IsString, IsNumber, IsQuotedExpr, etc.) y luego escribir rutinas para convertir los tokens en cuadros de cons.

Facilita la tarea de escribir o quitar el código C y facilita la depuración de problemas cuando las cosas van mal.

Answer 5

Me gustaría extender mi recomendación para Programming Languages: Application and Interpretation. Si quieres escribir un intérprete, ese libro te lleva allí en un camino muy corto. Si lees al escribir el código que lees y haces el ejercicio, terminas con un grupo de intérpretes similares pero diferentes (uno está ansioso, el otro es flojo, uno es dinámico, el otro tiene algo de tipeo, uno tiene alcance dinámico, otro tiene alcance léxico, etc.).