Wednesday, July 12, 2006

Final de Compiladores II

Hola amigos, regresamos por acá para comentarles acerca del desenlace de la clase de Compiladores II y sobre nuestro Compilador de C.
Gracias a Dios Todopoderoso, las cosas salieron muy bien. Después de 3 ó 4 meses de dura lucha y bonito aprendizaje, terminamos en buena lid.
Sin duda el mundo de los compiladores es bonito e interesante pero para disfrutarlo tenemos que meternos bien al rollo como se dice popularmente.

Vamos a ver, si podemos colocar el compilador de micro-C, para que lo puedan evaluar y además colocar links buenos, sobre las últimas herramientas en materia de compiladores.

Tengan buen día y pronto volveremos con más...

Tuesday, June 06, 2006

Seguimos con el código intermedio…

Hola amigos, poco a poco estamos aproximándonos al día de entrega del proyecto del curso de Compiladores II, y las horas día con día se hacen mas y mas cortas, como quisiéramos un chancecito mas para el proyecto, pero lastimosamente ya no se puede. Ni modo, que sea lo que Dios quiera.
Por lo pronto, nosotros seguimos en la generación de código intermedio, específicamente la generación de Quads.

Les quiero contar cómo realizamos la generación de Quads para nuestras expresiones aritméticas, pues lo hacemos de la siguiente manera:

En primer lugar sintetizamos el número de registro en donde se coloca el valor de la expresión aritmética así:

tmpCExpression.setNumRegistro(term.getNumRegistro());
// term ::= term MULT factor
ast.lQuads.add(new cQuad(cOperadorQuad._MULT,term.getNumRegistro(),factor.getNumRegistro(),term.getNumRegistro()));
cRegistrosT.freeRegisterT(factor.getNumRegistro());
RESULT=tmpCExpression;

En este caso en term se sintetiza un objeto cExpression en donde en uno de sus atributos se encuentra el numero de registro en donde se va a alojar el valor de dicha expresión. Luego agregamos el Quad a una lista de Quads, que al fin y al cabo esa es la lista que va a representar el código intermedio de nuestro proyecto.
Y por último liberamos el registro en donde se encontraba almacenado el operando derecho de la expresión.

Esto es análogo para las cuatro expresiones suma, resta, multiplicación y división. Además para las expresiones relacionales también estamos usando la misma idea.

Además, ya generamos los quads que crean el prólogo y el epílogo de una función, también los quads que reservan espacio para las variables locales de la función, igual que para los argumentos.

En lo que estamos pensando en estos momentos, es en los quads para los statements repeat-until, while y if. Pero esperamos terminarlos lo más pronto posible.

Gracias amigos por su atención, que pasen un feliz día.

Sunday, May 28, 2006

Los Quads, nuestro proximo objetivo…

Hola amigos, otra semana mas que transcurre y poco a poco nos acercamos al final del curso, aunque todavía no se ha avanzado lo que se esperaba en la construcción del micro-C, pero tenemos la confianza en Dios, que todo saldrá bien.

Recién la semana pasada, les comentamos que comenzamos a diseñar los Quads para la generación del código intermedio, sin duda, ésta será una labor muy ardua, ya que hay que considerar una gran cantidad de situaciones que podrían darse, durante la traducción del programa. Entre esas situaciones podríamos mencionar:

Declaración de variables, definición de funciones, especialmente las recursivas, que aunque tenemos una idea de como representarlas en el stack frame todavía dicha idea no nos convence en lo absoluto, entre otras de las cuales estaremos platicando seguramente en los próximos días.

Hablemos del caso especial de una función, la estrategia que tenemos pensado seguir, es que cuando el parser detecte que existe una definición de una función, nosotros procedamos a realizar las tareas que sean necesarias para reservar el espacio requerido en el stack para dicha función: como crear el stack frame, reservar espacio para las variables locales, no incluímos la reservación de espacio para los argumentos pasados a la función ya que éstos se almacenaran en el espacio del invocador, etc. En este apartado, nos entra la fuerte duda sobre cómo funcionaría esto en el caso particular de las funciones recursivas, ya que como todos sabemos, cada función recursiva debe de tener creado su propio stack frame, para que se pueda preservar el valor de cada una de sus variables en el ámbito que corresponda.
Entonces, si nosotros pensamos dedicar solo una porción del stack para la función, al momento en que se realice el auto-llamado, la función invocada sustituiría los valores de las variables de la función invocadora, entonces es evidente, por lo menos desde nuestro punto de vista, de que se tiene que crear otro stack frame para la función invocada. Pero el problema es que no sabemos cuantas veces se llamará a si misma la función, como para reservar ese espacio de antemano, por lo que todavía no esta claro como vamos a ir creando los stack frames conforme la función se vaya auto-llamando.

