COMPILADORES E INTERPRETES

1. En el cuadro siguiente escriba dos tareas para cada analizador:

Analizador Léxico

1.Pone el programa en un formato compacto y uniforme.
2.Elimina información innecesaria (comentarios).
3.La información ingresada preliminarmente se almacena dentro de tablas de simbolos y atributos

4.Formatea y enlista el programa fuente.
5.Descompone el programa fuente en una serie de tokens

Ejemplo: Calculadora
Entrada: 12+5*-2
Tokens: NUM (12), +, NUM (5), *, -, NUM (2)
Todos los caracteres que se encuentran deben formar parte de un token , de otro modo se alerta la presencia de un error léxico

Analizador Sintáctico

1.El analizador sintáctico verifica si una sintaxis está escrita correctamente, sin embargo si es encontrado un error, se sugiere el diagnostico adecuado.

2.En ocasiones una recuperación o reparación de un error sintáctico se puede realizar automáticamente consultando tablas de reparación de errores creadas por un generador, que repara o corrige el análisis sintáctico

3.Construye un árbol sintáctico del programa fuente en donde las hojas corresponden a los tokens, los nodos internos a reducciones gramaticales y la raíz es el nodo inicial de la gramática.
Ejemplo: árbol sintáctico para 12 + 5 * -2
+
NUM(12)
*
5
- (unario)
2
La lectura secuencial de las hojas del árbol corresponde a la secuencia de tokens entregada por el análisis léxico. Si el analizador no es capaz de atribuir un token a alguna regla de la gramática se alerta de la presencia de un error sintáctico.

Analizador Semántico

1.Revisión de la semántica estática de cada construcción (líneas). Esto se refiere a la verificación de que dicha construcción sea legal y significativa (que las variables involucradas sean definidas con el tipo correcto, etc.).

2.Una vez que la construcción es semánticamente correcta, las rutinas también hacen la traducción. Esto implica la generación de código intermedio que implemente correctamente la construcción generada. Las rutinas semánticas son manejada y asociadas con producciones individuales de la gramática libre de contexto o subárboles del árbol sintáctico

3.Consistencia semántica del árbol sintáctico
Ejemplo: no tiene sentido restar dos strings.

2. Transformar las siguientes expresiones a notación postfija y prefijo.

a) a * b % c – d * a – d % e

Posfija: a b * c % d a * - d e % -
Prefija: - - % * a b c * d a % d e

b) (a + c) – (d * e) / x % y

Posfija: a c + d e * x / y % -
Prefija: - + a c % / * d e x y

c) (h – i – j * k) % m / x / y

Posfija: h i – j k * - m % x / y /
Prefija: / / % - - h i * j k m x y

3. Dado el árbol de derivación, obtener la expresión en notación infija, postfija y prefija.

Prefija: * - % * a b c d % - h f e
Infija: a * b % c – d * h – f % e
Posfija: a b * c % d – h f – e % *

4. Señale dos ventajas de la generación de código intermedio

· El código objeto es abstraído para una maquina virtual. esta abstracción ayuda a separar operaciones de alto nivel y realizar dependientes de la maquina.

· La generación de código y el asignamiento de registros temporales son separados de las rutinas semánticas, los cuales solo trabajan con la abstracción presentada por la representación intermedia. las dependencias del código objeto son aisladas de las rutinas de generación de código.

· La abstracción puede ser hecha en el nivel de representación intermedia. esta organización ayuda a hacer una optimización completamente independiente del código objeto, con lo que hace que las rutinas de optimización complejas sean más transportables. debido a que las representaciones intermedias son por diseño mas abstracta y uniforme, las rutinas de optimización puede ser más simples.

5. Explique con un ejemplo la optimización de código.

OPTIMIZACIÓN POR REDUCCIÓN SIMPLE.-Se realizan sobre los elementos de una expresión aritmética cuando todos ellos son conocidos.

Ejemplo:
(3 + 5) * 8 8 * 8 = 64

OPTIMIZACIÓN POR REACONDICIONAMIENTO DE INTERRUPCIONES.- En ocasiones es posible reestructurar una expresión dada de forma que se evite en lo posible el uso de variables temporales. De las expresiones aritméticas en muchas ocasiones basta de disponer de otra forma el acomodo de los elementos para dar con el objetivo deseado.

Ejemplo:
A: = B * C * (D + E)

A: = (D + E) * B * C

OPTIMIZACION DE CODIGO - Utilizando Generics

