INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA
CAMPUS CULHUACAN
CARRERA
INGENIERÍA EN COMPUTACIÓN
MATERIA
COMPILADORES
TEMA
UNIDAD I
PROF. JUAN MANUEL HERNÁNDEZ ESPINOSA
GRUPO: 5CM24 ACADÉMIA DE COMPUTACIÓN FECHA: 01/02/2018
TURNO MATUTINO
CONTENIDO
I. Introducción
II. Justificación
III. Objetivo
IV. Traductores de Lenguajes
i. Historia de los compiladores
ii. Programas relacionados con los compiladores
iii. Proceso de traducción
iv. Estructuras de datos principales en un
compilador
v. Otras cuestiones referentes a la estructura
del compilador
vi. Arranque automático y portabilidad
vii. Lenguaje y compilador de muestra TINY
viii. Un lenguaje para un proyecto de compilador
V. Conclusiones
VI. Glosario
[Link]-Bibliografía
Introducción
El objetivo de esta presentación es mostrar
un esbozo general del curso de
compiladores, que se imparte en el quinto
semestre de la carrera de Ingeniería en
Computación de la ESIME Culhuacán.
Justificación
Es de vital importancia para el ingeniero en
computación conocer, comprender y aplicar
los contenidos de la asignatura de
compiladores, para posteriormente
insertarse exitosamente en su vida
profesional.
Objetivo (didáctico)
Que el alumno conozca y comprenda las
etapas que se llevan a cabo en la
traducción de un código fuente a un
código destino a través de un compilador.
Presentación
Un compilador es un software traductor
de:
Programa en
Programa en
Compilador lenguaje
lenguaje fuente
objetivo
Lenguaje de Lenguaje de
alto nivel bajo nivel
Desarrollo
Historia
Primera Generación (1940-1950): Los programas
se escribían en lenguaje de máquina (códigos
numéricos que indicaban las operaciones por
realizarse).
Ejemplo: mover 5 a la dirección 0001 en
hexadecimal
C7 06 0001 0005
Luego el código o lenguaje de máquina fue
remplazado por el Lenguaje Ensamblador .
Ejemplo en lenguaje ensamblador: mover 5 a la
localidad de memoria X.
MOV X, 5
Así tenemos EL ENSAMBLADOR y el LENGUAJE
ENSAMBLADOR.
El ensamblador traduce los códigos simbólicos y
las localidades de memoria a código de
máquina. Y el lenguaje ensamblador es un
conjunto de mnemónicos que representan
instrucciones básicas para
los computadores, microprocesadores, microcon
troladores y otros circuitos
integrados programables.
Segunda Generación (1950-1960): Aparecen los
compiladores para los lenguajes de alto nivel
como FORTRAN.
El término compilador fue acuñado por Hopper. El
equipo FORTRAN dirigido por John W.
Backus de IBM está generalmente acreditado por
haber presentado el primer compilador completo,
en 1957. El primer compilador FORTRAN necesitó
de 18 años-persona para su creación.
Posteriormente surgen los Entornos de
Desarrollo Interactivos (IDE).
Que suelen integrar:
Editores
Ligadores
Depuradores
Administradores de proyectos
Ambientes seguros de prueba
Profilers
Traductores de lenguaje
Son software o programas de sistema, también
llamado software de base, que traducen los
programas fuente escritos en lenguajes de bajo
o alto nivel a código objetivo de bajo nivel.
Los traductores se dividen en:
• Ensambladores
• Interpretes y
• Compiladores
Código en
Lenguaje ensamblador es un lenguaje lenguaje
ensamblador
de programación de bajo nivel.
Consiste en un conjunto de
mnemónicos que representan
instrucciones básicas para los Ensamblador
computadores, microprocesadores,
microcontroladores y otros circuitos
integrados programables. Ensamblador
Código de
es usado para traducir sentencias del máquina
lenguaje ensamblador al código de
máquina del computador objetivo.
Intérpretes
Un intérprete es un traductor que toma
un programa fuente, lo traduce línea a
línea y de inmediato lo ejecuta sin pasar
por código objeto permanente.
Un lenguaje que soporte un traductor de
tipo intérprete se denomina lenguaje
interpretado. BASIC es el modelo por
excelencia interpretado.
Los programas fuente en BASIC se
escriben con ayuda de un programa
denominado IDE que suele venir
incorporado al programa intérprete.
Compiladores
Un compilador es un programa que traduce Programa Fuente
los programas fuente escritos en lenguajes de
alto nivel a lenguaje objeto de bajo nivel.
A los programas escritos en lenguajes de alto Compilador
nivel se les llama programas o código fuente y
el programa traducido se le conoce como
programa o código objetivo. Programa Objetivo
Lenguajes compilados típicos son: PASCAL,
COBOL, C, C++, Java, etc.
Fases de la compilación
La compilación es el proceso de la traducción
de programas fuente a programas objetivo.
El programa objetivo obtenido de la
compilación no ha sido traducido
normalmente a código máquina sino a
ensamblador. Para conseguir el programa
ejecutable real se debe utilizar un programa
llamado montador o enlazador (linker). El
proceso de montaje conduce a un código
directamente ejecutable.
Ejemplo del proceso de compilación
1. Escritura del programa fuente con un IDE y
almacenamiento en un dispositivo (un disco).
2. Compilar el programa con el compilador C++.
3. Verificar y corregir errores de compilación
(listado de errores).
4. Obtención del programa objetivo.
5. Con el montador-ligador se obtiene el
programa ejecutable.
6. Se ejecuta el programa y si no existen
errores, se tendrá la salida del mismo. Modificación
de un
programa
fuente
Fundamentos teóricos de los
compiladores
Los principios y técnicas que se usan
en la escritura de compiladores se
basan en los conceptos de la teoría de
autómatas y lenguajes formales, en
particular en las siguientes teorías.
1. Teorías de Kurt Gödel y Alan Turing (en el
fondo son equivalentes). Existencia de
problemas irresolubles.
2. Teoría de Shannon. Teoría matemática de la
comunicación, que a la postre daría origen a
las máquinas secuenciales y los autómatas
finitos.
3. Teoría de Chomsky. Teoría de las gramáticas
transformacionales. Que vino a formalizar la
teoría matemática de la lingüística (teoría de
los lenguajes), incluyendo el de computadora.
El estudio de los lenguajes se divide en
el análisis de la estructura de las frases
(gramática) y de su significado
(semántica). A su vez, la gramática
puede analizar las formas que toman
las palabras (morfología), su
combinación para formar frases
correctas (sintaxis) y las propiedades
del lenguaje hablado (fonética).
Esquema de los fundamentos teóricos de los compiladores
Problemas
computables
Otros programas relacionados con los
compiladores son:
Ligadores: programa que recopila código
compilado o ensamblado de diferentes
archivos objeto y les adjunta las librerías
necesarias para generar un programa
directamente ejecutable.
Código Objeto + Librerías = Código o
programa ejecutable
Cargadores: programa que relocaliza las
direcciones de memoria relativas a una
dirección base o de inicio, trabaja en conjunto
con el ligador para obtener el programa
ejecutable.
Preprocesadores: programa que elimina
comentarios, incluye otros archivos
necesarios y ejecuta sustituciones de macro,
antes de realizarse la traducción real del
código fuente a código ejecutable.
Editores: programa que permite la captura del
código fuente. Hay editores enfocados a la
estructura del lenguaje en turno, que emiten
mensajes de error. Suelen pertenecer a los
IDE.
Depuradores: programa que permite
identificar los errores de ejecución en un
programa compilado, es decir, permite
visualizar la ejecución del programa paso a
paso. Suele estar integrado con el IDE.
Perfiladores: programa que recolecta
estadísticas sobre el comportamiento de un
programa objeto durante la ejecución.
Administradores de proyecto: programa que
permite combinar el trabajo de diversos
usuarios en uno general y disponible para
todos. Manteniendo la historia de cada
proyecto individual y la del general por
versiones o actulizaciones.
Pasos para la generación de código fuente a código ejecutable
Código Fuente
Analizador Léxico o rastreador
Tokens
Analizador Sintáctico
Árbol Sintáctico
Tabla de Símbolos
Analizador Semántico
Árbol con anotaciones Tabla de Literales PROCESO DE TRADUCCIÓN DEL
COMPILADOR
Optimizador de Código
Manejador de Errores
Código Intermedio
Generador de código
Código Objetivo
Optimizador de Código Objetivo
Código Objetivo
Analizador morfológico, también llamado
analizador lexical, preprocesador, rastreador o
scanner, en inglés.
Realiza la primera fase de la compilación.
Convierte el programa que va a ser compilado
en una serie de unidades lógicas llamadas
unidades sintácticas o tokens (cadenas
específicas: palabras reservadas y puntuación; o
no específicas: identificadores, constantes y
etiquetas) que desempeñan el papel de
símbolos de entrada para el analizador
sintáctico.
Esto puede hacerse generando dichas unidades
de una en una o línea a línea. Eliminando
espacios en blanco, comentarios y detectando
errores morfológicos. Usualmente se
implementa mediante un autómata finito
determinista.
Los tokens se diferencian si son conocidos
previamente o no. Una palabra reservada for es
conocida previamente en el lenguaje que la
utilice, el nombre de una variable la crea el
programador.
Los tokens tienen dos partes: su tipo y su valor
(lexema). En algunos casos no hay tipo (palabras
reservadas). Una variable X, su tipo es
identificador y su lexema es X
Analizador sintáctico (parser en inglés):
Es el elemento fundamental del procesador,
pues lleva el control del proceso e invoca
como subrutinas a los restantes elementos
del compilador. Realiza el resto de la
reducción al axioma de la gramática para
comprobar que la instrucción es correcta.
Usualmente se implementa mediante un
autómata de pila o una construcción
equivalente.
Analizador semántico. Esta fase revisa el árbol
sintáctico junto con los atributos y la tabla de
símbolos para tratar de encontrar errores
semánticos. Para todo esto se analizan los
operadores y operandos de expresiones y
proposiciones. Finalmente reúne la información
necesaria sobre los tipos de datos, rangos e
identificadores para la fase posterior de
generación de código.
El componente más importante del análisis
semántico es la verificación de tipos. Aquí, el
compilador verifica si los operandos de cada
operador son compatibles según la
especificación del lenguaje fuente.
Generador de código intermedio. Después de la
etapa de análisis, se suele generar una
representación intermedia explícita del
programa fuente. Dicha representación
intermedia se puede considerar como un
programa para una máquina abstracta.
Cualquier representación intermedia debe tener
dos propiedades importantes; debe ser fácil de
generar y fácil de traducir al código máquina
destino.
Optimizador de código. Esta fase trata de
mejorar el código intermedio, de modo que en
la siguiente fase resulte un código de máquina
más rápido de ejecutar.
Generación de Código Objeto. La fase final de
un compilador es la generación de código
objeto, que por lo general consiste en código
máquina reubicable o código ensamblador. Cada
una de las variables usadas por el programa se
traduce a una dirección de memoria (esto
también se ha podido hacer en la fase de
generación de código intermedio
Después, cada una de las instrucciones
intermedias se traduce a una secuencia de
instrucciones de máquina que ejecuta la misma
tarea. Un aspecto decisivo es la asignación de
variables a registros.
Tabla de Símbolos. También llamada «tabla de
nombres» o «tabla de identificadores», se trata
sencillamente de una estructura de datos de alto
rendimiento que almacena toda la información
necesaria sobre los identificadores de usuario.
Tiene dos funciones principales:
• Efectuar chequeos semánticos.
• Generar código.
Además, esta estructura permanece en memoria
sólo en tiempo de compilación, no de ejecución,
excepto en aquellos casos en que se compila con
opciones de depuración.
Gestor de errores
El manejo de errores es parte importante de un
compilador y el escritor del compilador siempre
debe tener esto presente durante su diseño.
El compilador debe ser capaz de detectar
errores en las etapas de análisis (atribuibles al
usuario) y de lógica; y en la etapa de síntesis
(atribuibles al desarrollador y/o herramienta
utilizada para el desarrollo).
El compilador debe recuperarse de los errores
sin perder demasiada información.
Y sobre todo, el compilador debe producir
mensajes de error que permita tanto al
programador como al desarrollador encontrar y
corregir fácilmente los elementos incorrectos.
Estructuras de datos principales en un
compilador.
Tokens: es una cadena de símbolos.
Árbol sintáctico: Es el conjunto de nodos o
tokens generados por el análisis sintáctico que
se integran un registro cuyos campos contienen
información recolectada en el análisis sintáctico
y semántico
Tabla de símbolos: mantiene la información
asociada con los identificadores, tales como
funciones (parámetros), variables, constantes y
tipos de datos en tablas de dispersión, árboles o
listas. Interactúa con casi todas las fases del
compilador.
Tabla de literales: almacena constantes y
literales o cadenas en el programa.
Código intermedio: el código es almacenado en
un arreglo, un archivo o una lista de tipo texto.
Por ejemplo código de tres direcciones o código
P.
Archivos temporales: mantienen los pasos
intermedios en la traducción
Otras cuestiones referentes a la estructura del
compilador.
Las etapas del compilador pueden verse como:
Etapa de análisis y etapa de síntesis
Lenguaje objetivo
Diagrama a Bloques del Proceso Completo de Compilación
S E
Análisis
í G
T r
m e
a r
d b s d
b o
e o t e
l r
l o
a e
o r
s
s Síntesis
Lenguaje objetivo
Diagrama a Bloques del Proceso Completo de Compilación
Etapa inicial y etapa final: los análisis léxico,
sintáctico y semántico conforman la etapa inicial
y la generación de código es parte de la etapa
final.
Pasadas: consiste en procesar la representación
intermedia, agregando información a ella,
alterando su estructura o produciendo una
representación intermedia. Las pasadas de un
compilador con optimización pueden ser: una,
dos hasta ocho.
Definición de lenguaje y compiladores
Las estructuras léxicas, sintácticas y semánticas
de un lenguaje de programación son recopiladas
en un manual de referencia del lenguaje o
definición de un lenguaje.
La estructura y comportamiento del ambiente
de ejecución que puede ser estático, semi-
dinámico y dinámico afectan la construcción de
los compiladores
Opciones de compilador e interfaces
Tanto a la interface como las opciones del
compilador se les llama en conjunto pragmáticas
del compilador.
Manejo de errores.
Los compiladores deben responder de forma
adecuada a los errores tanto del programa
fuente como los del programa objetivo. Así,
tenemos errores en tiempo de compilación
(errores estáticos) y errores en tiempo de
ejecución (errores dinámicos).
Arranque automático y portabilidad
Un compilador trabaja con un lenguaje fuente,
un lenguaje objetivo y un lenguaje anfitrión
(inicialmente el lenguaje máquina). Actualmente
existen lenguajes para la construcción de
compiladores que incluyen compiladores de
compiladores.
Al proceso de mejoramiento o pasadas de la
optimización de código para producir una
versión final se le llama arranque automático
por transferencia.
La portabilidad del compilador es la capacidad
de éste, de ser ejecutado en máquinas
diferentes.
lo creo
interprete
Lenguaje y compilador de muestra TINY
TINY es un lenguaje de programación reducido
con una sintaxis similar al lenguaje Pascal o Ada.
Cuenta con un pequeño compilador hecho en
lenguaje C, que ejemplifica las etapas del análisis
léxico, sintáctico, semántico y la generación de
código con propósitos pedagógicos.
TM
Es la máquina donde correrá el compilador TINY
y el lenguaje objetivo será en ensamblador. El
simulador TM se puede compilar desde
cualquier compilador de C estándar.
C-Minus: Un lenguaje para un proyecto de
compilador.
C-Minus es un lenguaje más extenso que TINY,
es un sub-lenguaje de C propio para un proyecto
educativo.
Herramientas para la construcción de
compiladores.
• Generadores de analizadores sintácticos
(parsers)
• Generadores de escáners
• Motores de traducción orientados a la
sintaxis
• Generadores de generadores de código
• Motores de análisis y flujo de datos
• Kits (conjuntos) de herramientas para la
construcción de compiladores.
Las optimizaciones de compiladores deben
cumplir con los siguientes objetivos de diseño:
• La optimización debe ser correcta; es decir,
debe preservar el significado del programa
compilado.
• La optimización debe mejorar el rendimiento
de muchos programas.
• El tiempo de compilación debe mantenerse
en un valor razonable.
• El esfuerzo de ingeniería requerido debe ser
administrable.
Aplicaciones de la tecnología de compiladores
• Implementación de lenguajes de
programación de alto nivel.
• Optimización para la arquitectura de
computadoras.
• Diseño de nuevas arquitecturas de
computadoras.
• Traducción de programas.
• Herramientas de productividad de software.
Fundamentos de los lenguajes de programación
de alto nivel
• La distinción entre estático y dinámico.
• Entornos y estados
• Alcance estático y estructura de bloques.
• Control de acceso explícito
• Alcance dinámico
• Mecanismos para el paso de parámetros.
• Uso de alias.
Conclusión(es)
Para comprender el proceso completo de la
compilación de un código fuente hasta lograr un
código destino, se requieren conocimientos de
programación de computadoras, teoría de
autómatas, estructuras de datos y lenguajes de
bajo y alto nivel.
Glosario
IDE: Entorno de Desarrollo Interactivo
Autómata: Sistema capaz de recibir señales de
su entorno, cambiar de estado y transmitir otras
señales.
Compilador: un software de sistema que traduce
de código fuente escrito en algún lenguaje de
alto nivel a un código objetivo de bajo nivel,
pasando por dos procesos principales: el análisis
y la síntesis, utilizando una tabla de símbolos y
un gestor de errores, para finalmente enlazarlo
con las librerías necesarias y obtener un código
directamente ejecutable.
Ciber-Bibliografía
[Link]
competencia-1/traductores-de-lenguaje
[Link]
[Link]