En cuanto a la declaración de las variables, estamos de acuerdo, de que por cada variable int o char, se reservaran 4 bytes en el stack frame, al mismo tiempo que se almacenara en la tabla de símbolos el offset respectivo para cada variable.

En cuando a la asignación indizada, por los momentos no nos preocuparemos, ya que a nosotros nos tocó el statement repeat-until.

Por cada ítem que les acabo de mencionar, haremos un Quad para cada caso. Además, haremos Quads para la traducción de statements como while, if, repeat-until, printf, scanf.



Por los momentos ya tenemos creadas varias clases, las cuales detallamos a continuación:

cQuad: Representa un quad, en el AST. Y sus atributos son:

private int operador;
private int operando1;
private int operando2;
private Object result;

Tenemos una clase, exclusivamente diseñada para la representación de cada operador que esté involucrado en un Quad en el AST. La clase es cOperatorQuad. La cual esta compuesta de una serie de atributos estáticos de tipo entero, los cuales describirán a través de su nombre el fin para el cual serán utilizados. Dichos atributos serán utilizados, para ser seteados en el campo operador de la clase cQuad que recién les mostramos.

Además, también tenemos una clase llamada cRegistrosT, la cual representaran cada uno de los 10 registros, $t0 … $t9, de MIPS, los cuales serán utilizados para la carga de variables locales y temporales, en la ejecución de los programas. A través de dicha clase se realizara la asignacion y liberación de cada uno de estos registros.

Esto es todo por hoy, ha sido un placer comunicarles el estado de avance del compilador micro-C.

Que tengan un buen día!

Saludos!

Monday, May 22, 2006

Culminando el Análisis Semántico...
Muy buen día amigos, espero que estén todos bien, esperando ansiosos el inicio de la copa del mundo, el cual es el máximo evento futbolístico en todo el planeta. En lo particular, les comento que soy un amante al fútbol, y cada cuatro años espero este grandioso momento, para ver sobre un terreno de juego a las mejores 32 selecciones a nivel mundial, disputándose el trofeo mas anhelado para todo futbolista.

Después de este momento tan placentero, entramos también a otro, muchísimo más placentero, claro, adivinaron, nuestro compilador micro-C. Gracias a Dios ya hemos culminado la parte correspondiente al análisis semántico, el cual se nos hizo bastante extenso. Recién en blogs pasados, les comentábamos algunos de los avances que habíamos tenido en este respecto. La verdad, no hemos avanzado lo que esperábamos, por la presión de las otras asignaturas, pero ya miramos que se está acercando el día D, por lo que tenemos que apresurar la marcha.

En relación a los aspectos recientemente validados podemos mencionar los siguientes:

En el llamado a una función el número y tipo de parámetros sea igual a los declarados.
En el llamado a una función el número y tipo de parámetros sea igual a los definidos.
Que solo dentro de los statements while y repeat, se permiten la aparición de statements continue y break. En cualquier otro lado es un error semántico.
Que el tipo de retorno de una función sea igual al que se especificó en la declaración o definición de la misma.
Que una función que retorna un valor, tenga obligatoriamente un return.
Que después de un return no deba existir ninguna otra instrucción, ya que ésta nunca llegaría a ejecutarse.

Uno de los ítems en el cual trabajamos mas en su validación, fue en el tipo de retorno de una expression, ya que esta involucra operaciones aritméticas, relacionales, llamados a funciones, entre otras cosas más. Por lo que teníamos que validar todo eso, para el caso, en las operaciones relacionales validábamos que no se compararan variables de diferentes tipos, ya que esto no tendría sentido; también en operaciones aritméticas, no multiplicar variables de diferentes tipos, y cosas por el estilo.
Todo esto fue un trabajo muy laborioso el cual nos consumió un gran porcentaje del tiempo invertido en esta etapa.

