Cuándo usar un árbol de sintaxis abstracto o concreto?

Question

He estado investigando sobre compiladores. El lexer parece ser muy sencillo: tomar una "oración" y dividirla en palabras (o tokens). Para garantizar la gramática correcta, se necesita un analizador. El analizador generalmente toma los tokens y crea un árbol que da como resultado un nodo raíz (palabras en oraciones, párrafos, páginas, etc.).

De this question parece que un analizador construiría un AST. El AST solo contiene lo que es necesario para ejecutar el código, por lo que cosas como paréntesis no serían necesarias ya que la precedencia del operador está integrada en un AST. Un AST es probablemente todo lo que necesita un compilador.

Pero, ¿qué hay de convertir el código de un idioma a otro? ¿Tomar un lenguaje inventado (gramática) o una gramática existente y convertirla en otra donde las reglas de precedencia del operador pueden ser diferentes o no? ¿La precedencia del operador también está "incorporada" a CST?

Como ejemplo digamos que inventé un idioma y quería traducirlo a código PHP. El operador ternario en la mayoría de los idiomas tiene una asociatividad de derecha a izquierda. PHP usa incorrectamente la asociatividad de izquierda a derecha (see more about this here). Quiero que "mi idioma" se use de derecha a izquierda, pero el código PHP resultante debe aplicar paréntesis para obtener el resultado correcto en PHP (con el link to Wikipedia, el resultado debe ser "train" en lugar de "horse").

Entonces, ¿para la traducción de idiomas sería mejor un CST? ¿La precedencia del operador generalmente está integrada en un CST? ¿Hay algo intermedio? ¿Hay algún ejemplo que compare ambos árboles con una ecuación de álgebra simple? ¿Algún ejemplo que ilustra un operador ternario?

(Is "transcodificación" el término correcto para "traducción lenguaje de programación" Una búsqueda en Google nos lleva a la conversión de los medios de comunicación?.)

Lo que estoy tratando de averiguar es: ¿Cuándo es más apropiado utilizar una sobre el otro?

Answer 1

Un AST que modele todos los detalles semánticos del idioma de origen es todo lo que necesita. Por definición, si modela la semántica correctamente, y su lenguaje incluye un operador ternario, modelará correctamente el orden específico en el que se aplican los operadores (por ejemplo, los resultados del módulo de predecesores anula, por ejemplo, entre paréntesis).

Así que su problema no está en el AST. Está generando a otro idioma usando operadores similares (ternarios) cuya precedencia es diferente.

Este es un problema ancestral en la generación de código: los operadores del objetivo no coinciden del todo con los operadores de la fuente, por lo que la salida no puede ser uno a uno. En su caso, debería ser capaz de resolver el problema generando operadores ternarios de PHP con paréntesis a su alrededor para controlar el orden y lograr la semántica original, por lo que este no es un gran problema.

En general, generar secuencias de código que logren un resultado deseado puede ser bastante complicado, y hay muchas maneras de hacerlo. Es por eso que los libros de compilación son gruesos en lugar de delgados. Parece que se ha establecido implícitamente en "obtener AST, caminar AST, escupir código"; esto es casi un generador de código sobre la marcha. Y esto funciona adecuadamente si no te importa si el código generado es particularmente bueno, y el idioma de destino es bastante cercano al idioma de origen.

Si el problema de generación de código es más complejo, lo que normalmente ocurre es que el AST se utiliza para generar lo que equivale a un modelo de flujo de datos del cómputo, compuesto por operadores que producen resultados y consumen resultados de operadores anteriores. en "operadores" que captan valores variables y constantes.Luego, la representación del flujo de datos se atraviesa para generar el código; esto tiene la ventaja de que puede elegir un operador en la representación de flujo de datos, encontrar una secuencia de código coincidente en el idioma de destino, generar eso y luego preocuparse por cómo se recopilan los operandos. Mejores esquemas coinciden con los subgrafos de flujo de datos (que representan construcciones equivalentes del lenguaje objetivo compuesto) al gráfico de flujo de datos producido; esto puede producir un código significativamente mejor. A menudo, uno puede aplicar optimizaciones específicas del idioma objetivo después de la generación de código sin procesar para producir un código aún mejor. En ambos casos, debe preocuparse por administrar los resultados del operador; ¿se pueden alimentar directamente al siguiente operador de idioma de destino, o deben entrar en algún tipo de almacenamiento temporal (para el código de máquina, este puede ser otro registro o una ubicación de memoria). Hacer todo esto no es fácil; nuevamente, es por eso que los libros de compilación no son delgados.

Una variación de esta idea son las transformaciones del programa fuente-fuente. Este mapa construye en código fuente "directamente" a las construcciones en el código objetivo, aunque esto generalmente se hace detrás de las escenas al operar en AST porque el texto del lenguaje de programación no analizado es difícil de igualar. Nuestro DMS Software Reengineering Toolkit es un ejemplo de este tipo de sistema. Con una herramienta de este tipo, se escriben patrones en el idioma de origen (que coinciden implícitamente con un árbol de análisis sintáctico) y patrones correspondientes en el lenguaje de destino (que produce implícitamente AST en el idioma de destino). Puede escribir construcciones de origen o de destino complejas dando mucho del efecto de la coincidencia de gráfico de flujo de datos anterior. La optimización posterior a la generación consiste en más reglas de reescritura que transforman el código objetivo en código objetivo.

Conclusión: Tener un AST no es suficiente a menos que su traducción sea realmente trivial. Puede obtener más información acerca de lo que necesita en esta respuesta SO: https://stackoverflow.com/a/3460977/120163

ADVERTENCIA: Continúa la opinión.

Re "Transcodificador": prefiero el compilador de "compilación", "traducción" o "fuente a fuente". He estado desarrollando herramientas de análisis y manipulación de programas durante casi 40 años. Nunca había escuchado el término "transcodificador" hasta que encontré esta pregunta SO: Experience migrating legacy Cobol/PL1 to Java y una respuesta que describía en mi humilde opinión un esquema de traducción de código realmente horrible llamado NACA. He oído desde que este término está ganando tracción; No veo por qué tuvimos que inventar otro término cuando tenemos los perfectamente adecuados. Por lo general, este es un signo de alguien inventando un sumo sacerdocio; "inventemos un nuevo término brillante para que la gente realmente no entienda lo que estamos haciendo". Me complace dejar ese término para traducciones tan horribles.