INTRODUCCION A LOS COMPILADORES.

Para que una máquina realice las tareas designadas es indispensable proporcionarle un adecuado conjunto de instrucciones agrupadas y ordenadas en un programa. Los programas se escriben en lenguajes de programación, que poseen sus reglas sintácticas, gramática, reglas de construcción, etc. Sin embargo, la máquina sólo entiende codificación binaría y para el ser humano utilizar un sistema binario resultaría extremadamente complejo, de allí surge el traductor entre el lenguaje usado por la computadora y el lenguaje humano. El lenguaje utilizado por el ser humano se le llama código fuente (Assembler, Fortran, Cobol, Basic, etc) y el utilizado por la máquina se le denomina código objeto (Binario). Entonces el traductor lo que hace es traducir lenguaje de alto nivel o bajo nivel a lenguaje máquina para que el equipo entienda lo que queremos ejecutar.

Cómo los códigos numéricos de las máquinas son engorrosos y difíciles de manejar, los primeros usuarios de los ordenadores creados para 1946, descubrieron la ventaja de escribir sus programas mediante claves más fáciles de recordar que esos códigos numéricos; al final, todas esas claves juntas se traducían manualmente a Lenguaje Máquina. Estas claves constituyen los llamados lenguajes ensambladores, que se generalizaron en cuanto se dio el paso decisivo de hacer que las propias máquinas realizaran el proceso mecánico de la traducción. A este trabajo se le llama ensamblar el programa. 

La finalidad del presente trabajo, es conocer paso a paso, como se logra llevar un programa fuente a un programa objeto de manera automática, que beneficios se lograron conseguir con este proceso y cuáles fueron los aportes obtenidos a lo largo de la historia. 

El encargado de traducir el lenguaje de alto nivel o bajo nivel a lenguaje máquina se le denomina: Ensamblador, compilador ó intérprete, sin embargo existen diferencia entre ellos, veamos:

                                                      Ensamblador

Se llaman ensamblador a los programas encargados de traducir los programas escritos en ensamblador (bajo nivel), que utiliza palabras mnemónicas a código binario. 

Fíjese en que tanto el programa traductor como el lenguaje se llaman del mismo modo: ensamblador.

Como el lenguaje ensamblador es muy próximo al binario, estos traductores son programas relativamente sencillos.

                                                       Compilador

Es un programa que reside en memoria y su función es traducir código fuente a código objeto. Para ello lo traduce instrucción por instrucción y lo guarda en secuencia en memoria RAM. Una vez que se ha compilado, el programa se puede correr tantas veces como se quiera porque ya está  traducido a lenguaje máquina, lo que significa tiempos de ejecución muy cortos. El problema básico que surge es que para hacer una modificación al programa original se debe volver al código fuente, editarlo y luego volverlo a compilar.

                                                         Intérprete

El interprete realiza la misma función solo que traduce el programa a código objeto a medida que va corriendo el programa, es decir, no tiene el programa previamente traducido, por supuesto, los tiempos de ejecución son sustancialmente mayores.

Si analizamos los traductores, podemos deducir que el ensamblador  trabaja con lenguaje de bajo nivel y solo lleva a binario el programa fuente, lo que dificulta la tarea del programador ya que debe utilizar adicionalmente ligadores que establezcan conexión entre el código y la biblioteca  para conseguir el programa objeto, los intérpretes hacen que los programas sean más portable, ya que un programa compilado bajo Windows no funcionara en una Macintosh o bajo Linux, a menos que se vuelva a compilar el programa fuente el nuevo sistema, en cambio, un programa interpretado funcionara en todas las plataformas, siempre que dispongamos del intérprete en cada una de ellas.

En conclusión, los lenguajes compilados no son mejores que los interpretados, ni al contrario. Optar por uno u otro depende de la función para la que vayamos a escribir el programa y del entorno donde deba ejecutarse.

                                                  FUNCION DE UN COMPILADOR:

A grandes rasgos un compilador es un programa que lee un programa escrito en un lenguaje, el lenguaje fuente, y lo traduce a un programa equivalente en otro lenguaje, el lenguaje objeto. Como parte importante de este proceso de traducción, el compilador informa a su usuario de la presencia de errores en el programa fuente.

  

                                         TIPOS DE COMPILADORES
 

