TRADUCTORES DE

LENGUAJE
Ing. Ma. Margarita Labastida Roldn
Verano 2013

Contenido

Porqu Compiladores?
Proceso de Traduccin
Estructura de Datos
Arranque automtico y portabilidad
Lenguaje y Compilador
C-Minus

Compiladores

Son programas de computadora que traducen un lenguaje a

otro.
Toma como entrada un programa escrito en lenguaje fuente y
produce un programa equivalente en lenguaje objetivo.
Programa
Fuente

Programa
Objetivo

Breve Historia
Jhon Von Neumann (1940)
Secuencia de cdigos o programas, para clculos. Escritos en principio en lenguaje mquina. [c7 06 0000 0002]

Lenguaje Ensamblador
Las instrucciones y las localidades de memoria son formas simblicas
dadas. [MOV X,2].

Traduce los cdigos simblicos y las localidades de memoria del

lenguaje a cdigo numricos correspondientes del lenguaje mquina.

Lenguaje FORTRAN
Dirigido por John Backus entre 1954 y 1957, la mayora de los procesos involucrados en la traduccin de lenguajes de programacin.

Noam Chomsky
Estructura del lenguaje natural. Permiti la semi-automatizacin de los
lenguajes.

Clasificacin de los lenguajes de acuerdo con la complejidad de sus

gramticas y la potencia de los algoritmos para reconocerlas

Breve Historia (2)

Jerarqua de Chomsky
Cuatro niveles, del tipo 0 al 3. Las del tipo 2 o gramticas libres de contexto, son las ms tiles para lenguajes de programacin.

Autmatas Finitos y Expresiones Regulares

Corresponden a las gramticas de tipo 3, relacionados con las
gramticas libres de contexto.

El estudio condujo a mtodos simblicos para expresar la estructura

de palabras o tokens de un lenguaje de programacin.

Tcnicas de optimizacin
Tcnicas de mejoramiento de cdigo, producen un cdigo objeto
ptimo y mejoran su eficacia.

Mtodo para la generacin de cdigo objeto eficaz.

Generadores de analizadores sintcticos / Generadores de analizador lxico

Automatizan slo una parte del proceso de compilacin, el ms
conocido es Yacc. Escrito por Steve Johnson en 1975

Cuyo representante ms conocido es Lex, o generador de

analizadores lxicos.

Breve Historia (3)

Los compiladores han incluido la aplicacin de

algoritmos ms sofisticados para inferir y/o
simplificar la informacin contenido en un
programa.
Los compiladores se han vuelto una parte de un
ambiente de desarrollo interactivo, o IDE, basado
en ventanas, que incluyen editores, ligadores,
depuradores y administradores de proyectos.

Programas relacionados

Existen algunos programas

que estn relacionados, o
que se utilizan, con los
compiladores y que con
frecuencia viene junto con
ellos en un ambiente de
desarrollo de lenguaje
completo.

Intrpretes

Ensambladores

Ligadores

Cargadores

Preprocesadores

Editores

Depuradores

Perfiladores

Intrpretes

Es un traductor de lenguaje, igual que un

compilador, pero difiere de ste en que ejecuta el
programa fuente inmediatamente, en vez de
generar un cdigo objeto que se ejecuta despus
de que se completa la traduccin.
Cualquier lenguaje de programacin se puede
interpretar o compilar, pero se puede preferir un
intrprete a un compilador dependiendo del
lenguaje que se use.

Intrpretes

Los lenguajes funcionales, como LISP tienden a ser

interpretados.
Los intrpretes tambin se utilizan en el desarrollo
de software, donde los programas son traducidos y
vueltos a traducir.

Ensambladores

Es un traductor para el lenguaje ensamblador de

una computadora en particular. El lenguaje
ensamblador es una forma simblica del lenguaje
mquina de la computadora y es fcil de traducir.
Un compilador generar lenguaje ensamblador
como su lenguaje objetivo y depender de un
ensamblador para terminar la traduccin a cdigo
objeto.

Ligadores

Los compiladores y los ensambladores a menudo

