COMPILADORES E INTERPRETES
1. En el cuadro siguiente escriba dos tareas para cada analizador:
Analizador Léxico
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
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
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
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)
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;
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:
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:
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
for (int i = 0; i <>
arrayEnteros.Add(i);
for (int i = 0; i <>
Una vez ejecutado obtendremos los siguientes valores (o muy parecidos dependiendo del computador de cada cual):
Resultado: 199999990000000 Tiempo Un/Boxing : 4695 Memoria: 883595136
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)>
suma = suma + arrayEnteros[i ];
return suma;
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í:
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;
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();
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
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”
