Download Lenguajes de Programación - Universidad Nacional del Sur

Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Lenguajes de Programación
Implementación de unidades
Ma. Laura Cobo
Universidad Nacional del Sur
Departamento de Ciencias e Ingeniería de la Computación
2017
Prof. Ma. Laura Cobo
Página 1
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
Si nuestro lenguaje considera unidades, nuestro procesador
abstracto debe considerar la unidad de activación de P. La
unidad de activación contiene toda la información relevante en
ejecución de la unidad.
Unidad de activación de
Unidad P
la unidad P
Segmento de código de P
Registro de activación de
P
2
Prof. Ma. Laura Cobo
Página 2
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
El registro de activación de P contiene la información sobre los
objetos de datos, del sistema y declarados en la unidad
registro de activación de
la unidad P
Dirección Registro de
activación P
Objetos de datos del
Sistema
Objetos de datos asociados
a las declaraciones en P
3
Prof. Ma. Laura Cobo
Página 3
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
El acceso a cualquier objeto de dato declarado en P, se calcula como:
Dirección Registro de Activación P + desplazamiento de la variable
Unidad P
…..
var x: real
……
x
……
En la declaración se determina el
desplazamiento de la variable x
En la uso se accede a la misma
mediante la fórmula:
Dir. RA P + desplazamiento de x
4
Prof. Ma. Laura Cobo
Página 4
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
El acceso a cualquier objeto de dato declarado en P, se calcula como:
Dirección Registro de Activación P + desplazamiento de la variable
registro de activación de
la unidad P
Dirección Registro de
activación P
Desplazamiento de x
Objetos de datos del
Sistema
Objeto de dato x
5
Prof. Ma. Laura Cobo
Página 5
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
Si tratamos con unidades simples, sin parámetros, el único objeto
del sistema que resulta imprescindible guardar es el puntero de
retorno.
registro de activación de
la unidad P
Dirección Registro de
Puntero de retorno
activación P
Objetos de datos asociados
a las declaraciones en P
6
Prof. Ma. Laura Cobo
Página 6
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
Los lenguajes de programación puede ser clasificados de
acuerdo las decisiones que toman en diseño. Se puede
clasificar de acuerdo al manejo de memoria y a las regla de
alcance.
La clasificación de acuerdo al manejo de memoria que utilizan
no conduce a lenguajes:
Estático
Basado en pila
Dinámico
7
Prof. Ma. Laura Cobo
Página 7
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Agregando unidades
Por otro lado la clasificación de acuerdo a las reglas de alcance y al
esquema de manejo de memoria:
Alcance estático
• Alocación estática
• Alocación semiestática (basada en pila)
• Alocación semidinámica (basada en pila)
• Alocación dinámica (basada en pila)
Alcance dinámico
Finalmente si tomamos en cuenta la resolución de invocaciones a objetos
de datos
Acceso local
Acceso global
Esquema de alocación
8
Prof. Ma. Laura Cobo
Página 8
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
En compilación se determina:
El alcance de cada variable y el ambiente de
referenciamiento de cada unidad.
El espacio requerido para mantener cada variable local a la
unidad y su desplazamiento dentro del registro de
activación.
El espacio requerido para ejecutar la unidad.
La asociación entre cada variable local del código y cada
objeto de dato del registro de activación a través del par:
dirección base del registro de activación + desplazamiento.
La asociación entre cada variable global del código y cada
objeto de dato en el área compartida: dirección base del
área compartida + desplazamiento.
9
Prof. Ma. Laura Cobo
Página 9
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
En vinculación se conoce el desplazamiento de:
La primera instrucción de cada unidad en el área de código
C, respecto a una dirección base dC.
Cada registro de activación en el área de datos, respecto a
una dirección base dD.
En la carga del programa:
Se reserva espacio de almacenamiento para todo el
código y todos los registros de activación.
Cada segmento de código queda asociado a un único
registro de activación.
10
Prof. Ma. Laura Cobo
Página 10
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono local:
Programa
program main
integer i,j
i:= 1
k:= 1
j:= i + k
Desplazamiento Identificador
Tipo
0
i
Integer
1
j
Integer
2
k
Integer
Observaciones:
- k está declarada en forma implícita.
- El desplazamiento 0 corresponde al
puntero de retorno.
11
Prof. Ma. Laura Cobo
Página 11
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono local:
Programa
program main
integer i,j
Segmento de código
SET Main+,1
i:= 1
k:= 1
j:= i + k
SET Main+2,1
SET Main+1, D[Main+0]+D[Main+2]
12
Prof. Ma. Laura Cobo
Página 12
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono local:
Segmento de código
Programa
program main
integer i,j
i:= 1
k:= 1
j:= i + k
SET Main+o,1
SET Main+2,1
SET Main+1, D[Main+0]+D[Main+2]
Registro de activación
0
i
1
j
2
k
3
13
Prof. Ma. Laura Cobo
Página 13
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono local:
Segmento de código
Unidad
SET dP+1,1
subroutine P
integer i,j
i:= 1
k:= 1
j:= i + k
SET dP+3,1
SET dP+2, D[dP+1]+D[dP+3]
Registro de activación
0
Puntero de retorno
1
i
2
j
3
k
14
Prof. Ma. Laura Cobo
Página 14
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono global:
Programa
subroutine unit
integer i,j
common k
Desplazamiento Identificador
Tipo
1
i
Integer
2
j
Integer
0
k
Integer
i:= 1
k:= 1
j:= i + k
15
Prof. Ma. Laura Cobo
Página 15
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono global:
Programa
subroutine unit
integer i,j
common k
Segmento de código
SET unit+1,1
SET Common+0,1
i:= 1
k:= 1
j:= i + k
SET unit+2, D[unit+1]+D[Common+0]
16
Prof. Ma. Laura Cobo
Página 16
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Acceso al entrono global:
Segmento de código
Programa
subroutine unit
integer i,j
common k
SET unit+1,1
SET Common+0 ,1
SET unit+2, D[unit+1]+D[Common+0]
Registro de activación
i:= 1
k:= 1
j:= i + k
0
k
1
puntero de retorno
2
i
3
j
17
Prof. Ma. Laura Cobo
Página 17
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Programa
dC
Segmento
de código
dD
Registro de
activación
program main
main
subroutine P
subroutine Q
cP
main
dP
subroutine P
cQ
subroutine Q
subroutine P
dQ
dCO
subroutine Q
Common
18
Prof. Ma. Laura Cobo
Página 18
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Programa
Segmento de código
dC
dD
program main
main
main
subroutine P
if x>0 goto 10
….
10: x=0
subroutine Q
Registro de
activación
110
SETR R1, D[dP+despx]<=0
dP
111
JUMP R1, 113
112
JUMP 125
..
……
125
SET dP+despx,0
dQ
subroutine Q
dCO
x
subroutine P
subroutine Q
cQ
Common
19
Prof. Ma. Laura Cobo
Página 19
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Programa
Segmento de código
dC
dD
Registro de
activación
program main
main
subroutine P
if x>0 goto 10
….
10: x=0
subroutine Q
110
SETR R1, D[dCo+despx]<=0
111
JUMP R1, 113
112
JUMP 125
..
……
125
SET dCo+despx,0
main
dP
subroutine P
dQ
subroutine Q
dCO
cQ
subroutine Q
Common
x
20
Prof. Ma. Laura Cobo
Página 20
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Activación de una unidad, pasos a realizar:
Guardar el puntero de retorno en el primer objeto de dato
del registro de activación de la unidad llamada.
Actualizar el IP con la dirección de la primera instrucción de
la unidad llamada.
La traducción involucra estas dos instrucciones del procesador
abstracto:
SET dU,IP+2 (se guarda en área de datos una dirección
del área de código)
JUMP cU.
21
Prof. Ma. Laura Cobo
Página 21
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Retorno de una unidad, paso a realizar:
Transferir el control recuperando el puntero de retorno
almacenado en el primer objeto de dato del registro de
activación de la unidad llamada.
La traducción involucra esta instrucción del procesador abstracto:
JUMP D[dU].
22
Prof. Ma. Laura Cobo
Página 22
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo, sea el siguiente programa:
Programa
Unidad P
Unidad Q
Program main
Subprogram P
Subprogram Q
integer i,j
integer i,k
integer i,m,n
common x,y
common x,y
common x,y
call P
call Q
x = m*n
j = i*x
…..
….
…..
End
End
End
23
Prof. Ma. Laura Cobo
Página 23
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Programa
program main
dC
Segmento
de código
dD
Registro de
activación
common
main
subroutine P
main
L1
subroutine P
subroutine Q
dMain
dP
subroutine P
L2
subroutine Q
dQ
subroutine Q
D[unidad+desplazamiento]
24
Prof. Ma. Laura Cobo
Página 24
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Programa
Identificador
Desplaz.
Unidad
Program main
i
0
main
integer i,j
j
1
main
common x,y
x
0
common
y
1
common
call P
j = i*x
…..
End
25
Prof. Ma. Laura Cobo
Página 25
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Programa
Segmento de código
Program main
SET dP, ip+2
integer i,j
JUMP L1
common x,y
SET Main+2, D[Main+1]+D[Common+0]
Registros de activación
call P
j = i*x
0
x
…..
1
y
End
0
Ptr. Ret
1
i
2
j
26
Prof. Ma. Laura Cobo
Página 26
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Unidad P
Identificador
Desplaz.
Unidad
Subprogram P
x
0
common
integer i,k
y
1
common
common x,y
i
1
P
k
2
P
call Q
…..
End
27
Prof. Ma. Laura Cobo
Página 27
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Segmento de código
Unidad P
SET dQ, ip+2
Subprogram P
JUMP L2
integer i,k
……
common x,y
JUMP D[dP+0]
call Q
Registro de activación
de P
…..
End
0
Ptr. Ret
1
i
2
k
28
Prof. Ma. Laura Cobo
Página 28
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Unidad Q
Subprogram Q
integer i,m,n
common x,y
x = m*n
Identificador
Desplaz.
Unidad
x
0
common
y
1
common
i
1
Q
m
2
Q
N
3
Q
….
End
29
Prof. Ma. Laura Cobo
Página 29
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
LP con Alcance Estático–Alocación Estática
Ejemplo
Segmento de código
Unidad Q
Subprogram Q
integer i,m,n
common x,y
SET common+0, D[dQ+2]*d[dQ+3]
….
……
JUMP D[dQ+0]
x = m*n
Registro de activación
de Q
….
End
Prof. Ma. Laura Cobo
0
Ptr. Ret
1
i
2
m
3
n
30
Página 30
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
En compilación:
Se determina la distancia entre la unidad que rereferencia
una variable y la unidad que contiene la declaración.
No es posible anticipar el espacio de memoria requerido
para ejecutar el programa.
31
Prof. Ma. Laura Cobo
Página 31
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
En ejecución:
Se reserva espacio de almacenamiento para el registro de
activación en el momento en que la unidad se activa.
Se conoce la dirección base de cada registro de activación.
Los registros de activación ocupan y liberan memoria
siguiendo un comportamiento de pila.
Cada segmento de código puede quedar asociado a varios
registros de activación
32
Prof. Ma. Laura Cobo
Página 32
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Programa
Programa
program main
program main
subroutine P
End P
subroutine P
subroutine Q
End Q
subroutine Q
End Q
End main
End P
End main
33
Prof. Ma. Laura Cobo
Página 33
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
main
P
Q
Programa
program main
subroutine Q
….
End Q
subroutine P
call Q
End P
Registro Activación
Main
actual
Registro Activación
P
actual
Registro Activación
Q
actual
call P
End main
34
Prof. Ma. Laura Cobo
Página 34
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Resulta necesario mantener la cadena dinámica de llamadas, en
orden de poder resolver las referencias no locales. Es por ello
que el registro de activación necesita mantener más
información que en el modelo anterior.
Registro de activación de la
unidad
puntero de retorno
enlace dinámico
35
Prof. Ma. Laura Cobo
Página 35
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
main
P
Q
Programa
actual
program main
subroutine Q
….
End Q
Puntero retorno
actual
subroutine P
call Q
End P
Puntero retorno
actual
call P
End main
36
Prof. Ma. Laura Cobo
Página 36
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Activación de una unidad, pasos a realizar:
Crear el registro de activación
Guardar puntero de retorno
Guardar enlace dinámico
Actualizar actual
Actualizar IP
37
Prof. Ma. Laura Cobo
Página 37
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Retorno de una unidad, paso a realizar:
Actualizar actual utilizando el enlace dinámico.
Actualizar IP utilizando el puntero de retorno.
Destruir el registro de activación
Este modelo admite Recursividad. En caso de utilizarlo, en la
cadena dinámica aparecen más de un registro de activación
asociados a la misma unidad.
38
Prof. Ma. Laura Cobo
Página 38
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
unidad
Tabla de
símbolos
registro de activación
de la unidad
declaraciones
Objetos de datos del
Sistema
Bloque ejecutable
Objetos de datos
asociados
a las declaraciones en P
39
Prof. Ma. Laura Cobo
Página 39
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno local – estructura de bloques anidados
Program main
Var i,j: real;
Identificador
Tipo
Anid.
Desplaz.
Procedure q
i
real
0
0
var j,k,l: real;
j
real
0
1
….
j
real
1
2
end q
k
real
1
3
….
l
real
1
4
End main
40
Prof. Ma. Laura Cobo
Página 40
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno local – estructura de bloques anidados
Program main
Var i,j: real;
Actual
a
Registro de
activación de Q
Procedure q
Ptr. Ret
var j,k,l: real;
Enlace dinámico
…., k:=j;
j
end q
k
….
l
Actual+3
End main
Segmento de código
SET Actual+3,D[Actual+2]
Prof. Ma. Laura Cobo
41
Página 41
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados
Program main
…..
main
P
Q
RA de P
Actual
Procedure q
var j,k,l: real;
…. i
end q
Procedure p
RA main
RA de Q
Ptr. Ret
Ptr. Ret
Enlace
dinámico
Enlace
dinámico
I
j
Var i: real;
…. i
End P
End main
Prof. Ma. Laura Cobo
k
l
42
Página 42
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados - recursividad
Program main
Procedure p
main
P
P
Q
var i: real;
Procedure q
i
End q
End p
End main
RA main
RA de P
RA de P
RA de Q
RA
de
Ptr. Ret
Ptr. Ret
Ptr. Ret
actual
Enlace
dinámico
Enlace
dinámico
Enlace
dinámico
i
i
43
Prof. Ma. Laura Cobo
Página 43
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Si se resuelven los accesos no locales, en lenguajes con estructuras
de bloques anidados, se debe mantener información sobre el
enlace estático de la unidad. Una forma de hacerlo, es
manteniéndolo en el registro de activación de la unidad
Registro de activación de la
unidad
puntero de retorno
enlace dinámico
enlace estático
44
Prof. Ma. Laura Cobo
Página 44
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados
Program main
Var i,j: real;
Identificador
Tipo
Anid.
Desplaz.
Procedure q
i
real
0
0
var j,k,l: real;
j
real
0
1
j
real
1
3
end q
k
real
1
4
….
l
real
1
5
i
End main
La distancia entre el uso y el nivel de anidamiento de
la declaración es 1
45
Prof. Ma. Laura Cobo
Página 45
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados
Program main
Var i,j: real;
main
P
Q
RA main
Procedure q
i
var j,k,l: real;
j
RA de Q
RA
de
Ptr. Ret
actual
…..
Enlace
dinámico
i
end q
….
j
End main
k
El acceso al entorno global se
logra con D[Actual+2]
El acceso a la variable i con D[D[Actual+2]+0]
Prof. Ma. Laura Cobo
l
46
Página 46
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados
Program main
Var i,j: real;
Actual
Registro de
activación de Q
Procedure q
Ptr. Ret
var j,k,l: real;
Enlace dinámico
…., k:=i+j;
Enlace estático
end q
j
….
k
End main
Actual+3
l
Segmento de código
SET Actual+4,D[D[Actual+2]+3]+D[actual+3]
Prof. Ma. Laura Cobo
47
Página 47
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Acceso al entorno global – estructura de bloques anidados
Si la distancia es uno, como en el ejemplo, la situación se resuelve
con una indirección; sin embargo claramente la distancia puede
ser mayor.
La cantidad de indirecciones involucradas es igual a la distancia
entre el uso y la declaración. A mayor cantidad de indirecciones,
mayor es el costo
48
Prof. Ma. Laura Cobo
Página 48
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Alocación de memoria
Para trabajar con la pila de datos y tener el control de los registros
de activación vamos a contar con dos registros rápidos:
- actual: mantiene una referencia al comienzo del registro de
activación correspondiente a la unidad que se encuentra en
ejecución.
- libre: mantiene una referencia al área de datos a partir de
donde la misma está disponible para su uso.
La alocación de memoria sigue un comportamiento de pila
49
Prof. Ma. Laura Cobo
Página 49
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Alocación semi-estática de memoria
En compilación se determina:
- El espacio requerido para mantener cada variable local a una
unidad.
- El tamaño del registro de activación
- El desplazamiento de cada variable local dentro del registro
de activación.
- La distancia entre la unidad que referencia a una variable y
la unidad que contiene la declaración.
50
Prof. Ma. Laura Cobo
Página 50
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Alocación semi-estática de memoria
En compilación se determina:
- La asociación entre cada variable local del código y cada
objeto de dato del registro de activación a través del par:
[dirección base RA + desplazamiento].
- La asociación entre cada variable global del código y cada
objeto de dato en la Pila. La dirección base considera la
distancia entre la declaración y la referencia, utilizando la
cadena estática.
51
Prof. Ma. Laura Cobo
Página 51
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Activación de una unidad
a. Guardar el puntero de retorno:
se realiza a través de la siguiente instrucción
Pila[libre,0]  IP + T
Siendo T la cantidad de instrucciones que se van a saltear
dentro de la unidad llamadora (como mínimo hay que
saltear la instrucción JUMP que realiza la transferencia de
control, si hay pasaje de parámetros hay que saltear las
instrucciones vinculadas y otras)
b. Guardar enlace dinámico:
Pila[libre,1]  actual
52
Prof. Ma. Laura Cobo
Página 52
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Activación de una unidad
c. Guardar el enlace estático:
se realiza a través de la siguiente instrucción
Pila[libre,2]  expresión de cálculo de EE
Analizaremos la expresión de cálculo de EE a contiuación.
d. Actualizar actual:
actual  libre
e. Actualizar libre:
libre  libre + S
Siendo S el tamaño del registro de activación (objetos de datos
del sistema, parámetros y variables locales). Este tamaño es
calculado por el compilador
53
Prof. Ma. Laura Cobo
Página 53
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
f.
Actualizar IP:
se realiza a través de la siguiente instrucción
IP  dirección del segmento de código de la unidad invocada (Cc)
Si escribimos el código necesario para realizar la activación de la
unidad en términos de nuestro procesador abstracto,
tendríamos:
a. Guardar el puntero de retorno: ASIG IP+6, PILA[LIBRE,0]
b. Guardar enlace dinámico:
ASIG ACTUAL, PILA[LIBRE,1]
c. Guardar enlace estático:
ASIG exp. EE, PILA[LIBRE,2]
d. Actualizar actual:
ASIG LIBRE, ACTUAL
e. Actualizar libre:
ASIG LIBRE+S, LIBRE
f. Actualizar IP:
JUMP Cc
54
Prof. Ma. Laura Cobo
Página 54
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Alocación semi-estática de memoria
Para retornar de una unidad se realizan los siguientes pasos:
- Actualizar el valor del registro libre.
- Actualizar el valor del registro actual.
- Actualizar el valor de IP.
Retorno de una unidad
a. Actualizar libre:
se realiza a través de la siguiente instrucción
Libre  Actual
55
Prof. Ma. Laura Cobo
Página 55
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Alcance Estático–Alocación basada en pila
Retorno de una unidad
b. Actualizar actual:
actual  Pila[libre,1]
c. Actualizar IP:
IP  Pila[libre,0]
Si escribimos el código necesario para realizar el retorno de la
unidad en términos de nuestro procesador abstracto,
tendríamos:
a. Actualizar libre: ASIG ACTUAL, LIBRE
b. Actualizar actual: ASIG PILA[LIBRE,1], ACTUAL
c. Actualizar IP:
JUMP PILA[LIBRE,0]
56
Prof. Ma. Laura Cobo
Página 56
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Cálculo del enlace estático
Program Principal
Procedure Q
Procedure R
end R
end Q
Procedure P
End P
End Principal
Prof. Ma. Laura Cobo
Hay tres situaciones posibles:
1. Dos unidades (diferentes entre si) P y
Q, ambas del mismo nivel léxico donde
P Q.
2. Una unidad, Q, invoca a otra que está
declarada dentro de ella, R.
Q R
3. Una unidad, R, invoca a una unidad
que la contiene.
R Q
Página 57
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Cálculo del enlace estático
Program Principal
Procedure Q
Procedure R
end R
end Q
Procedure P
End P
End Principal
Prof. Ma. Laura Cobo
Situación 1: P Q.
En este caso, la distancia entre la unidad
llamadora y la llamada es igual a
cero(ambas tienen el mismo nivel
léxico) por lo tanto en enlace estático
de P es el enlace estático de Q
también.
Enlace estático de Q  PILA[ACTUAL,2]
En código del procesador abstracto
ASIG PILA[ACTUAL,2], PILA[LIBRE,2]
Página 58
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Cálculo del enlace estático
Program Principal
Procedure Q
Procedure R
end R
end Q
Situación 2: Q R.
En este caso, la distancia entre la unidad
llamadora y la llamada es igual a uno
por lo tanto en enlace estático de R es
la dirección del registro de activación
de la unidad llamadora , es decir Q.
Procedure P
End P
End Principal
Prof. Ma. Laura Cobo
Enlace estático de R  ACTUAL
En código del procesador abstracto
ASIG ACTUAL, PILA[LIBRE,2]
Página 59
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Cálculo del enlace estático
Situación 3: R
Program Principal
Procedure Q
Procedure R
end R
end Q
Procedure P
End P
End Principal
Q.
En este caso, la distancia entre la unidad llamadora
y la llamada es igual a negativa, -1. en este
caso debe existir una instancia de Q
suspendida anteriormente, ya que no habría
instancia de R sin alguna instancia de Q. existe
por lo tanto una forma de recursión cruzada
involucrada.
Se debe recorrer la cadena estática tantos niveles
como intervienen en la distancia
Enlace estático de Q  PILA[PILA[ACTUAL,2],2]
En código del procesador abstracto
ASIG PILA[PILA[ACTUAL,2],2], PILA[LIBRE,2]
Prof. Ma. Laura Cobo
Página 60
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Ejemplo
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Program Princ
Var i: integer
Procedure A
var j,k
Procedure B
call C
end B
i:= 0
call B
end A
i:=1
Procedure C
call C
if I <> 0 then call A
End Princ
end C
Prof. Ma. Laura Cobo
Página 61
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Ejemplo
A 10 SET D[Actual+2],0
B 1 SET Libre, IP+6
11 SET Libre, IP+6
2 SET Libre+1,Actual
15 SETR Libre, Libre+3
6 JUMP C
PROCEDURE B
Prof. Ma. Laura Cobo
17 SETR Libre,Actual
18 SETR Actual,D[Libre+1]
RETORNO
9 JUMP D[Libre]
16 JUMP B
RETORNO
8 SETR Actual,D[Libre+1]
13 SET Libre+2,Actual
14 SETR Actual,Libre
5 SETR Libre, Libre+3
7 SETR Libre,Actual
12 SET Libre+1,Actual
CALL B
4 SETR Actual,Libre
CALL C
3 SET Libre+2,D[D[Actual+2]+2]
19 JUMP D[Libre]
PROCECURE A
Página 62
Lenguajes de Programación
Departamento de Cs. e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre de 2017
Ejemplo
30 SETR Actual,0
C 20 JUMP D[D[Actual+2]]=0, X
31 SETR Libre,1
21 SET Libre, IP+6
32 SET Actual,1
22 SET Libre+1,Actual
24 SETR Actual,Libre
CALL A
23 SET Libre+2,D[Actual+2]
33 SET Libre, IP+6
34 SET Libre+1,Actual
35 SET Libre+2,Actual
26 JUMP A
36 SETR Actual,Libre
29 JUMP D[Libre]
RETORNO
28 SETR Actual,D[Libre+1]
CALL C
25 SETR Libre, Libre+3+2
X 27 SETR Libre,Actual
i:=1
37 SETR Libre, Libre+3
38 JUMP C
39 STOP
PROCEDURE C
Prof. Ma. Laura Cobo
Página 63