dependen de un programa conocido como ligador, el
cual recopila el cdigo que se compila o ensambla por
separado en diferentes archivos objeto, a un archivo
que es directamente ejecutable.
Tambin conecta un programa objeto con el cdigo de
funciones de libreras estndar, as como con recursos
suministrados por el sistema operativo de la
computadora.

Cargadores

Un compilador, ensamblador o ligador producir un

cdigo que no est completamente organizado y listo,
pero cuyas principales referencias de memoria se
hacen relativas a una localidad de arranque en una
memoria.
El cdigo es relocalizable y un cargador resolver
todas las direcciones relocalizables relativas a una
direccin base, o de inicio.
Hace flexible el cdigo ejecutable, pero el proceso de
carga con frecuencia ocurre en segundo plano o
conjuntamente con el ligado.

Preprocesadores

Es un programa separado que es invocado por el

compilador antes de que comience la traduccin
real.
Puede eliminar comentarios, incluir otros archivos y
ejecutar sustituciones de macro.
Pueden ser requeridos por el lenguaje o pueden ser
agregados
posteriores
que
proporcionen
facilidades adicionales.

Editores

Un editor, puede ser orientado hacia el formato o

estructura del lenguaje de programacin.
Estos editores se denominan basados en estructura
y ya incluyen operaciones de un compilador, de
manera que pueda informarse al programador los
errores a medida que el programa se vaya
escribiendo en lugar de hacerlo cuando est
compilado.

Depuradores

Es un programa que puede utilizarse para determinar

los errores de ejecucin en un programa compilado.
La ejecucin de un programa con un depurador se
diferencia de la ejecucin directa en que el depurador
se mantiene al tanto de la informacin sobre el cdigo
fuente, como los nmeros de lnea y los nombres de las
variables y procedimientos.
Puede detener la ejecucin en ubicaciones previamente
especificadas llamadas puntos de ruptura.

Depuradores

El compilador debe suministrar al depurador la

informacin simblica apropiada.
La depuracin se convierte en una cuestin de
compilacin.

Perfiladores

Es un programa que recolecta estadsticas sobe el

comportamiento de un programa objeto durante la
ejecucin.
Las estadsticas son el nmero de veces que se
llama a cada procedimiento y el porcentaje de
tiempo de ejecucin que se ocupa en cada uno de
ellos.
A veces el compilador utilizar la salida del
perfilador para mejorar de manera automtica el
cdigo sin la intervencin del programador.

Proceso de Traduccin

Proceso de Traduccin

Un compilador se compone internamente de varias

fases, que realizan distintas operaciones lgicas.
Las fases de un compilador se ilustran, junto con los
tres componentes auxiliares que interactan con
alguna de ellas o con todas: la tabla de smbolos y
el manejador de errores.

Fases de un Compilador
Cdigo Fuente

Analizador
lxico

Tokens
Analizador
sintctico

rbol Sintctico
Analizador
semntico

rbol con anotaciones

Optimizador de
cdigo Fuente

Cdigo Intermedio
Generador de
cdigo

Cdigo Objeto
Optimizador de
cdigo objetivo

Cdigo Objeto

Analizador lxico (Scanner)

Efecta la lectura real del programa fuente, el cual

est en la forma de un flujo de caracteres.
Realiza lo que se conoce como anlisis lxico:
recolecta secuencias de caracteres en unidades
significativas denominadas tokens, las cuales son
como las palabras de un lenguaje natural.
Realiza una funcin similar al deletreo.

Scanner
Ejemplo:
a[index] = 4 + 2

Este cdigo contiene 12 caracteres diferentes de un

espacio en blanco pero slo 8 tokens.
a
[
index
]
=
4
+
2

identificador
corchete izquierdo
identificador
corchete derecho
asignacin
Nmero
signo ms
nmero

Scanner

Cada token se compone de uno o ms caracteres

que se renen en una unidad antes de algn
procesamiento adicional.
Un analizador lxico puede realizar otras funciones
junto con la de reconocimiento de tokens.
Por

ejemplo: puede introducir identificadores en la

