Conferencia 3: Introducción a las Rutinas Semánticas.

- Elementos de arreglo.
- Rutinas semánticas para constantes expresiones, elementos de arreglo y asignación.

Bibliografía:
- Compilers, p. 481.
- Construcción de Compiladores. David Gries. Cap. 12, pp. 305-
- Conferencia en el servidor.

1. Introducción a las rutinas semánticas

Ya hemos visto como es posible diseñar formas internas del programa fuente para determinadas
expresiones y sentencias. Ahora veremos como es posible en el proceso de compilación generar dichas
formas internas a partir del análisis del programa fuente. Para alcanzar este objetivo el compilador se vale
de un conjunto de rutinas asociadas al analizador sintáctico, las cuales se denominan rutinas
semánticas. Al conjunto de tales rutinas se le denomina Analizador Semántico.

¿Cuál es la esencia del analizador semántico?

Las rutinas semánticas trabajan en coordinación con el analizador sintáctico en función de las reducciones
que por las diferentes reglas se realicen sobre la cadena fuente durante el proceso de análisis. Estas
rutinas o conjunto de acciones asociadas a cada regla de producción se ejecutan en el momento en que
el analizador sintáctico realiza una reducción por dicha regla. Luego la esencia del analizador semántico es
definir el conjunto de acciones semánticas que se asocian con cada regla sintáctica. El principio básico de
tal asociación se puede resumir en el enunciado siguiente:

“Si en un momento dado del análisis sintáctico aparece como empuñadura la cadena x = U donde  y
 son cadenas cualesquiera y U es un no terminal, esto implica que previamente ha sido realizada la
reducción por U (U) y se ejecutaron las rutinas semánticas asociadas a esta regla. Esto a su vez
implica que la forma interna correspondiente a dicha regla de producción ya fue generada”. O sea, a cada
regla sintáctica se asocia una rutina semántica (que puede ser vacía), la cual se ejecuta en el momento
en que el analizador sintáctico realiza una reducción por dicha regla. Luego, la función de las rutinas
semánticas se reduce a generar la porción de la forma interna asociada a cada regla.

Así por ejemplo, en la gramática:

EE+TT
TT*FF
F  ( E )  ident

Las acciones semánticas asociadas a cada regla podrían ser las siguientes:

Regla Acción
E  E+T Colocar en la cadena polaca el operador +
ET Ninguna
T  T*F Colocar en la cadena polaca el operador *
TF Ninguna
F  (E) Ninguna
F  ident Colocar en la cadena polaca el operador CARGA y la dirección de la entrada del ident
a la tabla de símbolos.

Así, si compilamos la expresión A*(B+C), el conjunto de reducciones que se realizan y la forma interna
que se genera es:
Forma sentencial Regla utilizada Cadena polaca generada
A*( B+C ) - -
F*( B+C ) F id CARGA, dir A
T*( B+C ) T F -
T*( F+C ) F id CARGA, dir B
T*( T+C ) T F -
T*( E+C ) E T -
T*( E+F ) F id CARGA, dir C
T*( E+T ) T F -
T*( E ) E E+T +
T*F F ( E ) -
T T T*F *
E E T -

con lo cual obtenemos la forma interna asociada a esta expresión:

CARGA, dir A, CARGA, dir B, CARGA, dir C, +, *

Para conocer cualquier atributo de los identificadores, las rutinas semánticas se auxilian de la tabla de
símbolos, la cual denotaremos por ahora mediante el arreglo TS. Cuando una rutina se disponga a
consultar la tabla de símbolos asumiremos que el scanner ha dejado la entrada correspondiente a dicho
símbolo en la variable p.

Para generar la cadena polaca utilizamos como apuntador al arreglo POLACA la variable J y una pila
auxiliar que denominamos por SEM con apuntador T. Asumiremos además que cada operador se escribe
en POLACA con su propio nombre. Sobre la base de los acuerdos anteriores las rutinas semánticas
anteriores pueden definirse como sigue:

Regla de producción Rutina semántica

EE+T POLACA[J++] = ‘+’;
TT*F POLACA[J++] = ‘*’;
POLACA[J++] = CARGA;
F  ident
POLACA[J++] = TS[p].dir;

Nota aclaratoria:
Observar que el arreglo POLACA se utiliza en dos momentos diferentes: durante la
generación del código y durante la ejecución de la forma interna. Es por eso que para evitar
confusiones lo indizamos con variables diferentes cada vez: ACT y J, respectivamente.
Asimismo, la pila auxiliar SEM solo se utiliza (en las rutinas semánticas) para la generación de
la forma interna, y no existe en el momento de la ejecución. En este caso utilizamos la pila
de ejecución PILA.

2. Elementos de arreglo

Cuando en una sentencia aparece un elemento de arreglo es necesario calcular, a partir de los valores
concretos de sus índices, la dirección de dicho elemento en memoria, ya sea para utilizar su valor o para
almacenar en él un resultado.

Veamos a continuación la forma en que se puede calcular la dirección de un elemento de arreglo.