• una sola pasada: examina el código fuente una vez, generando el código o programa objeto.

• pasadas múltiples: requieren pasos intermedios para producir un código en otro lenguaje, y una pasada final para producir y optimizar el

código producido durante los pasos anteriores.

• Optimación: lee un código fuente, lo analiza y descubre errores potenciales sin ejecutar el programa.

• Compilador cruzado: se genera código en lenguaje objeto para una máquina diferente de la que se está utilizando para compilar.

Es perfectamente normal construir un compilador de Pascal que genere código para MS-DOS y que el compilador funcione en Linux y se haya escrito en C++. 

MODELO DE ANALISIS Y SINTESIS DE LA COMPILACION.

            En la compilación hay dos partes: análisis y síntesis. La parte del análisis divide al programa fuente en sus elementos componentes y crea una representación intermedia del programa fuente. La parte de la síntesis construye el programa objeto deseado a partir de la representación intermedia. De las dos partes, la síntesis es la que requiere las técnicas más especializadas.

            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 de un nodo son los argumentos de la operación. Por ejemplo se mostrara para una proposición de asignación:

SISTEMA PARA  PROCESAMIENTO DE UN LENGUAJE

 

            La entrada para un compilador puede producirse por uno  o varios Preprocesadores, y  puede necesitarse otro procesamiento de la salida que produce el compilador antes de obtener un código de máquina ejecutable.

            Los Preprocesadores producen la entrada para un compilador, y  pueden realizar las siguientes funciones:

•          Procesamiento de macros.

•              Inclusión de Archivos

•               Preprocesadores “Racionales”.

•              Extensiones a lenguaje.

De tal forma que se muestra una compilación típica. El programa objeto creado por el compilador puede requerir procesamiento adicional antes de poderlo ejecutar. El Compilador crea código en lenguaje ensamblador el cual es traducido por un ensamblador a código de máquina y después se enlaza a algunas rutinas de biblioteca para producir el código que realmente se ejecute en la máquina.

En la compilación el Análisis del Programa Fuente consta de tres fases:

• ·         Análisis Lineal  o Análisis Léxico, Exploración: En el que 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.

• ·         Análisis Jerárquico ó Sintáctico: En el que los caracteres o los componentes léxicos se agrupan jerárquicamente en colecciones anidadas con un significado colectivo.

• ·         Análisis Semántico: En el que se realizan ciertas revisiones para asegurar que los componentes de un programa se ajustan de un modo significativo.

            En un compilador, el Análisis Lineal se llama Análisis Léxico o Exploración. Por ejemplo, en el análisis léxico, los caracteres de la proposición de asignación:

Posición:= Inicial + Velocidad * 60

            Se agrupan en los componentes léxico siguiente:

• 1.    El Identificador Posición.

• 2.    El Símbolo de Asignación :=

• 3.    El Identificador Inicial.

• 4.    El Signo de Suma.

• 5.    El Identificador Velocidad.

• 6.    El Signo de Multiplicación

7.    El Numero 60.

Los espacios en blanco que separan los caracteres de estos componentes léxicos normalmente se eliminan durante el análisis léxico.

         

           

     El Análisis Jerárquico se denomina Análisis Sintáctico. Este implica agrupar los componentes léxicos del programa fuente 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 tal como:

            En la expresión Inicial +Velocidad *60 , la frase Velocidad *60 es una unidad lógica, porque las convenciones usuales de las expresiones aritmética indican que la multiplicación se hace antes que la suma. Puesto que la expresión Inicial + Velocidad va seguida de un * y no se agrupa en una sola frase independiente.

            La estructura jerárquica de un programa normalmente se expresa utilizando reglas recursivas. Por ejemplo, se pueden dar las siguientes reglas como parte de la definición de expresiones:

• 1.    Cualquier Identificador es una expresión

• 2.    Cualquier número es una expresión

