lunes, 22 de junio de 2009

Prueba 2.

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

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

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


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

Por ejemplo en C# para el cálculo de potencias podemos optimización código utilizando la función Pow de la clase Math, en lugar de crearla nosotros mismos.

Método no optimizado:

public int Operacion(int n, int exponente)
{
int temp = 1;
for (int cont = 1; cont <= exponente; cont++)
{
temp = temp * n;
}
return temp;
}

Método optimizado:

public int Operacion(int n, int exponente)
{
double resp;
resp=Math.Pow(n,exponente);
return resp;
}


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

Lo primero que le ocurre a un fichero de código C# es el preprocesado. En este paso se sustituyen todas las macros y se eliminan los comentarios. El resultado, si lo vemos independientemente, es un fichero de código C# preprocesado.
El segundo paso es la compilación propiamente dicha, en el que el código C# preprocesado se convierte en código ensamblador, que si lo vemos independientemente es un fichero .s.
El tercer paso es el ensamblado del código ensamblador, lo que lo convierte en código máquina. Un fichero de código máquina también es llamado fichero objeto.
Dado que el camino anterior normalmente convierte un fichero en un fichero, se suele hacer en un sólo paso, de código C# a fichero objeto.
El último paso es el enlazado de los ficheros objeto en el ejecutable final.


4. Generar CI para el código siguiente:

If x>10 and Not(y<0) Then
A+=2
B+=1
End if

Código Intermedio:



for (i=0; i<10; i++){
x += i;
}


Código Intermedio:

Prueba 1.

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

Léxico:

1. Leer la secuencia de caracteres del programa fuente, caracter a caracter, y los agrupa para formar unidades con significado propio o tokens

2. Manejo del fichero de entrada del programa fuente: abrirlo, leer sus caracteres, cerrarlo y gestionar posibles errores de lectura.

Sintáctico:

1. Tomar el programa fuente en forma de tokens, que recibe del analizador léxico, y determinar la estructura de las sentencias del programa.

2. Obtiene un árbol sintáctico (u
otra estructura equivalente) en la cual las hojas son los tokens, y cualquier nodo que no sea una hoja, representa un tipo de clase sintáctica (operaciones).

Semántico:

1. Determinar el tipo de los resultados intermedios, una vez que se conoce la estructura sintáctica.

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

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

a) a * b % c – d * a – d % e
POSTFIJA: a b * c % d a * d e % - -
PREFIJA: - % * a b c - * d a % d e

b)(a + c) – (d * e) / x % y
POSTFIJA: a c + d e * - x y % /
PREFIJA: / - + a c * d e % x y

c)(h – i – j * k) % m / x / y
POSTFIJA: 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.



INFIJA: ( ( a * b % c ) – d ) * ( ( h – f ) % e )
POSTFIJA: a b * c % d – h f – e % *
PREFIJA: * - % * a b c d % - h f e

miércoles, 13 de mayo de 2009

Herramientas para la construcción de compiladores

Se han creado algunas herramientas generales para el dise˜no automatico de componentes especıficos de compilador. Estas herramientas utilizan lenguajes especializados para especificar e implantar el componente, y pueden utilizar algoritmos bastante complejos. Las herramientas mas efectivas son las que ocultan los detalles del algoritmo de generacion y producen componentes que se pueden integrar con facilidad al resto del compilador. La siguiente es una lista de algunas herramientasutiles para la construccion de compiladores:

1. Generadores de analizadores sintacticos: Estos generadores producen anal-izadores sintacticos, normalmente a partir de una entrada fundamentada en una gramatica independiente del contexto. En los primeros com-piladores, el analisis sintactico consumıa no solo gran parte del tiempo de ejecucion del compilador, sino gran parte del esfuerzo intelectual de escribirlo. Esta fase se considera ahora una de las mas faciles de aplicar. Muchos de los generadores de analizadores sintacticos utilizan poderosos algoritmos de analisis sintactico, y son demasiado complejos para realizarlos manualmente.

2. Generadores de analizadores lexicos. Estas herramientas generan automaticamente analizadores lexicos, por lo general a partir de una especificacionbasada en expresiones regulares. La organizacion basica del analizadorlexico resultante es en realidad un automata finito. Una herramienta muyutilizada en la especificacion de analizadores lexicos para varios lenguajeses el compilador LEX.

3. Dispositivos de traduccion dirigida por la sintaxis. Estos producen grupos de rutinas que recorren el arbol de analisis sintactico, como el visto enclase, generando codigo intermedio. La idea basica es que se asocian una o mas ”traducciones” con cada nodo del arbol de analisis sintactico, y cada traduccion se define partiendo de traducciones en sus nodos vecinos en el arbol.

