php - ast - abstract syntax trees

Compilando un AST de vuelta 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 mi pregunta anterior . El analizador funciona bastante bien.

Ahora, obviamente, un analizador en sí mismo 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, hay dos posibilidades que veo:

1. Compila el código usando algún esquema predefinido
2. Mantenga el formato del código original y aplique 1. solo en los Nodos que fueron modificados.

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

Pero no estoy seguro de qué patrón de diseño se puede usar para compilar el código. La manera más fácil de implementar esto es agregar un método de ->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 algún NodeTraverser que itera recursivamente sobre todos los Nodos y llama a un método de ->visit de un Visitor . Esto suena muy prometedor para la manipulación de nodos, donde el método Visitor->visit podría simplemente cambiar el Node 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 la forma en que 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).

Hacer una buena impresión requiere generalmente 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 lleva a cabo la impresión genérica 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 crear un bloque de instrucciones, puede 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 esto escupe texto sobre la marcha al visitar el árbol.

Hay una serie de detalles que necesita para administrar:

• Para nodos AST que representan literales, debe regenerar el valor literal. Esto es más difícil de lo que parece si quieres que la respuesta sea precisa. Imprimir números en coma flotante sin perder precisión es mucho 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 concatena los fragmentos de cadena, permitiendo que las transformaciones se apliquen dentro de la cadena "literal").

• Espaciado: algunos idiomas requieren espacios en blanco en lugares críticos. Los tokens ABC17 42 no se imprimen mejor 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.

• Newlines: los lenguajes que permiten espacios en blanco arbitrarios pueden regenerarse técnicamente como una sola línea de texto. La gente odia esto, incluso si vas a compilar el resultado; a veces hay que mirar el código generado y esto lo hace 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 fuente que normalmente no se cree que almacene Para literales, puede que tenga que regenerar la raíz del 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 la cadena deben escaparse. Algunos idiomas permiten palabras clave en mayúscula o minúscula ( 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 hacerlo debe almacenar en la información del número de columna para tokens concretos, y tener reglas de impresión sobre cuándo usar esa columna- numerar los datos para colocar el 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) rechazan 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 reiniciación. 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, a partir de la impresión de fidelidad cuyo propósito es regenerar el texto para que coincida con la fuente original en la mayor medida posible. 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 todos los lenguajes de programación basados ​​en texto se representan muy bien en términos de bloques rectangulares de texto. (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 (apilar cajas una encima de la otra, esto en efecto reemplaza las líneas nuevas de impresión), Sangría (Composición horizontal con una caja de espacios en blanco), etc. Luego puede construir su impresora bonita construyendo y componiendo 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 kit de herramientas de reingeniería de software DMS utiliza este enfoque para imprimir prácticamente todos los idiomas que puede analizar (incluidos PHP, Java, C #, etc.). En lugar de adjuntar los cómputos de caja a los nodos AST a través de los visitantes, adjuntamos los cómputos de caja en una notación de cuadro de texto específica del dominio

• H (...) para cajas horizontales
• V (....) para cajas verticales
• Yo (...) para cajas con sangría)

directamente a las reglas de la gramática, lo que nos permite expresar de forma sucinta la gramática (analizador) y la impresora bonita ("antipasesador") en un solo 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 de DMS:

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

Puede ver un ejemplo más amplio de cómo se hace esto para el lenguaje de programación Oberon de Wirth PrettyPrinter, que muestra cómo se combinan las reglas gramaticales y las reglas de impresión genérica . El PHP Front End se ve así, pero es mucho más grande, obviamente.

Una forma más compleja de realizar impresiones bonitas es construir un traductor dirigido por sintaxis (es decir, recorrer el árbol y construir texto u otras estructuras de datos en orden de á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. Vea este documento técnico: Pretty-printing para reingeniería de software

Un punto adicional: por supuesto, puedes construir toda esta maquinaria tú 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 tiene ambos integrados.]