PDF de programación - Procesadores de Lenguajes - Tema 6. Tipos y generación de código

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Escuela Técnica Superior de Ingeniería Informática

Procesadores de Lenguajes

Tema 6
Tema 6

Tipos y generación de código
Tipos y generación de código

Javier Vélez Reyes
[email protected]

Javier Vélez Reyes [email protected]

Objetivos del Tema
Objetivos del Tema

Aprender a utilizar los ETDS para
(cid:132)(cid:132) Aprender a utilizar los ETDS para
Obtener información acerca de los tipos
(cid:132)(cid:132) Obtener información acerca de los tipos
Generar código intermedio
(cid:132)(cid:132) Generar código intermedio
Estudiar las relaciones entre
(cid:132)(cid:132) Estudiar las relaciones entre
Los tipos del lenguaje
(cid:132)(cid:132) Los tipos del lenguaje
La generación de código intermedio
(cid:132)(cid:132) La generación de código intermedio
Estudiar el uso de la tabla de símbolos
(cid:132)(cid:132) Estudiar el uso de la tabla de símbolos
Estudiar los problemas de ámbito
(cid:132)(cid:132) Estudiar los problemas de ámbito
Estudiar posibles representaciones intermedias
(cid:132)(cid:132) Estudiar posibles representaciones intermedias

1

Javier Vélez Reyes [email protected]

Índice General
Índice General

Tabla de símbolos
(cid:132)(cid:132) Tabla de símbolos
Los ámbitos y la tabla de símbolos
(cid:132)(cid:132) Los ámbitos y la tabla de símbolos
Representaciones intermedias
(cid:132)(cid:132) Representaciones intermedias
Código de tres direcciones
(cid:132)(cid:132) Código de tres direcciones
Árboles abstractos
(cid:132)(cid:132) Árboles abstractos
Grafos dirigidos acíclicos
(cid:132)(cid:132) Grafos dirigidos acíclicos
Código de Máquina virtual
(cid:132)(cid:132) Código de Máquina virtual
Sistema de tipos
(cid:132)(cid:132) Sistema de tipos
Sobrecarga de operadores
(cid:132)(cid:132) Sobrecarga de operadores
Comprobaciones y conversiones de tipos
(cid:132)(cid:132) Comprobaciones y conversiones de tipos

Javier Vélez Reyes [email protected]

Índice General
Índice General

Código intermedio
(cid:132)(cid:132) Código intermedio
Para expresiones
(cid:132)(cid:132) Para expresiones
Para sentencias de control de flujo condicional
(cid:132)(cid:132) Para sentencias de control de flujo condicional
Para sentencias de control de flujo iterativo
(cid:132)(cid:132) Para sentencias de control de flujo iterativo
Tipos compuestos
(cid:132)(cid:132) Tipos compuestos
La tabla de tipos
(cid:132)(cid:132) La tabla de tipos
Ámbitos y la tabla de tipos
(cid:132)(cid:132) Ámbitos y la tabla de tipos
Código intermedio para tipos compuestos
(cid:132)(cid:132) Código intermedio para tipos compuestos
Código intermedio para arrays
(cid:132)(cid:132) Código intermedio para arrays
Código intermedio para registros
(cid:132)(cid:132) Código intermedio para registros

2

Javier Vélez Reyes [email protected]

Tabla de símbolos
Tabla de símbolos

Tabla de símbolos
(cid:132)(cid:132) Tabla de símbolos
Es una tabla que se utiliza para almacenar los nombres
(cid:132)(cid:132) Es una tabla que se utiliza para almacenar los nombres
definidos por el usuario en el programa fuente
definidos por el usuario en el programa fuente
Variables
(cid:132)(cid:132) Variables
Análisis Léxico
Análisis Léxico
Nombres de funciones
(cid:132)(cid:132) Nombres de funciones
Nombres de tipos
(cid:132)(cid:132) Nombres de tipos

Análisis Sintáctico
Análisis Sintáctico

Tabla de
símbolos

Análisis Semántico
Análisis Semántico

Generación de
Generación de
código intermedio
código intermedio

