Universidad Don Bosco
Facultad de Ingeniera
Escuela de Ingeniera en Computacin
Ciclo 02 2015
Asignatura: Compiladores GT01
Docente: Ing. Herson Miguel Serrano Chacn
UNIDAD I: SCANNING
Introduccin.
Los Lenguajes de programacin son notaciones que describen los clculos a las personas y
las mquinas. Nuestra percepcin del mundo en que vivimos depende de los lenguajes de
programacin, ya que todo el software que se ejecuta en todas las computadoras se escribi
en algn lenguaje de programacin. Pero antes de poder ejecutar el programa, primer debe
traducirse a un formato en que una computadora pueda ejecutarlo.
Los sistemas de software que se encargan de esta traduccin se llaman compiladores.
1.1 Definicin
Un compilador es un programa informtico, que se encarga de traducir el cdigo fuente de
una aplicacin que este en desarrollo, es decir convierte un programa hecho en lenguaje de
programacin de alto nivel a un lenguaje de mquina, el cual es conocido como de bajo nivel,
de tal forma que sea ms entendible y mucho ms fcil de procesar en el equipo en el que se
est ejecutando.
De igual manera un traductor es el que toma como entrada un texto escrito y da como salida
otro texto en un lenguaje llamado objeto.
Traductor: Programa que toma como entrada un texto escrito (llamado fuente) y da
como salida otro texto (llamado objeto).
Compilador: Traductor cuyo fuente es un lenguaje de alto nivel y cuyo objeto es un
lenguaje de bajo nivel.
Interprete: Compilador que ejecuta al mismo tiempo que traduce.
Compiladores / Material de Clase Semana 2 / Ciclo 02 - 2015
1.2 Estructura de Compiladores
En un compilador, la parte de anlisis divide el programa fuente en componentes e impone
una estructura gramatical sobre ellas. Despus utiliza esta estructura para obtener una
representacin intermedia del programa fuente. Si la parte del anlisis detecta que el
programa fuente est mal formado en cuanto a la sintaxis; o que no tiene semntica
consistente, entonces debe proporcionar mensajes informativos para que el usuario pueda
corregirlo. La parte del anlisis tambin recolecta informacin sobre el programa fuente y la
almacena en una estructura de datos llamada tabla de smbolos, la cual se pasa junto con la
representacin intermedia a la parte de la sntesis.
La parte de la sntesis constituye el programa destino deseado a partir de la representacin
intermedia y de la informacin en la tabla de smbolos. A la parte del anlisis se le llama
comnmente el front end del compilador; la parte de la sntesis (propiamente la
traduccin) es el back-end.
Anlisis Lxico
A la primera fase de la compilacin se le llama anlisis lxico o escaneo. El analizador lxico
lee el flujo de caracteres que componen el programa fuente y los agrupa en secuencias
Compiladores / Material de Clase Semana 2 / Ciclo 02 - 2015
significativas conocidas como lexema. Para cada lexema, el analizador lxico produce como
salida un token de la forma:
<nombre_token, valor_atributo>
Lexema:
Representan cadenas de caracteres en el programa fuente que se pueden tratar juntos como
una unidad lxica. Un lexema es una secuencia de caracteres en el programa fuente con la
que concuerda el patrn para un componente lxico.
Token:
Son las unidades lgicas que genera el analizador lxico. Formar caracteres en tokens es muy
parecido a formar palabras en un lenguaje natural.
Es el conjunto de cadenas de entrada que produce como salida el mismo componente lxico.
Cada token es una secuencia de caracteres que representa una unidad de informacin en el
programa fuente.
Los componentes lxicos ms comunes son los siguientes:
Palabras clave o reservadas.
Operadores aritmticos.
Operadores relacionales.
Operadores lgicos.
Operador de asignacin.
Identificadores.
Constantes.
Cadenas.
Literales.
Signos de puntuacin.
Libreras.
Anlisis Sintctico
La segunda fase del compilador se llama anlisis semntico o parsing. El parser (analizador
sintctico) utiliza los primeros componentes de los tokens producidos por el analizador
lxico para crear una representacin intermedia en forma de rbol que describa la estructura
gramatical del flujo de tokens. Una representacin tpica es el rbol sintctico, en el cual
cada nodo interior representa una operacin y los hijos del nodo representan los argumentos
de la operacin.
Anlisis Semntico
El analizador semntico, utiliza el rbol sintctico y la informacin en la tabla de smbolos
para comprobar la consistencia semntica del programa fuente con la definicin del lenguaje.
Compiladores / Material de Clase Semana 2 / Ciclo 02 - 2015
Una parte importante del anlisis semntico es la comprobacin (verificacin) de tipos, en
donde el compilador verifica que cada operador tenga operandos que coincidan. Por ejemplo,
muchas definiciones de lenguaje de programacin requieren que el ndice de un arreglo sea
entero; el compilador debe reportar un error si se utiliza un nmero de punto flotante para
indexar el arreglo.
Generacin de Cdigo Intermedio
En el proceso de traducir un programa fuente a cdigo destino, un compilador puede
construir una o ms representaciones intermedias, las cuales pueden tener una variedad de
formas. Los rboles sintcticos son una forma de representacin intermedia; por lo general,
se utilizan durante el anlisis sintctico y semntico.
Despus del anlisis sintctico y semntico del programa fuente, muchos compiladores
generan un nivel bajo explcito, o una representacin intermedia similar al cdigo de
mquina, que podemos considerar como un programa para una mquina abstracta. Esta
representacin intermedia debe tener dos propiedades importantes: debe ser fcil de
producir y fcil de traducir en la mquina destino.
Optimizacin de cdigo
La optimizacin de cdigo independiente de la mquina trata de mejorar el cdigo
intermedio, de manera que se produzca un mejor cdigo destino. Por lo general, mejor
significa ms rpido, pero pueden lograrse otros objetivos, como cdigo ms corto, un cdigo
de destino que consuma menos poder.
Generacin de Cdigo
El generador de cdigo recibe como entrada una representacin intermedia del programa
fuente y la asigna al lenguaje destino. Si el lenguaje destino es cdigo mquina, se seleccionan
registros o ubicaciones (localidades) de memoria para cada una de las variables que utiliza
el programa. Despus, las instrucciones intermedias se traducen en secuencias de
instrucciones de mquina que realizan la misma tarea.
1.3 Pasadas
Son repeticiones que un compilador procesa todo el programa fuente varias veces
antes de generar cdigo.
Despus del paso inicial, donde se construye un rbol sintctico una pasada consiste
en procesar la representacin intermedia agregando informacin a ella, alterando su
estructura o produciendo una representacin diferente.
Las pasadas pueden corresponder o no a las fases, a menudo una pasada consiste en
varias etapas.
4
Compiladores / Material de Clase Semana 2 / Ciclo 02 - 2015
La mayora de los compiladores utilizan ms de una pasada; por lo regular una para
anlisis lxico y sintctico y otra para anlisis semntico y optimizacin a nivel del
objetivo.
Manejo de Errores
Una de las funciones ms importantes en un compilador es su respuesta a los errores
en un programa fuente.
Los errores pueden ser detectados casi durante cualquier fase de la compilacin.
Los errores estticos o de tiempo de compilacin deben ser notificados por un
compilador, y si es importante que el compilador es capaz de generar mensajes de
error.
1.4 ARRANQUE AUTOMTICO Y PORTABILIDAD
Hemos analizado el lenguaje fuente y el lenguaje objetivo como factores determinantes en la
estructura de un compilador y la utilidad de separar cuestiones de lenguaje fuente y objetivo
en etapas inicial y final. Pero no hemos mencionado el tercer lenguaje involucrado en el
proceso de construccin de compiladores: el lenguaje en que el compilador mismo est
escrito. Para que el compilador se ejecute inmediatamente, este lenguaje de implementacin
(o lenguaje anfitrin) tendra que ser lenguaje de mquina.
Un enfoque ms razonable en la actualidad es escribir el compilador en otro lenguaje para el
cual ya exista un compilador. Si el compilador existente ya se ejecuta en la mquina objetivo,
entonces solamente necesitamos compilar el nuevo compilador utilizando el compilador
existente para obtener un programa ejecutable:
1.5 EXPRESIONES REGULARES
Es un equivalente algebraico para un autmata.
Utilizado en muchos lugares como un lenguaje para describir patrones en texto que son
sencillos pero muy tiles.
Pueden definir exactamente los mismos lenguajes que los autmatas pueden describir:
Lenguajes regulares.
Ofrecen algo que los autmatas no: Manera declarativa de expresar las cadenas que queremos
aceptar.
Ser bueno no consiste en no cometer ninguna falta, sino en saber enmendarse
Don Bosco
Compiladores / Material de Clase Semana 2 / Ciclo 02 - 2015
