Introducción #

Tal y como se vio anteriormente, la misión del analizador sintáctico consiste en realizar dos tareas: identificar las estructuras y construir un árbol.

En los dos temas anteriores se ha visto cómo realizar la primera de dichas tareas, es decir, cómo se definía la sintaxis del lenguaje mediante una gramática y cómo se usaba esta para validar entradas.

El tema actual, el último dedicado al análisis sintáctico, se centrará en la segunda tarea: la construcción del árbol.

Por qué construir un árbol #

Una vez que el sintáctico ha identificado las estructuras de la entrada, es necesario indicar a las fases posteriores del traductor cuáles se han encontrado y dónde. Esto se hará mediante un árbol.

El motivo de elegir esta estructura de datos es porque, para las demás fases del traductor, resulta ser la más sencilla y directa para moverse por la entrada. Por ejemplo, en un fichero de texto se puede ir directamente al carácter en la posición 24 del mismo (acceso aleatorio). Pero, sin embargo, para las fases del traductor sería engorroso tener que acceder a la entrada a través de posiciones de caracteres. Lo que se quiere es acceder directamente a estructuras. Por ejemplo, se querría poder obtener directamente las siguientes estructuras sin importar su posición en el fichero:

• La primera sentencia de una determinada función.
• Su tipo de retorno.
• La posición del fichero donde está el tipo de su segundo parámetro.

Esto es lo que se consigue con un árbol: pasar de una estructura de datos en la que el direccionamiento se realiza a nivel de caracteres a otra en la que el direccionamiento se realiza a nivel de estructuras — lo que permite encontrar muy fácilmente los elementos anteriores.

Varias vs Una Pasada #

Construir un árbol implica una técnica denominada traducción en varias pasadas. Esta consiste, tal y como se ha visto hasta ahora, en que cuando el sintáctico encuentra una estructura se limita a añadir un nodo al árbol. Las fases posteriores del traductor recorrerán dicho árbol y, al encontrar cada nodo, harán sobre él las tareas específicas de dichas fases.

Por tanto, la entrada se recorre varias veces (varias pasadas). La primera pasada es la que realiza el analizador sintáctico. Las otras son cada uno de los recorridos del árbol que realizan las fases posteriores (dado que el árbol representa la entrada, cada recorrido del mismo es una nueva pasada sobre ésta). Esta opción, obviamente, tiene el inconveniente de ocupar más memoria (la del árbol) y de requerir más tiempo de ejecución para realizar los distintos recorridos del árbol.

Esto, que hoy en día no supone un problema en la práctica, no era así hasta hace relativamente poco. En máquinas con escasa memoria y potencia de procesamiento era más eficiente un enfoque en el que se evitara la construcción del árbol y sus recorridos. Por ello, se hacía una traducción en una pasada. En este enfoque, el análisis sintáctico tiene incrustado, entre su código, el código de las fases posteriores. Es decir, cuando encuentra una estructura, en vez de crear el nodo, realiza en ese momento (antes de seguir analizando el resto de la entrada) todas las tareas que el resto de las fases tengan que hacer sobre la estructura recién encontrada (por ejemplo, validarla y generar su código). Esta es la técnica que se encontrará comúnmente en los textos clásicos de compiladores y es el enfoque que se siguió en lenguajes como Pascal o C/C++.

El procesamiento en una pasada, aunque tiene las ventajas de menor ocupación y tiempo de ejecución, tiene también sus inconvenientes:

• Debido a que el código de todas las fases está mezclado, el compilador es mucho más difícil de entender y modificar.
• No se pueden implementar ciertas características en los lenguajes. Por ejemplo, no se pueden realizar acciones que requieran información que no haya aparecido previamente en el fichero. Es por ello que los lenguajes implementados con este enfoque tenían limitaciones como las siguientes:
  • Toda variable que se usara debía estar definida antes de su uso. En caso contrario, cuando se usara la variable no se sabría aún su tipo.
  • No se puede usar una función que haya sido definida debajo de su invocación. Es por ello que en lenguajes como C/C++ tuvieran que añadirse al principio de los ficheros las cabeceras de las funciones (habitualmente con #include<...>). Así, cuando se usara una función, ya se conocía el número y tipo de parámetros.

Por todo lo anterior, a pesar de la ligera pérdida de eficiencia de construir un árbol, la técnica de varias pasadas es la opción más común en los lenguajes de programación modernos y es la que se presenta en esta asignatura.