Comentarios Generales
sobre la Teoría de Compiladores.
Los lenguajes de programación
son las herramientas principales con que los científicos
de la computación trabajan con los computadores.
Hace apenas unas cuantas décadas, en los albores
de programación para computadores, se utilizaban
los llamados lenguajes de primera generación para
hacer que los computadores resolvieran problemas. Estos
lenguajes operan a nivel del código binario de la
maquina, una secuencia de ceros y unos con los que se instruye
al computador para que realice acciones. Así, la
programación era difícil y problemática.
Se dio un pequeño paso adelante con el advenimiento
de la programación en código octal o hexadecimal.
El código de maquina fue reemplazado
por los lenguajes de segunda generación, o lenguajes
ensambladores. Estos lenguajes permiten usar abreviaturas
nemónicas como nombres simbólicos, y la abstracción
ha cambiado del nivel de flip – flop al nivel de
registro.
Para sustituir los lenguajes ensambladores
se crearon los lenguajes de tercera generación,
o lenguajes de alto nivel. Con ellos se puede usar
estructuras de control basadas en objetos de datos lógicos
(TEUF – 91) variables de un tipo especifico. Ofrecen un
nivel de abstracción que permite la especificación
de los datos, funciones o procesos y su control en forma
independiente de la maquina. Entre los lenguajes representativos
de tercera generación estan:
-
ALGOL – 60
-
PASCAL
-
C
-
MODULA - 2
Ensamblador: Un lenguaje
ensamblador es una forma mas comprensible del código
de maquina. Es el primer paso hacia una representación
nemónica del programa. Los ensambladores traducen
programas escritos en lenguaje ensamblador (caracterizado
por el uso de los neumónicos que representan operaciones
de la maquina y quizás direcciones simbólicas)
a código de maquina.
Compilador: los compiladores
traducen programas escritos en un lenguaje de alto nivel
a código intermedio o a código maquina. El
código intermedio puede ser, por ejemplo, un lenguaje
ensamblador o alguna otra forma de representación
intermedia.
Interprete: Un interprete
no genera código objeto si no que analiza y ejecuta
directamente cada posición del código fuente.
Como no se genera código de maquina, en cierta forma
los interpretes son independientes de la maquina. Por lo
general hay que recompilar un interprete para que pueda
ejecutarse en otro hardware destino.
Procesador: entre las tareas
de un procesador podemos contar la sustitución de
macros, la inclusión de archivos o la extensión
del lenguaje. Por ejemplo, el preprocesador de un compilador
de C que comienza con #. Una línea de control como:
#include <stdio.h>
los compiladores a menudo producen, como
resultado del análisis semántico, una forma
de representación intermedia del código
fuente. Hoy en día es cada vez mas común que,
en ambientes de estación de trabajo o de computador
central, todos los compiladores de los distintos lenguajes
generan el mismo código intermedio, el cual después,
por un generador de código, es transformado en el
código objeto. Esto tiene una gran ventaja: si se
cambia el sistema operativo o alguna otra cosa, solo hay
que reemplazar el generador de código, y no todos
los compiladores.
Aspectos Formales.
Los compiladores traducen lenguajes
que usualmente consisten en elementos sintácticos
que pueden ser fácilmente descritos de manera formal.
Por lo tanto, no se pueden estudiar los compiladores sin
considerar los aspectos formales de la definición
de los lenguajes. Sin embargo, la teoría de los lenguajes
formales es una disciplina independiente y así solo
presentaremos del formalismo como lo creamos necesario para
la comprensión de los compiladores.
Definiciones:
Alfabeto: Un alfabeto es
un conjunto arbitrario, pero finito, de símbolos.
Por ejemplo, el código de maquina se basa en el alfabeto
binario A1={0,1}; otros ejemplos son A2{0,1,2,3,4,5,6,7,8,9},
A3{+,-,*,/,} etc.
Símbolos: Los elementos
del vocabulario (alfabeto) de un lenguaje formal se denominan
símbolos; en el caso de los lenguajes naturales los
conocemos como palabras.
Componente Léxico: las
ocurrencias múltiples de símbolos (o palabras)
se denominan componentes léxicos.
Frase: Una frase es una secuencia
de símbolos.
Gramática (sintaxis):
La gramática o la sintaxis de un lenguaje define
si una secuencia arbitraria de símbolos es correcta,
es decir, si es una frase significativa. Decimos que una
frase correcta será aceptada por el lenguaje.
Cadena: Sentencia (finita)
de elementos de un cierto conjunto (alfabeto)
Producción: Las reglas
para la sustitución de cadenas se denominan producciones.
Símbolos terminales: Son
los símbolos que realmente aparecen en una frase.
Símbolos no terminales:
Los símbolos no terminales deben ser definidos por
otras producciones (o reglas BNF, véase sec. 2.1);
es decir, también aparecen en el lado izquierdo de
las producciones. Los símbolos no terminales son
variables sintácticas.
Vocabulario = alfabeto:
Al igual que los lenguajes naturales, los lenguajes formales
se basan en un vocabulario especifico, a saber, los elementos
del lenguaje.
- Forma de Backus – Naur (BNF)
La forma de Backus – Naur fue creada para
definir la estructura del lenguaje de programación
ALGOL60 (véase NAUR 73)
Tabla 2.1 Notación BNF.
|
|
|
Símbolo
|
Significado
|
à
|
"se define como"
fin de definición
|
|
|
"or", alternativa
|
[x]
|
Una o ninguna ocurrencia de x
|
{x}
|
Numero arbitrario de ocurrencias de x(0,1,2,...)
|
(x | y)
|
Selección (x o y)
|
|
La forma Backus – Naur es un metalenguaje,
o sea, un lenguaje con que se describen otros lenguajes.
Hay algunos dialectos de la notación BNF. En la tabla
2.1. se presentan algunos de los (meta-) símbolos
mas comunes de la BNF. Con esa notación y los símbolos
terminales.
T= {+,-, 0,1,2,3,4,5,6,7,8,9}
Además de los símbolos no
terminales
N= {int, unsigned_int, digit}
Podemos definir los enteros con las siguientes
reglas (producciones) BNF:
int à
[+ | - ] unsigned_int
unsigned_int à
digit unsigned_int digit.
digit à
0|1|2|3|4|5|6|7|8|9|
La primera regla define un entero como
un entero sin signo mas un signo inicial. Este signo puede
estar ausente o ser "+" o "-". La segunda
regla indica que la notación BNF permite definiciones
recursivas.
Existe una descripción formal
de un lenguaje si existe un numero finito de reglas BNF
que permiten derivar cualquier frase del lenguaje. En este
aspecto, el conjunto finito de reglas anterior es una descripción
formal del conjunto infinito de los enteros.
2.2 Lenguajes Formales
En esta sección haremos
una breve introducción a los lenguajes formales,
presentando los términos y reglas importantes para
la teoría de los compiladores. El campo de los lenguajes
formales es muy amplio y constituye un área de investigación
independiente.
La BNF es un metalenguaje muy utilizado
para definir la estructura sintáctica de un lenguaje
de programación. Pero también podría
servir para describir enunciados en español. Usaremos
este ejemplo para explicar algunas de las reglas y la terminología
de los lenguajes formales. Presentando asi una breve introducción
a las ideas de Noam Chomsky, quien intento formalizar los
lenguajes naturales. Por ejemplo, un enunciado en español
(E) consiste en una "frase nominal" (FN) y una
"frase verbal" (FV). En BNF, esto se describiría
como:
E à
FN FV
En esta producción, FN y FV son
símbolos no terminales.
Un lenguaje que acepta la frase
El hombre tomo el balón
Podría definirse con las siguientes
producciones:
E à
FN FV
FN à
A N
A à
el
N à
hombre | balón | libro
FV à
V FN
V à
tomo | compró
Por lo tanto, el lenguaje definido
consta de los 18 enunciados siguientes (obviamente este
lenguaje considera la sintaxis del español, pero
dista mucho del español cotidiano que consiste en
sintaxis y semantica):
el hombre tomo el hombre el hombre tomo
el balón
el hombre tomo el libro el hombre
compro el hombre
el hombre compro el balón el
hombre compro el libro
el balón tomo el hombre el
balón tomo el balón
el balón tomo el libro el
balón compro el hombre
el balón compro el balón el
balón compro el libro
el libro tomo el hombre el libro tomo
el balón
el libro tomo el balón el
libro compro el hombre
el libro compro el balón el libro
compro el libro
Propiedades y definiciones.
Al considerar el proceso de derivación
podemos hallar dos estrategias importantes: derivaciones
por la izquierda y derivaciones por la derecha. Una
derivación se denomina por la izquierda (o por la
derecha) si siempre se reemplaza el no terminal mas a la
izquierda (o mas a la derecha). Esta definición es
necesaria para comprender el funcionamiento de varios métodos
de análisis sintáctico (véase Cap.
4). Un poco mas adelante, en esta sección, presentamos
ejemplos de derivaciones por la izquierda y por la derecha.
Una regla BNF
V à
s
Especifica que un solo símbolo no
terminal v Î N puede ser
substituido por s Î
(N È T) sin importar el
contexto donde aparezca v. Estas producciones se conocen
como independientes del contexto.
De acuerdo con N. Chomsky, una gramática
y un lenguaje correspondiente son independientes del contexto
si y solo si pueden definirse con un conjunto de producciones
independientes del contexto. Las gramáticas independientes
del contexto son muy importantes en la teoría de
los lenguajes de programación, ya que los lenguajes
que definen tienen, en general, una estructura muy sencilla.
Las técnicas de análisis sintáctico
suelen basarse en gramáticas independientes del contexto.
Una gramática independiente
del contexto es no ambigua si y solo si hay una sola
derivación por la derecha (o por la izquierda) y,
por ende, un solo árbol de análisis sintáctico
(es decir, la secuencia de derivaciones representada como
estructura de árbol) para cada frase que pueda derivarse
con las producciones de la gramática. En caso contrario
se le llama ambigua. Mas adelante en este capitulo
veremos algunos ejemplos de la ambigüedad, cuando hayamos
presentado los árboles de análisis sintáctico.
Una frase de una gramática ambigua
puede tener mas de un árbol de análisis sintáctico
y, por consiguiente, mas de un significado. Por ello, las
gramáticas ambiguas no son muy útiles ara
el análisis y la definición de los lenguajes
de programación.
Jerarquía de Gramáticas
Las gramáticas se clasifican de
acuerdo con su complejidad. Esta clasificación, conocida
como jerarquía de Chomsky, se establece aumentado
las restricciones sobre la forma de las producciones (véase
Fig. 2.1)
Las gramáticas de tipo 0 son
gramáticas sin restricciones, es decir, no
hay restricciones para el lado izquierdo ni para el lado
derecho de las producciones. Estas gramáticas generales
no tienen relevancia en los lenguajes de programación
de la actualidad. Escribir un analizador sintáctico
para una gramática de tipo 0 seria una tarea muy
ardua. Las formas d las producciones de las gramáticas
de tipo 1 implica que las sustituciones solo pueden efectuarse
en cierto contexto, esto es, son gramáticas dependientes
del contexto. En cambio, las gramáticas de tipo
2 son independientes del contexto, mientras que
las gramáticas lineales izquierda y derecha de tipo
3 son gramáticas regulares. Por supuesto,
una gramática de tipo i+1 también es de tipo
i, i = 0,1,2.
Figura 2.1 Jerarquía de Chomsky.
Árboles de Análisis
Sintáctico
Hasta ahora hemos mostrado que se puede
usar una gramática para generar frases de un lenguaje
especifico. Pero un compilador no debe generar programas,
sino revisar cadenas de símbolos para determinar
si pertenecen o no al lenguaje; es decir, encontrar de que
manera se puede derivar una secuencia de símbolos
a partir del inicial mediante las producciones gramaticales,
para luego exhibir la derivación (o mostrar que la
frase no puede derivarse del símbolo inicial). Este
problema se conoce como problema de análisis sintáctico.
Podemos ilustrar este proceso de
derivación con un árbol, como muestra a continuación.
Para este ejemplo, definamos una gramática G0
(T0, N0, P0, S0)
que acepta expresiones arimeticas como x+y-x-y.
T0 = {x,y,+,-,*,/,(,)}
N0 = {EXPR, TERM, FACTOR}
P0 = {EXPR à
TERM | EXPR + TERM | EXPR – TERM
TERM à
FACTOR | TERM * FACTOR | TERM / FACTOR
FACTOR à
X | Y | (EXPR)}
S0 = {EXPR}
Vemos que cada expresión es una
secuencia de términos separados por "+"
o "-". En la figura 2.2 se muestra el árbol
de análisis sintáctico de la expresión
x + y – x * y; representa gráficamente la derivación
de una frase del lenguaje de acuerdo con la gramática
G0 (T0, N0, P0,
S0).
También podemos considerar la
derivación por la izquierda de x + y – x*y:
EXPR à
EXPR – TERM
-
EXPR + TERM – TERM
-
TERM + TERM – TERM
-
FACTOR + TERM – TERM
-
X – TERM – TERM
-
X – FACTOR – TERM
Figura 2.2 Árbol de análisis
sintáctico para la expresión x+y – x * z
à
x + y – TERM
à
x + y – TERM * FACTOR
à
x + y – FACTOR * FACTOR
à
x + y – x * FACTOR
à x
+ y – x * y
La derivación por la derecha es:
EXPR à
EXPR – TERM
-
EXPR – TERM * FACTOR
-
EXPR – TERM * y
-
EXPR – FACTOR * y
-
EXPR – x * y
-
EXPR – x * y
-
EXPR – TERM – x * y
-
EXPR – FACTOR – x * y.
-
EXPR + y –x * y
-
TERM + y – x *y
-
FACTOR + y – x * y
-
x + y – x * y
Técnicas del análisis.
En la sección anterior
vimos como una gramática G0 (T0,
N0, P0, S0) puede definir
formalmente un lenguaje y como puede generarse o dedicarse
una frase especifica. Entonces la tarea de un compilador
no es la generación de una frase, si no la identificación
de una frase.
El análisis sintáctico
es el proceso donde hay que determinar el árbol sintáctico
correspondiente a una frase dada, de acuerdo con la gramática
del lenguaje de programación. En principio hay dos
métodos para realizar este análisis.
- Análisis sintáctico descendente, y
- Análisis sintáctico ascendente
El primer método parte de la raíz
del árbol sintáctico y desciende hasta las
hojas; el segundo opera en orden inverso, comenzando por
las hojas.
Análisis sintáctico
descendente
Explicaremos este método con
un ejemplo, usando la siguiente gramática simple,
G1 (T1, N1, P1,
S1) que define los enteros no negativos (ENN)
T1 = {0,1,2,3,4,5,6,7,8,9}
N1 = {DIGITO, ENN}
P1 = {ENN à
DIGITO | ENN DIGITO}
DIGITO à
0|1|2|3|4|5|6|7|8|9|
S1 = {ENN}
Queremos analizar la frase 123. en
un principio solo conocemos la raíz del árbol
y la frase que debe analizarse.
Árbol semántico frase
ENN 1 2 3
En el primer paso encontramos la producción
ENN à ENN DIGITO y obtenemos
el inicio del árbol de análisis sintáctico.
En el siguiente paso hallamos de nuevo
al misma producción.
Después encontramos la producción
ENN à DIGITO, que expande
el árbol sintáctico a lo siguiente:
Encontramos ahora la producción DIGITO à
1, que establece la conexión con el primer elemento
de la frase dada.
La producción DIGITO à
2 establece la conexión con el segundo elemento de
la frase:
Por ultimo el árbol de análisis
sintáctico queda completo con la producción
DIGITO à 3.
Podemos ver que el árbol crece de
arriba abajo a medida que se lee la frase de entrada de
izquierda a derecha. por consiguiente, este método
se denomina análisis sintáctico descendente.
Análisis sintáctico
ascendente.
Ejemplifiquemos
el análisis sintáctico ascendente usando otra
vez la gramática G1 y la frase 123. de nuevo, solo
sabemos cual es la raíz del árbol de análisis
sintáctico y la frase que debemos de analizar. En
el primer paso se encuentran la reducción 1 ß
DIGITO y se obtiene el inicio del árbol sintáctico.
En el segundo paso se encuentra la reduccion
del DIGITO ß ENN y se
obtiene el segundo arbol sintactico
El tercer paso reduce el
segundo elemento de la frase usando la reducción
2 ß DIGITO
Entonces se aplica la reducción
DIGITO ß ENN para continuar
con el arbol de análisis sintactico:
En el paso siguiente se reduce a un digito
el ultimo elemento de la frase: 3 ß
DIGITO.
Para concluir se completa el árbol
de análisis sintáctico con la reducción
ENN DIGITO ß ENN:
A partir de este ejemplo podemos ver que
comenzamos con las hojas del árbol sintáctico
y asciende hacia la raíz. Por ello, este método
se denomina análisis sintáctico ascendente.
2.4 Grafos sintácticos.
Una forma de representar la estructura
sintáctica de un lenguaje es con la notación
BNF. Los grafos sintácticos son otra manera
(grafica) de representar la sintaxis de un lenguaje. La
representación grafica de la sintaxis facilita el
estudio de una definición de lenguaje.
La representación del lenguaje con
grafos sintácticos es equivalente a la representación
con la BNF. De acuerdo con [WIRT86], introducimos 6 reglas
que permiten la transformación de una notación
BNF a un grafo sintáctico.
R1. Las producciones
de la forma.
N à
s 1 | s
2 ... s n
Se representa con el siguiente grafo:
R2. Los términos
de la forma
s à
a1 | a2 ... an
Se representa con el siguiente grafo:
|