Compilación de un AST de nuevo al código fuente

Question

Actualmente estoy en el proceso de construir un analizador de PHP escrito en PHP, ya que ningún analizador existente apareció en my previous question. El parser itself funciona bastante bien.

Ahora, obviamente, un analizador por sí solo no sirve de mucho (aparte del análisis estático). Me gustaría aplicar transformaciones al AST y luego compilar de nuevo al código fuente. Aplicar las transformaciones no es un gran problema, un patrón de Visitante normal debería hacer.

Cuál es mi problema actualmente, es cómo compilar el AST de nuevo a la fuente. Básicamente, existen dos posibilidades: que veo

1. compilar el código con algún esquema predefinido
2. Mantener el formato del código original y aplicar sólo en 1. Los nodos que se han cambiado.

Por ahora me gustaría concentrarse en 1. 2. como parece bastante difícil de lograr (pero si tienes consejos referentes a eso, me gustaría escucharlos).

Pero no estoy muy seguro de qué patrón de diseño se puede utilizar para compilar el código. La forma más fácil de implementar esto es agregar un método ->compile a todos los Nodos. El inconveniente que veo aquí es que sería bastante difícil cambiar el formato de la salida generada. Uno necesitaría cambiar los Nodos para hacer eso. Por lo tanto, estoy buscando una solución diferente.

He oído que el patrón Visitor también se puede usar para esto, pero realmente no puedo imaginar cómo se supone que funciona. Según entiendo el patrón de visitante, tiene NodeTraverser que itera recursivamente sobre todos los Nodos y llama al método ->visit de Visitor. Esto suena bastante prometedor para la manipulación de nodos, donde el método Visitor->visit podría simplemente cambiar el Nodo que se pasó, pero no sé cómo se puede usar para la compilación. Una idea obvia sería iterar el árbol de nodos de las hojas a la raíz y reemplazar los nodos visitados por el código fuente. Pero esto de alguna manera no parece una solución muy limpia?

Answer 1

El problema de convertir un AST de nuevo en código fuente generalmente se llama "impresión bonita". Hay dos variaciones sutiles: regenerar el texto que coincide con el original tanto como sea posible (lo llamo "impresión de fidelidad"), y (bonito) de impresión bonita, que genera texto muy bien formateado. Y cómo se imprime importa dependiendo de si los codificadores trabajarán en el código regenerado (a menudo quieren la impresión de fidelidad) o su única intención es compilarlo (en este punto cualquier impresión legal válida está bien).

Para hacer una buena impresión, por lo general, se requiere más información de la que recaba un analizador clásico, agravada por el hecho de que la mayoría de los generadores de analizadores no admiten esta recopilación de información adicional. Llamo a analizadores que recopilan información suficiente para hacer esto bien "analizadores de reingeniería". Más detalles a continuación.

La forma fundamental en que se realiza la impresión bonita es caminando por el AST ("Patrón de visitante" como lo indica), y generando texto basado en el contenido del nodo AST. El truco básico es: llamar a los nodos hijos de izquierda a derecha (asumiendo que es el orden del texto original) para generar el texto que representan, intercalando texto adicional según corresponda para este tipo de nodo AST. Para prettyprint un bloque de instrucciones que podría tener el siguiente psuedocode:

PrettyPrintBlock: 
    Print("{"}; PrintNewline(); 
    Call PrettyPrint(Node.children[1]); // prints out statements in block 
    Print("}"); PrintNewline(); 
    return; 


PrettyPrintStatements: 
    do i=1,number_of_children 
     Call PrettyPrint(Node.children[i]); Print(";"); PrintNewline(); // print one statement 
    endo 
    return; 

Tenga en cuenta que este escupe texto sobre la marcha mientras visita el árbol.

Hay una serie de detalles que necesita para gestionar:

