Obtener gráfico de flujo de control del árbol de sintaxis abstracta

Question

tengo un AST derivado del Analizador generador antlr 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 en 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. Cheers, Chris

---

EDITAR - Mi principal preocupación es conseguir un gráfico de flujo de control (CFG) de la 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.

Answer 1

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

Desde sus idiomas de origen y destino son los mismos, no hay paso de generación de código - que ya está! 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.

Primera asociado con cada declaración java un nodo en el CFG, junto con un nodo de entrada y salida.En una primera aproximación, recorrer el árbol y:

1. si la instrucción actual es una llamada a un método, averiguar dónde está el nodo de entrada es para el cuerpo correspondiente de esa llamada a un método, y crea un borde que apunta desde el estado de cuenta actual a ese 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.
2. para cada declaración no saltar, hacer un borde entre éste y el próximo estado de cuenta.

Esto le 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.

¿Tiene esto sentido?

Answer 2

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

Answer 3

Cuando he hecho esto en el pasado, solía graphviz, en particular, la herramienta de punto, 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 del gráfico 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.

Answer 4

Sobre la base de algunos comentarios, parece que el PO realmente quiere hacer code generation - para convertir la AST en una secuencia de nivel inferior de instrucciones basadas en bloques básicos y puntos de salto.

La generación de código es muy específicos del lenguaje, y una gran cantidad de trabajo se ha puesto en este tema. Antes de generar el código, debe conocer el 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 lenguaje.)

La representación que elija para la generación de código contendrá el gráfico de control-flujo, implícitamente 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 comentar si desea más aclaraciones.)

Answer 5

Producir un diagrama de flujo de control total que realmente tenga en cuenta todos los problemas de lenguaje 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 función (más o menos fácil, pero identificar el objetivo puede ser más difícil), donde las operaciones entre bastidores como pueden ser los inicializadores de clase. y preocuparse por los puntos donde pueden ocurrir excepciones y donde se activa el control si se produce una excepción.

Si examina la mayoría de los idiomas cuidadosamente, también serán claros sobre el orden de evaluación de cálculos en expresiones, y esto importa si tiene dos efectos secundarios en una expresión; el flujo de control debe reflejar el orden (o la no orden, si no se define).

Tal vez sólo quieren una abstracción del control de flujo tener los elementos básicos y las condicionales. Eso es obviamente un poco más fácil.

En cualquiera de los casos (CFG simple o plena CFG), es necesario caminar por la AST, en cada punto de tener una referencia a posibles objetivos de control de flujo (por ejemplo, para la mayoría de los casos, tales como IF, hay dos objetivos de flujo: las cláusulas THEN y ELSE). En cada nodo, enlace ese nodo a la meta de flujo de control apropiado , la posibilidad de sustituir el flujo se dirige (por ejemplo, cuando se encuentra con un IF).

Hacer esto para la semántica de lenguaje completo de Java (o C) es bastante mucho trabajo. Quizás desee simplemente usar una herramienta que calcule este comercial. Ver http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html por lo que esto realmente se parece, que sale de nuestras herramientas.