En informática , un grafo semántico abstracto ( ASG ) 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 ASG se encuentra en un nivel de abstracción más alto que un árbol de sintaxis abstracta (o 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 los gráficos 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, no pueden representar términos compartidos. Los ASG suelen ser gráficos acíclicos dirigidos (DAG) , aunque en algunas aplicaciones se pueden permitir gráficos que contengan ciclos [ aclaración necesaria ] . Por ejemplo, un gráfico que contenga un ciclo podría utilizarse para representar las expresiones recursivas que se utilizan habitualmente en los lenguajes de programación funcional como construcciones de iteración sin bucles . La mutabilidad de estos tipos de gráficos se estudia en el campo de la reescritura de gráficos .
El término de nomenclatura gráfico está asociado con el campo de reescritura de gráficos de términos , [2] que involucra la transformación y procesamiento de expresiones mediante la especificación de reglas de reescritura, [3] mientras que el gráfico semántico abstracto se utiliza cuando se discute lingüística , lenguajes de programación , sistemas de tipos y compilación .
Los árboles de sintaxis abstracta no pueden compartir nodos de subexpresiones porque no es posible que un nodo de un árbol propio tenga más de un padre. Aunque esta simplicidad conceptual es atractiva, puede tener como consecuencia una representación redundante y, a su vez, una posible duplicación ineficiente del cálculo de términos idénticos. Por este motivo, los ASG se utilizan a menudo como lenguaje intermedio en una etapa de compilación posterior a la construcción de árboles de sintaxis abstracta mediante análisis sintáctico.
Un gráfico 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 ser, por ejemplo, la adición de punteros hacia atrás , aristas desde un nodo identificador (donde se utiliza una variable ) a un nodo que representa la declaración de esa variable. La abstracción puede implicar la eliminación de detalles que son relevantes solo para el análisis sintáctico , no para la semántica.
Por ejemplo, considere el caso de la refactorización de código . Para representar la implementación de una función que toma un argumento de entrada, al parámetro recibido se le asigna convencionalmente un nombre arbitrario y distinto en el código fuente para que se pueda hacer referencia a él. 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 totalidad 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 co-identificar los múltiples usos o apariencias de la entidad de 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 dado es que las propiedades de cada elemento se almacenan, por definición, de forma única. Esto simplifica las operaciones de refactorización, porque hay exactamente un nexo existencial para cualquier instancia de propiedad dada. Si el desarrollador decide cambiar un valor de propiedad como el "nombre" de cualquier elemento de código (el "argumento de función" en este ejemplo), el ASG expone inherentemente ese valor exactamente en un lugar, y se deduce que dichos cambios de propiedad se propagan de manera implícita, trivial e inmediata a nivel global.
La noción de gráfico de términos codifica un refinamiento de la sintaxis generada inductivamente en la que se presta atención a la compartición y el descarte de subtérminos.