• Para nodos que representan AST literales, tiene que regenerar el valor literal. Esto es más difícil de lo que parece si quieres que la respuesta sea precisa. Imprimir números de punto flotante sin perder ninguna precisión es lote más difícil de lo que parece (los científicos lo odian cuando se daña el valor de Pi). Para los literales de cadena, debe regenerar las comillas y el contenido literal de la cadena; debes tener cuidado de regenerar las secuencias de escape para los personajes que tienen que escapar. Los literales de cadenas doblemente citadas en PHP pueden ser un poco más difíciles, ya que no están representados por tokens individuales en el AST. (Nuestro PHP Front End (un analizador de reingeniería/prettyprinter los representa esencialmente como una expresión que une los fragmentos de cadena, lo que permite transformaciones que deben aplicarse dentro de la cadena "literal")

• y distancia entre ejes. Algunos idiomas requieren espacios en blanco en los lugares críticos El. tokens ABC17 42 no se imprime como ABC1742, pero está bien que los tokens (ABC17) se impriman como (ABC17). Una forma de resolver este problema es poner un espacio donde sea legal, pero a la gente no le gustará. el resultado: demasiado espacio en blanco. No es un problema si solo está compilando el resultado.

• Líneas nuevas: los lenguajes que permiten espacios en blanco arbitrarios pueden regenerarse técnicamente como una sola línea de texto. f va a compilar el resultado; A veces, tiene para ver el código generado y esto hace que sea imposible. Por lo tanto, necesita una forma de introducir nuevas líneas para los nodos AST que representan los principales elementos del lenguaje (sentencias, bloques, métodos, clases, etc.). Esto no suele ser difícil; cuando visite un nodo que represente tal construcción, imprima la construcción y agregue una nueva línea.

• Descubrirá, si desea que los usuarios acepten su resultado, que deberá conservar algunas propiedades del texto de origen que normalmente no almacenaría Para literales, puede que tenga que regenerar la raíz de lo literal; los codificadores que hayan ingresado un número como un literal hexadecimal no estarán contentos cuando regenere el equivalente decimal, aunque signifique exactamente lo mismo. Del mismo modo, las cadenas deben tener las comillas "originales"; la mayoría de los lenguajes permiten "o" como caracteres de comillas y las personas quieren lo que usaron originalmente. Para PHP, que utiliza las materias y determina qué caracteres del literal de cadena deben ser escapados. Algunos idiomas permiten palabras clave mayúsculas o minúsculas (o incluso abreviaturas), y los nombres de variables en mayúscula y minúscula significan la misma variable; de ​​nuevo, los autores originales normalmente quieren recuperar su envoltura original. PHP tiene caracteres divertidos en diferentes tipos de identificadores (por ejemplo, "$") pero descubrirá que no siempre está ahí (vea $ variables en cadenas literales). A menudo la gente quiere su formato de diseño original, para ello debe almacenar información de número de columna para tokens concretos, y tiene reglas de impresión sobre cuándo usar esa columna -número de datos para colocar texto muy impreso donde esté en la misma columna cuando sea posible, y qué hacer si la línea impresa hasta el momento se llena más allá de esa columna.

• Comentarios: la mayoría de los analizadores estándar (incluido el que implementó usando el analizador Zend, estoy bastante seguro) descartan los comentarios por completo. Nuevamente, la gente lo odia y rechazará una respuesta impresa en la que se pierden los comentarios. Esta es la razón principal por la que algunos ilustradores intentan regenerar el código utilizando el texto original (el otro es copiar el diseño del código original para la impresión de fidelidad, si no capturó la información del número de columna). En mi humilde opinión, el truco correcto es capturar los comentarios en el AST, de modo que las transformaciones de AST puedan inspeccionar/generar comentarios también, pero todos hacen su propia elección de diseño.

Toda esta información "extra" es recopilada por un buen analizador de reinicio. Los analizadores convencionales generalmente no recopilan nada, lo que dificulta la impresión de AST aceptables.

Un enfoque más basado en principios distingue a las impresiones bonitas cuyo propósito es el buen formato, desde la impresión de fidelidad cuyo propósito es regenerar el texto para que coincida con la fuente original en una extensión máxima. Debería quedar claro que a nivel de los terminales, usted quiere prácticamente la impresión de fidelidad. Dependiendo de su propósito, puede imprimir bastante con un buen formato o impresión de fidelidad. Una estrategia que usamos es establecer de forma predeterminada la impresión de fidelidad cuando el AST no se ha modificado, y la impresión bonita donde se encuentra (porque a menudo el mecanismo de cambio no tiene ninguna información sobre números de columna o radix de números, etc.). Las transformaciones sellan los nodos AST que se generan recientemente como "sin datos de fidelidad presentes".

Un enfoque organizado para la buena impresión es comprender que prácticamente todo el lenguaje de programación basado en texto se procesa bien en términos de bloques de texto rectangulares. (El generador de documentos TeX de Knuth también tiene esta idea). Si tiene un conjunto de cuadros de texto que representan partes del código regenerado (por ejemplo, cuadros primitivos generados directamente para los tokens de terminal), entonces puede imaginar operadores para componer esos cuadros: Composición horizontal (apilar un cuadro a la derecha de otro), Vertical (cajas de pila en la parte superior de uno al otro, lo que, en efecto, sustituye a las nuevas líneas de impresión), guión (composición horizontal con una caja de espacios en blanco), etc a continuación, puede construir su prettyprinter mediante la construcción y la composición de los cuadros de texto:

PrettyPrintBlock: 
    Box1=PrimitiveBox("{"); Box2=PrimitiveBox("}"); 
    ChildBox=PrettyPrint(Node.children[1]); // gets box for statements in block 
    ResultBox=VerticalBox(Box1,Indent(3,ChildBox),Box2); 
    return ResultBox; 

PrettyPrintStatements: 
    ResultBox=EmptyBox(); 
    do i=1,number_of_children 
     ResultBox=VerticalBox(ResultBox,HorizontalBox(PrettyPrint(Node.children[i]); PrimitiveBox(";") 
    endo 
    return; 

El valor real en esto es que cualquier nodo puede componer los cuadros de texto producidos por sus hijos en orden arbitrario con texto intermedio arbitrario. Puede reorganizar grandes bloques de texto de esta manera (imagine VBox'ing los métodos de clase en orden de nombre de método). No se escuchan textos como se encuentran; solo cuando se alcanza la raíz, o algún nodo AST donde se sabe que todos los cuadros secundarios se han generado correctamente.

Nuestro DMS Software Reengineering Toolkit utiliza este enfoque para imprimir bastante todos los idiomas que puede analizar (incluidos PHP, Java, C#, etc.). En lugar de unir los cálculos fallado nodos AST a través de los visitantes, adjuntamos los cálculos de la caja en una notación texto-box-dominio específico

• H (...) para cajas horizontales
• V (....) para cajas verticales
• I (...) para cajas corrugadas)

directamente a las reglas de la gramática, lo que nos permite expresar de manera sucinta la gramática (analizador) y el prettyprinter ("anti-parser") en un lugar. Las reglas de la caja bonita son compiladas automáticamente por DMS en un visitante. La maquinaria de impresión bonita tiene que ser lo suficientemente inteligente como para entender cómo los comentarios juegan en esto, y eso es francamente un poco arcano, pero solo tienes que hacerlo una vez. Un ejemplo DMS:

block = '{' statements '}' ; -- grammar rule to recognize block of statements 
<<PrettyPrinter>>: { V('{',I(statements),'}'); }; 

Se puede ver un ejemplo más de cómo se hace esto para Wirth's Oberon programming language PrettyPrinter que muestra cómo se combinan las reglas gramaticales y reglas prettyPrinting. El PHP Front End se ve así, pero es mucho más grande, obviamente.

Una forma más compleja que hacer prettyPrinting es la construcción de un traductor dirigido por la sintaxis (medios, pie del árbol y construir el texto u otras estructuras de datos con el fin visted-árbol) para producir cuadros de texto en un cuadro de texto especial AST.El cuadro de texto AST está muy bien impreso por otra caminata de árbol, pero las acciones son básicamente triviales: imprima los cuadros de texto. Consulte este documento técnico: Pretty-printing for software reengineering

Un punto adicional: por supuesto, puede construir toda esta maquinaria usted mismo. Pero la misma razón por la que elige usar un generador de analizador (es mucho trabajo hacer una, y ese trabajo no contribuye a su objetivo de una manera interesante) es la misma razón por la que desea elegir un generador de estante generador de foto bonita. Hay muchos generadores analizadores alrededor. No hay muchos generadores de bonita impresora. [DMS es uno de los pocos que ha incorporado tanto en.]