Para la realización del análisis semántico, construimos las siguientes clases:

cExpression: Esta clase es una representación de una expresión, tiene atributos como tipo, valor, número de línea y nuúmero de columna. En donde tipo puede tener los valores como:

var=variable, funcArg=función con argumentos, funcSArg=función sin argumentos.

cParametro: Clase que representa un parámetro de una función. Contiene los atributos de tipo y nombre.

cStatement: Clase que representa un statement de nuestro lenguaje. Los atributos son los siguientes:

Tipo, Establece el tipo del statement. El cual puede ser: ret=return ;, retExp=return expression, while=while, if=if, break=break, continue=continue, exp=expression, stmtList=statement_list
ifelse=if-else, repeat=repeat-until

Tipo de Expression, en caso de que el statement sea un return entonces en este atributo se almacenará el tipo de retorno del return.
numeroLinea
numeroColumna
Lista de statements, esto es porque un statement puede tener en su interior otra lista de statements.
Una expression, esta es la expression de un statement return expression, y nos fué de mucha utilidad para validar el tipo de retorno de una función.

cInfoHeaderFunction: Nos mantiene la información del encabezado de una función. Y sus atributos son: El Tipo de Retorno y el Id de la función.

Las clases anteriores nos fueron de extrema utilidad para realizar nuestro análisis semántico.

Después del análisis semántico, lo que viene es la generación del código intermedio, utilizando para ello los Quads.
Para esto tenemos pensado crear una clase llamada cQuad, la cual va a tener cuatro o más atributos según se requiera, para ir colocando las instrucciones en código intermedio que posteriormente serán traducidas a código MIPS.

Esto es todo por hoy, espero platicarles más, la semana que entra.
Saludos.

Monday, May 15, 2006

SSA form y TSA Form

Que tengan un feliz día, hoy como de costumbre venimos con un tema más que interesante relacionado a la representación de código intermedio, concepto que es de mucha utilidad sobre todo cuando hablamos de la portabilidad de las aplicaciones programadas en x lenguaje.
La forma de representación de código intermedio de la cual trataremos este día, es la forma SSA(SSA form).
Dicha forma de representación, tiene como principal objetivo optimizar el código intermedio generado por un determinado lenguaje. Y lo optimiza en el sentido en que cada variable que se use en el código fuente es asignada exactamente una vez. Y en qué forma lo hace?, pues la forma es simple, solamente se divide la variable en distintas versiones dependiendo del número de veces que cambie su valor durante la ejecución del programa, y a cada versión la identificamos por un subíndice y el nombre original de la variable.

Por ejemplo:

y = 1
y = 2
x = y

Sería visto de la siguiente forma, aplicando SSA form.

y1 = 1
y2 = 2
x1 = yz

Además en ejemplos como el siguiente:

x = 5
x = x-3
if x < 3 then
y=x*2
w=y
else
y=x-3
w=x-y
z=x+y

Ahora nosotros podemos apreciar que después de que se evalúa la expresión if, cuando se usa posteriormente la variable “y”, no sabemos qué valor tendría ésta, si y=x*2 ó y=x-3. Entonces para esto nos auxiliamos de una función llamada phi(Φ), que nos dice que variable “y” usar. Ahora veamos como quedaría después de aplicarle la forma SSA.

x1 = 5
x2 = x1-3
if x2 < 3 then
y1=x2*2
w1=y1
else
y2=x2-3
y3= Φ(y1,y2)
w2=x2-y3
z1=x2+y3


En referencia al surgimiento de este tipo de IR(Intermediate Representation), les queremos comentar que ésta fue desarrollada por investigadores de IBM en la década de los 80s.

Ahora daremos un ejemplo, en el cual vamos a optimizar el código intermedio para alguna de las expresiones aritméticas de nuestro proyecto:

Si tuviéramos el siguiente código:

h=20
i=30
while(h>50) {
i=i+1
h=h+i
}

La representación en SSA form seria:

h0=20
i0=30
if (h0<=50) goto L0
L1: i1= Φ(i0,i2)
h1= Φ(h0,h2)
i2=i1+1
h2=h1+i2
if (i2>50) goto L1
L0: i3= Φ(i0,i2)
h3= Φ(h0,h2)

