c++ - registros - procedimiento documentado ejemplo
Referencias necesarias para implementar un intérprete en C/C++ (5)
Me encuentro vinculado 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 había 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 ++). Entonces, restricciones:
- la implementación estará en C ++
- el análisis probablemente se manejará con una gramática yacc / bison (es ahora)
- las sugerencias de ecologías completas de VM / intérprete como NekoVM y LLVM probablemente no sean prácticas para este proyecto. Independiente es mejor, incluso si esto suena como NIH.
Lo que realmente estoy buscando es leer material sobre los fundamentos de la implementación de intérpretes. Hice algunas búsquedas 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 reunido hasta ahora:
Lisp en pequeñas piezas , 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.
Estructura e interpretación de programas informáticos . 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.
En 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.
Implementación de loros . Esto parece una lectura divertida. No estoy seguro de que me proporcione los fundamentos.
Esquema de 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.
Patrones de implementación del lenguaje: Cree sus propios lenguajes específicos de dominio y de programación , recomendados en la secuencia de comentarios para Libros sobre la creación de idiomas interpretados . 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.
- Nuevo (y aún viejo , es decir, 1979): Escritura de compiladores e intérpretes interactivos por PJ 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.
Entonces, ¿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 ejecutándolo en nuestro entorno de aplicación. Los builtins se usan para afectar nuestra representación de datos en memoria.
no debería ser terriblemente lento. El árbol andador actual parece aceptable.
El lenguaje se basa en Lisp, pero no es Lisp, por lo que no se requiere el cumplimiento de estándares.
- 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 revisaré sus citas. ¡Gracias a todos!
Echa un vistazo a JScheme de 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).
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 autohospedaje mínimo: http://www.scheme.dk/blog/2006/12/self-evaluating-evaluator.html .
Una respuesta un poco más larga:
Es difícil dar consejos sin saber lo que necesita 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 estándares? Labios comunes? R5RS? R6RS? ¿Qué SFRI necesitas?
Si necesita algo más elegante que un simple árbol de arborescencia de sintaxis, le recomiendo incrustar un subsistema de esquema rápido. El esquema de Gambit me viene a la mente: http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Main_Page .
Si ese no es un capítulo de la opción 5 en SICP y 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 menciona una pareja: http://webkit.org/blog/189/announcing-squirrelfish/ .
También están los documentos del esquema canónico: http://library.readscheme.org/page1.html para el compilador RABBIT.
Si me dedico a un poco de especulación prematura, la administración de la memoria puede ser un hueso duro de roer. Nils M Holm ha publicado un libro "Esquema 9 del espacio vacío" http://www.t3x.org/s9fes/, que incluye una simple marca para dejar de fumar y barrer al recolector de basura. 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 .
Sí en SICP.
He hecho esta tarea varias veces y esto es lo que haría si fuera usted:
Diseña tu 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 VM y asegúrate de mantener limpia la API. Mi última implementación tenía esto como una API de nivel superior (perdone el formateo - SO está cargando mi vista previa)
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 no es necesario, se implementa en términos de lectura, evaluación e impresión. REPL es un patrón común para intérpretes, especialmente LISP.
Un ConsBoxFactory está disponible para crear nuevos buzones de cons y para 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 tu trabajo debe seguir estos tres pasos. Luego, encontrará que su código de cliente y su código de soporte también se parece mucho a LISP:
t_ConsBox *ConsBoxFactory::Cadr(t_ConsBox *list)
{
return Car(Cdr(list));
}
Puedes escribir el analizador en yacc / lex, pero ¿para 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.
Facilite la tarea de escribir y sacar el código C y facilitar la depuración de problemas cuando las cosas van mal.
Los intérpretes Kamin 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 Small Pieces entra en más profundidad, pero eso es bueno y malo para tu 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 te 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.
Me gustaría extender mi recomendación para Lenguajes de Programación: Aplicación e Interpretación . 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.).