Grafo semántico abstracto

En informática , un grafo semántico abstracto ( GSA ) o grafo de términos es una forma de sintaxis abstracta en la que una expresión de un lenguaje formal o de programación se representa mediante un grafo cuyos vértices son los subtérminos de la expresión . Un GSA se encuentra en un nivel de abstracción superior al de un árbol de sintaxis abstracta (AST), que se utiliza para expresar la estructura sintáctica de una expresión o programa .

Los ASG son más complejos y concisos que los AST porque pueden contener subtérminos compartidos (también conocidos como "subexpresiones comunes"). ^{[ 1 ]} Los compiladores suelen utilizar grafos semánticos abstractos como representación intermedia para almacenar los resultados de la eliminación de subexpresiones comunes en árboles de sintaxis abstracta . Los AST son árboles y, por lo tanto, son incapaces de representar términos compartidos. Los ASG suelen ser grafos acíclicos dirigidos (DAG) , aunque en algunas aplicaciones se permiten grafos que contienen ciclos . Por ejemplo, un grafo que contiene un ciclo podría utilizarse para representar las expresiones recursivas que se utilizan comúnmente en lenguajes de programación funcional como construcciones de iteración sin bucle . La mutabilidad de este tipo de grafos se estudia en el campo de la reescritura de grafos .

El término de nomenclatura grafo está asociado con el campo de la reescritura de grafos de términos , ^{[ 2 ]} que implica la transformación y el procesamiento de expresiones mediante la especificación de reglas de reescritura, ^{[ 3 ]} mientras que el grafo semántico abstracto se utiliza cuando se habla de lingüística , lenguajes de programación , sistemas de tipos y compilación .

Los árboles de sintaxis abstracta no pueden compartir nodos de subexpresión, ya que un nodo en un árbol propiamente dicho no puede tener más de un padre. Si bien esta simplicidad conceptual resulta atractiva, puede conllevar una representación redundante y, por consiguiente, una posible duplicación ineficiente del cálculo de términos idénticos. Por este motivo, los generadores de sintaxis abstracta (ASG) se utilizan a menudo como lenguaje intermedio en una etapa posterior de compilación para la construcción de árboles de sintaxis abstracta mediante análisis sintáctico.

Un grafo semántico abstracto se construye típicamente a partir de un árbol sintáctico abstracto mediante un proceso de enriquecimiento y abstracción. El enriquecimiento puede consistir, por ejemplo, en la adición de punteros inversos , es decir, aristas que conectan un nodo identificador (donde se utiliza una variable ) con un nodo que representa la declaración de dicha variable. La abstracción puede implicar la eliminación de detalles que solo son relevantes para el análisis sintáctico , no para la semántica.

Por ejemplo, consideremos el caso de la refactorización de código . Para representar la implementación de una función que recibe un argumento de entrada, el parámetro recibido suele recibir un nombre arbitrario y distinto en el código fuente para poder referenciarlo. La representación abstracta de esta entidad conceptual, una instancia de "argumento de función", probablemente se mencionará en la firma de la función y también una o más veces dentro del cuerpo del código de implementación. Dado que la función en su conjunto es el padre tanto de su información de encabezado o "firma" como de su cuerpo de implementación, un AST no podría usar el mismo nodo para identificar conjuntamente los múltiples usos o apariciones de la entidad del argumento. Esto se resuelve mediante la naturaleza DAG de un ASG. Una ventaja clave de tener una identidad de nodo única y distinta para cualquier elemento de código es que las propiedades de cada elemento se almacenan, por definición, de forma única. Esto simplifica las operaciones de refactorización, ya que existe exactamente un nexo existencial para cualquier instancia de propiedad. Si el desarrollador decide cambiar el valor de una propiedad, como el "nombre" de cualquier elemento de código (el "argumento de la función" en este ejemplo), el ASG expone inherentemente ese valor en un único lugar, y, por consiguiente, cualquier cambio de propiedad de este tipo se propaga de forma implícita, trivial e inmediata a nivel global.

• Ontología (informática)
• Web semántica
• Red semántica

• Dean, Tom. "CPPX  — Extractor de hechos de C/C++" .
• Devanbu, Premkumar T.; Rosenblum, David S.; Wolf, Alexander L. "Generación de herramientas de prueba y análisis con Aria" . Archivado del original el 27 de mayo de 2006.
• Mamas, Evan; Kontogiannis, Kostas (2000). Hacia representaciones portátiles de código fuente utilizando XML . Séptima Conferencia de Trabajo sobre Ingeniería Inversa. pp. 172–182 . CiteSeerX 10.1.1.88.6173 .  
• Raghavan, Shruti; Rohana, Rosanne; Leon, David; Podgurski, Andy; Augustine, Vinay (2004). "Dex: una herramienta de comparación de grafos semánticos para estudiar cambios en grandes bases de código" . 20.ª Conferencia Internacional IEEE sobre Mantenimiento de Software, 2004. Actas . Conferencia Internacional IEEE sobre Mantenimiento de Software. págs. 188–197 . CiteSeerX 10.1.1.228.9292 . doi : 10.1109/icsm.2004.1357803 . ISBN   0-7695-2213-0Archivado del original el 17 de enero de 2008. Consultado el 1 de mayo de 2007 .