COMPILADORES
INTRODUCCIÓN
M.C. José Andrés Vázquez Flores
Facultad de Ciencias de la Computación
[email protected]
FCC-BUAP
1
Introducción
¿Qué es un compilador (traductor)?
Programa que lee un programa (fuente) en un lenguaje ascii y lo traduce a un programa
EQUIVALENTE en otro lenguaje (objeto)
Además:
da mensajes de error
lleva a cabo determinadas “correcciones” (recuperación de errores)
puede optimizar el código generado
Permite programar “independientemente” de la
máquina
Importante, ya que el número de máquinas diferente crece deprisa
2
¿De dónde el nombre “compilador”?
Grace Murray Hopper (50’s)
La traducción se veía como la “compilación”
de una secuencia de subprogramas tomados
de una librería (biblioteca) de programas
Compilación (actual) se llamaba
“programación automática”
se veía como algo futurista
Primeros compiladores modernos:
FORTRAN (finales 50)
“independencia” de la máquina
4
No siempre el lenguaje objeto tiene que ser de “bajo nivel”
(traductor)
Técnicas aplicables para:
editores/formateadores de texto
nroff, troff, eqn, tbl, pic de UNIX,TeX
lenguajes de consulta
SQL, shells
transformación de formatos de ficheros
5
Clasificación de los lenguajes
Lenguajes máquina
– Son los lenguajes de más bajo nivel: secuencias binarias de
ceros y unos.
– Históricamente, los primeros
• Lenguajes ensambladores
– Segunda generación de lenguajes
– Versión simbólica de los lenguajes máquina (MOV, ADD).
• Lenguajes de alto nivel
– Lenguajes de tercera generación (3GL)
• Estructuras de control, Variables de tipo, Recursividad, etc.
• Ej.: C, Pascal, C++, Java, etc
• Lenguajes orientados a problemas.
– Lenguajes de cuarta generación (4GL)
• Ej. SQL
INTERPRETE
• El intérprete ejecuta el código según
lo va interpretando.
– Cada vez que se escribe una línea el
programa comprueba si es correcta,
si lo es, la ejecuta.
– La ejecución es interactiva.
– Los intérpretes más puros no guardan
copia del programa que se está
escribiendo.
– Ejemplos: Procesos por lotes, CAML,
etc.
– El intérprete siempre debe estar
presente.
COMPILADOR
El compilador es el traductor más extendido
Realiza un análisis y genera un programa
ejecutable
El programa ejecutable, una vez creado, no
necesita el compilador para funcionar
COMPILADOR VS INTERPRETE
• Compilador • Intérprete
– Se compila una vez, se – Se traduce cada vez
ejecuta n veces que se ejecuta.
– El proceso de compilación – Permite interaccionar
tiene una visión global de más con el código en
todo el programa, por lo tiempo de ejecución.
cual la gestión de errores – Necesita menos
es más eficiente.
memoria
– La ejecución es más
rápida.
10
Las FASES de un compilador
Primera fase (precompilador)
no siempre se realiza
sustituciones de macros
eliminación de comentarios
inclusión de ficheros
extensiones al lenguaje (C+SQL)
Segunda fase
es la parte fundamental (y siempre presente)
consta de:
analizador léxico
analizador sintáctico
generador de código
traduce el código fuente a otro objeto
puede ser el definitivo
puede ser un código intermedio
11
Las FASES de un compilador
Tercera fase
no siempre presente
realiza optimizaciones (algunas) sobre el código (intermedio) generado
Cuarta fase:
traduce el código intermedio (optimizado) a
ensamblador
binario
Muchas variaciones posibles:
sin preprocesador
sin usar código intermedio
optimizando directamente sobre el ensamblador de la máquina
generar directamente binario, sin pasar por el ensamblador
.........
12
Tipos de Compiladores
Ensamblador: el lenguaje fuente es lenguaje 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.
13
Tipos de Compiladores
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.
Descompilador: es un programa que acepta como
entrada código máquina y lo traduce a un lenguaje de
alto nivel, realizando el proceso inverso a la
compilación.
14
ESTRUCTURA DE UN COMPILADOR
Etapas que constituyen el proceso de compilación
Programa Fuente
Análisis Léxico
Análisis Sintáctico
Manejo de la Manejo de
Análisis Semántico Errores
Tabla de Símbolos
Generación de Código Intermedio
Optimización de Código
Generación de Código
15 Programa Objeto
Las partes principales
La primera fase (front end) es la encargada
de analizar el programa fuente – Fase de
Análisis.
(back end) es la encargada de generar
código para la máquina objeto.- Fase de
síntesis.
El puente de unión entre las dos fases era un
lenguaje intermedio que se designó con el
nombre de UNCOL (UNiversal Computer
Oriented Language).
El analizador léxico
Lo realiza un “scanner”
también “tokenizer”
El scanner recorre los caracteres de entrada (el fuente)
hasta reconocer un “token”
token: unidad léxica indivisible
ejemplos: while,if,==,>=,ancho,...
La secuencia de caracteres correspondiente se llama
“lexema” (componente léxico)
1 token <> 1 lexema
Existen Generadores automáticos de analizadores lexicos
como LEX
17
El analizador léxico
Además, suele realizar otras tareas:
procesar directivas al compilador (opciones)
introducir información preliminar en la tabla de símbolos
eliminar separadores innecesarios
sustituir macros
listar el fuente
Normalmente, los tokens se describen mediante
expresiones regulares
18
El analizador léxico
Ejemplo:
El scanner deberá reconocer sucesivamente,
19
El analizador sintáctico
O “parser”
Objetivo: agrupar los tokens suministrados por el scanner
para reconocer “frases”
¿Cómo lo hace?
La sintaxis se suele especificar formalmente mediante una GLC
también de otros tipos
El parser recibe tokens y los agrupa de acuerdo a especificadas
por la GLC
El parser detecta errores sintácticos
Y si es bueno, puede además realizar algunas correcciones
producciones
20
El analizador sintáctico
Ejemplo:
supongamos sintaxis asignación como:
y debemos analizar
21
El analizador sintáctico
El árbol sintáctico correspondiente es
22
El analizador semántico
Realiza dos funciones:
Análisis de la semántica estática
¿Es cada construcción legal y “con sentido”?
variables en una expresión definidas
del tipo adecuado
alcance de los objetos
Generación del código intermedio
Generalmente se lleva a cabo mediante gramáticas
de atributos
la GLC se completa con atributos necesarios
tipo
valor
acciones a ejecutar cuando se detecta una construcción
legal
....
23
Generación de Código Intermedio
Cuando el número de lenguajes fuente crece hasta
un número grande M, y/o cuando el número de
lenguajes objeto también crece hasta un numero
grande N, es necesario encontrar una técnica para
evitar tener que diseñar MxN compiladores.La
solución consiste en utilizar un lenguaje intermedio
o una representación intermedia; de esta forma
solo hay que construir M programas que traduzcan
de cada lenguaje fuente al lenguaje intermedio y N
programas que traduzcan del lenguaje intermedio a
cada lenguaje objeto.
24
Generación de Código Intermedio
La generación de código While (A>B) AND (A<=2*B-5)
intermedio transforma un Do A := A + B
árbol de análisis sintáctico
L1: IF A>B GOTO L2
(semántico) en una
GOTO L3
representación en un
L2: T1:= 2*B
lenguaje intermedio, que
T2:= T1-5
suele ser código
IF A<=T2 GOTO L4
suficientemente sencillo
GOTO L3
para poder luego generar
L4: A:= A+B
código máquina.
GOTO L1
25 L3: ....
OPTIMIZACION DE CODIGO
El código intermedio generado es analizado y transformado
en uno equivalente optimizado
Es una tarea muy costosa
De hecho, generalmente se puede invocar al compilador
activando/desactivando esta opción
Otras veces, optimiza el código objeto
usual la optimización “peephole”:
tomar una porción pequeña de código y hacer una optimización local
“desenrrollado” de bucles
eliminación de recursividad final
....
26
GENERACION DE CODIGO
Toma código intermedio y genera código objeto para
la máquina considerada
Es la parte más próxima a la arquitectura de la
máquina
Habitualmente, se escriben “a mano”
desarrollo “a medida” para cada máquina específica
Dada la complejidad, si no se va a realizar
optimización, se asocia la generación de código a las
rutinas semánticas
compiladores de “una pasada”
27
La tabla de símbolos
Mecanismo para almacenar/acceder la información
de los identificadores
Las informaciones asociadas a un identificador se
denominan “atributos”
Cada vez que se usa un identificador, la tabla de
símbolos proporciona la información necesaria
Se usa tanto en la parte de análisis como en la de
síntesis
28
Manejo de errores
Es una de las misiones mas importantes de un compilador,
aunque al mismo tiempo, es lo que mas dificulta su realización
debido principalmente a dos motivos:
1) A veces unos errores ocultan otros
2) A veces un error provoca una avalancha de muchos errores que
se solucionan con el primero
Criterios en el manejo de errores
a) Pararse al detectar el primer error
b) Detectar todos los errores de un pasada
29