En la mayoría de los lenguajes de programación los elementos de un arreglo se almacenan en memoria
en localizaciones sucesivas, variando más rápidamente los índices más a la derecha. Así por ejemplo, un
arreglo:

A[1..m, 1..n]

se almacena en la forma

A[1,1], A[1,2], ...., A[1,n], A[2,1], A[2,2], ..., A[2,n], ..., A[m,1], A[m,2], ..., A[m,n]

Luego, si asumimos que cada elemento del arreglo ocupa long bytes, la dirección del elemento A[i, j] es:

dir(A[i, j] ) = dir(A[1, 1] ) + long*[(i-1)*n + j-1].

Para un arreglo de tres dimensiones A[1..n1, 1..n2, 1..n3] la dirección del elemento A[i, j, k] es:

dir(A[i, j, k]) = dir(A[1, 1, 1]) + long*[(i-1)*n2*n3 + (j-1)*n3 + (k-1)].

En general, para un arreglo A[l1..u1, l2..u2, ..., ln..un] nos quedaría:

dir(A[i1, i2, …, in]) = dir(A[l1,l2, …,ln] ) + long*[(i1-l1)*r2*…*rn + (i2-l2)*r3*…*rn + (in-1-ln-1)*rn + (in-ln)]

donde:

r1 = u1–l1+1
r2 = u2–l2+1
...
rn = un–ln+1
long: cantidad de bytes que ocupa un elemento del arreglo.

La fórmula anterior puede factorizarse en una parte constante –que puede calcularse desde el momento
mismo de la compilación– y una parte variable que necesita ser calculada en tiempo de ejecución, en
dependencia de los valores de los índices. Separando ambos términos, podemos expresar la fórmula
como:

dir(A[i1, i2, …, in]) = ParteConst + ParteVar

donde:

ParteConst = dir(A[l1, l2, …, ln] ) - long*[((….(l1*r2 + l2)*r3 + l3)*r4 + … + ln-1)*rn + ln)]

