F # parsing Árboles sintácticos abstractos

Question

¿Cuál es la mejor manera de usar F # para analizar un AST para construir un intérprete? Hay muchos ejemplos de F # para sintaxis trivial (operaciones aritméticas básicas) pero parece que no puedo encontrar nada para lenguajes con rangos de características mucho mayores.

Las uniones discriminadas parecen ser increíblemente útiles, pero ¿cómo construir una con un gran número de opciones? ¿Es mejor definir los tipos (por ejemplo, suma, resta, condicionales, flujo de control) en otro lugar y simplemente juntarlos como tipos predefinidos en la unión?

¿O me he perdido algún medio mucho más eficaz de escribir intérpretes? ¿Tener una función eval para cada tipo es más efectiva, o quizás usar mónadas?

Gracias de antemano

Answer 1

sindicatos parecen ser discriminado incrediably útil, pero ¿cómo lo ir sobre la construcción de una con gran número de opciones ? ¿Es mejor para definir los tipos (por ejemplo, sustracción, condicionales, control flujo) en otro lugar y simplemente traerlos juntos como tipos predefinidos en la unión ?

No estoy seguro de lo que está preguntando aquí; incluso con una gran cantidad de opciones, los DU todavía son simples de definir. Ver p. this blog entry para la estructura de DU de un lenguaje pequeño (así como una discusión más general sobre cómo escribir transformaciones de árbol). Está bien tener un DU con muchos más casos, y común en compiladores/intérpretes para usar dicha representación.

En cuanto al análisis sintáctico, prefiero los combinadores de analizadores monádicos; echa un vistazo a FParsec o ver this old blog entry. Después de usar esos combinadores de analizadores, nunca podré volver a nada como lex/yacc/ANTLR: las DSL externas parecen tan primitivas en comparación.

(EDIT: Los 'pequeños ejemplos aritméticos' que ha encontrado son probablemente más o menos representativa de lo que las soluciones de mayor tamaño se parece así Los ejemplos 'juguete' suele mostrar la arquitectura adecuada..)

Answer 2

que no he hecho a mí mismo un intérprete. Espero que lo siguiente ayude :)

Here es un curso de compilador impartido en Yale utilizando ML, que puede serle útil. Las notas de la conferencia son muy concisas (cortas) e informativas. Puede seguir las primeras notas de clase y las tareas. Como sabes F #, no tendrás problemas para leer los programas de ML.

Btw, el profesor fue alumno de A. Appel, quien es el creador de la implementación de SML. Entonces, a partir de estas notas, también obtienes la forma más natural para escribir un compilador/intérprete en el lenguaje de la familia ML.

Answer 3

Puede que esté interesado en consultar la sección Lexing and Parsing del F # WikiBook. El F# PowerPack library contiene las herramientas FsLex y FsYacc, lo que ayuda mucho con esto. La guía WikiBook es una buena manera de comenzar con esto.

Más allá de eso, tendrá que pensar en cómo realmente desea ejecutar el código del formulario AST, que es común en el diseño de compiladores e intérpretes. En general, esto se considera la parte más fácil, y hay muchos recursos generales sobre compiladores/intérpretes que deberían proporcionar información al respecto.

Answer 4

Debe llevar una copia de "Starting F #" de Robert Pickering.

El capítulo 13, "análisis de texto", contiene un ejemplo con FsLex y FsYacc, según lo sugerido por el Noldorin.

Aparte de eso, en el mismo libro, capítulo 12, el autor explica cómo compilar un compilador simple real para un lenguaje aritmético que propone. Muy esclarecedor La parte más importante es lo que estás buscando: el analizador AST.

Buena suerte.

Answer 5

Me segunda Brian sugerencia de echar un vistazo a FParsec. Si estás interesado en hacer las cosas a la vieja usanza con FsLex y FsYacc, un lugar para buscar cómo analizar un lenguaje no trivial es la propia fuente de F #. Consulte el directorio source\fsharp\FSharp.Compiler en la distribución.

Answer 6

This is un excelente ejemplo de una implementación básica pequeña completa con F # y FParsec. Incluye incluso el compilador de IL. Todo el código es muy accesible y está acompañado de una serie de entradas de blog del autor al http://trelford.com/blog/