Lenguaje Compilador

Funciones de un compilador 

Un compilador es un programa que lee un programa escrito en un lenguaje fuente y lo traduce a un programa equivalente en otro lenguaje, el lenguaje objeto [Aho et al. 1990]. Como parte importante de este proceso de traducción, el compilador informa al usuario de la presencia de errores en el programa fuente. 

En la compilación hay dos partes análisis y síntesis . Durante el análisis se determinan las operaciones que implica el programa fuente y se registran en una estructura jerárquica llamada árbol. A menudo se usa una clase especial de árbol llamado árbol sintáctico , donde cada nodo representa una operación y los hijos del nodo son los argumentos de la operación.

Fases de un Compilador 

Un compilador típicamente opera en fases , cada una lleva a cabo una tarea sobre el programa fuente.

Las primeras tres fases suelen agruparse en una sola fase llamada fase de análisis y las últimas tres en una llamada fase de síntesis. La fase de análisis y el modulo de manejo de errores se describen posteriormente en este mismo capítulo. La fase de síntesis no es relevante en el contexto de un lenguaje multibase de datos, ya que este sigue un enfoque diferente que el de los lenguajes tradicionales, por esta razón solo se menciona. 

Muchas herramientas de software que manipulan programas fuente realizan primero algún tipo de análisis, entre estas se encuentran los editores de estructuras, impresoras estéticas, verificadores estáticos y los interpretes.

Tipos de compiladores

Compilador cruzado: Es el que genera un código objeto ejecutable en un ordenador distinto de aquél en el que se realiza la compilación.

Compilación-Montaje-Ejecución: En las aplicaciones grandes es conveniente fragmentar el programa a realizar en módulos que se compilan por separado, y una vez que estos estén compilados unirlos mediante un programa denominado montador para formar el módulo ejecutable. El montador se encarga, a su vez, de incluir las librerías donde están guardadas las funciones predefinidas de uso común.

Compilación en una o varias pasadas: Se llama pasada a cada lectura que hace el compilador del texto fuente.

Compilación incremental. Este compilador actúa de la siguiente manera. Compila un programa fuente. Caso de detectar errores al volver a compilar el programa corregido sólo compila las modificaciones que se han hecho respecto al primero.

Autocompilador: Es aquél que está escrito en el mismo lenguaje que se pretende compilar. Supongamos, por ejemplo, que queremos desarrollar la versión 2.0 de un compilador Pascal. Dicho compilador generará un código mucho más rápido y eficiente que el que generaba la versión anterior 1.0. Sin embargo, son ya muchas las máquinas (IBM 370, Serie 1, PDP 11, ...) que disponen del antiguo compilador, o que al menos tienen otro compilador Pascal. La mejor opción consiste en escribir el nuevo compilador en Pascal, ya que así podrá (el compilador) ser compilado en las distintas máquinas por los compiladores Pascal ya existentes.

Metacompilador: Es un traductor que tiene como entrada la definición de un lenguaje y como salida el compilador para dicho lenguaje².

Decompilador: Es el que traduce código máquina a lenguaje de alto nivel. Los decompiladores más usuales son los desensambladores, que traducen un programa en lenguaje máquina a otro en ensamblador.

Bootstrapping: Es una técnica muy usada actualmente para el desarrollo de compiladores de lenguajes de alto nivel, en especial si se quiere obtener un autocompilador, o sea, un compilador que se compile a sí mismo.

Para describir el proceso de autocompilación se emplea la notación en T que representa gráficamente los tres lenguajes implicados en el proceso de compilación:

• Lenguaje fuente: Lenguaje origen que traduce el compilador.
• Lenguaje objeto: Lenguaje meta, al cuál traduce el compilador.
• Lenguaje del compilador: Lenguaje en el que está escrito el compilador.

 

Análisis lexicográfico.

La cadena de caracteres que constituye el programa fuente se lee de izquierda a derecha y se agrupa en componentes léxicos, que son secuencias de caracteres que tienen un significado colectivo. El análisis léxico se encarga de hacer esta agrupación¹.

Las principales funciones que realiza son:

1. Identificar los símbolos.
2. Eliminar los blancos, caracteres de fin de línea, etc...
3. Eliminar los comentarios que acompañan al fuente.
4. Crear unos símbolos intermedios llamados tokens.
5. Avisar de los errores que detecte. 

Ejemplo: A partir de la sentencia en PASCAL siguiente

nuevo := viejo + RAZON*2

genera un código simplificado para el análisis sintáctico posterior, por ejemplo:

<id1> <:=> <id2> <+> <id3> <*> <ent>

Notas: 

Cada elemento encerrado entre <> representa un único token. 

Las abreviaturas id y ent significan identificador y entero, respectivamente².

Análisis sintáctico

