Semántica de Los Operadores en FI

Conferencia 2: Semántica de los operadores de Forma Interna
2.1 Constantes
2.2 Expresiones booleanas
2.3 Saltos
Bibliografía: Construcción de Compiladores. David Gries. Cap. Pág.
Semántica de los operadores en forma interna del tipo notación polaca:
En los ejemplos anteriores hemos evaluado las expresiones escritas en notación polaca como si
tuviéramos el valor de los operandos en la propia representación, lo cual en general no es posible
debido a que al momento de generarse la notación polaca no se conoce en general dicho valor,
luego en realidad cuando se va a evaluar una expresión lo que puede aparecer como parte de la
notación polaca es, o bien, la dirección del operando, o su entrada en la tabla de símbolos.
Luego si tenemos la expresión A:=B+A*D su notación polaca en realidad sería:

dir A, dir B, dirA, dir D, *, +, := .
Luego si fuésemos a evaluar dicha representación con ayuda de una pila, como hemos hecho hasta
el momento tendríamos:
Dir D
Dir A
Dir B
Dir A
Y al evaluar el operador * tendríamos:
A*D
Dir B
Dir A
Lo cual complica enormemente la lógica de evaluación de los operandos ya que en algunos casos se
tendría en la pila direcciones y otros casos el valor de los operandos. Para evitar lo anterior puede
implementarse un operador denominado CARGA, el cual coloca en la pila el valor contenido en
una dirección dada.
Haciendo uso de este operador la expresión A+B se escribiría:

CARGA, dir A, CARGA, dir B, +
con lo cual volveremos a tener en la pila solo valores.
Veamos a continuación como se podría representar la semántica de los diferentes operadores en

notación polaca.
Simbología:
POLACA: arreglo que contiene los componentes de la notación polaca.
ACT: apuntador a la posición actual del arreglo polaca.
PILA: arreglo para simular la pila de ejecución.
TOP: apuntador al tope de la pila.
MEM: función que en función de una entrada a la tabla de símbolos nos
devuelve el valor del símbolo.
Con los criterios anteriores la semántica del operador CARGA sería:
PILA[++TOP] = MEM(POLACA[++ACT]);
++ACT;
Con el operador CARGA no se resuelven todos los problemas, veamos que sucedería, por ejemplo
si tenemos la sentencia:
A:=B+A*D
Al evaluar los operadores * y + con la inclusión del operador CARGA, se resuelve la situación de
tener en la pila valores de los operandos, sin embargo, para evaluar el operador := necesitamos
cargar en la pila la dirección del operando a y no su valor.
Para resolver esta situación podemos introducir el operador CARGADIR, el cual lleva a la pila la
dirección del operando que le sigue en la cadena polaca.
Así la expresión anterior se podría escribir en la forma:
CARGADIR, dir A, CARGA, dir B, CARGA, dir A, CARGA, dir D, *, +, :=
Y la semántica del operador CARGADIR sería:
PILA[++TOP] = POLACA[++ACT];
++ACT;
La notación polaca usual (A,b,+) se denomina notación polaca simbólica y la notación polaca con
los operadores añadidos se denomina notación polaca explícita.
2.1 Constantes en la notación polaca
Las constantes que aparecen en las expresiones pueden representarse en la cadena polaca de dos
formas diferentes:
1.- Colocar la dirección de la constante en la cadena polaca.
2.- Colocar el valor de la constante en la cadena polaca.
La primera variante permite una más amplia categoría de constantes pero utiliza más memoria e
implica un mayor tiempo de ejecución.
Así por ejemplo la expresión A:=2*B+C-4 se podría representar como:
cargardir, dir A, CARGA, dir 2, CARGA, dir B, *, CARGA, dir C, +, CARGA, dir 4, -, :=
La segunda variante podría implementarse mediante el operador CARGADIR:
CARGADIR, dir A, CARGADIR, 2, …
Semántica de los operadores aritméticos:

Los operadores aritméticos encuentran el valor de sus operandos en el tope y el subtope de la pila, si
son binarios o en el tope si es un operador unario.
Estos operadores deben realizar la operación indicada eliminar dos operandos de la pila y colocar el
resultado en el nuevo tope de esta.
Así por ejemplo:

Suma:
PILA[TOP-1] += PILA[TOP--];
ACT++;
Resta:
PILA[TOP-1] -= PILA[TOP--];
ACT++;
Operador de asignación:
Este operador debe encontrar en el subtope de la pila la dirección donde debe asignar el valor, el
cual se encuentra en el tope y a continuación elimina valor y dirección de la pila:
MEM2(PILA[TOP-1] , PILA[TOP]);
TOP -= 2;
++ACT;
En esta rutina semántica se ha hecho uso de la función MEM2, que recibe 2 argumentos: la
dirección de una variable y un valor, y asigna a la variable el valor dado.
2.2 Expresiones booleanas
Para representar valores lógicos, asumiremos el convenio siguiente:

