Comiladores

COMPILADORES

Visión histórica del desarrollo de los compiladores

•1946, se desarrolla el primer ordenador digital

Las instrucciones que se ejecutaban eran códigos numéricos, lenguaje de máquina., esto es engorroso, entonces surgen los ensamblador. Al inicio el programa se escribía mediante claves y luego se traducía manualmente al lenguaje de máquina. Cuando esto lo hizo la misma máquina, a este trabajo se le llamó ensamblar el programa.

•1950, John Backus dirige una investigación en IBM en un lenguaje algebraico

•1954, se comienza a desarrollar FORTRAN

•1957, FORTRAN se utiliza en la IBM modelo 704

•Surge el concepto traductor

•El primer compilador de FORTRAN tardó 18 años-persona en realizarse

•FORTRAN era dependiente de la máquina

•Paralelamente al desarrollo de FORTRAN en América, en Europa surge una corriente que pretende que los lenguajes fuesen independientes de la máquina, esta corriente estaba influida por los trabajos sobre GLC de Chomsky

•Surge un grupo Europeo encabezado por F.L. Bauer, en la que participó ACM y John Backus. De este grupo surge un informe que define un Lenguaje Algebraico Internacional, publicado en Zurich en 1958

•1969, aparece Algol 60

•Junto con los lenguajes también la técnica de los compiladores avanza

•1958, Strong y otros proponen una solución al problema de que un compilador fuera portable, y esta era dividir al compilador en dos fases “front end” (analiza el programa fuente) y “back end” (genera código objeto para la máquina objeto).

•El puente de unión era un lenguaje intermedio denominado UNCOL –Universal Computer Oriented Language(no funcionó)

•1959, Rabin y Scott proponen el empleo de AFD y AFN para el reconocimiento lexicográfico de los lenguajes

•Aparece BNF (Backus-1960, Naur-1963, Knuth-1964) como una guía para el desarrollo del análisis sintáctico

•1959, Sheridan describe un método de parsing de FORTRAN para introducir paréntesis en una expresión

•En los 60’s se desarrollan diversos métodos de parsers ascendentes y descendentes

•Floyd más adelante introduce la técnica de precedencia de operadores y uso de funciones de precedencia

•1961, se usa por primera vez un parsing descendente recursivo

•En los 60’s se estudia el paso de parámetros por nombre, valor y referencia y se incluyen los procedimientos recursivos para Algol 60

•Se desarrolla la localización dinámica de datos

•1968, se estudia y definen las GLC, los parsers predictivos y la eliminación de recursividad izquierda

•1975, aparece LEX generador automático de analizadores léxicos a partir de expresiones regulares bajo UNIX

•A mitad de los 70’s Johnson crea YACC para UNIX (generador de analizadores sintácticos)

•Ahora un compilador de divide en varias fases

•El último lenguaje de programación de amplia aceptación es JAVA (es interpretado)

Conceptos Básicos

Traductor. Cualquier programa que toma como entrada un texto escrito en un lenguaje llamado fuente y da como salida un programa equivalente en otro lenguaje, el lenguaje objeto.

Si el lenguaje fuente de un lenguaje de programación de alto nivel y el objeto un lenguaje de bajo nivel (ensamblador o código de máquina), al traductor se le denomina compilador.

Ensamblador. Es un programa traductor cuyo lenguaje fuente es el lenguaje ensamblador.

Intérprete. Es un programa que no genera un programa equivalente, sino que toma una sentencia del programa fuente en un lenguaje de alto nivel y la traduce al código equivalente y al mismo tiempo lo ejecuta.

En un principio debido a la escasez de memoria se utilizaban más los intérpretes, ahora se usan más los compiladores (a excepción de JAVA)

Ventajas de compilar vs a interpretar:

•Se compila una vez, se ejecuta n veces

•En ciclos, la compilación genera código equivalente, interpretándolo se traduce tantas veces una línea como veces se repite el ciclo

•El compilador tiene un visión global del programa

Ventajas del intérprete vs el compilador:

•Un intérprete necesita menos memoria que un compilador

•Permiten una mayor interactividad con el código en tiempo de desarrollo

Programas que el compilador necesita para obtener un programa ejecutable:

•Preprocesador. Se ocupa de incluir ficheros,expandir macros, eliminar comentarios.

