Árbol de sintaxis dinámica - Dynamic syntax tree

Estructura de árbol de sintaxis dinámica

El árbol de sintaxis dinámica ( DST ), fue creado por M. Barzanti como una alternativa del árbol de sintaxis abstracta y las representaciones del árbol de análisis de la estructura del código fuente escrito en un lenguaje de programación . A diferencia de los lenguajes de programación tipados estáticamente , el análisis de un lenguaje de programación dinámico tiene que estimar el sistema de tipos (tipos, variables, funciones) a partir de la semántica del fragmento de código, así como todos los archivos de configuración y archivos binarios . La implementación del árbol de sintaxis dinámica también tiene en cuenta las declaraciones implícitas y explícitas no estáticas y no tipificadas (programación informática) , de modo que la información resultante cubra la mayoría de los fragmentos de código dinámico legibles.

El mapeo de construcciones de lenguaje de un lenguaje dinámico en un árbol de sintaxis dinámica (DST) es una especie de análisis semántico (compiladores) . La información que se deriva de la sintaxis se analiza y los resultados se vuelven a insertar en el mismo árbol, pero en forma de información estática completa. El preprocesamiento del código fuente creará un árbol de sintaxis especializado para cada clase encontrada. Eso también se puede aplicar a los lenguajes de programación tradicionales, como COBOL , donde las clases se pueden representar mediante programas, métodos mediante llamadas / ejecuciones, parámetros mediante el uso, etc.

Aplicación en herramientas SAST

Los árboles de sintaxis dinámica se utilizan principalmente en el análisis de programas y los sistemas de transformación de programas . Los árboles de sintaxis dinámica son estructuras de datos que se utilizan en algunas herramientas de análisis de programas estáticos , debido a su propiedad de representar rápidamente una estructura optimizada de código de programa y su archivo binario relacionado .

Motivación

• Comparado con el código fuente , un DST no incluye ciertos elementos, como puntuación y delimitadores no esenciales (llaves, punto y coma, paréntesis, etc.).
• Se debe procesar todo el archivo fuente, en una forma analizada, y se debe analizar cada expresión o construcción. Como resultado, amplía parte de la información de nodo existente o agrega nuevos nodos de declaración (declaraciones implícitas). En lenguajes estáticos, normalmente es suficiente escanear construcciones de declaración solamente (declaración de clase, declaración de variable, etc.); las expresiones únicas no son necesarias para recopilar los símbolos disponibles y su descripción.
• Además de los símbolos definidos estáticamente, se agregan otros nodos de árbol utilizando el análisis semántico de la DST. También se puede modificar parte de la información existente. Las expresiones particulares se escanean para encontrar, por ejemplo, variables declaradas implícitamente y miembros de objeto agregados dinámicamente. También se descubren los posibles valores de las variables, los tipos estimados y el comportamiento influenciado por la configuración. El DST construido hasta ahora se utiliza para eso. El proceso de mapeo de la Expresión de Asignación, que contiene el Uso de Variables (incluido el declarado en las páginas web o JavaScript) en la declaración estática de la variable usada y los archivos de Configuración que influyen en el Comportamiento, se muestra en la Figura del lado derecho.
• El mapeo recopila información conocida de las expresiones y la almacena en la representación estática del código fuente (DST). El proceso de mapeo de árbol de sintaxis dinámico único se realiza cada vez que cambia el código fuente correspondiente, por lo que es adecuado implementar algunas optimizaciones. Además, podría haber árboles que contengan símbolos de grandes bibliotecas de lenguaje estático, por ejemplo, de ensamblajes .NET, que administran típicamente miles de símbolos. La inicialización de todos ellos puede ser demasiado lenta.

Mejoramiento

A diferencia del árbol de sintaxis abstracta y del árbol de análisis CST , en el caso de clases enormes que tengan más de 65535 objetos, la estructura del diccionario de objetos DST (68,083 nodos) se paginará en algunos archivos XML pequeños, de aproximadamente 575 KB de tamaño cada uno. Lo mismo se hará con el árbol de sintaxis dinámica en sí: solo se procesarán 4096 clases a la vez, con un máximo de 135 KB cada una. No habrá ningún caso de uso de memoria RAM de acceso aleatorio superior a 700 MB, lo que significa que puede realizar un análisis estático utilizando una computadora portátil Windows XP de gama baja con 1 GB de RAM y un procesador de un solo núcleo, y hasta 5 simultáneamente estática El análisis de diferentes aplicaciones a la vez se puede lograr utilizando solo una máquina con procesador de doble núcleo y 4 GB de RAM. Por lo tanto, los rendimientos serán escalables en función de la arquitectura del hardware, con la garantía de realizar al menos un análisis estático completo partiendo de un portátil y subiendo a una máquina multinúcleo. Un aspecto de optimización importante que AST y CST será el número de nodos del árbol. Por ejemplo, GCC 2.52 del paquete de pruebas de SPEC 95 Standard Performance Evaluation Corporation comprende 604,000 nodos AST frente a solo 127,067 nodos paginados en 2 DST, y Word 1.1A (1990) comprende 607,700 nodos AST frente a solo 204,249 nodos, paginados en 3 DST. GCC 2.52 tiene unas 140.000 líneas de código y Word 1.1A unas 322.000. Los tiempos de procesamiento del análisis estático usando DST fueron de media hora para GCC y de 1 hora y media para Word 1.1A. La fuente de Word 1.1A se descargó del sitio del Museo de Historia de la Computación . Parte de la inicialización de información adicional se puede posponer hasta que se solicite, porque no todos los elementos de origen deben analizarse y mapearse de inmediato.

Ver también

• Gráfico semántico abstracto (ASG)
• Patrón compuesto
• Gráfico de flujo de control
• Modelo de objetos de documento (DOM)
• Árbol de resolución semántica (SRT)
• Tabla de símbolos
• Gráfico de término

Referencias

• Este artículo se basa en material extraído del Diccionario de Computación en línea gratuito antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.

Otras lecturas

• Syman, David. "Árbol de sintaxis dinámica: Sandboxing binario optimizado" . Cite journal requiere |journal=( ayuda )
• Syman, David. "Árbol de sintaxis dinámica: resultados de implementación del primer trimestre de 2016" . Cite journal requiere |journal=( ayuda )