Demostración
Lo primero que haremos sera crear una pequeña aplicación por consola en C# en la cual declararemos esta constante y la siguiente función:

const int tamano = 30000000;
private static long Boxing_Unboxing()
{
long suma = 0;
ArrayList arrayEnteros = new ArrayList();
for (int i = 0; i <>
arrayEnteros.Add(i);
for (int i = 0; i <>
suma = suma + (int)arrayEnteros[i ];
return suma;

}

No requiere mucha explicación, esta función efectúa el llenado (boxing) de una colección con un numero determinado de elementos y seguidamente suma todos estos elementos en un acumulado (ahí hace unboxing) el cual retorna.
Ahora adicionaremos esta función que hace exactamente lo mismo pero utilizando colecciones genericas:

private static long Generics()
{
long suma = 0;
List arrayEnteros = new List();
for (int i = 0; i <>

arrayEnteros.Add(i);

for (int i = 0; i <>

suma = suma + arrayEnteros[i ];
return suma;

}

Ahora en el método main crearemos el código necesario para invocar las dos funciones anteriores, adicionalmente mediremos el tiempo de ejecución de las mismas para lo cual utilizaremos System.Environment.TickCount y finalmente incluiremos código para medir el consumo de memoria de la aplicación para lo cual haremos uso de dos metodos de la clase estática GC, GC.GetTotalMemory para saber el consumo total de memoria en un momento dado y GC.Collect para liberar los recursos que ya no estan en uso. El código queda así:

static void Main(string[] args)

{

int tiempo =0;

tiempo = System.Environment.TickCount;

long suma = Boxing_Unboxing();

tiempo = System.Environment.TickCount - tiempo;

Console.WriteLine("Resultado: "+suma.ToString()+" Tiempo Un/Boxing\t:"+tiempo.ToString

().PadLeft(10,' ')+ " Memoria: "+GC.GetTotalMemory(false).ToString

().PadLeft(7,' '));

GC.Collect();
tiempo = System.Environment.TickCount;

suma = Generics();

tiempo = System.Environment.TickCount - tiempo;

Console.WriteLine("Resultado: " + suma.ToString() + " Tiempo Generics\t:"

+tiempo.ToString().PadLeft(10, ' ')+" Memoria: " + GC.GetTotalMemory

(false).ToString().PadLeft(7, ' '));
GC.Collect();

Console.ReadLine();

}

Una vez ejecutado obtendremos los siguientes valores (o muy parecidos dependiendo del computador de cada cual):

Resultado: 199999990000000 Tiempo Un/Boxing : 4695 Memoria: 883595136

Resultado: 199999990000000 Tiempo Generics : 764 Memoria: 202279736

Como ven en los resultados, generics se muestran aproximadamente 6 veces más rápido que la técnica tradicional y fue casi 5 veces más efectivo en el uso de la memoria.

Como desconozco que hardware tienen ustedes, pueden hacer pruebas modificando el valor de la constante tamaño de acuerdo a las características de su procesador y memoria, esto porque si exceden el límite de almacenamiento en memoria de sus máquinas el sistema operativo iniciara el proceso de swap a disco poniéndose la cosa muy lenta... ahí obtendrán diferencias de tiempo mucho mayores incluso proporcionalmente.

6. Señale el proceso de compilación de un programa en C#.

El proceso de compilación involucra cuatro etapas sucesivas:

1. Preprocesamiento
2. Compilación
3. Ensamblado
4. Enlazado

Preprocesado: En esta etapa se interpretan las directivas al preprocesador. Entre otras cosas, las variables inicializadas con USING son sustituidas en el código por su valor en todos los lugares donde aparece su nombre.

Compilación: La compilación transforma el código C# en el lenguaje ensamblador propio del procesador del computador en el cual se realizó la compilación.

Ensamblado: El ensamblado transforma el programa escrito en lenguaje ensamblador a código objeto, un archivo binario en lenguaje de máquina ejecutable por el procesador.

Enlazado: Las funciones de C# incluidas en nuestro código, tal como console.WriteLine (), se encuentran ya compiladas y ensambladas en bibliotecas existentes en el sistema. Es preciso incorporar de algún modo el código binario de estas funciones a nuestro ejecutable. En esto consiste la etapa de enlace, donde se reúnen uno o más módulos en código objeto con el código existente en las bibliotecas.

7. Generar CI para el código siguiente:

If x>10 and Not(y<0)>

Generacion de código Intermedio

Oper: “:=#” -- Arg1:”A” -- Arg2:”2” -- Resol:”$t0”

Oper: “:=#” -- Arg1:”B” -- Arg2:”1” -- Resol:”$t1”

Oper: “operplus” -- Arg1:”$t0” -- Arg2:”$t1” -- Resol:”$t2”

for (i=0; i<10;>

Generacion de código Intermedio

Oper: “:=#” -- Arg1:”i” -- Arg2:”i+1” -- Resol:”$t0”

Oper: “:=#” -- Arg1:”x” -- Arg2:”x+i” -- Resol:”$t1”

Oper: “operplus” -- Arg1:”$t0” -- Arg2:”$t1” -- Resol:”$t2”

ANALISIS SEMANTICO

ANALISIS SEMANTICO

El analisis semantico es posterior al sintáctico y mucho más difícil de formalizar que éste. Se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc. En definitiva, comprobará que el significado de lo que se va leyendo es válido.

También se encarga de revisar que cada agrupación o conjunto de token tenga sentido, y no sea un absurdo. En esta etapa se reúne la información sobre los tipos para la fase posterior, en esta etapa se utiliza la estructura jerárquica de la etapa anterior y así poder determinar los operadores, y operandos de expresiones y preposiciones. Se compone de un conjunto de rutinas independientes, llamadas por los analizadores léxico 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 lineal (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. En el caso de los operadores polimórficos (un único símbolo con varios significados), el análisis semántico determina cuál es el aplicable. Por ejemplo, consideremos la siguiente sentencia de asignación: A := B + C En Pascal, el signo “+” sirve para sumar enteros y reales, concatenar cadenas de caracteres y unir conjuntos. El análisis semántico debe comprobar que B y C sean de un tipo común o compatible y que se les pueda aplicar dicho operador. Si B y C son enteros o reales los sumará, si son cadenas las concatenará y si son conjuntos calculará su unión.

Funciones

Entre las funciones de un analizador semántico están las siguientes:

· Detectar si las variables, constantes y funciones han sido declaradas antes de ser utilizadas.

· Verificar que las variables, constantes y funciones sean accesibles (visibilidad) desde el ámbito en que son utilizadas.

· Comprobar que los diferentes identificadores solo hayan sido declarados una vez.

· Comprobaciones de tipos al evaluar las expresiones. Por ejemplo que no se multiplique un número por una cadena que la expresión a evaluar en un IF sea del tipo booleano. Las reglas de inferencia de tipos gobiernan el tipo de una expresión en función del operador y el tipo de sus operandos.

· Verificar que no se intente modificar el valor de una constante.
· Generar la tabla de símbolos.

¿Cómo hacer un análisis semántico?

Para realizar el análisis semántico utilizaremos una gramática de atributos. Dichos atributos se asociaran tanto a los símbolos terminales como a los no terminales y se propagarán por el árbol sintáctico desde abajo hacia arriba, dando lugar al árbol semántico.

Lo primero que haremos será definir las reglas semánticas, para ello utilizaremos de nuevo la notición BNF a la que añadiremos en pseudocódigo las reglas semánticas. Recorreremos recursivamente el árbol sintáctico en postorden (para cada nodo procesamos recursivamente todos los descendientes primero y luego el nodo). Iremos añadiendo atributos con información al árbol a medida que procesemos nodos. Como el recorrido se realiza en postorden cuando procesemos un nodo ya habremos procesado previamente todos sus descendientes por lo que dispondremos de la información de que nos provean sus atributos.

Añadiremos a la tabla de símbolos todas las constantes y variables que se vayan reconociendo, junto con la información del tipo y el valor (en el caso de las constantes). La tabla de símbolos será una lista de elementos del tipo símbolo.

Ejemplo 1:

// Un identificador no se puede utilizar si previamente no se ha definido.
char a; // Variable tipo char
int i; // Variable tipo entero
a = i + 2 ;
Análisis Léxico: Devuelve la secuencia de tokens: id asig id suma numero
Análisis Sintáctico: Orden de los tokens válido
Análisis Semántico: Tipo de variables asignadas incorrecta

Ejemplo 2:

Análisis de tipos: se anota el árbol sintáctico con el tipo de cada una de la expresiones y subexpresiones.

Ejemplo en Java: 3 / 2 + 3 * 0.5 / 2
+ : double
/ : int
3 : int
2 : int
/ : double
* : double
3 : int
0.5 : double
2 : int

Las reglas de inferencia de tipos gobiernan el tipo de una expresión en función del operador y el tipo de sus operandos.

Consistencia semántica del árbol sintáctico: Por ejemplo, no tiene sentido restar dos strings.