Elegante modelo AST

Question

Estoy en el proceso de escribir un compilador de juguetes en scala. El idioma de destino en sí se parece a scala, pero es un campo abierto para experimentar.

Después de varias refactorizaciones grandes, no puedo encontrar una buena manera de modelar mi árbol de sintaxis abstracta. Me gustaría usar las funciones de la coincidencia de patrones de scala, el problema es que el árbol lleva información en movimiento (como tipos, símbolos) a lo largo del proceso de compilación.

puedo ver un par de soluciones, ninguna de las cuales me gustan:

• clases de casos con campos variables (creo que el compilador de Scala hace esto): el problema es que esos campos no se presentan una cada etapa de la compilación y, por lo tanto, tienen que anularse (u Opción'd) y se vuelve realmente pesado depurar/escribir código. Además, si, por ejemplo, encuentro un nodo con un tipo nulo después de la fase de tipeo, me es muy difícil encontrar la causa del error.

• enorme jerarquía de clases rasgo/caja: algo así como Nodo, NodeWithSymbol, NodeWithType, ... parece como un dolor para escribir y trabajar con

• mano algo completamente hecho a mano con extractores

Tampoco estoy seguro si es una buena práctica ir con un AST completamente inmutable, especialmente en scala donde no hay intercambio implícito (porque el compilador no está al tanto de la inmutabilidad) y podría perjudicar las actuaciones para copiar el árbol todo el tiempo .

¿Puedes pensar en un patrón elegante para modelar mi árbol usando el potente sistema de scala?

Answer 1

Recientemente comencé a escribir un verificador de juguetes para un lenguaje pequeño, y estoy usando la biblioteca Kiama para las fases del analizador, del resolver y del verificador de tipos.

Kiama es una biblioteca de Scala para el procesamiento del lenguaje. Permite el análisis conveniente y la transformación de datos estructurados. Los estilos de programación admitidos por la biblioteca se basan en paradigmas conocidos de procesamiento del lenguaje formal, incluidos attribute grammars, tree rewriting, abstract state machines y pretty printing.

voy a tratar de resumir mi experiencia (bastante limitado):

• [+] Kiama viene con varios ejemplos, y el principal contribuyente suele responder rápidamente a las preguntas formuladas en la lista de correo

• [+] El paradigma atributo gramática permite una agradable separación en "componentes inmutables" de los nodos, por ejemplo, nombres y subnodos, y "componentes mutables", por ejemplo, información del tipo

• [+] La biblioteca viene con un sistema de reescritura versátil que, hasta ahora, cubrió todos mis casos de uso

• [+] La biblioteca, p., La impresora bonita, hacer buenos ejemplos de DSL y de diversos patrones/enfoques/ideas funcionales

• [-] La curva de aprendizaje que sin duda empinada, incluso con ejemplos y la lista de correo a la mano

• [- ] Implementar la fase de resolución en un estilo "puramente funcional" (ver my question) parece complicado, pero un enfoque híbrido (que aún no lo he probado) parece posible

• [-] El paradigma de gramática de atributos y la separación de preocupaciones resultante no hace que sea obvio cómo documentar las propiedades que tienen los nodos al final (my question)

• [-] Los rumores dicen, que el paradigma de atributos gramática no dió las implementaciones más rápidas

Resumiendo mi resumen, me gusta utilizar Kiama mucho y lo recomiendo encarecidamente que lo prueben , o al menos echar un vistazo a los ejemplos.

(PS No estoy afiliado con Kiama.)

Answer 2

TL; DR prefiero mantener el AST inmutable y llevar a cosas como información de tipo en una estructura separada, por ejemplo, un Mapa, que puede ser referido por ID almacenados en el AST. Pero no hay una respuesta perfecta.

No eres el primero en luchar con esta pregunta. Permítanme enumerar algunas opciones:

1) Estructuras mutables que se actualizan en cada fase. Todas las ventajas y desventajas que mencionas.

2) Rasgos/patrón de pastel. Factible, pero caro (no hay intercambio) y un poco feo.

3) Un nuevo tipo de árbol en cada fase. De alguna manera esto es teóricamente más limpio. Cada fase puede tratar solo con una estructura producida por la fase anterior. Además, el mismo enfoque lleva todo el camino desde el frente hasta el final. Por ejemplo, puedes "desugar" en algún momento y tener un nuevo tipo de árbol significa que las fases aguas abajo no tienen que siquiera considerar la posibilidad de tipos de nodos que se eliminan mediante el desalado. Además, las optimizaciones de bajo nivel generalmente necesitan IR que sean significativamente más bajos que el AST original. Pero también es un montón de código, ya que casi todo tiene que volver a crearse en cada paso. Este enfoque también puede ser lento ya que casi no puede haber datos compartidos entre fases.

4) Etiquete cada nodo en el AST con un ID y use ese ID para referenciar información en otras estructuras de datos (mapas y vectores y similares) que contienen información calculada para cada fase. En muchos sentidos, este es mi favorito. Conserva la inmutabilidad, maximiza el uso compartido y minimiza el código "excedente" que tiene que escribir. Pero aún tiene que lidiar con el potencial de la información "perdida" que puede ser difícil de depurar. Tampoco es tan rápido como la opción mutable, aunque es más rápido que cualquier opción que requiera producir un nuevo árbol en cada fase.