java - sintactico - Obtener el gráfico de flujo de control del árbol de sintaxis abstracto

arbol sintactico java (5)

Tengo un AST derivado del ANTLR Parser Generator para Java. Lo que quiero hacer es de alguna manera construir un flujograma de control del código fuente, donde cada enunciado o expresión es un Nodo único. Entiendo que debe haber cierta recursividad para esta identificación, me preguntaba qué sugeriría usted como la mejor opción y si ANTLR tiene un conjunto de herramientas que pueda usar para este trabajo. Saludos, Chris

EDITAR - Mi principal preocupación es obtener un gráfico de flujo de control (CFG) del AST. De esta forma puedo obtener una representación en árbol de la fuente. Para aclarar, tanto el código fuente como el lenguaje de implementación son Java.

Producir un diagrama de flujo de control completo que realmente tenga en cuenta todos los problemas de idioma es más difícil de lo que parece. No solo debe identificar lo que parecen ser los "bloques básicos", sino que debe identificar las llamadas a las funciones (algo fácil, pero identificar el objetivo podría ser más difícil), donde las operaciones entre bastidores, como los inicializadores de clase, pueden ocurrir. y preocuparse por los puntos en los que pueden producirse excepciones y donde se aplica el control si se produce una excepción.

Si examina la mayoría de los lenguajes con cuidado, también tendrá en claro el orden de la evaluación de los cómputos en las expresiones, y esto importa si tiene dos efectos secundarios en una expresión; el flujo de control debe reflejar el orden (o el no orden, si no está definido).

Tal vez solo desee una abstracción del flujo de control que tenga los bloques básicos y los condicionales. Eso es obviamente un poco más fácil.

En cualquier caso (CFG simple o CFG completo), debe recorrer el AST, en cada punto tener una referencia a posibles objetivos de flujo de control (por ejemplo, para la mayoría de los casos, como las declaraciones IF, hay dos objetivos de flujo: THEN y Cláusulas ELSE). En cada nodo, vincule ese nodo al objetivo de flujo de control apropiado, posiblemente reemplazando los objetivos de flujo (por ejemplo, cuando encuentre un IF).

Hacer esto para la semántica de lenguaje completo de Java (o C) es bastante trabajo. Puede usar simplemente una herramienta que lo calcule de manera estándar. Consulte http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html para saber cómo se ve realmente, saliendo de nuestras herramientas.

¿Alguna vez probaste ANTLR Studio ? No genera el gráfico AST del agujero, pero para su revisión, ya es bastante útil.

Cuando hice esto en el pasado, utilicé graphviz , en particular la herramienta de puntos, para generar el gráfico. Creé el archivo de entrada de puntos al atravesar el gráfico de flujo de control en tiempo de compilación.

El diseño de gráficos es un problema difícil , y graphviz hace un excelente trabajo. Puede generar ps, pdf y varios formatos de imagen, y el diseño suele ser bastante intuitivo. Lo recomiendo altamente.

Por lo general, los CFG se calculan en una representación de nivel inferior (por ejemplo, código de byte JVM). Alguien hizo una tesis sobre tales cosas hace unos años. Podría haber una manera útil de describir cómo llegar a esa representación.

Dado que los idiomas de origen y destino son los mismos, no hay paso de generación de código: ¡ya ha terminado! Sin embargo, ahora puedes caminar el AST. En cada nodo del AST, debes preguntarte: ¿es esto una instrucción de "saltos" o no? Las llamadas a métodos y las sentencias if son ejemplos de instrucciones de salto. También lo son las construcciones de bucle (como for y while ). Las instrucciones tales como la suma y la multiplicación no son saltantes.

Primero asocie con cada instrucción java un nodo en el CFG, junto con un nodo de entrada y salida. Como primera aproximación, camine el árbol y:

si el enunciado actual es una llamada a método, averigüe dónde está el nodo de entrada para el cuerpo correspondiente de esa llamada al método, y haga un borde apuntando desde el enunciado actual al nodo de entrada. si la instrucción es un retorno de método, enumere los lugares que podrían haberlo llamado y añada una ventaja a esos.
para cada declaración que no salta, establezca una ventaja entre esta y la siguiente declaración.

Esto te dará algún tipo de CFG. El procedimiento es un poco peludo en el paso 2 porque el método llamado puede declararse en una biblioteca, y no en otro lugar en el AST; si es así, o bien no hace un borde o hace un borde a un nodo especial que representa la entrada a ese método de biblioteca.

¿Esto tiene sentido?

Según algunos comentarios, parece que el OP realmente quiere generar código : convertir el AST en una secuencia de instrucciones de nivel inferior basada en bloques básicos y puntos de salto.

La generación de código es muy específica del idioma, y se ha dedicado mucho trabajo a este tema. Antes de generar código, debe conocer su idioma de destino , ya sea ensamblador o simplemente otro lenguaje de alto nivel. Una vez que haya identificado esto, simplemente necesita recorrer el AST y generar una secuencia de instrucciones que implemente el código en el AST. (Digo que esto es simple, pero puede ser difícil, es difícil generalizar porque las consideraciones aquí son bastante específicas del idioma).

La representación que elija para la generación de código contendrá el gráfico de control-flujo, implícita o explícitamente. Si el idioma de destino es bastante bajo (cerca del ensamblador), entonces el gráfico de flujo de control debería ser relativamente fácil de extraer.

(Por favor, coméntenos si desea más aclaraciones).