Defina las estructuras de datos de árboles de sintaxis y tablas de símbolos.

Para realizar un seguimiento de los nombres en un programa de ámbito estático, el compilador se basa en una estructura de datos llamada tabla de símbolos. En el nivel más básico, una tabla de símbolos es un diccionario: asigna nombres a información relevante conocida por el compilador. La operación más básica aquí es colocar la nueva relación de mapeo (restricción de nombre de objeto) en la tabla y (de forma no destructiva) extraer la información debajo del mapeo usando el nombre de pila. Más adelante nos referiremos a estas dos operaciones como inserción y búsqueda respectivamente.

Las reglas de alcance estático en la mayoría de los lenguajes también introducen otro nivel de complejidad, requiriendo diferentes entornos de referencia para diferentes partes del programa. Para manejar reglas de rango, es posible que deseemos simplemente agregar una operación de eliminación. Debido a que el compilador escanea el código de principio a fin durante la fase de análisis semántico, puede insertar nuevas restricciones al principio del rango y revocarlas al final del rango. Sin embargo, hay algunos factores que hacen que este enfoque directo no sea práctico.

En muchos lenguajes con ámbitos anidados, el efecto de las declaraciones internas eclipsa las declaraciones externas, lo que significa que la tabla de símbolos debe poder contener cualquier número de asignaciones para un nombre determinado. La operación de búsqueda debe devolver el mapeo más interno y el mapeo externo debe volver a ser visible al final del alcance.

Los registros (estructuras) en lenguajes tipo Algol tienen algunas propiedades de alcance, pero no tienen una estructura de anidamiento tan agradable como los ámbitos. Cuando el analizador semántico ve una declaración de registro, debe anotar los nombres de los campos de cada registro (también son recursivos, ya que los registros se pueden anidar). Al final de esta declaración, cada nombre de dominio debe volver a ser invisible. Sin embargo, después de esto, tan pronto como aparezca una variable de este tipo de registro en el cuerpo del programa (por ejemplo, en my_rec.field_name), estos campos deben volver a ser visibles inmediatamente después del punto de la referencia. En Pascal y otros lenguajes con declaraciones with, los nombres de los campos de registro también deberían ser visibles en el contexto de declaraciones múltiples.

A veces algunos nombres pueden usarse antes de ser declarados, incluso en lenguajes como Algol. Por ejemplo, tanto Algol 60 como Algol 68 permiten etiquetas de referencia directas. Pascal evita esta situación al exigir que las etiquetas se declaren al principio del alcance, pero aún permite referencias directas para declaraciones de puntero:

Tipos