Optimización de
Optimización de
código intermedio
código intermedio

Generación de
Generación de
código objeto
código objeto

Javier Vélez Reyes [email protected]

Tabla de símbolos
Tabla de símbolos

Se utiliza para comprobar
(cid:132)(cid:132) Se utiliza para comprobar
Uso de variables no declaradas
(cid:132)(cid:132) Uso de variables no declaradas
Variables declaradas varias veces
(cid:132)(cid:132) Variables declaradas varias veces
Incompatibilidad en los tipos de una expresión
(cid:132)(cid:132) Incompatibilidad en los tipos de una expresión
(cid:132)(cid:132) Etc.Etc.
Para cada entrada hay un registro de información
(cid:132)(cid:132) Para cada entrada hay un registro de información

Tipo de símbolo
Tipo de símbolo

Información
Información

Variable
Variable

Función
Función

TipoTipo

Nombre, tipo, tamaño, dirección
Nombre, tipo, tamaño, dirección

Nombre, tipo, comienzo del código
Nombre, tipo, comienzo del código

Nombre, tipo, tamaño
Nombre, tipo, tamaño

Constante
Constante

Nombre, tipo, tamaño, valor
Nombre, tipo, tamaño, valor

3

Javier Vélez Reyes [email protected]

Tabla de símbolos
Tabla de símbolos

Funciones
(cid:132)(cid:132) Funciones
Añadir un símbolo
(cid:132)(cid:132) Añadir un símbolo
Buscar un símbolo
(cid:132)(cid:132) Buscar un símbolo
Eficiencia en la búsqueda
(cid:132)(cid:132) Eficiencia en la búsqueda
Uso de tablas hash
(cid:132)(cid:132) Uso de tablas hash
Objetos como registros de información
(cid:132)(cid:132) Objetos como registros de información
Añadir implica buscar
(cid:132)(cid:132) Añadir implica buscar
Comprobar si existe el símbolo en la tabla
(cid:132)(cid:132) Comprobar si existe el símbolo en la tabla
Si existe emitir un error
(cid:132)(cid:132) Si existe emitir un error
Si no existe insertar el símbolo
(cid:132)(cid:132) Si no existe insertar el símbolo

Javier Vélez Reyes [email protected]

Tabla de símbolos
Tabla de símbolos

Ejercicio
(cid:132)(cid:132) Ejercicio
Dado el programa, ¿Cuál es su tabla de símbolos?
(cid:132)(cid:132) Dado el programa, ¿Cuál es su tabla de símbolos?

int a, b;
int a, b;
float c, d;
float c, d;
char e, f;
char e, f;

Tipo de símbolo
Tipo de símbolo

Información {TIPO, TAMAÑO, DIR}
Información {TIPO, TAMAÑO, DIR}

aa

bb

cc

dd

ee

ff

{ ENTERO, 2, 100 }
{ ENTERO, 2, 100 }

{ ENTERO, 2, 102 }
{ ENTERO, 2, 102 }

{ REAL, 4, 104 }
{ REAL, 4, 104 }

{ REAL, 4, 108 }
{ REAL, 4, 108 }

{ CARACTER, 1, 112 }
{ CARACTER, 1, 112 }

{ CARACTER, 1, 113 }
{ CARACTER, 1, 113 }

4

Javier Vélez Reyes [email protected]

Tabla de símbolos
Tabla de símbolos

La tabla de símbolos y los ETDS
(cid:132)(cid:132) La tabla de símbolos y los ETDS
Los símbolos deben insertarse cuando aparecen en G
(cid:132)(cid:132) Los símbolos deben insertarse cuando aparecen en G
Deben ubicarse correctamente las acciones semánticas
(cid:132)(cid:132) Deben ubicarse correctamente las acciones semánticas
Puede ser preciso rediseñar la gramática
(cid:132)(cid:132) Puede ser preciso rediseñar la gramática
En relación con la tabla de símbolos, los errores son
(cid:132)(cid:132) En relación con la tabla de símbolos, los errores son
Utilizar una variable no declarada
(cid:132)(cid:132) Utilizar una variable no declarada
Declarar dos veces una variable
(cid:132)(cid:132) Declarar dos veces una variable
Desbordamiento en memoria de la tabla de símbolos
(cid:132)(cid:132) Desbordamiento en memoria de la tabla de símbolos