Como ustedes pueden ver, el valor de las variables i1 y h1, se obtiene haciendo uso de nuestra función phi, la cual la primera vez que entra al ciclo while toma el valor de i0 y h0, respectivamente. Pero después de la primera iteración, tomarían el valor de i2 y h2, de igual forma.

Espero que hayan comprendido la idea de este tipo de IR, entretanto, enseguida hablaremos de SafeTSA, la cual es otro tipo de IR.

Sunday, May 07, 2006

Ven! Te invito a aprender algo acerca de los Argumentos Variables en C y el uso de la función alloca()...

Muy buen día estimados amigos lectores. Hoy regresamos con todos los ánimos del mundo para conversarles aspectos importantes en relación a la forma de utilizar funciones que admiten un número de argumentos variables en el lenguaje C, así como el uso de la función alloca y el impacto que tiene el uso de ésta en el stack frame.

Según lo que investigamos no es algo tan trivial el uso de argumentos variables en C, pero también no es cosa del otro mundo, solo que tenemos que seguir algunas reglas para realizar su programación.

Para que puedan llegar a comprender mejor como se realiza este proceso, los vamos a hacer revisando el siguiente ejemplo.

En primer lugar, vamos a utilizar un archivo de cabecera llamado stdarg.h, en el cual se encuentran unas macros que nos serán de mucha utilidad en todo este proceso. La sentencia que tendremos que escribir en el área de nuestros includes es la siguiente:

#include

A continuación explicamos en que consiste cada macro:

void va_start(va_list pa, last): hace que pa apunte al último argumento justo antes de que comience la lista de argumentos variables.
tipo va_arg(va_list pa, tipo): devuelve el valor del siguiente argumento apuntado por pa y de tipo tipo.
void va_end(va_list pa): manipula un retorno normal de la función cuya lista de argumentos variables fue inicializada por va_start.

El argumento last, el cual se le envía a la macro o función va_start, es el ultimo argumento que conoce la función, es decir, el que esta exactamente antes del primer argumento en la lista de argumentos variables.

Además es importante decir en que consiste el tipo de dato va_list, éste es un tipo de dato que define un puntero a la lista de argumentos variables.

Para tener una idea más exacta, a continuación mostraremos una porción de pseudo código que nos dirá cómo utilizar cada una de estas macros con el fin de programar una función que acepte argumentos variables.

tipo funcionVariable(last,...) {
va_list pa;
tipo_X argumento_de_tipo_X;
va_start(pa,last);
while (quedanArgumentos)
argumento_de_tipo_X = va_arg(pa, tipo_X);

va_end(pa);
}

Ahora explicaremos brevemente el pseudo código anterior:

Primero declaramos el apuntador a la lista de argumentos variables, llamada pa. Seguidamente, declaramos variables de diferentes tipos de datos, los cuales son los distintos tipos que podrá aceptar nuestra función. Ahora, procedemos a hacer que pa apunte al último argumento, ubicado justo antes del primer argumento en la lista de argumentos variables. Con esto, ya tendremos una ubicación exacta de donde comienzan los argumentos que no conocemos. Esto lo hacemos mediante la macro va_start.

Posteriormente en un ciclo while, recorreremos la lista de argumentos variables, con la ayuda de nuestra macro va_arg. Y para culminar, siempre colocamos el llamado a la macro va_end, quien se encarga de que el retorno de la función sea procesado sin problemas.

Existen diferentes formas de implementación de esta clase de argumentos en C. Por ejemplo, utilizando una variable que nos indique el numero de argumentos que recibirá la función, o lo que es similar, una cadena de formateo, al puro estilo de la función printf, la cual nos dirá cuántos argumentos espera la función y el orden de los mismos.

Y para llevar un poco de lo visto anteriormente a la práctica, enseguida mostramos una función con argumentos variables y su respectiva invocación, codificada en lenguaje C.
Esta función, como ustedes verán mas adelante, es una imitación de la función printf de C, en donde la variable formato es una cadena que nos especificará el orden en que se imprimirán los argumentos variables. En dicha función, los caracteres ?s representan una cadena y ?d un numero tipo entero. Pero sin más rodeos, veamos mejor el código:

