Obtener el Control de flujo gráfico de Árbol de Sintaxis Abstracta

Question

Tengo un AST derivados de la ANTLR Parser Generator para Java.Lo que quiero hacer es de alguna manera la construcción de un control gráfico de flujo del código fuente, donde cada declaración o expresión es un Nodo único.Entiendo que debe ser algo de la recursividad a esta identificación, me preguntaba lo que podría sugerir, como la mejor opción y si ANTLR tiene un conjunto de herramientas que puedo utilizar para este trabajo.Saludos, Chris

---

EDITAR - Mi principal preocupación es conseguir un flujo de control gráfico(CFG) de la AST.De esta forma, se puede obtener una representación del árbol de la fuente.Para aclarar, tanto el código fuente y la aplicación del lenguaje Java.

Answer 1

Generalmente CFGs están calculadas en un menor nivel de representación (por ejemplo,JVM bytecode).Alguien lo hizo una tesis sobre este tipo de cosas hace un par de años.Podría ser una manera útil, se describe allí para llegar a esa representación.

Desde sus idiomas de origen y destino son el mismo, no hay generación de código, paso a paso, ya está hecho!Sin embargo, ahora se llega a pie en el AST.En cada nodo del AST, usted tiene que preguntarse a sí mismo:es este un "salto" de la instrucción o no?Las llamadas de método y si las declaraciones son ejemplos de instrucciones de salto.Así son construcciones de bucle (como for y while).Instrucciones tales como la adición y la multiplicación son de no saltar.

Primer asociado con cada java declaración de un nodo en la CFG, junto con una entrada y salida del nodo.Como una primera aproximación, a pie de un árbol y:

1. si la instrucción es una llamada de método, averiguar dónde está el nodo de entrada es por el organismo correspondiente de la llamada al método, y hacer un borde que apunta desde el estado de cuenta actual para que el nodo de entrada.si la declaración es un método de devolución, enumerar los lugares en los que podría haber llamado y añadir un borde a aquellos.
2. para cada uno de los saltos de instrucción, hacer un borde entre ella y la siguiente instrucción.

Esto le dará a usted algún tipo de CFG.El procedimiento es ligeramente peludo en el paso 2, ya que el método de la llama puede ser declarado en una biblioteca, y no en otra parte, en el AST -- si es así, no hacer un borde o hacer un borde a un nodo especial que representa la entrada a ese método de la biblioteca.

¿Esto tiene sentido?

Answer 2

La producción de un completo control de flujo gráfico que realmente toma en cuenta todos los idiomas problemas es más difícil de lo que parece.No sólo usted tiene que identificar lo que parece ser que el "básicos", pero usted tiene que identificar la función de llamadas (una especie de fácil, pero la identificación de la objetivo podría ser más difícil), donde detrás de las escenas de las operaciones, tales como la clase inicializadores puede suceder.y preocuparse de los puntos en que las excepciones pueden ocurrir y cuando el control pasa si aparece una excepción.

Si usted examina la mayoría de los idiomas cuidadosamente, también serán claro en cuanto a la ordenación de la evaluación de los cálculos en expresiones, y esto es importante, si usted 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 usted sólo quiere una abstracción del control de flujo tener los bloques básicos y condicionales.Que obviamente es un poco más fácil.

En cualquiera de los casos (simple CFG o completo CFG), usted necesita para caminar la AST, en cada punto de tener una referencia a la posible controlar el flujo de los objetivos de (por ejemplo, para la mayoría de los casos, como en el CASO de las declaraciones, hay dos de flujo objetivos:las cláusulas then y ELSE).En cada nodo, el nodo de enlace que a la adecuado flujo de control de destino, posiblemente sustituyendo el flujo de objetivos (por ejemplo, cuando usted se encuentre con un SI).

Para hacer esto para el lenguaje pleno de la semántica de Java (o C) es bastante un montón de trabajo.Puede que desee utilizar simplemente una herramienta que calcula esta off-the-shelf.Ver http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html por lo que esto realmente es así, saliendo de nuestras herramientas.

