El algoritmo de Steensgaard

En informática , el algoritmo de Steensgaard es un algoritmo escalable e independiente del flujo para el análisis de punteros . Se utiliza frecuentemente en compiladores debido a su velocidad (por ejemplo, existe una implementación disponible en el marco de compilación LLVM ). ^{[ 1 ]} En su formulación original, este algoritmo era independiente del campo, del contexto y de la matriz.

El algoritmo de Steensgaard se basa en restricciones de igualdad ^{[ 2 ]} , a diferencia del algoritmo de Andersen , que se basa en restricciones de subconjunto . Esto permite rastrear la información de referencias mediante una estructura de datos de unión-búsqueda . Esta elección le confiere al algoritmo su velocidad característica; cuando se implementa utilizando una estructura de datos de unión-búsqueda, su complejidad espacial es lineal y su complejidad temporal es casi lineal con respecto al tamaño del programa de entrada.

La formulación del algoritmo de Bjarne Steensgaard se basó en la inferencia y la verificación de tipos . Steensgaard propuso el análisis de punteros para un lenguaje de punteros pequeño, imperativo pero genérico, que captura las propiedades esenciales de otros lenguajes comunes con punteros, como C. La semántica del lenguaje y las reglas de tipado constituyen el análisis.

• Steensgaard, Bjarne (1996). «Análisis de punteros en tiempo casi lineal» (PDF) . POPL '96: Actas del 23.er simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . Nueva York, NY, EE. UU.: ACM. págs. 32-41 . doi : 10.1145/237721.237727 . ISBN  0-89791-769-3.
• Smaragdakis, Yannis; Balatsouras, George (2015). "Análisis de punteros" (PDF) . Fundamentos y tendencias en lenguajes de programación . 2 (1): 1– 69. doi : 10.1561/2500000014 . Recuperado el 30 de mayo de 2019 .