•Ligador. Se encarga de construir el fichero ejecutable añadiendo al fichero objeto generado por el compilador las cabeceras necesarias y las funciones de librería utilizadas por el programa fuente.

•Cargador

•Depurador. Permite seguir paso a paso la depuración de un programa.

•Ensamblador

Tipos de compiladores:

•De una pasada

•De múltiples pasadas

•De carga y ejecución

•De depuración

•De optimización

•Ensamblador. El lenguaje fuente es ensamblador y posee una estructura sencilla.

•Compilador cruzado. Se genera código en lenguaje objeto para una máquina diferente de la que se está utilizando para compilar.

•Compilador con montador. Compilador que compila distintos módulos de forma independiente y después es capaz de enlazarlos.

•Autocompilador. Compilador que está escrito en el mismo lenguaje que va a compilar. Evidentemente, no se puede ejecutar la primera vez. Sirve para hacer ampliaciones al lenguaje y mejorar el código generado.

•Metacompilador. Es sinónimo de compilador de compiladores y se refiere a un programa que recibe como entrada las especificaciones del lenguaje para el que se desea obtener un compilador y genera como salida el compilador para ese lenguaje. No se ha logrado desarrollar, pero se han creado generadores de analizadores léxicos y sintácticos, como el lex y yacc para UNÍS. El inconveniente de estos, es que no son muy eficientes.

•Descompilador. Es un programa que acepta como entrada código máquina y lo traduce a un lenguaje de alto nivel, resultando el proceso inverso a la compilación. Hasta ahora no se han obtenido buenos descompiladores, sólo algunos desensambladores.

Modelo de análisis y síntesis de la compilación

Partes en la que está dividida la compilación: análisis y síntesis

La parte del análisis divide al programa fuente en sus elementos componentes y crea una representación intermedia del programa fuente. La parte de la síntesis construye el programa objeto deseado a partir de la representación intermedia. La síntesis es la que requiere las técnicas más especializadas.

Herramientas de software que realizan algún tipo de análisis a los programas fuente que manipulan:

1. Editores de estructuras. Esta herramienta toma como entrada una secuencia de órdenes para construir un programa fuente. No solo realiza las funciones de un editor de textos ordinario, sino que analiza el texto de un programa. Por ejemplo, puede proporcionar palabras clave de forma automática, puede saltar desde un ‘begin’ hasta su ‘end’. Además la salida de tal editor suele ser similar a la salida de la fase de análisis de un compilador.

2. Impresoras estéticas. Analizan un programa y lo imprimen de forma que la estructura de un programa resulte claramente visible. Por ejemplo combinando tipos o color de letra, colocando indentación.

3. Verificadores estáticos. Leen un programa, lo analizan e intentan descubrir errores potenciales sin ejecutar el programa, pueden ejecutar si existen partes de un programa que nunca se ejecutarán, o tratarán de descubrir errores lógicos como intentar utilizar una variable entera como apuntador.

4. Intérpretes. En lugar de producir un programa objeto como resultado de una traducción, un intérprete realiza las operaciones que implica un programa fuente.

La tecnología de compiladores se aplica en otros lugares, en especial la parte de análisis de los siguientes ejemplos es parecida a la de un compilador convencional:

•Formadores de Texto . Este toma como entrada una cadena de caracteres, la mayor parte dela cual es texto para componer, pero alguna incluye órdenes para indicar párrafos, figuras o estructuras matemáticas. P/E TEX.

•Compiladores de circuitos de silicio. Tiene un lenguaje fuente similar o idéntico a un lenguaje de programación convencional. Sin embargo, las variables del lenguaje no representan localidades de memoria, sino señales lógicas (0 o 1) o grupos de señales en un circuito de conmutación. La salida es el diseño de un circuito en un lenguaje apropiado.

•Intérpretes de consultas. Traducen un predicado que contiene operadores relacionales y boléanos a órdenes para buscar en una base de datos registros que satisfagan ese predicado.

Estructura de un compilador

Para la realización del proceso de traducción es necesario dividir el compilador en varias fases.

Al inicio de la historia de los compiladores :

1. Una computadora no tenía memoria suficiente

2. Se tuvo que dividir al compilador en fases

3. Cada fase leía un archivo y producía otro

Actualmente

1. Se tiene memoria suficiente

2. El tamaño del archivo ejecutable es relativamente pequeño

3. Se

...