True  0
False = 0
Así la notación polaca explícita de la expresión a && ~b || c sería:
CARGA, dir a, CARGA, dir b, NOT, AND, CARGA, dir c, OR
y, por tanto la semántica del operador AND sería:
if (PILA[TOP-1] != 0 && PILA[TOP] != 0)

PILA[TOP-1]=1
else
PILA[TOP-1]=0;
--TOP;
++ACT;
o simplemente
PILA[TOP-1] &&= PILA[TOP--];

ACT++;
Para evaluar expresiones booleanas que contengan operadores relacionales debe, similarmente ,
definirse la semántica de dichos operadores, así por ejemplo la semántica del operador >= podría
ser
if (PILA[TOP-1] >= PILA[TOP] )

PILA[TOP-1] = 1;
else
PILA[TOP-1] = 0;
--TOP;
++ACT;
o simplemente:
PILA[TOP-1] = PILA[TOP-1] >= PILA[TOP--];

ACT++;
2.3 Saltos
A continuación estudiaremos la representación de los saltos en forma interna y las rutinas semánticas
correspondientes. Los saltos pueden ser, como ya sabemos, incondicionales o condicionales.
Saltos incondicionales
Una sentencia del tipo goto A podría representarse de dos formas diferentes:
a) SE, dirA, donde dirA representa la entrada del identificador A en la tabla de símbolos, en tal caso se
deberá guardar allí en su momento la dirección real del salto. Esta representación presupone que el
operador encuentra a continuación de él en la cadena polaca la dirección de la entrada de A en la tabla de
símbolos, luego su semántica sería:
ACT = TS[POLACA[ACT+1]].Dir;
b) SI, n, donde n sería el valor de la nueva posición en polaca hacía donde se realiza el salto. La rutina
semántica en este caso es:
ACT = POLACA[ACT+1];
Saltos condicionales
Para generar la cadena polaca de una sentencia del tipo:
if (<exp bool>)
<sent1>
else
<sent2>
Podemos utilizar el operador SSF (salta si falso ) en la forma siguiente:
R(<exp.bool>), SSF, (a),
donde (a) representa la dirección en la cadena polaca hacia donde se debe saltar en caso de ser falsa la
condición. En caso de un if completo en la dirección (a) en polaca se codificaría la sentencia a ejecutar
asociado al else.
El operador SSF encuentra en el tope de la pila el valor de la condición y debe realizar el salto si dicho valor
es cero, en caso contrario debe continuar en secuencia:
Su semántica sería:
if (!PILA[TOP--])
ACT = POLACA[ACT+1];
else
ACT+=2;
Luego la notación polaca de la sentencia sería:

________________
 
R(<exp bool>), SSF, , R(<sent1>), SI, , R(<sent2>), ,
__________
Ejemplo:
if a+1 <= c
then a:=k+1
else p:=k+p-1
nos quedaría:
_______________
 
a, 1, +, c, <=, SSF, , a, k, 1, +, :=, SI, , p, k, p, +, 1, -, :=,
______________

Semántica de Los Operadores en FI

Cargado por

Copyright:

Formatos disponibles

Semántica de Los Operadores en FI

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Semántica de Los Operadores en FI

Cargado por

Copyright:

Formatos disponibles

Conferencia 2: Semántica de los operadores de Forma Interna

Bibliografía: Construcción de Compiladores. David Gries. Cap. Pág.

Semántica de los operadores en forma interna del tipo notación polaca:

Luego si tenemos la expresión A:=B+A*D su notación polaca en realidad sería:

Y al evaluar el operador * tendríamos:

Haciendo uso de este operador la expresión A+B se escribiría:

Veamos a continuación como se podría representar la semántica de los diferentes operadores en

CARGADIR, dir A, CARGA, dir B, CARGA, dir A, CARGA, dir D, *, +, :=

Y la semántica del operador CARGADIR sería:

2.1 Constantes en la notación polaca

La segunda variante podría implementarse mediante el operador CARGADIR:

CARGADIR, dir A, CARGADIR, 2, …

Semántica de los operadores aritméticos:

Así por ejemplo:

2.2 Expresiones booleanas

Para representar valores lógicos, asumiremos el convenio siguiente:

Así la notación polaca explícita de la expresión a && ~b || c sería:

CARGA, dir a, CARGA, dir b, NOT, AND, CARGA, dir c, OR

y, por tanto la semántica del operador AND sería:

if (PILA[TOP-1] != 0 && PILA[TOP] != 0)

PILA[TOP-1] &&= PILA[TOP--];

if (PILA[TOP-1] >= PILA[TOP] )

PILA[TOP-1] = PILA[TOP-1] >= PILA[TOP--];

Para generar la cadena polaca de una sentencia del tipo:

Podemos utilizar el operador SSF (salta si falso ) en la forma siguiente:

R(<exp.bool>), SSF, (a),

Luego la notación polaca de la sentencia sería:

También podría gustarte