Compilar un AST de vuelta al código fuente

El problema de convertir un AST de nuevo en código fuente generalmente se llama "prettyprinting". Hay dos variaciones sutiles: regenerar el texto que coincida con el original tanto como sea posible (yo llamo a esto "impresión de fidelidad"), y (agradable) prettyprinting, que genera un texto con un formato agradable. Y cómo imprimir importa dependiendo de si los codificadores estarán trabajando en el código regenerado (a menudo quieren impresión de fidelidad) o su único la intención es compilarlo (momento en el que cualquier prettyprinting está bien).

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

La forma fundamental en que se logra la impresión de prettyprint es caminando por el AST ("Patrón de visitante", como lo dices) y generando texto basado en el AST contenido del nodo. El truco básico es: llamar a nodos hijos de izquierda a derecha (suponiendo que ese sea 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 sentencias es posible que tenga 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 mientras visita el árbol.

Hay una serie de detalles que debe administrar:

• Para nodos AST que representan literales, tienes 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 en coma flotante sin perder precisión es un lote más difícil de lo que parece (los científicos 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; debe tener cuidado de regenerar las secuencias de escape para los caracteres que deben escaparse. Literales de cadena doblemente citados en PHP puede ser un poco más difícil, ya que no están representados por fichas individuales en el AST. (Our PHP Front End (a reengineering parser/prettyprinter represents them essentially as an expression that concatenates the string fragments, enabling transformations to be applied inside the string "literal").

• Espaciado: algunos idiomas requieren espacios en blanco en lugares críticos. Es mejor que los tokens ABC17 42 no se impriman como ABC1742, pero está bien que los tokens (ABC17 ) sean impreso 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.

• Nuevas líneas: los lenguajes que permiten espacios en blanco arbitrarios técnicamente se pueden regenerar como una sola línea de texto. La gente odia esto, incluso si va a compilar el resultado; a veces tiene para mirar el código generado y esto lo hace imposible. Así que necesitas una forma de introducir nuevas líneas para nodos AST que representan los principales elementos del lenguaje (sentencias, bloques, métodos, clases, etc.).). Esto no suele ser difícil; al visitar un nodo que representa una construcción de este tipo, imprimir la construcción y añadir una nueva línea.

• Descubrirás, si quieres que los usuarios acepten tu resultado, que tendrás que conservar algunas propiedades del texto fuente que normalmente no pensarías almacenar Para literales, es posible que tenga que regenerar la raíz de la literal; los codificadores que han introducido un número como un literal hexadecimal no están contentos cuando se regenera el equivalente decimal aunque signifique exactamente lo mismo. Del mismo modo, las cadenas tienen que tener las comillas "originales"; la mayoría de los idiomas permiten " o " como caracteres de comillas de cadena y la gente quiere lo que usó originalmente. Para PHP, qué cita se usa importa, y determina qué caracteres en el literal de la cadena debe escaparse. Algunos idiomas permiten palabras clave en mayúsculas o minúsculas (o incluso abreviaturas), y los nombres de las variables mayúsculas y minúsculas que significan la misma variable; de nuevo, los autores originales típicamente quieren que se devuelva su mayúscula original. PHP tiene caracteres divertidos en diferentes tipos de identificadores (por ejemplo,"$"), pero descubrirá que no siempre está allí (vea variables variables en cadenas literales). A menudo, la gente quiere su formato de diseño original; para hacer esto, debe almacenar información en el número de columna para tokens concretos, y tener reglas de impresión prettyprinting sobre cuándo usar eso columna-número de datos para posicionar el texto prettyprinted donde en la misma columna cuando sea posible, y qué hacer si la línea prettyprinted hasta ahora se llena más allá de esa columna.

• Comentarios: La mayoría de los analizadores estándar (incluido el que implementaste usando el analizador de Zend, estoy bastante seguro) desechan los comentarios por completo. Una vez más, la gente odia esto, y rechazará una respuesta prettyprinted en la que los comentarios se pierden. Esta es la razón principal por la que algunos prettyprinters intentan regenerarse código usando el texto original (la otra es copiar el diseño de 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, para que las transformaciones AST también puedan inspeccionar/generar comentarios, pero cada uno hace su propia elección de diseño.

Toda esta información "extra" es recopilada por un buen analizador de reingeniería. Los analizadores convencionales generalmente no recopilan nada de eso, lo que hace que la impresión ASTS aceptable difícil.

Un enfoque más basado en principios distingue la prettyprinting cuyo propósito es un buen formato, 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. Debe quedar claro que en el nivel de los terminales, más o menos desea la impresión de fidelidad. Dependiendo de su propósito, puede imprimir bastante con buen formato, o impresión de fidelidad. Una estrategia que utilizamos es por defecto a la impresión de fidelidad cuando el AST no se ha cambiado, y prettyprinting donde tiene (porque a menudo la maquinaria de cambio no tiene ninguna información sobre números de columna o números radiales, etc.). Las transformaciones sellan los nodos AST que se generan recientemente como "no hay datos de fidelidad presentes".

Un enfoque organizado para prettyprinting nicely es entender que prácticamente todos los lenguajes de programación basados en texto se representan bien en términos de rectangulares bloques de texto. (El generador de documentos TeX de Knuth tiene esta idea, también). Si tiene algún conjunto de cajas de texto que representan piezas del código regenerado (por ejemplo, cajas primitivas generadas directamente para los tokens de terminal), puede imaginar operadores para componer esas cajas: Composición horizontal (apilar una caja a la derecha de otra), Vertical (apilar cajas una encima de la otra; esto en efecto reemplaza la impresión de nuevas líneas), Sangría (Composición horizontal con una caja de espacios en blanco), etc. Entonces usted puede construir su prettyprinter construyendo y componer 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 escupirá ningún texto como encontrado; solo cuando se alcance la raíz, o algún nodo AST donde se sepa que todos los cuadros secundarios se han generado correctamente.

Nuestro Reingeniería de Software DMS Toolkit utiliza este enfoque para imprimir todos los lenguajes que puede analizar (incluyendo PHP, Java, C#, etc.).). En lugar de adjuntar los cálculos de caja a nodos AST a través de visitantes, adjuntamos los cálculos de caja en una notación de caja de texto específica del dominio

• H(...) para cajas Horizontales
• V(....) para cajas verticales
• I(...) para cajas con sangría)

Directamente a las reglas gramaticales, lo que nos permite expresar sucintamente la gramática (analizador) y la prettyprinter ("anti-parser") en un solo lugar. Las reglas de prettyprinter box son compiladas automáticamente por DMS en un visitante. La maquinaria de prettyprinter tiene que ser lo suficientemente inteligente para entender cómo los comentarios juegan en esto, y eso es francamente un poco arcano, pero solo tiene 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 grande de cómo se hace esto para El lenguaje de programación Oberon de Wirth PrettyPrinter mostrando cómo se combinan las reglas gramaticales y las reglas de prettyprinting. El Front-End de PHP se ve así, pero es mucho más grande, obviamente.

Una forma más compleja de hacer prettyprinting es construir un traductor dirigido a la sintaxis (significa, caminar por 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 es entonces prettyprinted por otro paseo del árbol, pero las acciones para él son básicamente triviales: imprima los cuadros de texto. Ver este documento técnico: Pretty-printing for software reingeniería

Un punto adicional: por supuesto, puede ir a construir toda esta maquinaria usted mismo. Pero la misma razón por la que eliges usar un generador de analizador sintáctico (es mucho trabajo hacer uno, y ese trabajo no contribuye a tu objetivo de una manera interesante) es la misma razón por la que quieres elegir un generador de impresoras prettyprinter listo para usar. Hay un montón de generadores de analizador por ahí. No hay muchos generadores de prettyprinter. [DMS es uno de los pocos que tiene ambos incorporados.]