Answer 3

Basado en algunos de los comentarios, parece que el OP realmente quiere hacer la generación de código -- para convertir el AST en un nivel inferior de la secuencia de instrucciones basado en bloques básicos y puntos de salto.

La generación de código es muy específico del lenguaje, y una gran cantidad de trabajo se ha puesto en este tema.Antes de realizar la generación de código que usted necesita saber su idioma de destino -- ya sea ensamblador o simplemente algún otro lenguaje de alto nivel.Una vez identificado esto, usted necesita simplemente caminar por la AST y generar una secuencia de instrucciones que ejecuta el código en el AST.(Digo esto es simple, pero puede ser difícil ... es difícil generalizar, porque las consideraciones que aquí son bastante específicos del idioma.)

La representación que usted elija para la generación de código va a contener el flujo de control del gráfico, de forma implícita o explícita.Si su idioma de destino es bastante baja (cerca de ensamblador), entonces el flujo de control del gráfico debe ser relativamente fácil de extraer.

(Por favor comente si quieres más aclaraciones.)

Answer 4

¿Alguna vez has probado ANTLR Studio?No se genera el agujero AST gráfico, pero para su revisión, su ya de por sí bastante útil.

Answer 5

Cuando he hecho esto en el pasado, he usado graphviz, en particular, el punto de la herramienta, para generar el gráfico.He creado el punto archivo de entrada por la realidad que atraviesa el flujo de control del gráfico en tiempo de compilación.

El diseño gráfico es una el problema difícil, y graphviz hace un trabajo excelente.Se puede dar salida a ps, pdf, y varios formatos de imagen, y el diseño es por lo general bastante intuitivo a la vista.Lo recomiendo altamente.

Answer 6

Creo que no voy a ser capaz de responder a su pregunta de una manera que tal vez estén buscando ya que no sé de alguna manera en ANTLR para producir una CFG con o sin un AST.Pero, en definitiva usaría lo que ANTLR produce a generar por separado un programa en Java para producir una CFG.Usted podría utilizar la ANTLR generado árbol de sintaxis como de entrada para generar su CFG por separado, en un programa de Java de su propia creación.En este punto son, en esencia, la construcción de un compilador.La diferencia entre el "compilador" y una JVM es que su salida es una representación visual (CFG) de cómo un programa de ramas y de sus diversas rutas de ejecución y una JVM/Java compilador genera código para su ejecución en una máquina real (CPU).

Una analogía es que si alguien se sienta a escribir un libro (en inglés, por ejemplo), las palabras individuales se usa en oraciones son los símbolos de un lenguaje de computadora, las oraciones se forman de una manera similar que el contexto gramáticas libres de expresar válido código de computadora, y párrafos enteros y novelas de contar una historia en una manera similar que el análisis semántico/compiladores/CFGs podría producir/representar lógicamente válido programas que realmente hacer algo útil y son más o menos libre de errores de lógica.En otras palabras, una vez que usted consiga más allá de la cuestión de la validez de la sintaxis (la forma correcta estructura de la oración), cualquier persona puede escribir un montón de frases en una página, pero sólo ciertas combinaciones de frases producir un texto que realmente hace algo (contar una historia).

Lo que estamos pidiendo es que la última pieza - cómo ir sobre la toma de un árbol de sintaxis y de la transformación o de la interpretación de lo que el AST en realidad no, lógicamente.Y por supuesto que se necesita para construir un "compilador" para cada idioma que desee hacer esto.Tener una correcta gramática no decirle ¿ un programa no - sólo que un programa es correcto a partir de una gramática de la perspectiva.

Pelusa y la sintaxis de los lápices de colores y los IDEs son todas construido alrededor de la idea de tratar de hacer esta última pieza del rompecabezas una forma más fácil y más eficiente de tareas para los seres humanos.