PDF de programación - Procesadores de Lenguajes I - Tablas de símbolos

1



04/01/2008

Francisco Charte Ojeda

Tablas de símbolos

Procesadores de Lenguajes I

qwertyuiopasdfghjklzxcvbnmqwer
tyuiopasdfghjklzxcvbnmqwertyuiopa
sdfghjklzxcvbnmqwertyuiopasdfghjkl
zxcvbnmqwertyuiopasdfghjklzxcvbn
mqwertyuiopasdfghjklzxcvbnmqwert
yuiopasdfghjklzxcvbnmqwertyuiopas
dfghjklzxcvbnmqwertyuiopasdfghjklz
xcvbnmqwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnmqwerty
uiopasdfghjklzxcvbnmqwertyuiopasd
fghjklzxcvbnmqwertyuiopasdfghjklzx
cvbnmqwertyuiopasdfghjklzxcvbnmq
wertyuiopasdfghjklzxcvbnmqwertyui
opasdfghjklzxcvbnmqwertyuiopasdfg
hjklzxcvbnmrtyuiopasdfghjklzxcvbn
mqwertyuiopasdfghjklzxcvbnmqwert
yuiopasdfghjklzxcvbnmqwertyuiopas
dfghjklzxcvbnmqwertyuiopasdfghjklz

Tabla de contenido

1. Utilidad de una tabla de símbolos ................................................................................ 3

2. Estructura lógica de una tabla de símbolos .................................................................. 4

3. Operaciones fundamentales en la tabla de símbolos .................................................. 7

4. Estructuras de datos subyacentes ................................................................................ 8

4.1. Listas o tablas sin orden ........................................................................................ 9

4.2. Listas o tablas con orden ..................................................................................... 10

4.3. Árboles binarios ................................................................................................... 10

4.4. Tablas hash .......................................................................................................... 11

4.5. Cómo abordar el problema de los ámbitos ......................................................... 13

4.6. Tablas de símbolos locales .................................................................................. 16

5. Contenido de la tabla de símbolos ............................................................................. 16

6. Referencias ................................................................................................................. 17



Página 2 de 17



1. Utilidad de una tabla de símbolos

Los compiladores e intérpretes son programas que analizan un código de entrada, el
código fuente, a fin de generar un código de salida ejecutable que puede ser escrito en un
archivo, en el caso de los compiladores, o utilizado de forma inmediata en memoria, en el de
los intérpretes. Para ello pasan por varias fases, siendo preciso en algunas de ellas determinar
qué significado (tipo de elemento y atributos asociados) tienen los identificadores que se en-
cuentran en el código fuente.

Las tablas de símbolos se crean en las primeras fases del proceso, durante el análisis
léxico y sintáctico, permitiendo a las siguientes asociar un contexto a cada uno de los símbolos
que haga posible saber, por ejemplo, si un identificador representa una variable o el nombre
de un procedimiento, cuál es el tipo de dato de la variable o la lista de argumentos que precisa
ese procedimiento, cuál es el ámbito que les corresponde en el caso de los lenguajes con es-
tructura de bloques y orientados a objetos, etc.

Mediante la tabla de símbolos un compilador (la mayoría de lo dicho sería aplicable

también a un intérprete) puede, dependiendo de la fase en que se encuentre, determinar:

 Si un identificador es una variable, conociendo su tipo o la dirección relativa

que se le ha asignado.

 Si una variable o un procedimiento ha sido declarado antes de utilizarse la

primera vez.

 Si un identificador es una palabra reservada y por tanto no debe permitir su

redefinición.



Los identificadores que son visibles dependiendo de su ámbito y el bloque que
se está procesando en cada momento.

La tabla de símbolos es una estructura de datos temporal en el caso de los compilado-
res, ya que una vez generado el código objeto se descarta al no tener mayor utilidad. Algunos
compiladores, no obstante, tienen la capacidad para incluirla en el ejecutable a fin de facilitar
la depuración, de forma que el programador puede ir inspeccionando las variables por su
nombre, no como posiciones de memoria, y de igual forma identificar los procedimientos a los
que se invoca, argumentos de entrada y salida, etc.

Los intérpretes emplean la tabla de símbolos durante todo el proceso de traducción y
ejecución del programa, lo cual les permite, por ejemplo, saber qué valor contiene una cierta
variable en cada momento y actuar sobre éste.

Puede afirmarse, por tanto, que la tabla de símbolos es una de las piezas fundamenta-
les en el funcionamiento de los compiladores, de ahí que sea importante su estudio en una
asignatura como Procesadores de lenguajes: operaciones que contempla, estructura de datos
subyacente, evolución a lo largo de las distintas fases de compilación, etc.