Implica agrupar los componentes léxicos en frases gramaticales que el compilador utiliza para sintetizar la salida. Por lo general, las frases gramaticales del programa fuente se representan mediante un árbol de análisis sintáctico.

La división entre el análisis léxico y el análisis sintáctico es algo arbitraria. Generalmente se elige una división que simplifique la tarea completa del análisis. Un factor para determinar la división es si una construcción es inherentemente recursiva o no. Las construcciones léxicas no requieren recursión, mientras que las construcciones sintácticas suelen requerirla. Las gramáticas independientes de contexto son una formalización de reglas recursivas que se pueden usar para guiar el análisis sintáctico¹.

Comprueba que las sentencias que componen el texto fuente son correctas en el lenguaje, creando una representación interna que corresponde a la sentencia analizada. De esta manera se garantiza que sólo serán procesadas las sentencias que pertenezcan al lenguaje fuente. Durante el análisis sintáctico, así como en las demás etapas, se van mostrando los errores que se encuentran.

Ejemplo: 

El esquema de la sentencia anterior corresponde al de una sentencia de asignación del lenguaje Pascal. Estas sentencias son de la forma:

• <id> <:=> <EXPRESION>
• y la parte que se denomina <EXPRESION> es de la forma²:
• <id> <+> <EXPRESION> o bien
• <id> <*> <EXPRESION> o bien
• <real>

La estructura de la sentencia queda, por tanto, de manifiesto mediante el siguiente esquema:

<id1> <:=> <EXPRESION> / | \ <id2> <+> <EXPRESION> / | \ <id3> <*> <EXPRESION> | <real>

Análisis semántico

La fase de análisis semántico utiliza la estructura sintáctica determinada por la fase de análisis sintáctico para identificar los operadores y operandos de expresiones y proposiciones. En el caso de un interprete de consultas se debe validar que los nombres de atributos y de relaciones sean válidos y tengan sentido desde el punto de vista semántico. 

Un componente importante del análisis semántico es la verificación de tipos. Aquí, el interprete verifica si cada operador tiene operandos permitidos por la especificación del lenguaje fuente y verifica la compatibilidad de los tipos cuando estos están involucrados, por ejemplo, en una condición¹.

Se ocupa de analizar si la sentencia tiene algún significado. Se pueden encontrar sentencias que son sintácticamente correctas pero que no se pueden ejecutar porque carecen de sentido. En general, el análisis semántico se hace a la par que el análisis sintáctico introduciendo en éste unas rutinas semánticas.

Ejemplo: 

En la sentencia que se ha analizado existe una variable entera. Sin embargo, las operaciones se realizan entre identificadores reales, por lo que hay dos alternativas: o emitir un mensaje de error "Discordancia de tipos", o realizar una conversión automática al tipo superior, mediante una función auxiliar inttoreal².

<id1> <:=> <EXPRESION> / | \ <id2> <+> <EXPRESION> / | \ <id3> <*> <EXPRESION> | <real> | <inttoreal> | <int>

Generación de código intermedio.

El código intermedio es un código abstracto independiente de la máquina para la que se generará el código objeto. El código intermedio ha de cumplir dos requisitos importantes: ser fácil de producir a partir del análisis sintáctico, y ser fácil de traducir al lenguaje objeto. Esta fase puede no existir si se genera directamente código máquina, pero suele ser conveniente emplearla.

Ejemplo: 

Consideremos, por ejemplo, un código intermedio de tercetos, llamado así porque en cada una de sus instrucciones aparecen como máximo tres operandos. La sentencia traducida a este código intermedio quedaría²:

temp1 := inttoreal (2)temp2 := id3 * temp1temp3 := id2 + temp2id1 := temp3

Generación de código completo.

A partir de los análisis anteriores y de las tablas que estos análisis van creando durante su ejecución produce un código o lenguaje objeto que es directamente ejecutable por la máquina. Es la fase final del compilador. Las instrucciones del código intermedio se traducen una a una en código máquina reubicable.

Nota: 

Cada instrucción de código intermedio puede dar lugar a más de una de código máquina.

Ejemplo: 

El código anterior traducido a ensamblador DLX quedaría:

LW R1,id3MUL R1,R1,2LW R2,id2ADD R2,R2,R1SW id1,R2

en donde id1, id2 y id3 representan las posiciones de memoria en las que se hallan almacenadas estas variables; R1 y R2 son los registros de la máquina; y las instrucciones LW, SW, MUL y ADD representan las operaciones de colocar un valor de memoria en un registro, colocar un valor de un registro en memoria, multiplicar en punto flotante y sumar, respectivamente. 

Optimización de código

A partir de todo lo anterior crea un nuevo código más compacto y eficiente, eliminando por ejemplo sentencias que no se ejecutan nunca, simplificando expresiones aritméticas, etc... La profundidad con que se realiza esta optimización varía mucho de unos compiladores a otros. En el peor de los casos esta fase se suprime.