ParteVar = long*((…(i1*r2 + i2)*r3 +…+ in-1)*rn + in

La expresión ParteVar(n) para un arreglo de dimensión n puede expresarse recursivamente como:

ParteVar(1) = i1;
ParteVar(2) = long*(i1*r2) + i2;
…
ParteVar(k) = ParteVar(k-1)*rk + ik.

En los lenguajes con asignación de memoria estática la cantidad de memoria necesaria para almacenar un
arreglo se conoce desde la compilación y durante la ejecución basta realizar la asignación según la
dirección de inicio (después del primer elemento del arreglo) y se pueden calcular las direcciones
efectivas de cada elemento, evaluando las fórmulas anteriores para los valores concretos de los índices.
La información necesaria para la evaluación de estas fórmulas se guarda en los denominados dope
vectores, los cuales pueden tener diferentes estructuras, nosotros asumiremos la siguiente:

n, long, l1, u1, r1, ..., ln, un, rn, ParteConst

Para calcular la dirección de un elemento de arreglo definimos el operador EARR, cuyos operandos serán
los valores de los índices de los elementos y la dirección del dope vector del arreglo, dejando al ejecutar
en el tope de la pila la dirección calculada.

Así, para el elemento de arreglo A[<expr1>, <expr2>, ..., <exprn>] la cadena polaca generada será:

R(<expr1>), R(<expr2>), ..., R(<exprn>), EARR, dir A

donde dir A representa la dirección del primer elemento del dope vector.

Ejemplo:

Para el elemento de arreglo A[b*c, i, –j] su codificación en notación polaca simbólica sería:

b, c, * , i, j, @, EARR, dir A

Luego, al ejecutar la forma interna, al llegar al operador EARR en la pila tendremos:

-j
I
b*c

Y necesitamos que al terminar la ejecución del operador EARR se tenga:

dir(A[])

Luego, la rutina semántica asociada al operador EARR sería:

dope = POLACA[++ACT];
dim = MEM(dope++);
long = MEM(dope++);
TOP -= dim–1;
if (MEM(dope) <= PILA[TOP] && PILA[TOP] <= MEM(dope+1))
{
ParteVar = PILA[TOP];
dope += 3;
TOP++;
}
else error("índice fuera de rango");
for (i=1; i<= dim–1; i++)
if (MEM(dope) <= PILA[TOP] && PILA[TOP] <= MEM(dope+1))
{
ParteVar = ParteVar*MEM(dope+2) + PILA[TOP];
dope +=3;
TOP++;
}
else error ("índice fuera de rango");
TOP -= dim;
PILA[TOP] = ParteVar*long + MEM(dope);
ACT++;

3. Rutinas semánticas para constantes, expresiones, elementos de arreglo y

asignación.

Veamos a continuación una gramática para sentencias de asignación algo más cercana a la realidad y
construiremos para ella las rutinas semánticas asociadas.

(1) <sent-asign>  <var> := <expr>

(2, 3) <var>  <ident> | <id-arreglo>[<lista de exp>]
(4) <id-arreglo>  <ident>
(5, 6) <list-de-exp>  <exp> | <lista-de-exp>, <exp>
(7, 8, 9, 10) <exp>  <exp> + <term> | <exp> - <term> | - <term> | <term>
(11, 12, 13) <term>  <term> * <factor> | <term> / <factor> | <factor>
(14, 15, 16) <factor>  (<expr>) | <var> | <constante>

Las rutinas semánticas asociadas a las reglas 7 a la 14 coinciden, en general, con las rutinas
anteriormente analizadas para la gramática simplificada anterior luego centraremos nuestra atención en
las reglas 1 a la 6 y las reglas 15 y 16.

Para la regla

(16) <factor>  <constante>

las acciones semánticas deben añadir a la cadena polaca los elementos:

CARGA, dir constante

sobre la base que el scanner al procesar una constante le cree una entrada en la tabla de símbolos similar
a un identificador. La rutina semántica sería:

POLACA[J++] = CARGA;
POLACA[J++] = TS[p].dir;

La regla

(2) <var>  <ident>

tiene dos posibles generaciones diferentes:

CARGADIR, dir ident

CARGA, dir ident

en función de que la reducción se haya hecho en la parte izquierda de la asignación o en el contexto de

una expresión. Si estamos en presencia del segundo caso, podríamos fácilmente detectar su ubicación, ya
que en tal caso, la próxima reducción sería por la regla:
(15) <factor>  <var>

Luego podemos generar siempre, al reducir por la regla 2 la primera variante, y al reducir por la regla 15
destruimos el CARGADIR inapropiado y lo sustituimos por un operador CARGA. Luego, la rutina
semántica asociada a estas dos reglas sería:

(2) <var>  <ident>

POLACA[J++] = CARGADIR;
POLACA[J++] = TS[p].dir;

(15) <factor>  <var> (más adelante será mejor definida esta rutina)

POLACA[J-2] = CARGA;

La regla

(4) <id-arreglo>  <ident>

debe tener asociada las acciones semánticas siguientes:

1. Chequear si el identificador realmente fue declarado como un identificador de arreglo

(supondremos un campo tipo en la tabla de símbolos de valor 2 si se trata de un identificador de
arreglo).
2. Guardar la dirección de entrada del identificador en la tabla de símbolos para utilizarlo después en
la regla
<var>  <id-arreglo>[<lista-de-exp>]
que se tendrá que reducir a continuación.
3. Colocar un cero en la pila semántica para posteriormente contar la dimensión con que el
identificador de arreglo ha sido utilizado para verificar que coincide con la declarada.

Luego su rutina semántica asociada podría ser:

if (TS[p].tipo ) <> 2
error("identificador de arreglo incorrecto");
else
{
SEM[++T] = p;
SEM[++T] = 0;
}

Para las reglas:

(5, 6) <list-de-exp>  <exp> | <lista-de-exp>, <exp>

su efecto semántico se reduce a ir contando la cantidad de expresiones aritméticas que van formando los
índices del elemento de arreglo que se reduce. Luego, para ambas la rutina semántica sería:

SEM[T]++;

Cuando se realiza la reducción por la regla

(3) <var>  <id-arreglo>[<lista-de-exp>]

se tiene en el tope de la pila semántica la cantidad de expresiones, y en el subtope la entrada en la tabla
de símbolos del ident de arreglo, y de otra parte se han generado la forma interna de las expresiones que
forman los índices, luego su semántica será:

p = SEM[T-1] ;
if (TS[p].dim <> SEM[T])
error("elemento de arreglo con referencia diferente a declaración");
else
{
POLACA[J++] = EARR;
POLACA[J++] = TS[p].dir;
}
T -= 2;

Nótese que la regla

(3) <var>  <id-arreglo>[<lista-de-exp>]

pudo haberse escrito también como

<var>  <ident>[<lista-de-exp>]

pero en tal caso no tendríamos forma de resguardar la entrada de ident en la tabla de símbolos.

Veamos a continuación una modificación que será necesario introducir a la rutina semántica de la regla

(15) <factor>  <var>

Anteriormente habíamos dicho que esta regla debe corregir el operador CARGADIR que escribió la rutina
de reducción por la regla

(2) <var>  <ident>

En realidad la regla 15 debe corregir dicho CARGADIR si la reducción anterior fue por la regla 2, pero si
la reducción anterior fue por

(3) <var>  <id-arreglo>[<lista-de-exp>]

lo que debe hacerse es sustituir la dirección que está en el tope de la pila por su valor asociado.
Definimos para esta función el operador CARGAIND. Luego, la rutina semántica asociada a la regla 15
debe ser:

if (POLACA[J-2] == 'EARR') // anteriormente se redujo por <var>  <id-arreglo>

POLACA[J++] = 'CARGAIND';
else // anteriormente se redujo por <var>  <ident>
POLACA[J-2 ] = 'CARGA';

Ejercicio propuesto:

1. Escriba la semántica del operador CARGAIND.