Download Introducción - Rogelio Davila

Cb00843 Traductores
Rogelio Dávila Pérez
Profesor Planta
Instituto Tecnológico y de Estudios Superiores de Monterrey,
Campus Guadalajara
[email protected]
Introducción
Compiladores, Interpretes y Ensambladores
Def. Un traductor es un programa que toma un programa escrito en un
lenguaje, llamado fuente, y genera un programa equivalente en otro
lenguaje, llamado objeto.
Cuando el lenguaje fuente es un lenguaje de alto nivel (JAVA, C,
LISP, ...), y el lenguaje objeto es lenguaje de máquina (unos y ceros),
al traductor se le denomina compilador.
Programa
fuente
Traductor
Errores
Programa
objetivo
Introducción
Def. Un interprete es un programa que acepta un programa escrito en
lenguaje fuente y lo ejecuta. Ej. PROLOG, SQL, etc.
NOTA: Un interprete NO produce código en lenguaje objeto, solo
ejecuta el programa fuente mismo.
Def. Un ensamblador es un programa que toma un programa escrito en
lenguaje de ensamblador y lo traduce a lenguaje de máquina.
Ejercicio:
– compilador vs. Intérprete - ventajas y desventajas.
Introducción
Lenguajes de programación
– Lenguajes de máquina
• Las instrucciones consisten en cadenas de unos y ceros.
• Cada lenguaje es particular a su procesador .
– Lenguajes de ensamblador
• Consisten en instrucciones básicas,
ej.
LDA 5
-- carga un 5 al registro ‘A’ del procesador
• En la mayoría de los casos, sus instrucciones están en
relación uno-a-uno con el lenguaje de máquina.
• Se utilizan en programación de interfaces a dispositivos
periféricos.
Introducción
– Lenguajes de alto nivel
• Manejan bloques
• Contienen estructuras de control:
if-then-else, do-while, repeat-until, etc.
• Introducen recursividad
• Manejan tipos
Existen distintos modelos de lenguajes de alto nivel
•
•
•
•
Imperativos: C, Pascal, Fortran
Orientados a objetos: Java, C++
Funcionales: LISP, ML
Programación Lógica: Prolog
Introducción
¿Porque tantos lenguajes de programación?
– Un lenguaje nuevo normalmente cubre huecos
que lenguajes previos no cubrían.
– Un nuevo lenguaje favorece la realización de
tareas antes consideradas difíciles.
Introducción
Distintos dominios de aplicación requieren habilidades
diferentes:
– Aplicaciones comerciales: generación de reportes.
– Aplicaciones científicas: gran precisión matemática.
– Programación del sistema: acceso a instrucciones de
bajo nivel.
– Aplicaciones de Inteligencia Artificial:
manipulación simbólica
– Lenguajes de propósito específico.
Introducción
¿Porqué sirve saber sobre compiladores?:
– Mejora el entendimiento acerca del funcionamiento
del computador.
– Apoya la generación de software de alto nivel.
– Ayuda a aprender nuevos lenguajes de programación.
– Incrementa la capacidad del estudiante para imaginar
lenguajes de más alto nivel.
Introducción
• El proceso de traducción
Programa
en
lenguaje
fuente
Programa
en
lenguaje
objetivo
Análisis
Se genera una representación
abstracta del programa que
captura su significado.
Síntesis
A partir de la representación
abstracta se genera la versión
en el lenguaje objetivo.
Introducción
• Etapas de la compilación
Programa en
lenguaje fuente
Errores
Errores
Análisis
Analizador
Lexicográfico
Analizador
Tabla de
Símbolos
Generador de
código
Sintáctico
Optimizador
de código
Codigo objeto
optimizado
Programa en
lenguaje
objetivo
Síntesis
Analizador
Arbol
Sintáctico
Código
objeto
Semántico
Generador de
código intermedio
Arbol
sintáctico
abstracto
Introducción
• Analizador Lexicográfico (Scanner)
– Toma el programa escrito en código fuente y lo divide en símbolos
(tokens), generando la llamada tabla de símbolos (token table). 1
Ej.
Cadena de símbolos:
posición : = inicial + relación*60
Tabla de símbolos:
Símbolo
Tipo
Nombre
‘posición’
identificador
id1
‘: =‘
operador
:=
‘inicial’
identificador
id2
‘+’
operador
+
‘relación’
identificador
id3
‘*’
operador
*
‘60’
constante
60
_______________________
1Ejemplo
tomado de [ASU., 86]
Introducción
• Analizador Sintáctico (Parser)
– Toma la tabla de símbolos y mediante el uso de una gramática,
recupera la estructura sintáctica de la oración.
– Utilizando la siguiente gramática para analizar la oración en el
ejemplo:
<exp> = <const>
<exp> = <ident>
<exp> = <ident> : = <exp>
<exp> = <exp> * <exp>
<exp> = <exp> + <exp>
Introducción
El analizador genera el árbol sintáctico (parsing tree):
<exp>
<exp>
<exp>
<ident>
id1
:=
<exp>
<exp>
<exp>
<ident>
<ident>
<const>
id2
+
id3
*
60
Introducción
• Analizador semántico
– checa el programa fuente para detectar posibles
errores semánticos y verifica la compatibilidad de
tipos.
Ej.
En la subexpresión ‘id3 * 60’ el simbolo de
la multiplicación se aplica a un real y a
un entero.
Para que la operación sea uniforme la expresión
se transforma en:
id3 * inttoreal(60)
Introducción
• Generación de código intermedio
– Esta etapa es el inicio del proceso de síntesis de la expresión y
genera una representación intermedia explicita del programa.
Esta representación debe tener dos propiedades:
• Debe ser fácil de producir
• Debe ser fácil de traducir al lenguaje objetivo
Ej.
temp1 : = inttoreal(60)
temp2 : = id3 * temp1
temp3 : = id2 + temp2
id1 : = temp3
Introducción
• Optimizador de código
– El código generado en la etapa anterior se optimiza para su
ejecución de manera más eficiente:
temp1 : = id3 * 60.0
id1 : = id2 + temp1
• Generación de código
– La versión final del codigo es generada a partir del código
optimizado:
MOVF id3, R2
MULF #60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1
Introducción
• Aplicaciones de las metodologías de traductores
–
–
–
–
Lenguajes de interrogación a bases de datos: ej. SQL
Traductores a formato html
Generadores de reportes
Procesamiento de macros: permiten extender el lenguaje
mediante el uso de abreviaciones para construcciones mayores.
– Extensiones a lenguajes: ej. El SQL incluido en C o Java.
Introducción
• Herramientas de apoyo a la construcción de traductores
– Generadores de análisis lexicográfico LEX
– Generadores dc análisis sintáctico YYAC
Bibliografía
[ASU, 86]
Aho A. V., Sethi R., Ullman J. D., “COMPILERS,
Principles, Techniques and Tools,” Addison-Wesley
publishers, 1986.