Zephyr ADSL (de sintaxis abstracta Description Language)

Question

Pregunta:

¿Cuál es el Zephyr ADSL y cómo se relaciona con otras tecnologías como el compilador lexers y generadores de analizadores sintácticos?

(Le agradecería que estuviera razonablemente completo, pero apunte a otras referencias en línea cuando sea más bien técnico, porque la mayoría de lo que sé sobre los compiladores proviene de jugar con yacc y flex, escribir un simple maximizador de munch en C, y mirando hacia arriba y la lectura de material en línea)

pregunta de fondo:

he estado leyendo http://docs.python.org/devguide/compiler.html y me encontré con la siguiente línea:

La especificación de los nodos AST se especifica utilizando el lenguaje de definición de sintaxis abstracta (ASDL) Zephyr .

que siguieron la cita en la parte inferior de encontrar: http://www.cs.princeton.edu/research/techreps/TR-554-97.

Mi primera lectura del artículo ha sido bastante tumultuosa, y esperaba poder entender mejor cuál era el propósito de ASDL (en el contexto del proceso de compilación) antes de volver a intentarlo.

Answer 1

Lexer y Parser generadores aceptar descripciones de lexemas y gramáticas, y generar código que implementan el artefacto correspondiente. Lex requiere una expresión regular para describir tokens. Los generadores de analizadores toman varios tipos de notaciones BNF extendidas.

En el documento se hace referencia es bastante claro en mi humilde opinión: ADSL es un poco de lenguaje para describir de forma abstracta un conjunto de nodo de árbol (sus tipos y firmas). Al usar este lenguaje, uno puede escribir (y los autores del artículo lo hicieron) una herramienta que convierte estas descripciones en el conjunto de tipos de registros que necesitaría para implementar árboles para usar con un analizador. Entonces ADSL es algo así como Regexes y BNF, ya que su propósito es ser alimentado a un generador de código que produce una parte de un compilador.

Una vista expansiva es que los compiladores son una tecnología bastante bien entendida, y que uno debe ser capaz de generar ellos a partir de descripciones de varias piezas. Regex/BNF/ADSL son las claves esenciales para la fase de análisis.

Lo ideal sería disponer de los idiomas de descripción para conjuntos de instrucciones de destino, análisis de flujo, traducciones (mencionó maximal munch) de los árboles abstractos al conjunto de instrucciones de destino y una forma de describir las optimizaciones. Luego, con las herramientas correspondientes para cada pieza, puede compilar todo el compilador a partir de "especificaciones". Hay realmente ha sido mucho trabajo en esta área; las personas han hecho todo esto por separado y juntas. Como era de esperar algo de él proviene del proyecto "Zephyr" antes de Princeton (parece el sitio web Zephyr ahora hay muertos), cuyo objetivo era hacer precisamente este tipo de cosas.

De todos modos intente buscar bajo Google Académico para "generador de compilador".

Answer 2

ADSL se utiliza cuando se necesita para generar un árbol en un módulo de entrada y el mismo árbol en otro módulo (o casi el mismo árbol, de algún modo optimizado).

Para esto, necesita tener funciones de construcción (idealmente con verificador de tipos), función de impresión del árbol de manera que al visualizarlo esté seguro de haberlo generado correctamente.

ASDL toma como entrada un árbol escrito en una sintaxis casi idéntica a la sintaxis del tipo de datos algebraico (como en haskell o ml), o la sintaxis en BNF pero mucho más simplificada, y autogenera todos los contructors, imprimiendo funciones que comienzan con la descripción simple de un árbol.

Por ejemplo, si tiene un lexer, deberá generar lexemas que tengan un tipo. También necesita ver el flujo de salida de lexemas (esto es en forma lineal, por lo que es un árbol muy simple). En lugar de escribir las funciones de impresión, la construcción de lexemas, se les define algo así

lexeme= 
     ID(STRING) 
    | INT(num_integer) 
    | FLOAT(num_float) 
    attributes(int coord_x, int coord_y) 
    num_integer: 
    .... 
    num_float: 
    .... 

y se llama a los constructores de identificación, int, float, etc de su léxico. ASDL convertirá esta sintaxis simple en todas las funciones que necesite, ya sea para construir nodos para AST, o para imprimir, o lo que sea que necesite. ASDL no impone restricciones en el código generado.

Si agrega attributes a un tipo, como las coordenadas de un token, dichos atributos se anexan a los parámetros de cada contructor de ese tipo.

Un árbol más complejo, creado por un programa de análisis se vería que

expr: SUM(expr, expr) 
     |PRODUCT(expr, expr) 
     |number 
number: num_integer 

En este caso asdl comprobará que la llamada de SUMA (_ _) hecha por el analizador pasará a resumir los nodos creados con uno de los constructores de expr. num_integer se define externamente, tal vez por un árbol asdl para el lexer.

Tenga en cuenta que no está permitido definir constructores que contengan expresiones regulares, como number: [0-9]+. ASDL es más simple que EBNF.

Estos constructores se definirán de manera que para construir lo que necesita y más que eso, tipeen check, para asegurarse de que su generador de lexer/analizador/código genere árboles que cumplan con el lenguaje definido por asdl.

Para entender bien ASDL necesita escribir 3-4 analizadores y ver qué es común en el código que generan. Esa parte común es, de hecho, ASDL, por lo que esta es una abstracción para el resultado de los analizadores en particular.