tabla de smbolos, y puede introducir literales en la
tabla de literales

Analizador sintctico (Parser)

Recibe el cdigo fuente en la forma de tokens

proveniente del analizador lxico y realiza el
anlisis sintctico, que determina la estructura del
programa.
Es

semejante a realizar el anlisis gramatical sobre una

frase en un lenguaje natural.

El anlisis determina los elementos estructurales del

programa y sus relaciones. Los resultados se
representan como un rbol de anlisis gramatical
o rbol sintctico.

Parser

Parser

Los nodos internos del rbol de anlisis estn

etiquetados con los nombres de las estructuras que
representan y que la hojas del rbol representan la
secuencia de tokens de la entrada.
Un rbol de anlisis gramatical es un auxiliar para
visualizar la sintaxis de un programa o de un elemento
de programa.
Los analizadores sintcticos tienden a generar un rbol
sintctico que condensa la informacin contenida en el
rbol de anlisis gramatical.

Parser (rbol sintctico abstracto)

En el rbol sintctico muchos de los nodos han

desaparecido (incluyendo los nodos de tokens). Si sabemos
que una expresin es una operacin de subndice, entonces
ya no ser necesario mantener los parntesis cuadrados
que representan esta operacin en la entrada original.

Analizar Semntico

La semntica de un programa es su significado, en

oposicin a su sintaxis, o estructura.
La semntica de un programa determina
comportamiento durante el tiempo de ejecucin.

su

Existen algunas caractersticas como semntica

esttica, y el anlisis de esta semntica es la tarea del
analizador semntico.
Las caractersticas tpicas de la semntica esttica
incluyen las declaraciones y la verificacin de tipos.

Analizar Semntico(2)

Los tipos de datos que se calculan mediante el

analizador semntico se llaman atributos y se
agregan al rbol como anotaciones o
decoraciones.
En

el ejemplo: a[index] = 4 + 2 la informacin que se

tendra que obtener antes del anlisis sera que a sea
un arreglo de valores enteros con subndices
proveniente de un subintervalo de los enteros y que
index sea una variable entera.

Analizar Semntico(3)
El

analizador semntico registrar el rbol sintctico

con los tipos de todas las subexpresiones y
posteriormente verificar que la asignacin tenga
sentido.

Optimizador de Cdigo Fuente

Permite posibilidades de mejoramiento del cdigo

que dependen del cdigo fuente.
En el ejemplo, la expresin 4 +2 se puede calcular
previamente por el compilador(incorporacin de
constantes).
Esta optimizacin se puede realizar de manera
directa sobre el rbol sintctico al colapsar el
subrbol secundario de la derecha del nodo raz.

Optimizador de Cdigo Fuente(2)

Muchas optimizaciones se pueden efectuar directamente

sobre el rbol, pero en ocasiones es ms fcil optimizar de
forma linealizada del rbol.

Existen variedades de cdigo: cdigo en tres

direcciones, cdigo intermedio, representacin intermedia
o RI.

Generador de Cdigo

Toma el cdigo intermedio y genera el cdigo para

la mquina objetivo.
Se emplean instrucciones que existen en la mquina
objetivo, se considera la representacin de los
datos , los bytes o palabras de memoria.
En el ejemplo se debe decidir cuntos enteros se
almacenarn para generar el cdigo para la
indizacin del arreglo.

Generador de Cdigo(2)

Una posible secuencia de cdigo:

Optimizador de cdigo objetivo

Intenta mejorar el cdigo objetivo generado por el

generador de cdigo.
Incluye la seleccin de modos de direccionamiento
para mejorar el rendimiento, reemplazando las
instrucciones lentas por rpidas y eliminando las
operaciones redundantes.

Optimizador de cdigo objetivo(2)

En el ejemplo, se puede utilizar una instruccin de

desplazamiento para reemplazar la multiplicacin
en la segunda instruccin. Se emplea un modo de
direccionamiento indizado para el almacenamiento.

Estructura de Datos de un
Compilador

Estructura de Datos Principales

Un compilador debera poder compilar un