• 3.    Si expresión1 y expresión2, son expresiones, entonces también lo son:

                         Expresión1 + Expresión2

                         Expresión1 * Expresión2

                          (Expresión1).

            Las Reglas (1) y (2) son reglas básicas (no recursivas) en tanto que la regla (3) define expresiones en función de operadores aplicados a otras expresiones. Así, por regla (1), inicial y velocidad son expresiones. Por la regla (2), 60 es una expresión, mientras que por la regla (3), primero podemos inferir que velocidad *60 es una expresión y finalmente, que inicial + velocidad *60, también es una expresión.

                                                          Analizador Sintáctico.

           También llamado parser, en inglés. Es el elemento fundamental del procesador, pues lleva el control del proceso e invoca como subrutinas a los restantes elementos del Compilador realiza el resto de la reducción al axioma de la gramática para comprobar que la instrucción es correcta usualmente se implementa mediante un autómata a pila o una construcción equivalente.

                                                          Analizador Semántico.

Comprueba la corrección semántica de la instrucción, por ejemplo, la compatibilidad del tipo de las variables en una expresión. La información como los tipos de datos que se calculan mediante el analizador semántico se llaman atributos y se agregan al árbol sintáctico como anotaciones

Los atributos también se pueden introducir en la tabla de símbolos.

La fase de análisis semántico de un procesador de lenguaje es aquélla que computa la información adicional necesaria para el procesamiento de un lenguaje, una vez que la estructura sintáctica de un programa haya sido obtenida. Es por tanto la fase posterior a la de análisis sintáctico y la última dentro del proceso de síntesis de un lenguaje de programación.

                                                     Generador y Optimizador.

Generador de código

Traduce el programa fuente al lenguaje objeto utilizando toda la información proporcionada por las restantes partes del compilador.

Optimizador de código

 Mejora la eficiencia del programa objeto en ocupación de memoria o en tiempo de ejecución. En un intérprete no existen las fases degeneración y optimización de código, que se sustituyen por una fase de ejecución de código.

                                                         Análisis Semántico.

•         Lenguajes Naturales                  

Sintaxis: Controla la  buena formación de las oraciones    

Acorde  con  la   gramática del lenguaje.                                             

Semántica: El significado de  las  oraciones bien formadas.

•        Lenguaje de programación.

Sintaxis: Controla la construcción de    programas   bien formados,

Acorde  con  la gramática del lenguaje lenguaje.

Semántica: El significado de los programas sintácticamente válidos.

Clasificación de la semántica:

                                              

·      DINAMICA: hace referencia a aspectos que sólo pueden ser conocidos en tiempo de ejecución.

·      ESTATICA: hace referencia a aspectos que pueden ser controlados en tiempo de compilación.

          El análisis Semántico Se compone de un conjunto de rutinas independientes, llamadas por los analizadores morfológico y sintáctico.

            El análisis semántico utiliza como entrada el árbol sintáctico detectado por el análisis sintáctico para comprobar restricciones de tipo y otras limitaciones semánticas y preparar la generación de código.

            En compiladores de un solo paso, las llamadas a las rutinas semánticas se realizan directamente desde el analizador sintáctico y son dichas rutinas las que llaman al generador de código. El instrumento más utilizado para conseguirlo es la gramática de atributos.

     En compiladores de dos o más pasos, el análisis semántico se realiza independientemente de la generación de código, pasándose información a través de un archivo intermedio, que normalmente contiene información sobre el árbol sintáctico en forma linealizada (para facilitar su manejo y hacer posible su almacenamiento en memoria auxiliar).

      En cualquier caso, las rutinas semánticas suelen hacer uso de una pila (la pila semántica) que contiene la información semántica asociada a los operandos (y a veces a los operadores) en forma de registros semánticos. 

Propagación de atributos

Las fases de un compilador.

Las fases de análisis

    

PROGRAMAS DE SISTEMA RELACIONADOS CON UN COMPILADOR

PROCESADORES: Estos producen la entrada para un compilador, y pueden realizar las siguientes funciones:

PROCESAMIENTO DE MACROS: Un procesador puede permitir a un usuario definir macro, que son abreviaturas de construcción mas grandes.

INCLUSIÓN DE ARCHIVOS: Un procesador puede insertar archivos de encabezamiento en el texto del programa .

PREPROCESADORES “ RACIONALES”: Estos procesadores enriquecen los lenguajes antiguos con recursos mas modernos de flujo de control y de estructuras de datos.

EXTENSIONES A LENGUAJES:  Estos procesadores tratan de crear posibilidades al lenguaje que equivales a macros incorporados. 

                                           Agrupamiento de las Fases