Javier Vélez Reyes [email protected]

Los ámbitos y la Tabla de símbolos
Los ámbitos y la Tabla de símbolos
Ámbitos anidados
(cid:132)(cid:132) Ámbitos anidados
Pueden existir distintos ámbitos de declaración anidados
(cid:132)(cid:132) Pueden existir distintos ámbitos de declaración anidados
Cada ámbito declara variables
(cid:132)(cid:132) Cada ámbito declara variables
Pueden solaparse nombres
(cid:132)(cid:132) Pueden solaparse nombres
¿Cómo se resuelve b en (2)?
(cid:132)(cid:132) ¿Cómo se resuelve b en (2)?
Primero busca en (2)
(cid:132)(cid:132) Primero busca en (2)
Si no existe busca en (1)
(cid:132)(cid:132) Si no existe busca en (1)

{
{

}
}

}
}

5

int a, b;
int a, b;
a = 7;
a = 7;
if (true) {
if (true) {
int i, a;
int i, a;
a = 8;
a = 8;
b = a;
b = a;
i = a + b;
i = a + b;

a?

1

2

a, b, i?

a, b, i?

Javier Vélez Reyes [email protected]

Los ámbitos y la Tabla de símbolos
Los ámbitos y la Tabla de símbolos
Cuando se sale de un ámbito
(cid:132)(cid:132) Cuando se sale de un ámbito
Deben olvidarse las variables declaradas en él
(cid:132)(cid:132) Deben olvidarse las variables declaradas en él
Deben eliminarse las entradas de la tabla de símbolos
(cid:132)(cid:132) Deben eliminarse las entradas de la tabla de símbolos
Solución
(cid:132)(cid:132) Solución
O asociar un campo de ámbito a las entradas de la tabla
(cid:132)(cid:132) O asociar un campo de ámbito a las entradas de la tabla

O crear una pila de tabla de símbolos
(cid:132)(cid:132) O crear una pila de tabla de símbolos

2

a
i

1

a
b

1
1
2
2

a
b
a
i

Javier Vélez Reyes [email protected]

Los ámbitos y la Tabla de símbolos
Tabla de símbolos
Los ámbitos y la
Añadir un nuevo símbolo
(cid:132)(cid:132) Añadir un nuevo símbolo
Al añadir un nuevo símbolo se debe buscar sólo entre
(cid:132)(cid:132) Al añadir un nuevo símbolo se debe buscar sólo entre
los símbolos del mismo ámbito
los símbolos del mismo ámbito
Se comienzan las búsquedas comenzando desde el final
(cid:132)(cid:132) Se comienzan las búsquedas comenzando desde el final
de la tabla y terminando cuando se llega al principio de
de la tabla y terminando cuando se llega al principio de
la tabla o cuando el nivel de anidamiento es menor que
la tabla o cuando el nivel de anidamiento es menor que
el actual
el actual

Ejemplo
(cid:132)(cid:132) Ejemplo

1
1
2
2

a
b
a
i

6

Javier Vélez Reyes [email protected]

Los ámbitos y la Tabla de símbolos
Tabla de símbolos
Los ámbitos y la
Buscar un símbolo
(cid:132)(cid:132) Buscar un símbolo
Al buscar un símbolo que aparece en una instrucción se
(cid:132)(cid:132) Al buscar un símbolo que aparece en una instrucción se
debe buscar el símbolo desde el final de la tabla hasta el
debe buscar el símbolo desde el final de la tabla hasta el
principio, de manera que se encuentre el símbolo del
principio, de manera que se encuentre el símbolo del
ámbito no cerrado más cercano
ámbito no cerrado más cercano

Ejemplo
(cid:132)(cid:132) Ejemplo
Buscando b…
(cid:132)(cid:132) Buscando b…

1
1
2
2

a
b
a
i

Javier Vélez Reyes [email protected]

Los ámbitos y la Tabla de símbolos
Tabla