Dado que la tabla de símbolos es una estructura de datos relativamente compleja, en
la que se contemplan varios tipos de operaciones posibles, lo habitual es que exista una lógica

Página 3 de 17



independiente encargada de gestionarla. En el diagrama siguiente se han representado los
distintos pasos de un hipotético compilador y cuáles serían las operaciones que solicitarían al
gestor de la tabla de símbolos:

2. Estructura lógica de una tabla de símbolos

Sin entrar en un principio a detallar la estructura de datos subyacente, la estructura

lógica de una tabla de símbolos podría ser la siguiente:



Símbolo

Edad

DifFecha

Nombre

...

Atributos

Var, Entero, $02

Func, Entero,2,Fecha,Fecha

Var, Cadena, $06

...

La primera columna contendría el identificador de cada símbolo: nombre de variable,
función, etc. En la segunda habría una lista de atributos mediante los que se obtiene informa-
ción sobre el símbolo: categoría (variable, función, constante ...), tipo, dirección de almacena-
miento, lista de argumentos, tipo de retorno, etc.

Página 4 de 17



Dependiendo de las características de cada lenguaje, el compilador puede almacenar
directamente en la tabla de símbolos la secuencia de caracteres que componen cada identifi-
cador o, en su lugar, mantener una estructura paralela. En el primer caso es obvio que existe
una longitud máxima para los identificadores, además de un desperdicio de espacio.

Hasta no hace mucho había compiladores, recuerdo algunos de la firma Borland, en los
que los identificadores podían tener cualquier longitud pero solamente eran significativos los
primeros 32 caracteres, de forma que dos nombres de variable que coincidiesen en esos 32
caracteres (no era habitual) el compilador los identificaba como un mismo símbolo. Supongo
que esa limitación se debía a que en la tabla de símbolos de estos compiladores los identifica-
dores se almacenaban en la propia tabla, donde había reservados 32 bytes para tal fin.

La alternativa, utilizada por la mayoría de los compiladores actuales, consiste en guar-
dar los identificadores en una estructura paralela, almacenando en la propia tabla de símbolos
únicamente un puntero a la posición del identificador y su longitud, por ejemplo:

Símbolo

$00,4

$04,8

$12,6

...

Atributos

Var, Entero, $02

Func, Entero,2,Fecha,Fecha

Var, Cadena, $06

...

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19

E

d

a

d

D

i

f F

e

c

h

a

N

o

m

b

r

e



Otra posibilidad sería almacenar como símbolo en la tabla principal solamente el pun-
tero, sin especificar la longitud, usando un delimitador de final de cadena en la tabla donde se
guarden los identificadores. Sería el caso representado en el siguiente diagrama:

Página 5 de 17



En cuanto a los atributos se refiere, cada símbolo tendrá unos u otros dependiendo de
la categoría a que pertenezca: variable, constante, procedimiento, etc. Algunos habituales son:

 Categoría: Determina a qué pertenece el símbolo asociado.

 Tipo: En el caso de las variables, establece el tipo de información que con-
tendrán. Si el símbolo es una función, este mismo atributo indicaría el tipo de
valor devuelto.

 Argumentos: Para los procedimientos, funciones o métodos indicará la lista de

parámetros que precisa y sus tipos.

 Posición: Para las variables es habitual contar con una posición relativa de
memoria asociada. Los intérpretes utilizarán dicha posición a medida que eje-
cuten el código para leer y modificar el valor.

 Valor: Si el símbolo es una constante este atributo contendría el valor que re-

presenta.

 Ámbito: En los lenguajes orientados a objetos y con estructura de bloques
pueden existir múltiples símbolos con el mismo identificador en ámbitos dis-
tintos, sirviendo este atributo para determinar el ámbito a que pertenecen.

Otros atributos que podrían existir sería la indicación de si una variable es un array o
matriz, el número de dimensiones con que cuenta y el número de elementos de cada dimen-
sión, si los parámetros de entrada a un procedimiento tienen asociado un valor por defecto y
cuál es éste, si un cierto método de un objeto está vinculado estáticamente o de forma diná-
mica (late-binding) en cuyo caso hay que buscar durante la ejecución en las vtable de métodos
virtuales, etc.

En los lenguajes más evolucionados, con orientación a objetos y a componentes como
pueden ser C# o Java, la tabla de símbolos llega a ser una estructura realmente compleja por la
cantidad de atributos que pueden existir. Esto no implica, sin embargo, unas necesidades de
almacenamiento muy grandes en la tabla de símbolos, ya que suelen utilizarse paquetes de
bits en los que se resume toda la información aso