void pprintf(char *formato, ...) {
char *p;
va_list pa;
va_start(pa, formato);
for (p = formato; *p; p++) {
if (*p != '?') {
putchar (*p);
continue;
}

switch (*++p) {
case 'd':
printf("(%d)", va_arg(pa, int));
break;
case 's':
printf("(%s)", va_arg(pa, char *));
break;
default:
putchar(*p);
break;
}
}
va_end(pa);
}


int main (void) {
pprintf("Probemos a poner paréntesis a una ?s y a un ?d \n", "cadena", 25);
return 0;
}

El retorno de la función pprintf es el siguiente:
”Probemos a poner paréntesis a una (cadena) y a un (25)”.

Y con esto finalizamos la explicación de cómo programar funciones con argumentos variables en C.

Por otra parte, con respecto a la función alloca() del lenguaje C, queremos decirles que ésta reserva memoria en el marco de pila de las funciones, la cual es implícitamente liberada al retornar.
Es decir, que alloca() reserva un espacio determinado en el stack frame a la hora en que se invoca una función, y una vez que la función termina de hacer su trabajo, o sea, que se produce el return, el espacio lo libera automáticamente.

La ventaja de usar esta función es el rendimiento, ya que es muy eficiente. Además, es oportuno mencionar que a esta función se le envía de parámetro el tamaño del área a reservar en el stack frame.

En adición, es importante citar, que cuando se use alloca() el espacio que se vaya a reservar no sea mayor al espacio libre en el stack frame, ya que si esto pasa, entonces se levanta una excepción llamada “core dump”.

Otro aspecto importante, es que para utilizar la función alloca() se debe de incluir el archivo de cabecera alloca.h en nuestro programa, ya que si este archivo no se incluye, se pierde una gran cantidad de rendimiento al ejecutar la función.

Y por ultimo, el espacio liberado por alloca() al termino de una función, puede ser reutilizado perfectamente para alojar otra función o para cualquier actividad similar.

Bueno amigos, esto es todo en cuanto a los argumentos variables y a la función alloca() del lenguaje C, pero también, quisiera comentarles algo con respecto al avance en la construcción de nuestro compilador micro-C.

En los últimos días, hemos estado realizando toda clase de validaciones en relación al análisis semántico, ya que a partir de este próximo lunes comenzamos a ver el tema de código Intermedio en la clase, por lo que para realizar la traducción a código intermedio es un requerimiento esencial la culminación de toda la parte semántica del compilador.

Hasta pronto!

Monday, May 01, 2006

Primeros pasos en la generación de código MIPS...

En esta ocasión presentaremos la resolución del laboratorio #2, en el cual se nos solicito realizar la traducción a código MIPS del calculo de algunas operaciones aritméticas básicas, de las cuales hicimos un laboratorio en la clase de Compiladores I.

La práctica de laboratorio consiste en leer un archivo de texto .txt como el siguiente:


En el cual se encuentran una serie de operaciones aritméticas separadas por el caracter “;”. Al realizar el análisis léxico y sintáctico de este archivo, se generara en un archivo aparte con extensión .s, el código MIPS concerniente al calculo del resultado de cada una de esas expresiones. En este caso particular, el código MIPS generado es el siguiente:


La programación de la generación de las instrucciones MIPS lo hicimos en el archivo minimal.cup. Además quiero comentarles que hicimos una clase llamada cRegisterS, para que nos controlara los registros libres de la CPU. A continuación les colocamos una parte del código que efectúa el trabajo de la traducción a código MIPS:

terminal SEMI, PLUS, TIMES, DIV, MINUS, LPAREN, RPAREN;
terminal Integer NUMBER;

non terminal expr_list, expr_part;
non terminal String expr;

precedence left PLUS;
precedence left TIMES;

