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 A₁={0,1}; otros ejemplos son A₂{0,1,2,3,4,5,6,7,8,9}, A₃{+,-,*,/,} 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.

1. 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.

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 G₀ (T₀, N₀, P₀, S₀) que acepta expresiones arimeticas como x+y-x-y.

T₀ = {x,y,+,-,*,/,(,)}

N₀ = {EXPR, TERM, FACTOR}

P₀ = {EXPR à TERM | EXPR + TERM | EXPR – TERM

TERM à FACTOR | TERM * FACTOR | TERM / FACTOR

FACTOR à X | Y | (EXPR)}

S₀ = {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 G₀ (T₀, N₀, P₀, S₀).

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 G₀ (T₀, N₀, P₀, S₀) 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

Análisis sintáctico descendente

Explicaremos este método con un ejemplo, usando la siguiente gramática simple, G₁ (T₁, N₁, P₁, S₁) que define los enteros no negativos (ENN)

T₁ = {0,1,2,3,4,5,6,7,8,9}

N₁ = {DIGITO, ENN}

P₁ = {ENN à DIGITO | ENN DIGITO}

DIGITO à 0|1|2|3|4|5|6|7|8|9|

S₁ = {ENN}

Queremos analizar la frase 123. en un principio solo conocemos la raíz del árbol y la frase que debe analizarse.

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 ₁ | s ₂ ... s _n

Se representa con el siguiente grafo:

R2. Los términos de la forma

s à a₁ | a₂ ... a_n

Se representa con el siguiente grafo: