Date post: | 22-Dec-2015 |
Category: |
Documents |
Upload: | christian-mirsha-velasco-castilla |
View: | 63 times |
Download: | 7 times |
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 8
Unidad 1. Introducción a los lenguajes formales.
En primer lugar, se debe esclarecer los términos de Lenguaje Formal y Lenguaje Natural. Es posible
distinguir a ambos por medio de la pregunta “¿qué surgió primero, el lenguaje o sus reglas
gramaticales?”. En general, un lenguaje natural es aquel que ha evolucionado con el paso del
tiempo para fines de la comunicación humana, por ejemplo, el español, el inglés o el alemán. Estos
lenguajes continúan su evolución sin tomar en cuenta reglas gramaticales formales; cualquier
regla se desarrolla después de que sucede el hecho en un intento por explicar, y no determinar, la
estructura de un lenguaje. Como resultado de esto, pocas veces los lenguajes naturales se ajustan
a reglas gramaticales sencillas u obvias.
En contraste con los lenguajes naturales, los formales están definidos por reglas preestablecidas y,
por lo tanto, se ajustan a todo rigor a ellas. Como ejemplo se tienen a los lenguajes de
programación de computadoras y los lenguajes matemáticos como el álgebra y la lógica de
proposiciones. Gracias a esta adhesión a las reglas, es posible construir traductores
computarizados eficientes para los lenguajes de programación, a la vez que la falta de observancia
a las reglas establecidas dificulta la construcción de un traductor para un lenguaje natural.
(Brookshear. 2005).
La teoría de los lenguajes formales tiene su origen en un campo aparentemente bastante alejado
de la informática: la Lingüística. El primer trabajo que desarrolló teorías formales sobre gramáticas
y lenguajes fue obra de Avram Noam Chomsky quién es sin duda la figura más destacada de la
lingüística moderna, tanto para desarrollar sus fundamentos matemáticos, como por sus teorías
sobre el origen y la naturaleza de los lenguajes naturales.
En el campo de la Informática, poco después de las primeras publicaciones de Chomsky, el
concepto de gramática formar adquirió una gran importancia para la especificaciones de lenguajes
de programación. Concretamente, se definió con sus teorías las sintaxis del lenguaje ALGOL,
usándose una gramática libre de contexto. Ello condujo rápidamente al diseño riguroso de
algoritmos de traducción y compilación.
Finalmente, y enlazando con el campo de la lingüística, la Teoría de Lenguajes Formales es de gran
utilidad para el trabajo de otros campos de la informática por ejemplo: en Informática Teórica,
Inteligencia Artificial, Procesamiento de Lenguajes Naturales y Reconocimiento del habla.
La teoría de los Lenguajes y Gramáticas Formales tiene una relación directa con la Teoría de
Autómatas, siendo posible establecer entre ambas una correspondencia denominada (en álgebra)
Isomorfismo.
La Teoría de los Autómatas proviene del campo de la Ingeniería Eléctrica. Claude Elwood Shannon
publicó varios trabajos, donde mostraba las bases para la aplicación de la lógica matemática a los
circuitos combinatorios y secuencias. A lo largo de las décadas siguientes, las ideas de Shannon se
desarrollaron considerablemente. Los autómatas son sistemas que reciben información, la
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 9
transforman y producen otra información que se transmite al entorno. Esta teoría tiene aplicación
en campos muy diversos:
Lógica de los circuitos secuenciales.
Teoría de control de sistemas.
Teoría de la comunicación.
Arquitectura de computadoras.
Redes de comunicación.
Teorías de los sistemas evolutivos.
Reconocimiento de patrones.
Redes neuronales.
Reconocimiento y procesado de lenguajes de programación.
Traducción de lenguajes. (Cueva, 2001).
1.1 Alfabeto.
El Alfabeto es un “conjunto de símbolos empleados en un sistema de comunicación” (RAE, 2001) y
que dan forma al Abecedario o una serie de las letras de un idioma para representar de una
manera escrita los conceptos e ideas que se desean transmitir de entre un emisor y un receptor a
través de un mensaje.
En el idioma español, las letras “A”, “B”, “C”,…, “X”, “Y”, “Z” tanto en mayúsculas como en
minúsculas forman parte del alfabeto. Los símbolos como el punto “.”, la coma “,”, el acento “´”,
los signos de interrogación “¿?”, los de admiración “¡!” y demás también lo integran.
Prácticamente todos elementos gráficos con los cuales contamos para escribir un texto,
cumpliendo ciertas reglas léxicas, sintácticas y semánticas, nos permite dotarle de significado así
como de coherencia para poder comunicarnos con las demás personas a través del mismo.
La noción más primitiva es la de símbolo que es simplemente una representación distinguible de
cualquier información. Un símbolo es una entidad indivisible. El alfabeto es un conjunto no vacío
de símbolos. Así, el alfabeto del idioma español está conformado entonces por:
zyxcba ,,,...,,,
(Brena, 2003).
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 10
1.2 Cadenas de caracteres.
Con los símbolos de un alfabeto es posible formar secuencias o cadenas de caracteres, tales como
“mxzjptlk”, “balks”, “r”, etcétera. Las cadenas de caracteres son llamadas también Palabras. Un
caso particular de una cadena de texto es la palabra vacía, ε, la cual no tiene ninguna letra.
La longitud de una palabra es la cantidad de letras que contiene, contando las repeticiones. Se
denota por |ω| para una palabra ω. Por ejemplo, |perro| tiene una longitud 5.
Cuando se escriben varias palabras o caracteres uno a continuación de otro, se supone que
forman una sola palabra (se concatenan). La notación usada para denotar la concatenación de dos
cadenas α y β es αβ. Por ejemplo, si ω = “abra” y χ = “cada”, la concatenación de tales cadenas de
caracteres junto con la cadena de texto “ωχbra” da como resultado una nueva cadena de texto
“abracadabra” con una longitud de 11 símbolos o caracteres.
La concatenación de palabras es asociativa, esto es, (χγ)ζ es igual a χ(γζ), pero no conmutativa. La
longitud de una concatenación cumple la propiedad |χγ|=|χ|+|γ|.
Una palabra ν es una subcadena de otra ω cuando existen cadenas χ, γ – posiblemente vacías –
tales que χνγ sea igual a ω. Por ejemplo, “bora” es subcadena de “víbora” y ε es subcadena de
toda palabra.
El conjunto de todas las palabras que se pueden formar con un alfabeto ∑ es denotado
convencionalmente por ∑*. Por ejemplo, si ∑ = {a, b} entonces ∑* = {ε, a, aa, aaa,…, b, bb, bbb,…,
ab, ba, abba, baab,…}. Normalmente el conjunto ∑* es infinito, pero enumerable. (Brena, 2003).
1.3 Lenguajes.
Un lenguaje es simplemente un conjunto de palabras. Así, {abracadabra} es un lenguaje de una
sola palabra. {ali, baba, y, sus, cuarenta, ladrones} es otro. Puesto que los lenguajes son conjuntos,
se puede efectuar con ellos todas las operaciones de los conjuntos (Unión, Intersección,
Diferencia). Se define además la operación Concatenación de Lenguajes, escrita como: L1 • L2
como una extensión de la concatenación de palabras. Se denota como sigue:
},,|{ 2121 LyLxxyLL
Por ejemplo, dados los lenguajes L1 = {ca, ma} y L2 = {nta, sa} la concatenación de los dos
lenguajes sería {canta, casa, manta, masa}. Como se aprecia en este ejemplo, para calcular la
concatenación de dos lenguajes hay que concatenar cada palabra del primero de ellos con cada
una del segundo.
Otra operación que involucra a los lenguajes es la Estrella de Kleene o Cerradura de Kleene en
honor al matemático norteamericano Stephen Cole Kleene. Su logro más importante es la Teoría
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 11
de la Recursividad con la cual ayudo a fortalecer y formalizar las ciencias computacionales.
Además fue inventor de varios conceptos matemáticos como la Jerarquía de Kleene, el Álgebra de
Kleene y el Teorema del Punto Fijo de Kleene. También estableció el término “Expresiones
Regulares”. Vea la figura 1.
Figura 1. Stephen Cole Kleene.
Tal contribución indica que si L es un lenguaje, L*, llamado “Cerradura de Kleene” de L, es el más
pequeño conjunto que contiene:
La palabra vacía, ε.
El conjunto L.
Todas las palabras formadas por la concatenación de miembros de L*.
Por ejemplo, si L = {abra, cadabra}, L* = {ε, abra, abraabra, abracadabra, cadabraabra,…}.
Obsérvese que la definición de la Cerradura de Kleene es recursiva, pues en la tercera regla se
supone que ya hay palabras en L*, las cuales pueden concatenarse para producir una nueva
palabra.
Esta definición es congruente con la notación ∑* que se utilizó para definir el conjunto de todas las
palabras sobre un alfabeto, pues de hecho ∑* es la Cerradura de Kleene del alfabeto, tomando los
símbolos de éste como palabras de una letra. (Brena, 2003).
1.4 Tipos de lenguajes.
Se le llama “Clase de Lenguajes” a conjuntos de lenguajes que comparten una cierta propiedad
dada. Esta noción es muy abstracta, pues ya los lenguajes son en sí mismos conjuntos de
secuencias de símbolos, y las clases de lenguajes son entonces conjuntos de conjuntos de
secuencias de símbolos.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 12
La clasificación de lenguajes en Clases de Lenguajes es debida a Avram Noam Chomsky (figura,
profesor emérito de lingüística del Instituto Tecnológico de Massachusetts (MIT), y es muy
importante para la Teoría de la Computación. En ella, se establecen que las “clases más complejas
incluyen a las más simples”. Vea la figura 2.
Los “Lenguajes Regulares”, es la clase más pequeña e incluye a los lenguajes más simples.
Un ejemplo de lenguaje regular es el conjunto de todos los números binarios.
Los “Lenguajes Libres de Contexto”, que incluyen a los Lenguajes Regulares. Por ejemplo,
la mayoría de los lenguajes de programación son Lenguajes Libres de Contexto.
Los “Lenguajes Recursivamente Enumerables”, que incluyen a los Lenguajes Libres de
Contexto y por lo tanto a los Lenguajes Regulares.
Figura 2. Avram Noam Chomsky.
Todas estas clases de lenguajes son representables de manera finita (mediante cadenas de
caracteres que sirven como representación). Ahora bien, hay más lenguajes que posibles
representaciones finitas, por lo que se puede intuir que hay lenguajes más allá de los
Recursivamente Enumerables. Sin embargo, desde el punto de vista práctico, los lenguajes más
útiles son aquellos que tienen una representación finita, por lo que los demás lenguajes son sólo
de interés teórico. Cada una de estas clases está asociada a un tipo de Autómata capaz de
procesar estos lenguajes. Esto hace pensar que las categorías de Chomsky tienen una validez y no
son arbitrarias. (Brena, 2003).
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 13
Figura 3. Los lenguajes regulares en la jerarquía de Chomsky.
1.5 Herramientas computacionales ligadas con lenguajes.
Los lenguajes de programación son notaciones que describen los cálculos a las personas y las
máquinas. Nuestra percepción del mundo en que vivimos depende de los lenguajes de
programación, ya que todo el software que se ejecuta en todas las computadoras se escribió en
algún lenguaje de programación. Pero antes de poder ejecutar un programa, primero debe
traducirse a un formato en el que una computadora pueda ejecutarlo. Los sistemas de software
que se encargan de esta conversión se llaman Traductores. (Aho, et. al. 2008). Ellos, normalmente
son las herramientas computacionales ligadas con lenguajes, sin embargo no son las únicas.
1.6 Estructura de un traductor.
Dicho en forma simple, un Traductor es un programa que puede leer un programa en un lenguaje
(el lenguaje fuente) y convertirlo en un programa equivalente en otro lenguaje (el lenguaje
destino). Una función importante del traductor es reportar cualquier error en el programa fuente
que detecte durante el proceso. Existen dos tipos de traductores: el Compilador y el Intérprete.
Vea la figura 4.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 14
Figura 4. Un Compilador.
Si el programa objeto es un programa ejecutable en código máquina, entonces el usuario puede
ejecutarlo para procesar las entradas y producir salidas (resultados). Vea la figura 5.
Figura 5. Ejecución del programa de Destino.
Un Intérprete es otro tipo común de procesador de lenguaje. En vez de producir un programa
destino como en una compilación, el intérprete nos da la apariencia de ejecutar directamente las
operaciones especificadas en el programa de origen (fuente) con las entradas proporcionadas por
el usuario. Vea la figura 6.
Figura 6. Un Intérprete.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 15
El programa destino en código máquina que produce un compilador es, por lo general, más rápido
que un intérprete al momento de asignar las entradas a las salidas. No obstante, por lo regular, el
intérprete puede ofrecer mejores diagnósticos de error que un compilador, ya que ejecuta el
programa fuente instrucción por instrucción.
Además de un compilador, pueden requerirse otros programas más para la creación de un
programa destino ejecutable, como se muestra en la figura 6.
Un programa fuente puede dividirse en módulos guardados en archivos separados. La tarea de
recolectar el programa de origen se confía algunas veces a un programa separado, llamado
Preprocesador. El preprocesador también puede expandir algunos fragmentos de código
abreviados de uso frecuente, llamados macros, en instrucciones del lenguaje fuente.
Después, el programa fuente ya modificado se alimenta a un compilador. El compilador puede
producir un programa destino escrito en Lenguaje Ensamblador como su salida, ya que es más fácil
su depuración. A continuación, el lenguaje ensamblador se procesa mediante un programa
llamado Ensamblador, el cual produce código máquina relocalizable como su salida.
A menudo, los programas extensos se compilan en partes, por lo que tal vez haya que enlazar
(vincular) el código máquina relocalizable con otros archivos objeto relocalizables y archivos de
biblioteca para producir el código que se ejecute en realidad en la máquina. El Enlazador resuelve
las direcciones de memoria externas, en donde el código de un archivo puede hacer referencia a
una ubicación en otro archivo. Entonces, el Cargador reúne todos los archivos objeto ejecutable en
la memoria para su ejecución. (Aho, et. al., 2008).
En resumen, el proceso de traducción consta de cinco componentes básicos: análisis léxico,
análisis sintáctico, análisis semántico, optimización y generación de código como se plantea en la
siguiente sección y en la figura 8. Los primeros dos componentes dependen en gran medida de la
capacidad para reconocer patrones. Si éstos se basan en reglas gramaticales, entonces el proceso
de reconocimiento también puede apoyarse en estas reglas. Lo anterior sucede al procesar un
lenguaje formal. Sin embargo, si el lenguaje que se traduce no se adhiere estrictamente a reglas
gramaticales bien definidas, puede ser muy difícil construir un segmento de programa para el
análisis sintáctico del lenguaje. Consulte la siguiente sección. (Brookshear, 2005).
1.7 Fases de un compilador.
Hasta este punto se ha tratado al compilador como una caja simple que mapea un programa
fuente a un programa destino con equivalencia semántica. Si se abre esta caja un poco, se puede
observar que hay dos procesos en esta asignación: análisis y síntesis.
La parte de Análisis divide el programa fuente en componentes e impone una estructura
gramatical sobre ellas. Después utiliza esta estructura para crear una Representación Intermedia
del programa fuente. Si la parte de análisis detecta que el programa fuente está mal formado en
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 16
cuanto a la sintaxis, o que no tiene una semántica consistente, entonces debe proporcionar
mensajes informativos para que el usuario pueda corregirlo. La parte de análisis también recolecta
información sobre el programa fuente y la almacena en una estructura de datos llamada Tabla de
Símbolos, la cual pasa junto con la representación intermedia a la parte de la síntesis.
La parte de la Síntesis construye el programa destino deseado a partir de la representación
intermedia y de la información en la tabla de símbolos. A la parte del análisis se le llama
comúnmente el front-end del compilador; la parte de la síntesis (propiamente la traducción) es el
back-end.
Figura 7. Un sistema de procesamiento de lenguajes.
Si se examina el proceso de compilación con más detalle se puede ver que opera como una
secuencia de fases, cada una de las cuales transforma una representación del programa fuente en
otro. La figura 8 muestra una descomposición típica de un compilador en fases. En la práctica
varias fases pueden agruparse, y las representaciones intermedias entre las fases agrupadas no
necesitan construirse de manera explícita.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 17
Figura 8. Fases de un Compilador.
La tabla de símbolos y el manejador de errores son partes del compilador que son utilizadas
durante todas las fases o componentes ya que almacenan información de importancia y muestran
las inconsistencias detectadas.
Algunos compiladores tienen una fase de optimización de código independiente de la máquina,
entre el front-end y el back-end. El propósito de esta optimización es realizar transformaciones
sobre la representación intermedia, para que el back-end pueda producir un mejor programa
destino de lo que hubiera producido con una representación intermedia sin optimizar.
Análisis de léxico.
A la primera fase de un compilador se le llama análisis de léxico o escaneo. El analizador de léxico
lee el flujo de caracteres que componen el programa fuente y los agrupa en secuencias
significativas conocidas como lexemas. Para cada lexema, el analizador léxico produce como salida
un token de la forma:
‹nombre-token, valor-atributo›
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 18
Tal forma pasa a la siguiente fase, el análisis de la sintaxis. En el token, el primer componente
nombre-token es un símbolo abstracto que se utiliza durante el análisis sintáctico, y el segundo
componente valor-atributo apunta a una entrada en la tabla de símbolos para este token. La
información de la entrada en la tabla de símbolos se necesita para el análisis semántico y la
generación de código.
Por ejemplo, suponga que un programa fuente contiene la instrucción de asignación:
posición = inicial + velocidad * 60
Los caracteres en esta asignación podrían agruparse en los siguientes lexemas y mapearse a los
siguientes tokens que se pasan al analizador sintáctico:
posición es un lexema que se asigna a un token‹id, 1›, en donde id es un símbolo
abstracto que representa la palabra identificador y 1 apunta a la entrada en la tabla de
símbolos para posición. La entrada en la tabla de símbolos para un identificador
contiene información acerca de éste, como su nombre y tipo.
El símbolo de asignación = es un lexema que se asigna al token‹=›. Como este token no
necesita un valor-atributo, se omite el segundo componente. Se podría haber
utilizado cualquier símbolo abstracto como asignar para el nombre-token, pero por
conveniencia de notación se opta por usar el mismo lexema como el nombre del símbolo
abstracto.
inicial es un lexema que se asigna al token‹id, 2›, en donde 2 apunta a la entrada en
la tabla de símbolos para inicial.
+ es un lexema que se asigna al token‹+›.
velocidad es un lexema que se asigna al token‹id, 3›, en donde 3 apunta a la entrada
en la tabla de símbolos para velocidad.
*es un lexema que se asigna al token‹*›.
60 es un lexema que se asigna al token‹60›.
El analizador léxico ignora los espacios en blanco que separan a los lexemas. La figura 8 muestra la
representación de la instrucción de asignación después del análisis léxico como la secuencia de
tokens: ‹id, 1›‹=›‹id, 2›‹+›‹id, 3›‹*›‹60›. En esta representación, los nombres de los
tokens=, + y * son símbolos abstractos para los operadores de asignación, suma y multiplicación.
Análisis sintáctico.
La segunda fase del compilador es el análisis sintáctico o parsing. El parser (analizador sintáctico)
utiliza los primeros componentes de los tokens producidos por el analizador léxico para crear una
representación intermedia en forma de árbol que describa la estructura gramatical del flujo de
tokens. Una representación típica es el árbol sintáctico, en el cual cada nodo interior representa
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 19
una operación y los hijos del nodo representan los argumentos de la operación. La figura 8
muestra un árbol sintáctico para el flujo de tokens como salida del analizador sintáctico.
Éste árbol muestra el orden en el deben de llevarse a cabo las operaciones en la siguiente
asignación: posición = inicial + velocidad * 60. El árbol tiene un nodo interior
etiquetado como *, con ‹id, 3› como su hijo izquierdo, y el entero 60 como su hijo derecho. El
nodo ‹id, 3› representa al identificador como velocidad. El nodo etiquetado como * hace
explícito que primero se debe multiplicar el valor de velocidad por 60. El nodo etiquetado como
+ indica que debemos sumar el resultado de esta multiplicación al valor de inicial. La raíz del
árbol, que se etiqueta como =, indica que se debe almacenar el resultado de esta suma en la
ubicación del identificador posición. Este ordenamiento de operaciones es consistente con las
convenciones usadas de la aritmética, las cuales nos indican que la multiplicación tiene mayor
precedencia que la suma y, por ende, debe realizarse antes de que la suma.
Las fases siguientes del compilador utilizan una estructura gramatical para ayudar al programa
fuente y generar el programa fuente y generar el programa destino.
Análisis semántico.
El analizador semántico utiliza el árbol sintáctico y la información en la tabla de símbolos para
comprobar la consistencia semántica del programa fuente con la definición del lenguaje. También
recopila información sobre el tipo y la guarda, ya sea en el árbol sintáctico o en la tabla de
símbolos, para usarla más tarde durante la generación de código intermedio.
Una parte importante del análisis semántico es la comprobación (verificación) de tipos, en donde
el compilador verifica que cada operador tenga operandos que coincidan. Por ejemplo, muchas
definiciones de lenguajes de programación requieren que el índice del arreglo sea entero; el
compilador debe marcar un error si se utiliza un número de punto flotante para indexar el arreglo.
La especificación del lenguaje puede permitir ciertas conversiones de tipo conocidas como
coerciones. Por ejemplo, puede aplicarse un operador binario aritmético a un par de enteros o a
un par de números de punto flotante. Si el operador se aplica a un número de punto flotante y a
un entero, el compilador puede convertir u obligar a que se convierta en un número de punto
flotante.
Dicha conversión aparece en la figura 8. Suponga que posición, inicial y velocidad se han
establecido como números de punto flotante, y que el lexema 60 por sí solo forma un entero. El
comprobador de tipo en el analizador semántico descubre que se aplica el operador * al número
de punto flotante velocidad y al entero 60. En este caso, el entero puede convertirse en un
número de punto flotante. Observe la figura 8 que la salida del analizador semántico tiene un
nodo adicional para el operador convertirEnteroReal(), que convierte de manera explícita
su argumento tipo entero en un número de punto flotante.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 20
Generación de código intermedio.
En el proceso de traducir un programa fuente a código destino, un compilador puede construir
una o más representaciones intermedias, las cuales pueden tener una variedad de formas. Los
árboles sintácticos son una forma de representación intermedia; por lo general, se utilizan durante
el análisis sintáctico y semántico.
Después del análisis sintáctico y semántico del programa fuente, muchos compiladores generan
un nivel bajo explícito, o una representación intermedia similar al código máquina, que se puede
considerar como un programa para una máquina abstracta. Esta representación intermedia debe
tener dos propiedades importantes: debe ser fácil de producir y fácil de traducir en la máquina
destino.
El código de tres direcciones es una secuencia de instrucciones similares al lenguaje ensamblador,
con tres operandos por instrucción. Cada operando puede actuar como un registro. La salida del
generador de código intermedio de la figura 8 consiste en una secuencia de este tipo de código.
temp1 = convertirEnteroReal(60)
temp2 = id3 * temp1
temp3 = id2 + temp2
id1 = temp3
Hay varios puntos que vale la pena mencionar sobre las instrucciones de tres direcciones. En
primer lugar, cada instrucción de asignación de tres direcciones tiene, por lo menos, un operador
del lado derecho. Por ende, estas instrucciones corrigen el orden en el que se van a realizar las
operaciones; la multiplicación va antes que la suma en el programa fuente. En segundo lugar, el
compilador debe generar un nombre temporal para guardar el valor calculado por una instrucción
de tres direcciones. En tercer lugar, algunas “instrucciones de tres direcciones” como la primera y
la última en la secuencia anterior, tienen menos de tres operandos.
Optimización de código.
La fase de optimización de código independiente de la máquina trata de mejorar el código
intermedio, de manera que se produzca un mejor código destino. Por lo general, mejor significa
más rápido, pero pueden lograrse otros objetivos, como un código más corto, o un código destino
que consuma menos poder. Por ejemplo, un algoritmo directo genera el código intermedio de la
figura 8, usando una instrucción para cada operador en la representación tipo árbol que produce
el analizador semántico.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 21
Un algoritmo simple de generación de código intermedio, seguido de la optimización de código es
una manera razonable de obtener un buen código de destino. El optimizador puede deducir que la
conversión del 60, de entero a punto flotante, puede realizarse de una vez por todas en tiempo de
compilación, por lo que se puede eliminar la operación convertirEnteroReal() sustituyendo
el entero 60 por el número de punto flotante 60.0. Además, t3 se utiliza sólo una vez para
transmitir su valor a id1, para que el optimizador pueda transformar la conversión en la siguiente
secuencia más corta:
temp1 = id3 * 60.0
id1 = id2 + temp1
Hay una gran variación en la cantidad de optimización de código que realizan los distintos
compiladores. En aquellos que realizan la mayor optimización, a los que se denomina como
“Compiladores Optimizadores”, se invierte mucho tiempo en esta fase. Hay optimizaciones
simples que mejoran en forma considerable el tiempo de ejecución del programa destino, sin
reducir demasiado la velocidad de la compilación.
Generación de código.
El generador de código recibe como entrada una representación intermedia del programa fuente y
la asigna al lenguaje destino. Si el lenguaje destino es código máquina, se seleccionan registros o
ubicaciones (localidades) de memoria para cada una de las variables que utiliza el programa.
Después, las instrucciones intermedias se traducen en secuencias de instrucciones de máquina
que realizan la misma tarea. Un aspecto crucial de la generación de código es la asignación juiciosa
de los registros para guardar las variables.
Por ejemplo, usando los registros R1 y R2, el código intermedio anterior puede traducirse en el
siguiente código de máquina:
MOV R2, id3 MUL #60.0 MOV R1, id2 ADD R1, R2 MOV id1, R1
El primer operando de cada instrucción específica un destino. Cada instrucción trata con números
de punto flotante. El código carga la dirección de memoria de id3 al registro R2 y después lo
multiplica con la constante de punto flotante 60.0. El # indica que el número 60.0 se va a tratar
como una constante inmediata. La tercera instrucción mueve id2 al registro R1 y la cuarta lo
suma al valor que se había calculado antes en el registro R2. Por último, el valor en el registro R1
se almacena en la dirección de id1, por lo que el código implementa en forma correcta la
instrucción de asignación.
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 22
Administración de la tabla de símbolos.
Una función especial de un compilador es registrar los nombres de las variables que se utilizan en
el programa fuente, y recolectar información sobre varios atributos de cada nombre. Estos
atributos pueden proporcionar información acerca del espacio de almacenamiento que se asigna
para un nombre, su tipo, su alcance (en qué parte del programa puede usarse su valor), y en el
caso de los nombres de procedimientos, cosas como el número y los tipos de sus argumentos, el
método para pasar cada argumento (por ejemplo, por valor o por referencia) y el tipo devuelto.
La tabla de símbolos es una estructura de datos que contiene un registro para cada nombre de
variable, con campos para los atributos del nombre. La estructura de datos debe diseñarse de tal
forma que permita al compilador buscar el registro para cada nombre, y almacenar y obtener
datos de ese registro con rapidez.
Manejador de errores.
Si un compilador tuviera que procesar sólo programas correctos, su diseño e implementación se
simplificaría de forma considerable. No obstante, se espera que un compilador ayude al
programador a localizar y rastrear los errores que, de manera inevitable, se infiltran en los
programas, a pesar de los mejores esfuerzos del programador. Aunque parezca increíble, son
pocos los lenguajes que se diseñan teniendo en mente el manejo de errores, aún cuando éstos son
tan comunes.
La mayoría de las especificaciones de los lenguajes de programación no describen la forma en que
compilador debe responder a los errores; el manejo de los mismos es responsabilidad del
diseñador del compilador. La planeación del manejo de los errores desde el principio puede
simplificar la estructura de un compilador y mejorar su capacidad para manejar los errores.
Los errores de programación comunes pueden ocurrir en muchos niveles distintos:
Los errores léxicos incluyen la escritura incorrecta de los identificadores, las palabras clave
o los operadores. Se presentan también en la omisión de comillas alrededor de un texto
que se debe de interpretar como cadena.
Los errores sintácticos incluyen la colocación incorrecta de los signos de punto y coma,
además de llaves adicionales o faltantes; es decir, “{ }” o la aparición de una instrucción
case sin una instrucción switch que la enciende.
Los errores semánticos incluyen los conflictos de tipos entre los operadores y los
operandos. Un ejemplo es una instrucción return en un método Java, con el tipo de
resultado void.
Los errores lógicos pueden ser cualquier cosa, desde un razonamiento incorrecto del
programador en el uso del operador de asignación = en lugar del de comparación == (en
Lenguajes y Autómatas 1 SCD-1015
Mtro. Christian Mirsha Velasco Castilla 23
C). El programa que contenga = puede estar bien formado; sin embargo, tal vez no refleje
la intención del programador.
El manejador de errores en un compilador debe llevar a cabo las siguientes actividades:
Reportar la presencia de errores con claridad y precisión.
Recuperarse de cada error lo bastante rápido como para poder detectar los errores
siguientes.
Agregar una sobrecarga mínima al procesamiento de los programas correctos.
El manejador de errores debe reportar el lugar en el programa fuente en donde se detectó un
error, ya que hay una buena probabilidad de que éste en sí haya ocurrido en uno de los pocos
tokens anteriores. Una estrategia común es imprimir la línea del problema como un apuntador a la
posición en la que se detectó el error. Vea la figura 9. (Aho, et. al., 2008).
Figura 9. Fases de un Compilador, Administrador de Símbolos y Manejador de Errores.