En informática , un gráfico semántico abstracto ( ASG ) o gráfico 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 gráfico cuyos vértices son los subtermos de la expresión . Un ASG tiene 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 términos compartidos (también conocidos como "subexpresiones comunes"). [1] gráficos semánticas abstractas se utilizan a menudo como una representación intermedia por los compiladores para almacenar los resultados de la realización de eliminación de subexpresiones comunes sobre árboles de sintaxis abstracta . Los AST son árboles y, por lo tanto, son incapaces de representar términos compartidos. Los ASG suelen ser gráficos acíclicos dirigidos (DAG) , aunque en algunas aplicaciones se pueden permitir gráficos que contienen ciclos [ aclaración necesaria ] . Por ejemplo, un gráfico que contiene un ciclo podría usarse para representar las expresiones recursivas que se usan comúnmente en los lenguajes de programación funcional como construcciones de iteración sin bucle . La mutabilidad de este tipo de gráficos se estudia en el campo de la reescritura de gráficos .
El gráfico de términos de nomenclatura está asociado con el campo de la reescritura de gráficos de términos , [2] que implica 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 usa 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 porque no es posible que un nodo en un árbol adecuado tenga más de un padre. Aunque esta simplicidad conceptual es atractiva, puede tener el costo de una representación redundante y, a su vez, posiblemente duplicar de manera ineficiente el cálculo de términos idénticos. Por esta razón, los ASG se utilizan a menudo como un lenguaje intermedio en una etapa de compilación posterior para la construcción del árbol de sintaxis abstracta mediante el análisis sintáctico.
Un gráfico semántico abstracto se construye típicamente a partir de un árbol de sintaxis abstracto mediante un proceso de enriquecimiento y abstracción. El enriquecimiento puede ser, por ejemplo, la adición de back-pointers , bordes desde un nodo identificador (donde se usa 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.
Ejemplo: refactorización de código
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 da convencionalmente un nombre distinto y arbitrario en el código fuente para que pueda ser referenciado. 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 encabezado o información de "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 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, por definición, se almacenan de forma única. Esto simplifica las operaciones de refactorización, porque existe exactamente un nexo existencial para cualquier instanciación de propiedad dada. Si el desarrollador decide cambiar el valor de una propiedad, como el "nombre" de cualquier elemento de código (el "argumento de función" en este ejemplo), el ASG expone inherentemente ese valor en exactamente un lugar, y se deduce que dichos cambios de propiedad son propagado implícita, trivial e inmediatamente a nivel mundial.
Ver también
- Árbol de sintaxis abstracta
- Ontología (informática)
- Web semántica
- Cuadrícula semántica
Referencias
- ^ Garner, Richard (2011). "Una visión abstracta de la sintaxis con compartir". Revista de Lógica y Computación . 22 (6): 1427-1452. arXiv : 1009.3682 . doi : 10.1093 / logcom / exr021 .
La noción de gráfico de términos codifica un refinamiento de la sintaxis generada inductivamente en la que se presta atención al intercambio y descarte de subterráneos.
- ^ Plump, D. (1999). Ehrig, Hartmut ; Engels, G .; Rozenberg, Grzegorz (eds.). Manual de Gramáticas de Gráficos y Computación por Transformación de Gráficos: aplicaciones, lenguajes y herramientas . 2 . World Scientific. págs. 9-13. ISBN 9789810228842.
- ^ Barendregt, HP; van Eekelen, MCJD; Glauert, JRW; Kennaway, JR; Plasmeijer, MJ; Sueño, MR (1987). Reescritura del gráfico de términos . PARLE Parallel Architectures and Languages Europe (Lecture Notes in Computer Science) . Apuntes de conferencias en Ciencias de la Computación. 259 . págs. 141-158. doi : 10.1007 / 3-540-17945-3_8 . ISBN 978-3-540-17945-0.
enlaces externos
- Dean, Tom . "CPPX - Extractor de hechos C / C ++" .
- Devanbu, Premkumar T .; Rosenblum, David S .; Wolf, Alexander L. "Generación de herramientas de análisis y pruebas con Aria" . Cite journal requiere
|journal=
( ayuda ) - Mamás, Evan ; Kontogiannis, Kostas . "Hacia representaciones de código fuente portátil utilizando XML". CiteSeerX 10.1.1.88.6173 . Cite journal requiere
|journal=
( ayuda ) - Raghavan, Shruti; Rohana, Rosanne; León, David; Podgurski, Andy; Agustín, Vinay (2004). Dex: una herramienta de diferenciación de gráficos semánticos para estudiar cambios en bases de código grandes . Conferencia internacional IEEE sobre mantenimiento de software. págs. 188-197. doi : 10.1109 / icsm.2004.1357803 . Archivado desde el original el 17 de enero de 2008 . Consultado el 1 de mayo de 2007 .