IMPORTANCIA DE LA TABLA DE SIMBOLOS Y EL MANEJO DE ERRORES

     La tabla de símbolos es de real importancia en un compilador debido a que en ella se encuentran registrada la información de los identificadores que va utilizar el programa fuente, esta funciona similar a una estructura que contiene un registro por cada identificador con los campos de cada atributo lo cual permite ubicar rápidamente un identificador y almacenar y consultar datos en los diferentes registros cuando en el análisis léxico se detectan algún identificador este de una vez se introduce en su búsqueda en la tabla de símbolos, y esta tabla es de suma importancia ya que por medio de esta el análisis semántica y la generación de código intermedio logra saber cuales son los identificadores y comprueba si el programa fuente los usa de la manera correcta para poder realizar las operaciones apropiadas  la importancia de esta radica en que en que el compilador la necesita para guardar y usar la información de objetos que se van encontrando en el texto fuente y depende del compilador el manejo de la misma administrar las entradas y búsqueda de objetos en la misma de manera eficiente.

   El manejo de errores en un compilador se puede decir que quizás sea una de las etapas mas engorrosas del compilador es ampliamente utilizada en las etapas de semántica y sintáctica aunque todas las fases la emplean generalmente su función es encontrar errores que han sido pasados por alto en alguna fase aunque a veces se encuentran errores dentro de los errores y la corrección de un error muchas veces provoca la aparición de otro es conveniente un buen manejo de errores para que detecte todos los errores posibles sin detenerse realizándolo de manera centralizada  logrando el control de errores en cada una de las fases.

Como conclusión se puede decir que tanto  la tabla de símbolos como el manejo de errores son muy importantes dentro de las fases del compilador ya que ambas trabajan conjuntamente para que las demás fases se lleven de manera armónica la tabla de símbolos por su parte conteniendo y actualizando todos los objetos posibles dentro del programa fuente y el manejo de errores controlando toda la aparición de posibles errores en las distintas fases  sin el trabajo en conjunto de ambas un compilador no podría realizar su función exitosamente

ANALIZADOR LÉXICO

Este analizador es la primera fase de un compilador, lee una cadena de caracteres de entrada de derecha a izquierda para agrupar dichos caracteres en una secuencia de componentes léxicos, identificarlos y clasificarlos con el fin de generar una salida que luego será utilizada por el analizador sintáctico.

Este proceso también puede ser llamado Análisis Lineal, Exploración ó Reconocimiento, el alfabeto y la tabla de símbolos utilizados por una analizador léxico varía de un compilador a otro y de un lenguaje a otro. 

Los errores que un analizador léxico reconoce son símbolos no válidos o no reconocidos por el léxico del lenguaje o que no forman parte de ningún componente léxico.

FUNCIÓN DEL ANALIZADOR LÉXICO

v  Leer carácter por carácter de la cadena de entrada y elaborar como salida una secuencia de componentes léxicos que utilizará el analizador sintáctico para continuar el análisis.

• v Manejar el archivo fuente, es decir, abrirlo, leer sus caracteres y cerrarlo.

• v Eliminar comentarios y espacios en blanco (espacios, tabuladores y fin de línea).

• v Relacionar los mensajes de error con las líneas del programa fuente.

• v  Introducir los identificadores en la tabla de símbolos.

• v  Reconocer los identificadores, palabras clave, constantes y numerales.

• v  Contabilizar el número de líneas y columnas para emitir mensajes de error.

Analizador léxico (scanner): lee la secuencia de caracteres del programa fuente, carácter a carácter, y los agrupa para formar unidades con significado propio, Estos componentes léxicos representan:

Palabras reservadas: if, while, do.

Identificadores: asociados a variables, nombres de funciones, tipos definidos por el usuario, etiquetas,... Por ejemplo: posición, velocidad, tiempo.

  

Operadores: = * + - / == > < & ! = .

 Símbolos especiales: ; ( ) [ ] f g.

 Constantes numéricas: literales que representan valores enteros, en coma flotante, etc, 982, 0xF678, -83.2E+2.

Constantes de caracteres: literales que representan cadenas concretas de caracteres, “hola mundo".

