PDF de programación - Introducción a la tecnología de compiladores

Lenguajes de alto nivel y
compiladores

UNIVERSIDAD DE CANTABRIA

Introducción a la tecnología

de compiladores

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

4

© Javier Gutiérrez, Michael González

24/nov/08

1

Notas:

UNIVERSIDAD DE CANTABRIA

1. Compiladores
2. Análisis léxico
3. Análisis sintáctico
4. Conclusión

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

2

1. Compiladores

UNIVERSIDAD DE CANTABRIA

“Un compilador es un programa que lee un programa escrito
en un lenguaje, y lo traduce a un programa equivalente en otro
lenguaje.”

programa
en lenguaje

fuente

compilador

mensajes
de error

programa
en lenguaje

destino

Durante la traducción el compilador informa de la presencia
de errores en el programa fuente.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

3

Notas:

UNIVERSIDAD DE CANTABRIA

Existen multitud de compiladores para un gran número de lenguajes fuente y lenguajes destino.

Los compiladores se utilizan tanto para lenguajes de programación tradicionales, como Fortran, C o
Ada, o para aplicaciones especializadas como por ejemplo lenguajes de descripción de hardware,
lenguajes de programación de robots, etc.

Los primeros compiladores aparecieron a primeros de los años 50, como resultado de proyectos
para la traducción de fórmulas aritméticas en código máquina.

Los primeros compiladores eran costosos de implementar. Hoy en día existen técnicas sistemáticas
para construir compiladores que hacen más sencillo el proceso.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

4

Análisis y síntesis

UNIVERSIDAD DE CANTABRIA

Compilación

Análisis

Síntesis

Léxico:
“tokens”

Sintáctico:
instrucciones

Semántico:
significado

Generación
de código

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

5

Notas:

UNIVERSIDAD DE CANTABRIA

Existen dos partes importantes en la compilación:

• Etapa de análisis: Parte el programa fuente en sus piezas constituyentes y crea una

representación intermedia del mismo.
- Análisis léxico: separación de cada elemento componente del programa (“token”)
- Análisis sintáctico: separación de cada instrucción o sentencia del lenguaje, que agrupa

varios componentes léxicos o “tokens”.

- Análisis semántico: Se revisa el programa fuente para comprobar que las reglas semánticas
del lenguaje (aquellas relativas al significado de las distintas instrucciones) se cumplen. Un
ejemplo de regla semántica es la comprobación de tipos en las expresiones.

• Etapa de síntesis: Construye el programa destino deseado a partir de una descripción en un

lenguaje de representación intermedia.

De las dos partes de la compilación, la síntesis es la que requiere las técnicas más especializadas,
aunque en los lenguajes de programación modernos (Ada, C++, Java) la parte de análisis está
alcanzando una gran complejidad.

Durante la fase de análisis la estructura del programa se guarda en una estructura de datos especial
que suele ser un árbol: el árbol sintáctico.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

6

Análisis y síntesis (cont.)

UNIVERSIDAD DE CANTABRIA

Algunas herramientas presentan también una etapa de
análisis:

- Editores orientados al lenguaje
- Impresión con formato (“pretty printer”)
- Comprobadores estáticos de programas
- Intérpretes

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

7

Notas:

UNIVERSIDAD DE CANTABRIA

La etapa de análisis se encuentra en muchas herramientas además de los compiladores:

• Editores orientados al lenguaje: Además de facilitar la introducción de texto por el teclado

analiza el programa fuente y proporciona la estructura y jerarquía necesarias. Por ejemplo,
puede comprobar que la sintaxis es correcta, proporcionar palabras clave, etc.

• Impresión con formato (“Pretty Printer”): Analiza el programa fuente y lo imprime de forma que

la estructura del programa aparece claramente visible.

• Comprobadores estáticos: Permiten analizar un programa y descubrir errores potenciales sin
necesidad de ejecutar el programa. Por ejemplo, se pueden detectar zonas de código que
no se ejecutarán nunca, variables no inicializadas, errores sintácticos, comprobación de tipos,
etc.

• Intérpretes: En lugar de producir un programa destino mediante un proceso de traducción, el

intérprete ejecuta las operaciones que especifica el programa fuente.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

8

Fases de un compilador

UNIVERSIDAD DE CANTABRIA

Programa
Fuente

Analizador

Léxico

Tokens

Analizador
Sintáctico

Árbol

Sintáctico

Analizador
Semántico

