PDF de programación - Introducción a compiladores y lenguajes formales - Fundamentos de compiladores

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

© Todos los derechos de propiedad intelectual de esta obra pertenecen en exclusiva a la Universidad
Europea de Madrid, S.L.U. Queda terminantemente prohibida la reproducción, puesta a disposición del
público y en general cualquier otra forma de explotación de toda o parte de la misma.

La utilización no autorizada de esta obra, así como los perjuicios ocasionados en los derechos de
propiedad intelectual e industrial de la Universidad Europea de Madrid, S.L.U., darán lugar al ejercicio
de las acciones que legalmente le correspondan y, en su caso, a las responsabilidades que de dicho
ejercicio se deriven.

2





Índice

Presentación

¿Por qué son necesarios los compiladores?

¿Cómo nos independizamos de la máquina?

Herramientas necesarias para los compiladores

Proceso de compilación

Fases de la compilación

¿Cómo diseñamos un compilador?

¿Cómo diseñamos un compilador?

Compilador cruzado

¿Por qué es importante entender los compiladores?

Resumen

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

4

5

7

9

13

16

20

21

22

23

24

3
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.

INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES



Presentación

El objetivo de este tema es que el estudiante comprenda la problemática asociada a los
compiladores, cuál fue su origen, por qué son necesarios y cómo han evolucionado, además de
presentar una visión global que permita identificar las distintas fases que los componen.

Los objetivos a conseguir en este tema son:

Saber por qué son necesarios los compiladores.

Conocer cómo nos independizamos de la máquina.

Conocer los tipos de compiladores y las fases de un compilador.

Reconocer cómo se diseña un compilador.

Motivaciones.

Veremos, por tanto, una reseña histórica para entender por qué era importante independizarse
de la máquina, así como las herramientas necesarias para compilar un programa y por qué son
necesarias. Debe verse el proceso de desarrollo de un compilador como un caso especial de
ingeniería del software.

4
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

¿Por qué son necesarios los compiladores?

Con la llegada de John Von Neumann al proyecto ENIAC (1945), y tras sufrir la problemática de
tener que cablear el ordenador para cada nueva tarea, decide resolver este problema. Lo
consigue en 1949, escribiendo secuencias de código o programas que hacen que estos
ordenadores realizaran los cálculos deseados. Estos programas se escribían utilizando códigos

numéricos que representaban las operaciones que se iban a realizar. El lenguaje utilizado para
construir estos programas se denominó lenguaje máquina porque estaba totalmente relacionado
con el hardware de la máquina.

Como se puede ver en el siguiente

ejemplo, esta

forma de escribir un

programa es difícil y tediosa, por lo que

pronto se dio nombre a los códigos de

las operaciones y a las direcciones de

memoria.

Código máquina vs código

ensamblador

Con el lenguaje ensamblador se mejoró
enormemente la velocidad y exactitud
con la que se escribían los programas. De hecho, todavía se encuentra en uso en situaciones

Máquina ENIAC (Electronic Numerical Integrator and
Computer) en Philadelphia, Pennsylvania (US Army)

donde se necesita velocidad y se tiene poco espacio para el código.

De todas formas, el lenguaje ensamblador no es perfecto. Sus principales desventajas son:

No es fácil de escribir.

Es difícil de leer y entender.

Depende de la máquina para la que se ha escrito.

5
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

Ejemplo

Ejemplo de código máquina vs código ensamblador

Un ejemplo de este código máquina es el siguiente:

Código máquina
Ensamblador

Código operación
00010101
LOAD

Dirección
10000011
X

6
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

¿Cómo nos independizamos de la máquina?

Como ya se ha indicado, el ensamblador depende totalmente de la máquina para la
que se ha escrito, y esto implica reescribir otra vez el programa si se va a ejecutar
en otra máquina. Por tanto, una vez superado el problema del cableado de la

máquina para cada nuevo programa, ahora el objetivo a conseguir era

independizarse de la máquina.

Es decir, se trataba de generar un código intermedio, denominado código objeto, que nos
ahorrara recordar las direcciones de memoria, así como otros aspectos totalmente ligados con
la máquina. Se pensaba que no iba a ser fácil, además de poco eficiente. Aquí vemos un ejemplo

de lo que se estaba buscando:

Ensamblador
Código

Codigo operación
MOV X, 5
X = 5

Dirección
10000011
X

Había que conseguir crear un lenguaje que nos permitiera realizar acciones de tal forma que
fuera fácil de manejar y aprender por una persona. Este tipo de lenguajes se denominó de alto
nivel, en contraposición con los de bajo nivel (código máquina y ensamblador) totalmente
dependientes de la máquina.

De esta forma, se llegó al que se denomina el primer compilador realizado por Grace Hopper,
el A-0. Se empezó a trabajar en él en el otoño de 1951 y la primera rutina "compilada" se probó

con éxito en un UNIVAC en la primavera de 1952 (Hopper & Mauchly, 1953). El concepto de

compilador de estos momentos consistía en la aceptación del pseudocódigo, su decodificación,

la búsqueda de la subrutina apropiada, la asignación de las direcciones de memoria a las

subrutinas en el programa, la selección e inserción de las posiciones de memoria de los

argumentos y resultados, la organización de la transferencia del control y la escritura del

programa terminado en una cinta. Esto era más un cargador o enlazador que el concepto actual
de compilador, pero fue la primera vez que se usó la palabra compiler.

Por otro lado, en 1954, John Backus comenzó el desarrollo de un compilador de FORTRAN para
IBM, concretamente para el IBM 704, que le llevó dos años y medio y 18 hombres para realizarlo.

Consistió en dos componentes: el lenguaje FORTRAN y el traductor para el IBM 704. Este
desarrollo fue un verdadero compilador tal y como lo entendemos actualmente.

7
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

UNIVAC

Máquina UNIVAC (US Army)

8
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

Herramientas necesarias para los compiladores

A continuación se indican las herramientas software necesarias para que el proceso de
compilación se realice de una forma adecuada y completa:

9
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

10
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

11
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

12
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

Proceso de compilación

La figura muestra el proceso de compilación, para, a partir de un fichero con el código fuente,
obtener un fichero con el código ejecutable.

13
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

14
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

15
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

Fases de la compilación

En esta figura vemos las fases por las que pasa un programa fuente desde que es recibido
por el analizador léxico hasta que se genera el código objeto y que va al cargador/enlazador para

su ejecución.

16
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

17
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

18
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

19
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LENGUAJES FORMALES

FUNDAMENTOS DE COMPILADORES

¿Cómo diseñamos un compilador?

Hasta ahora hemos partido de un lenguaje fuente y se trata de obtener el lenguaje objeto, pero no
hemos tenido en cuenta el lenguaje de implementación del propio compilador, que es
necesario para proporcionar la visión global necesaria para el diseño del mismo.

A la hora de diseñar un compilador utilizamos los diagramas de Tombstone, que son un conjunto

de piezas de puzzle muy útiles para esta tarea y que a su vez tienen unas reglas:

20
© Univ ersidad Europea de Madrid. Todos los derechos reserv ados.





INTRODUCCIÓN A COMPILADORES Y LEN