4. Generadores automaticos de codigo: Tales herramientas toman un conjunto de reglas que definen la traduccion de cada operacion del lenguaje intermedio al lenguaje de maquina para la maquina objeto. Las reglas deben incluir suficiente detalle para poder manejar los distintos metodos de acceso posibles a los datos; por ejemplo, las variables pueden estaren registros, en una posicion fija (estatica) de memoria o pueden tener asignada una posicion en una pila. La tecnica fundamental es la de ”concordancia de plantillas”. Las proposiciones de codigo intermedio se reemplazan por ”plantillas” que representan secuencias de instruccionesde maquina, de modo que las suposiciones sobre el almacenamiento de las variables concuerden de plantilla a plantilla. Como suele haber muchas opciones en relacion con la ubicacion de las variables (por ejemplo, en uno ovarios registros o en memoria), hay muchas formas posibles de ”cubrir” elcodigo intermedio con un conjunto dado de plantillas, y es necesario seleccionar una buena cobertura sin una explosion combinatoria en el tiempo de ejecucion del compilador.

5. Dispositivos para analisis de flujo de datos: Mucha de la informacion necesaria para hacer una buena optimacion de codigo implica hacer un ”analisis de flujo de datos”, que consiste en la recoleccion de informacion sobre la forma en que se transmiten los valores de una parte de un programa a cada una de las otras partes. Las distintas tareas de esta naturaleza se pueden efectuar esencialmente con la misma rutina, en la que el usuario proporciona los detalles relativos a la relacion que hay entre las proposiciones en codigo intermedio y la informacion que se esta recolectando.

Generación de Código Intermedio

En el modelo de análisis y síntesis de un compilador, 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.
Los detalles del lenguaje objeto se confinan en la etapa final, si esto es posible. Aunque un programa fuente se puede traducir directamente al lenguaje objeto, algunas
ventajas de utilizar una forma intermedia independiente de la máquina son:

1. Se facilita la redestinación; se puede crear un compilador para una máquina
distinta uniendo una etapa final para la nueva máquina a una etapa inicial ya existente.
2. Se puede aplicar a la representación intermedia un optimizador de código
independiente de la máquina.



Hay lenguajes que son pseudointerpretados que utilizan un código intermedio llamado
código-P que utiliza lo que se denomina bytecodes (sentencias de un μP hipotético). Por ejemplo
Java utiliza los ficheros .class, éstos tienen unos bytecodes que se someten a una
JavaVirtualMachine, para que interprete esas sentencias.
En este capítulo se muestra cómo se pueden utilizar los métodos de analizadores dirigidos
por la sintaxis para traducir a un código intermedio, construcciones de lenguajes de programación
como declaraciones, asignaciones y proposiciones de flujo de control. La generación de código
intermedio se puede intercalar en el análisis sintáctico.

Gestión de la memoria en tiempo de ejecución

Cuando un programa se ejecuta sobre un sistema operativo existe un proceso previo
llamado cargador que suministra al programa un bloque contiguo de memoria sobre el
cual ha de ejecutarse. El programa resultante de la compilación debe organizarse de
forma que haga uso de este bloque. Para ello el compilador incorpora al programa objeto el código necesario.
Las técnicas de gestión de la memoria durante la ejecución del programa difieren de unos lenguajes a otros, e incluso de unos compiladores a otros. En este capítulo se estudia la gestión de la memoria que se utiliza en lenguajes procedurales como FORTRAN,PASCAL, C, MODULA-2, etc. La gestión de la memoria en otro tipo de lenguajes(funcionales, lógicos, ...) es en general diferente de la organización que aquí se plantea.
Para lenguajes imperativos, los compiladores generan programas que tendrán en tiempo
de ejecución una organización de la memoria similar (a grandes rasgos) a la que aparece en la figura 1.



En este esquema se distinguen las secciones de:
- El Código
- La Memoria Estática.
- La Pila.
- El Montón.

viernes, 8 de mayo de 2009

ALGORITMO PARA CONVERTIR EXPRESIONES INFIJAS EN POSTFIJAS (RPN)


1. Incrementar la pila
2. Inicializar el conjunto de operaciones
3. Mientras no ocurra error y no sea fin de la expresión infija haz
- Si el carácter es:
*. PARENTESIS IZQUIERDO. Colocarlo en la pila


*. PARENTESIS DERECHO. Extraer y desplegar los valores hasta encontrar paréntesis izquierdo. Pero NO DESPLEGARLO

*. UN OPERADOR.
- Si la pila esta vacía o el carácter tiene más alta prioridad que el elemento del tope de la pila insertar el carácter en la pila.
- En caso contrario extraer y desplegar el elemento del tope de la pila y repetir la comparación con el nuevo tope.


*. OPERANDO. Desplegarlo.
4. Al final de la expresión extraer y desplegar los elementos de la pila hasta que se vacíe.

EXPRESIONES InFija, PreFija Y PosFija

1. PreFija:


La Expresión o Notación PreFija nos indica que el operador va antes de los operandos sus características principales son:


-Los operandos conservan el mismo orden que la notación infija equivalente.
-No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación.
-Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.
-Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando. Se repite este hasta que nos quede un solo resultado.



2. InFija:


La Expresión o Notación InFija es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión



3. PostFija:


Como su nombre lo indica se refiere a que el operador ocupa la posición después de los operandos sus características principales son:


-El orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua.
-La operación posfija no es exactamente lo inverso a la operación prefija equivalente



EJEMPLO:


Si deseamos representar la expresione (2+(3*4)) = x en las tres notaciones mencionadas, el resultado sería:


Notación prefija
= + 2 * 3 4 x


Notación infija
2+3*4 = x

Notación postfija
2 3 4 * + x =