Árbol

Sintáctico

Tabla de
Símbolos

Tabla de
Errores

Generador
cód. interm.

Código
Objeto

Generador

de cód. objeto

Código

Intermedio

Optimizador
de código

Código Intermedio

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

9

Notas:

UNIVERSIDAD DE CANTABRIA

En cada fase de un compilador se transforma el programa fuente de una representación a otra. Las
tres primeras fases forman la etapa de análisis, mientras las tres últimas forman la etapa de
síntesis.

La tabla de símbolos es una estructura de datos que almacena los identificadores utilizados en el
programa fuente así como los atributos de cada identificador. Estos atributos pueden proporcionar
información sobre el tipo del identificador, su tamaño, su rango de visibilidad, sus argumentos (en
caso de procedimientos), etc.

La tabla de símbolos tiene operaciones para encontrar un identificador rápidamente, y leer sus
atributos o modificarlos. Asimismo, permite introducir nuevos identificadores. Cada una de las fases
de compilación puede realizar modificaciones de los registros de una tabla de símbolos,
generalmente añadiendo más atributos a medida que se van conociendo.

El manejador de errores es un módulo que gestiona las acciones a realizar por cada uno de los
errores encontrados en las diferentes fases de la compilación. En general, es deseable que el
manejador de errores permita la continuación del proceso de compilación, con objeto de permitir
encontrar más errores en el programa. Las fases de análisis sintáctico y semántico son
habitualmente las que más errores encuentran.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

10

Ejemplo de análisis y síntesis

UNIVERSIDAD DE CANTABRIA

posicion := inicial + velocidad*60

Tabla de símbolos
1 posicion
...
2 inicial
...
3 velocidad ...
4 ...
...

Analizador Léxico

id1 := id2 + id3*60

Analizador Sintáctico

id1

:=

id2

+

*

id3

60

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

11

Notas:

UNIVERSIDAD DE CANTABRIA

Analizador Semántico

id1

:=

id2

+

*

id3

conv. a real

60

Generador de código intermedio

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

12

Ejemplo (cont.)

UNIVERSIDAD DE CANTABRIA

Generador de código intermedio

temp1 := conv_a_real(60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3

Optimizador de código

temp1 := id3 * 60.0
id1 := id2 + temp1

Generador de Código

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

13

Notas:

UNIVERSIDAD DE CANTABRIA

Generador de Código

MOVF id3 , R2
MULF #60.0 , R2
MOVF id2 , R1
ADDF R2 , R1
MOVF R1 , ID1

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

14

El contexto de un compilador

UNIVERSIDAD DE CANTABRIA

Preprocesador

Compilador

Ensamblador

Librerías

Enlazador

Programa fuente

Programa fuente final

Código Ensamblador

Objetos en
Código Máquina

Programa final

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

15

Notas:

UNIVERSIDAD DE CANTABRIA

Además de un compilador, otros programas pueden ser necesarios para crear un programa destino
ejecutable:

• Preprocesador: Un programa fuente puede estar dividido en módulos almacenados en ficheros
diferentes. La tarea de recopilar el código fuente almacenado en estos ficheros puede ser
encomendada a un preprocesador. Asimismo, un preprocesador puede expandir las macros
convirtiéndolas en instrucciones ejecutables.

• Ensamblador: Muchos compiladores proporcionan el programa final en lenguaje ensamblador.
Para poder obtener un programa ejecutable es preciso ensamblar este programa final con un
ensamblador convencional.

• Enlazador.Esta herramienta toma código máquina relocalizable de los diferentes objetos

compilados y de librería, modifica las direcciones relocalizables para situarlas a los valores
absolutos adecuados, y crea el programa ejecutable.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

16

2. Análisis léxico

UNIVERSIDAD DE CANTABRIA

Convierte una cadena de caracteres que conforma el
programa fuente en un grupo de “palabras”, que son
secuencias de caracteres con significado propio. Ejemplo:

if Existe then
posicion:=60;
end if;

la palabra reservada “if”
1.
la expresión booleana “Existe”
2.
3.
la palabra reservada “then”
4. el identificador “posicion”
5. el símbolo de asignación “:=”
6.
7. el final de instrucción “;”
la palabra reservada “end”
8.
9.
la palabra reservada “if”
10. el final de instrucción “;”

la constante “60”

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

24/nov/08

17

Notas:

UNIVERSIDAD DE CANTABRIA

Durante el análisis léxic