VENTAJAS DE SEPARAR EL ANÁLISIS LÉXICO Y EL SINTÁCTICO

v  Facilita el transporte del traductor (por ejemplo, si decidimos en un momento dado cambiar las palabras reservadas begin y end de inicio y fin de bloque, por {y}, solo hay que cambiar este modulo.

v  Se simplifica el diseño el analizador que es un objeto con el que se interactúa mediante ciertos métodos. Se localiza en un único módulo la lectura física de los caracteres, por lo que facilita tratamientos especializados de E/S.

v  Diseño más sencillo: los símbolos que trata el analizador léxico se describen con una gramática más simple (gramática regular) que la del analizador sintáctico (gramática libre de contexto).

v  Mejora la eficiencia: gran parte del tiempo de compilación se consume en la lectura y exploración de caracteres. Con técnicas especializadas de manejo de buffers se puede mejorar significativamente el rendimiento del compilador.

v  Mejora la portabilidad: se pueden tener varias versiones del analizador léxico una para distintos códigos (EBCDID, ASCII), con el mismo analizador sintáctico.

v  Las peculiaridades del alfabeto de entrada (códigos ASCII, EBCDIC, considerar mayúsculas diferentes o no que las correspondientes minúsculas) pueden quedar limitadas al analizador léxico.

v  Ciertas ambigüedades pueden resolverse en el analizador léxico (variable o sentencia: DO1I = 8.15 ó DO1I = 8; 15).

ESTRUCTURA FUNCIONAL DEL ANÁLISIS LÉXICO

Las funciones detalladas que ha de realizar el analizador léxico son:

v  Leer el siguiente carácter (sigtecar()).

v  Analizarlo.

v  Acumular el carácter si no se ha determinado aún un token (guadacar()).

v  Emitir un mensaje de error si se ha encontrado un error léxico (menserror()).

v  Instalar en la tabla de símbolos si se ha determinado un identificador (instalaTDS()).

v  Entregar el componente léxico que se haya determinado y el atributo correspondiente si hay lugar (return).

v  En ocasiones sólo se puede determinar un token cuando se ha recibido un carácter que pertenece al siguiente token. En este caso se debe reinsertar dicho carácter a la entrada para realizar el análisis léxico de la siguiente petición del analizador léxico (reinsertar()).

COMPONENTES LÉXICOS

Símbolos terminales de la gramática del lenguaje fuente. Los Componentes léxicos comunes en los lenguajes de programación Identificadores, Palabras claves, Operadores, Constantes, Cadena de literales, Signos de puntuación (paréntesis, coma, punto y coma, etc.).

Patrón: es una regla que genera la secuencia de caracteres que puede representar a un determinado componente léxico (una ex-presión regular). El conjunto de cadenas de la entrada se describe mediante una regla llamada patrón asociada al componente léxico. Un patrón es una regla que describe el conjunto de lexemas. Para describir los patrones se utiliza la notación de expresiones regulares.

Lexema: es una cadena de caracteres que concuerda con un patrón que describe un componente léxico. Un componente léxico puede tener uno o infinitos lexemas. Por ejemplo: palabras reservadas tienen un único lexema. Los números y los identificadores tienen infinitos lexemas.

                                  Atributos de los Componentes Léxicos

v  Cuando una secuencia de caracteres (por ejemplo, pi) aparece en el programa fuente se devuelve al analizador sintáctico un componente léxico que representa un identificador.

v  Es necesario que el analizador léxico proporcione información adicional sobre el lexema concreto. Esta información adicional se denomina Atributos.

v  El patrón num concuerda con las cadenas 3.1416 y 0, pero es indispensable que el generador de código conozca que cada cadena fue realmente la que se emparejo.

v  El analizador léxico recoge información sobre los componentes léxicos en sus atributos asociados.

v  Los componentes léxicos influyen en las decisiones del analizador sintáctico, y los atributos, en la traducción de los componentes léxicos.

v  En la práctica los componentes léxicos suelen tener un solo atributo, un puntero a la tabla de símbolos, donde se guarda información del componente léxico. El puntero se convierte en el atributo del componente léxico.

v  No siempre se necesita un valor de atributo, el componente léxico es suficiente para identificar al lexema.

EXPRESIONES REGULARES DEL ANÁLISIS LÉXICO

Una expresión regular denota un conjunto de secuencias de símbolos  válidas que se construyen en base al alfabeto de un lenguaje.

Este conjunto se denomina lenguaje generado por la expresión regular. Vale decir que la palabra lenguaje se utiliza para definir “conjunto de cadenas” y no tiene una relación específica con el lenguaje de programación.

Este lenguaje depende en primer lugar del conjunto de caracteres ASCII o de algún subconjunto del mismo, en ocasiones el conjunto será más general que el conjunto de caracteres ASCII.  En cuyo caso los elementos se describirán como Símbolos. Este conjunto de símbolos legales se conoce como alfabeto y se representa con el símbolo griego (sigma).

Por último una expresión regular r puede contener caracteres que contengan significados especiales, este tipo de caracteres se llama metacaracteres o metasímbolos.

Funciones de las Expresiones Regulares del análisis léxico

v  Son una notación para definir lenguajes.

v  Se ha demostrado que pueden expresar la clase de los  lenguajes regulares.

v  Permiten hacer una definición algebraica de un lenguaje.

v  Se expresa el lenguaje de manera declarativa.

Operaciones sobre lenguajes del análisis léxico

Cerradura Kleene: L se repite de 0 a infinito

Cerradura Positiva: L se repite de 1 a infinito

AUTÓMATA

Es un modelo matemático que realiza cómputos de forma automática sobre una entrada y produce una salida. Es una máquina que dada una entrada de símbolos, "salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). Esta función de transición dice al autómata a que estado cambiar dados un determinado estado y símbolo. Hace únicamente para lo que está diseñado.

TEORÍA DE AUTÓMATAS

Es una rama de las ciencias de la computación que estudia de manera abstracta y con problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.

TABLA DE TRANSICIÓN DE ESTADOS

• Matriz bidimensional cuyos elementos proporcionan el resumen de un diagrama de transiciones.

•       Tantas filas como estados.

•      Tantas columnas como símbolos de entrada.

•      Columna adicional etiquetada con ג para marcar los estados de aceptación.

•    Si no existe ninguna transición desde el estado i con el símbolo n, marcar la casilla correspondiente con un estado de error (-).

REPRESENTACIÓN DEL AUTÓMATA COMO DIAGRAMA DE ESTADO

AUTOMATAS FINITOS

Es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito.

CLASIFICACIÓN DE LOS AUTÓMATAS FINITOS

v  Autómata Finito Determinista AFD

Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (∑) y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida. Además cumple con ls siguientes reglas o parámetros:

v Ningún estado tiene una transición ε (Vacía) como inicio, es decir, una transición con la entrada ε.

v Para cada estado (S) o (θ) y cada símbolo de entrada “a” hay a lo sumo una arista etiquetada “a” que sale de S.

v  Autómatas finitos no determinista AFN

Es un modelo matemático que consiste de:

1.- Un conjunto de estados (S) o (θ).

2.- Un conjunto de símbolos de entrada (∑).

3.- Una función de transición (δ).

4.- Un estado (So)  o (θo) que se denota como el estado inicial.

5.- Un conjunto de estados (F) que denotan los estados de aceptación o finales.

Un AFN no tiene restricciones para que exista más de una transición con el mismo nombre a diferentes estados por lo que en una representación tabular no es posible determinar de manera única el estado destino para un símbolo        determinado.

El cual se puede representar con diagramas de grafos dirigido etiquetado, llamado grafo de transiciones, donde los nodos son los estados y las aristas etiquetadas representa la función transición.

GRAMÁTICAS

Gramática: cuádrupla (V,T,S,R) donde

NT: conjunto de símbolos no terminales.

T: conjunto de símbolos terminales (alfabeto) (T=∑).

S: axioma o símbolo de inicio. SeV.

R: conjunto de reglas de producción (reescritura) de la forma XY     ZW, donde X,Y,Z.

W: representan combinaciones cualesquiera de símbolos terminales y no terminales, con la restricción de que en la parte izquierda de la regla debe haber al menos un símbolo no terminal.

                                        GENERACION DE CODIGO INTERMEDIO:

El proceso de la compilación se desglosa en dos partes: la parte que depende solo del lenguaje fuente (etapa inicial) y la parte que depende solo del lenguaje objeto (etapa final).

La etapa inicial traduce un programa fuente a una representación intermedia a partir de la cual  la etapa final genera el código objeto. De esta forma, los detalles que tienen que ver con las características del lenguaje objeto, la arquitectura de la  maquina, el entorno de ejecución y el sistema operativo se engloban en la etapa final y se aíslan del resto.

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.

Una representación intermedia es una estructura de datos que representa al programa fuente durante el proceso de la traducción a código objeto. El compilador primero traduce el código fuente en una forma más situable para la optimización, para luego convertirla en el código de máquina. El compilador transforma el código en un lenguaje más manejable, usualmente código de tres direcciones, el cual representa exactamente una instrucción de código de máquina, verifica tipos y traduce expresiones.

                                     GENERACIÓN DE CÓDIGO INTERMEDIO

Después de los análisis sintáctico y semántico, algunos compiladores generan una representación intermedia explícita del programa fuente. Se puede considerar esta representación intermedia 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 al programa objeto.

La generación de código es la tarea más complicada de un compilador. Las ventajas de utilizar esta representación intermedia, independiente de la máquina en la que se va a ejecutar el programa, son:

·         Se puede crear un compilador para una nueva máquina distinta uniendo la etapa final de la nueva máquina a una etapa inicial ya existente.

·         Se facilita la redestinación.

·         Se puede aplicar, a la representación intermedia, un optimador de código independiente de la máquina.

Ventajas del Código Intermedio:

Permite abstraer la máquina, separar operación desde alto nivel de su implementación a bajo nivel.

Permite la reutilización de los front-ends y back-ends.

Permite optimizaciones generales.

LENGUAJES INTERMEDIOS

Los árboles sintácticos y la notación postfija son dos clases de representaciones intermedias.

                                                                  Notación postfija

Es también una representación linealizada de un árbol sintáctico, es una lista de nodos de un árbol en la que un nodo aparece inmediatamente después de su hijo. Utiliza el método postorden para recorrer árboles, comenzando por el nodo izquierdo, luego por el derecho y por último la raíz.

• La notación postfija pone el operador al final de los dos operandos, por lo que la expresión queda: ab+5-

• La notación postfija utiliza una estructura del tipo LIFO (Last In First Out) pila, la cual es la más utilizada para la implementación.

Las aristas de un árbol sintáctico no aparecen explícitamente en la notación postfija. Se pueden recuperar según el orden en que aparecen los nodos y el número de operadnos que espera el operador de un nodo.

Los árboles sintácticos para las proposiciones de asignación  son producidos por la definición dirigida por la sintaxis. El no terminal S genera una proposición de asignación. Los dos operandos  binarios + y * son ejemplos del conjunto completo de operadores de un lenguaje típico.         

TIPOS DE REPRESENTACIONES INTERMEDIAS

EL CÓDIGO DE 3-DIRECCIONES

                                        

Una representación intermedia es una estructura de datos que representa al programa fuente durante el proceso de la traducción a código objeto. Hasta ahora hemos usado el ´árbol de análisis sintáctico como representación intermedia, junto con la tabla de símbolos que contenía información sobre los nombres (variables, constantes, tipos y funciones) que aparecían en el programa fuente.

El árbol de análisis sintáctico es una representación valida, no se parece ni remotamente al código objeto, en el que solo se emplean saltos a direcciones en memoria en vez de construcciones de alto nivel, como sentencias if-then-else. Es necesario generar una nueva forma de representación intermedia. A esta representación intermedia, que se parece al código objeto pero que sigue siendo independiente de la máquina, se le llama código intermedio.

El condigo intermedio puede tomar muchas formas. Todas ellas se consideran como una forma de linearización del árbol sintáctico, es decir, una representación del árbol sintáctico de forma secuencial.

El código de tres direcciones es una secuencia de proposiciones de la forma general

x = y op z

Donde op representa cualquier operador; x, y, z representan variables definidas por el programador o variables temporales generadas por el compilador. y, z también pueden representar constantes o literales. Op representa cualquier operador: un operador aritmético de punto fijo o flotante, o un operador lógico sobre datos booleanos.

No se permite ninguna expresión aritmética compuesta,  sólo hay un operador en el lado derecho. Por ejemplo, x+y*z se debe traducir a una secuencia, donde  t1, t2 son variables temporales generadas por el compilador.

Las expresiones compuestas y las proposiciones de flujo de control se han de descomponer en proposiciones de este tipo, definiendo un conjunto suficientemente, amplio de operadores. Se le llama código de 3-direcciones porque cada proposición contiene, en el caso general, tres direcciones, dos para los operandos y una para el resultado.

El código de tres direcciones es una representación linealizada (de izquierda a derecha) del  árbol sintáctico en la que los nombres temporales corresponden a los nodos internos. Como estos nombres temporales se representan en la memoria no se especifica más información sobre ellos en este tipo de código. Normalmente se asignaran directamente a registros o se almacenarán en la tabla de símbolos.

Tipos de proposiciones de 3-direcciones

La forma de código de 3-direcciones es insuficiente para representar todas las construcciones de un lenguaje de programación (saltos condicionales, saltos incondicionales, llamadas a funciones, bucles, etc.), por lo tanto es necesario introducir nuevos operadores. El conjunto de proposiciones (operadores) debe ser lo suficientemente rico como para poder implantar las operaciones del lenguaje fuente.

Las proposiciones de 3-direcciones van a ser en cierta manera análogas al código ensamblador. Las proposiciones pueden tener etiquetas simbólicas y existen instrucciones para el flujo de control (goto). Una etiqueta simbólica representa el índice de una proposición de 3-direcciones en la lista de instrucciones.

Las proposiciones de 3-direcciones más comunes que utilizaremos:

1. Proposiciones de la forma x = y op z donde op es un operador binario aritmético, lógico o relacional.

2. Instrucciones de la forma x = op y, donde op es un operador unario (operador negación lógico, menos unario, operadores de desplazamiento o conversión de tipos).

3. Proposiciones de copia de la forma x = y, donde el valor de y se asigna a x.

4. Salto incondicional goto etiq. La instrucción con etiqueta etiq es la siguiente que se ejecutará.

5. Saltos condicionales como if false x goto etiq.

6. param x y call f para apilar los parámetros y llamadas a funciones (los procedimientos se consideran funciones que no devuelven valores). También return y, que es opcional, para devolver valores. Código generado como parte de una llamada al procedimiento p(x1, x2,..., xn).

param x1

param x2

…

param  xn

call p, n.

7. Asignaciones con índices de la forma x = y[i], donde se asigna a x el valor de la posición en i unidades de memoria más allá de la Posición y. O también x[i] = y.

8. Asignaciones de direcciones a punteros de la forma x = &y (el valor de x es la dirección de y), x = *y (el valor de x  se iguala al contenido de la dirección indicada por el puntero y) o *x = y (el objeto apuntado por x se igual al valor de y).

Implementación de código de tres direcciones

Una proposición de código de 3-direcciones se puede implantar como una estructura tipo registro con campos para el operador, los operandos y el resultado. La representación final Sera entonces una lista enlazada o un vector de proposiciones.

Implementación mediante cuádruplos

Un cuádruplo es una estructura tipo registro con cuatro campos que se llaman (op, result, arg1, arg2). El campo op contiene un código interno para el operador.

Por ejemplo, la proposición de tres direcciones x = y + z se representa mediante el cuádruplo (ADD, x, y, z). Las proposiciones con operadores unarios no usan el arg2.  Los campos que no se usan se dejan vacíos o un valor NULL. Como se necesitan cuatro campos se le llama representación mediante cuádruplos.

Implementación mediante tripletes

Para evitar tener que introducir nombres temporales en la tabla de símbolos, se hace referencia a un valor temporal según la posición de la proposición que lo calcula. Las propias instrucciones representan el valor del nombre temporal. La implantación se hace mediante registros de sólo tres campos

(op, arg1, arg2).

En la notación de tripletes se necesita menor espacio y el compilador no necesita generar los nombre temporales. Sin embargo, en esta notación, trasladar una proposición que defina un valor temporal exige que se modifiquen todas las referencias a esa proposición. Lo cual supone un inconveniente a la hora de optimizar el código, pues a menudo es necesario cambiar proposiciones de lugar.