expr_list ::= expr_list expr_part expr_part;
expr_part ::= expr:e {:

strMipsCode.append("#Mostrar mensaje personalizado\n");
strMipsCode.append("addi $v0, $zero, 4\n");
strMipsCode.append("la $a0, mensaje0\n");
strMipsCode.append("syscall\n");
strMipsCode.append("#Mostrar el resultado de la operación\n");
strMipsCode.append("li $v0, 1\n");
strMipsCode.append("move $a0, "+e+"\n");
strMipsCode.append("syscall\n");
strMipsCode.append("#Mostrar newline\n");
strMipsCode.append("addi $v0, $zero, 4\n");
strMipsCode.append("la $a0, newline\n");
strMipsCode.append("syscall\n");
cRegistrosS.freeRegisterS(e);
:} SEMI;
expr ::= NUMBER:n
{:
String freeRegister=cRegistrosS.getFreeRegisterS();
if(!freeRegister.equals("0")){
strMipsCode.append("li "+freeRegister+", "+n.intValue()+"\n");
RESULT=freeRegister;
}else{
System.out.println("Error: Insuficientes registros de la CPU");
}
System.out.println("expr ::= NUMBER");
:}
expr:l PLUS expr:r
{:
strMipsCode.append("add "+l+", "+l+", "+r+"\n");
cRegistrosS.freeRegisterS(r);
RESULT=l;
System.out.println("expr ::= expr PLUS expr");
:}
expr:l MINUS expr:r
{:
strMipsCode.append("sub "+l+", "+l+", "+r+"\n");
cRegistrosS.freeRegisterS(r);
RESULT=l;
System.out.println("expr ::= expr MINUS expr");
:}
expr:l TIMES expr:r
{:
strMipsCode.append("mul "+l+", "+l+", "+r+"\n");
cRegistrosS.freeRegisterS(r);
RESULT=l;
System.out.println("expr ::= expr TIMES expr");
:}
expr:l DIV expr:r
{:
strMipsCode.append("div "+l+", "+l+", "+r+"\n");
cRegistrosS.freeRegisterS(r);
RESULT=l;
System.out.println("expr ::= expr DIV expr");
:}
LPAREN expr:e RPAREN
{:
RESULT=e;
System.out.println("expr ::= LPAREN expr RPAREN");
:}
;


La idea principal para poder realizar la generación de las instrucciones MIPS, fue colocar en la producción expr, como atributo sintetizado, el numero de registro en el cual estaba alojado el resultado de expr, de esta manera cuando en el consecuente existía una expr, para poder realizar una operación con ella, lo hacíamos sin ningún problema, porque sabíamos en qué registro estaba el resultado de la misma.

Además, programamos algunas funciones útiles, por ejemplo, para generar tanto el prólogo del archivo .s como su respectivo epílogo. A continuación, citamos dichas funciones:

public String generarPrologo(){
StringBuffer strPrologo=new StringBuffer();
strPrologo.append("\n");
strPrologo.append("#Código MIPS para Laboratorio #2\n");
strPrologo.append("#Programado por: Rafael Alejandro Acosta Sandoval\n");
strPrologo.append(".data\n");
strPrologo.append("mensaje0: .asciiz \"Resultado: \"\n");
strPrologo.append("newline: .asciiz \"\\n\" \n");
strPrologo.append(".text\n");
strPrologo.append(".globl main\n");
strPrologo.append("main:\n");
strPrologo.append("#Establecer Stack Frame\n");
strPrologo.append("sub $sp, $sp, 32\n");
strPrologo.append("sw $ra, 28($sp)\n");
strPrologo.append("sw $fp, 24($sp)\n");
strPrologo.append("add $fp, $sp, 20\n");
strPrologo.append("\n");
return strPrologo.toString();
}

public String generarEpilogo(){
StringBuffer strPrologo=new StringBuffer();
strPrologo.append("\n");
strPrologo.append("#Quitar Stack Frame\n");
strPrologo.append("lw $fp, 24($sp)\n");
strPrologo.append("lw $ra, 28($sp)\n");
strPrologo.append("add $sp, $sp, 32\n");
strPrologo.append("li $v0, 10 #Exit\n");
strPrologo.append("syscall\n");
strPrologo.append("\n");
return strPrologo.toString();
}

Para finalizar, les quiero colocar el resultado de ejecutar el archivo MIPS, que colocamos anteriormente en este blog, en nuestro simulador PCSpim.


Gracias amigos, espero les haya resultado interesante el blog del día de hoy, y espero publicar la próxima semana otro blog en relación al avance del micro-C. Que tengan un buen día!