programa en un tiempo proporcional al tamao del
programa, es decir, en O(n) tiempo, donde n es una
medida del tamao del programa (por lo general
el nmero de caracteres).
Existen algunas estructuras de datos que son
necesarias para las fases como parte de su
operacin y que sirven para comunicar la
informacin entre fases.

Estructura de Datos Principales

Tokens
rbol Sintctico
Tabla de Smbolos
Tabla de Literales
Cdigo Intermedio
Archivos Temporales

Tokens

Cuando un analizador lxico rene los caracteres

en un token, generalmente representa el token de
manera simblica, es decir, como un valor de un
tipo de datos enumerado que representa el
conjunto de tokens del lenguaje fuente.
En los lenguajes el analizador lxico slo necesita
generar un token a la vez (bsqueda de smbolo
simple). Utilizando una variable global simple para
mantener la informacin del token

rbol Sintctico

Es una estructura estndar basada en un apuntador

que se asigna de manera dinmica a medida que
se efecta el anlisis sintctico.
El rbol entero puede entonces conservarse como
una variable simple que apunta al nodo raz.
Cada nodo en la estructura es un registro cuyos
campos representan la informacin recolectada
tanto por el analizador sintctico como el
analizador semntico.

Estructura de Datos Principales

Cada nodo de rbol sintctico por s mismo puede

requerir de atributos diferentes para ser
almacenado, de acuerdo con la clase de estructura
del lenguaje que represente.
Cada nodo en el rbol sintctico puede estar
representado por un registro variable, con cada
clase de nodo contenido solamente la informacin
necesaria para ese caso.

Tabla de smbolos

Esta estructura mantiene la informacin asociada con

los identificadores: funciones, variables, constantes y
tipos de datos.
La tabla de smbolos interacta con casi todas las fases
del compilador: analizador lxico, analizador sintctico
o semntico.
El primero introduce identificadores dentro de la tabla;
el semntico agregar tipos de datos y otra
informacin; las fases de optimizacin y generacin de
cdigo utilizan la tabla de smbolos para el cdigo
objeto.

Tabla de smbolos

Ya que la tabla de smbolos tendr solicitudes de

acceso con tanta frecuencia, las operaciones de
insercin, eliminacin y acceso necesitan ser
eficientes.
Una estructura de datos estndar es la tabla de
dispersin o clculo de direccin.
En ocasiones se utilizan varias tablas y se mantienen
en una lista o pila.

Tabla de Literales

Almacena constantes y cadenas utilizadas en el

programa.
Necesita impedir las eliminaciones porque sus datos se
aplican globalmente al programa y una constante o
cadena aparecer slo juna vez en esta tabla.
Es importante en la reduccin del tamao de un
programa en la memoria al permitir la reutilizacin de
constantes y cadenas.
Es importante para que el generador construya
direcciones simblicas para las literales y para las
definiciones de datos en el archivo de cdigo objeto.

Cdigo Intermedio

De acuerdo con la clase de cdigo intermedio y de

las clases de optimizacin realizadas, este cdigo
puede conservarse como un arreglo de cadenas de
texto, un archivo de texto temporal o bien una lista
de estructuras ligadas.

Archivos Temporales

Eran usados para mantener los productos de los

pasos intermedios durante la traduccin o bien al
compilar al vuelo, manteniendo slo la
informacin suficiente de las partes anteriores del
programa fuente que permite proceder a la
traduccin.
Los compiladores ocasionalmente encuentran til
generar archivos intermedios durante alguna etapa
del procesamiento.

Archivos Temporales (2)

Algo comn es la necesidad de direcciones de

correccin hacia atrs durante la generacin del
cdigo.
Por

ejemplo, una sentencia condicional:

if x = 0 then else
Debe generarse un salto desde la prueba para la
parte bicondicional else antes de conocer la ubicacin
del cdigo para el else.

Archivos Temporales (3)

Por

lo regular debe dejarse un espacio en blanco para

el valor de NEXT, el cal se llena una vez que se logra
conocer el valor.
Lo anterior se consigue con el uso de un archivo
temporal.