Ejemplo: 

Siguiendo con el ejemplo anterior, es posible evitar la función inttoreal mediante el cambio de 2 por 2.0, obviando además una de las operaciones anteriores. El código optimizado queda como sigue:

temp1 := id3 * 2.0id1 := id2 + temp1

Herramientas generadoras de compiladores

Esta es una lista de las herramientas más conocidas para la construcción de compiladores:

Nombre: Lex y Yacc 

Descripción: los generadores más populares de analizadores léxicos y sintácticos LALR(1).

Lenguaje: Pascal - C

Descargar: Turbo Pascal y FPK

Nombre: Flex y Bison 

Descripción: versiones mejoradas (generan analizadores más rápidos) de Lex y Yacc.

Lenguaje: C

Descargar: Linux - DOS

 

Nombre: BTYacc (Back Tracking Yacc)

Descripción: es una versión modificada de yacc que genera parsers con capacidad de backtracking automático.

Lenguaje: C

Descargar: DOS

 

Nombre: BYacc (Berkeley Yacc)

Descripción: es un generador de parsers LALR(1) de dominio público compatible con AT&T Yacc (el Yacc original).

Lenguaje: C

Descargar: 

Nombre: YAY (Yet Another YACC)

Descripción: es un generador de analizadores sintácticos ascendentes similar a Yacc pero con una extensión sumamente importante: soporta gramáticas LALR(2).

Lenguaje: C

Descargar: DOS

 

Nombre: ParseGenerator

Descripción: es una IDE (Entorno Integrado de Desarrollo), bajo Windows32, para los generadores AYACC y  ALEX, clones de Yacc y Lex respectivamente.

Lenguaje: C - C++

Descargar: Win32

 

Nombre: Eli 

Descripción: ofrece soluciones a casi todas las tareas relacionadas con la implementación de un lenguaje.

Lenguaje:

Descargar: ELI

 

Nombre: COCKTAIL

Descripción: es un conjunto de generadores de programas para casi todas las fases de un compilador. LALR(1) - LL(1) - Generador de ASTs - Evaluador de Atributos - Herramienta de transformación de programas.

Lenguaje: 

Descargar: COCKTAIL

 

Nombre: PCCTS 

Descripción: es un conjunto de herramientas para la construcción de traductores y reconocedores de lenguajes. Comprende tres herramientas: ANTLR un generador de parsers LL(k), DLG un analizador de analizadores léxicos y SORCERER un generador de parsers para árboles que le permite al programador definir la estructura del árbol por medio de una gramática.

Lenguaje:

Descargar: PCCTS

 

Nombre: Coco/R

Descripción: es un generador de parsers descendentes.

Lenguaje: 

Descargar: COCO(R)

 

Nombre: Depot4 

Descripción: es un generador de parsers descendentes que soporta especificaciones al etilo de la traducción dirigida por la sintaxis.

Lenguaje: 

Descargar: Depot4

 

Nombre: LLgen 

Descripción: es una herramienta para generar parsers descendentes a partir de una gramática ELL(1).  La gramática puede ser ambigua o más general que una ELL(1).

Lenguaje: 

Descargar: LLGEN

 

Nombre: PRECC

Descripción: es un generador de compiladores para gramáticas dependientes del contexto con infinito lookahead.

Lenguaje: 

Descargar: PRECC

 

Nombre: RDP

Descripción: es un generador de parsers descedentes para gramáticas LL(1).

Lenguaje: 

Descargar: RDP

 

Nombre: Visual Parse++

Descripción:  provee una interfase visual que permite aprender y utilizar, de manera interactiva, la tecnología de parsing. Genera parsers en C, C++, VBasic y Java.

Lenguaje: ?

Descargar: VISUALPARSE++

 

Nombre: AnaGram

Descripción:  es un generador de parsers LALR con resincronización automática en presencia de errores. Usualmente no necesita de un analizador léxico.

Lenguaje: ?

Descargar: AnaGram

 

Nombre: TCLL1

Descripción: es un generador de parsers descendentes para gramáticas LL(1) y LL(k).

Lenguaje: ?

Descargar: TCLL1

 

Nombre: Elegant (recomendado por David Riemens)

Descripción: es un lenguaje orientado a la construcción de compiladores desarrollado por  Phillips y puesto a dispocisión del público en 1997.

Lenguaje:  ?

Descargar: Elegant

 

Nombre: Cogencee (link recomendado por Peter Evans) 

Descripción: generador de parsers descendentes en Delphi.

Lenguaje: Delphi 

Descargar: Cogencee

 

Nombre: ProGrammar (link recomendado por Norm Wilson)

Descripción: un moderno generador de parsers OO.

Lenguaje:  ?

Descargar: ProGrammar

Referencias:

Compiladores e Intérpretes  http://www.ucse.edu.ar/fma/compiladores/