martes, 26 de enero de 2010

Configurando Bison en Windows

Como podemos leer en la wikipedia, GNU|bison es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores lexicos se pueden también obtener de otras formas. En un post anterior mencioné la forma en que uno podía configurar Flex para realizar analizadores léxicos. Bueno, en esta oportunidad vamos a desarrollar una sencilla calculadora con Bison y Flex. Los pasos para configurar el flex, nos dejan configurado al bison, listo para ser usado en nuestra calculadora. Ahora, voy a pasar a explicar la forma que deben tener los scripts que ingresaremos tanto a flex como a bison.

Para flex el script debe tener la siguiente estructura:

%{

#include <stdio.h>
#include "y.tab.h"
%}
%option noyywrap
%option yylineno

DIGITO [0-9]
ID [a-zA-Z][a-zA-Z0-9_]*

%%
{DIGITO}+("."{DIGITO}+)? {yylval.real=atof(yytext); return(TKN_NUM);}
"="    {return(TKN_ASIGN);}
";"    {return(TKN_PTOCOMA);}
"*"    {return(TKN_MULT);}
"/"    {return(TKN_DIV);}
"+"    {return(TKN_MAS);}
"-"    {return(TKN_MENOS);}
{ID}   {return(TKN_ID);}
%%

Como nos podemos dar cuenta, en este fichero declaramos los símbolos y las expresiones que forman a los token numero (TKN_NUM). Asumo que ya tienen conocimiento de cada una de las partes de un archivo de flex, así que ahora paso a mostrar la forma que debe tener el archivo que le ingresaremos a Bison:

%{

#include <stdio.h>
#include <math.h>
extern int yylex(void);
extern char *yytext;
void yyerror (char *s);

%}

%union
{
float real;
}

%start Calculadora

%token <real> TKN_NUM
%token TKN_ASIGN
%token TKN_PTOCOMA
%token TKN_MULT
%token TKN_DIV
%token TKN_MAS
%token TKN_MENOS

%token <real> TKN_ID
%type <real> Expresion

%left TKN_MAS TKN_MENOS
%left TKN_MULT TKN_DIV

%%

Calculadora: TKN_ID {printf("El valor de %s es:", yytext);}
TKN_ASIGN Expresion TKN_PTOCOMA{printf("%5.2f", $4);};
Expresion : TKN_NUM{$$=$1;}|
Expresion Expresion TKN_MAS {$$=$1+$2;}|
Expresion Expresion TKN_MENOS {$$=$1-$2;}|
Expresion Expresion TKN_MULT {$$=$1*$2;}|
Expresion Expresion TKN_DIV {$$=$1/$2;};

%%

void yyerror(char *s)
{
printf("Error %s", s);
}

int main()
{
yyparse();
return 0;
}

Tampoco voy a explicar la estructura de este fichero puesto que la documentación en internet es muy variada. Lo que si voy a detallar es la forma de obtener los ficheros *.c y *.h, puesto que, a mi parecer, es lo más confuso y poco explicado.

Como mencioné anteriormente, al configurar el flex siguiendo los pasos que expliqué en el post anterior el Bison quedará configurado también. Así que solo hay que realizar los siguientes comandos por consola y tendremos todo listo para integrarlo a nuestro proyecto de Dev-C++.

Situamos ambos ficheros en el directorio D:\calculadora(Si no existe, tenemos que crearlo, lógicamente) y luego abrimos una consola de Windows, hacemos lo mismo que hicimos con el Flex, estableciendo las variables de entorno, como muestro en la siguiente imagen:

Y con esos comandos se nos generará unos ficheros, los cuales automáticamente podemos integrarlo a un proyecto de Dev-C++ por ejemplo o agregarle más funciones.


Ahora ya tenemos lista nuestra sencilla calculadora escrita con ayuda de Bison y Flex. Solo debemos ejecutar Calculadora.exe e ir introduciendo algunas expresiones (En notación polaca claro)

a=4 5+;
hola=8 12*;
g=12 6/;

Aquí les dejo la carpeta del proyecto con los archivos tanto de flex como de bison. También les muestro la forma de correr el programa de la calculadora en la siguiente imagen:

Para algo más aplicativo puedes revisar esto:

Creando un ejecutable con Swi-Prolog

Este post lo escribí pues algunos amigos me comentaron cómo se podría crear un ejecutable con swi prolog. Bueno, SWI-Prolog nos provee de un mecanismo sencillo para la creación de ejecutables.
La manera de hacerlo es como muestro a continuación:

Primero debemos tener un cuerpo principal, en donde estén los predicados que se ejecutaran al inicio de la llamada a nuestro programa, lo que se asemeja a la función principal de C:
int main(int argc,char *argv[])
{
//Cuerpo de la función principal
return 0;
}
O al método principal de Java:
public Class Main() {

public static void main(String[] arg) {
//Cuerpo del método principal
}

}
En nuestro caso, en SWI-Prolog se declararía del siguiente modo (Hago referencia a SWI-Prolog y no al lenguaje en general, puesto que cada Entorno de Prolog tiene su propia forma de realizar este proceso) :
main:-
%
% Cuerpo del predicado principal
%
halt.
Luego de realizado este proceso, tendrémos que invocar al predicado que se encargará de crear el ejecutable en sí.
qsave_program('c:/ejecutable.exe', [stand_alone(true), goal(main)]).
Con eso bastará para distribuir nuestro propio ejecutable, teniendo en cuenta que al llevar de una máquina a otra al *.exe, se debe hacer lo mismo con los archivos *.dll de la carpeta \bin de la instalación de nuestro SWI-Prolog. (tanto *.dll's como *.exe deben estar en una misma carpeta).

Para cerrar este post, aquí les dejo el código fuente de un Sistema Tomador de Decisiones para la detección de plagas en sembríos de Tara así como su respectivo ejecutable (ejecutable.exe). Debemos descomprimir todos los archivos en la unidad C: de tal forma que nos quede 'C:\programa' y luego seguir los pasos arriba mencionados para generar el ejecutable.

En todo caso adjunto las dll necesarias, en caso no se quiera instalar todo el SWI-Prolog. Las pueden descargar aquí.

Recuerden que dentro de la carpeta programa hay un archivo léeme!!!!.txt es cuál es muy importante que lo lean, o en todo caso lean estos tips para poder ejecutar el sistema experto y generar su respectivo ejecutable:

1. Primero debes crear una carpeta en tu unidad C:\ llamado programa.
2. Dentro de C:\programa descomprimes todos los archivos de programa.rar
3. Descarga
- Instala primero el swi prolog
- Luego dentro de setup.rar, que es el instalador del swi prolog editor, dale doble clic al archivo setup.exe
- Siguiente, siguiete y listo xD!
4. Abre el swi prolog editor y asegúrate de cerrar todos los archivos anteriormente trabajados haciendo clic en menú
Archivo y cerrar todo.
5. Abre el archivo proyectofinal.pl que está en C:\ llamado programa y luego en menú iniciar, dar clic a consultar.
6. En la parte inferior, en el editor de consultas escribe lo siguiente sin comillas: "main."
7. Listo, tenemos nuestro sistema experto ejecutándose.

lunes, 11 de enero de 2010

Algoritmo de anillo de fichas

Los procesos están organizados formando una estructura de anillo, donde a cada proceso se le asigna una posición en la estructura, de tal modo que cada proceso conoce a sus vecinos. Al inicializar el anillo se le da al proceso[0] el token, que circula en todo el anillo. Dicha ficha circula del proceso[k] al proceso[k + 1]. Como es obvio, el token estará circulando por todos los procesos, ya que estos se encuentran referenciados mediante una suerte de lista circular. Cuando un proceso obtiene la ficha de su vecino verifica si intenta entrar a una región crítica. En caso positivo el proceso entra a la región crítica (como se muestra en la zona marcada de rojo en la figura siguiente), hace el proceso necesario y sale de ella. Después de salir pasa la ficha a lo largo del anillo no se puede entrar a una segunda región crítica con la misma ficha (token o permiso).

En caso negativo:
La vuelve a pasar.

En un instante dado solo un proceso puede estar en una región crítica. En la figura podemos ver que solo un proceso es de color verde, es decir que solo ese proceso tiene la ficha y solo él está en facultad de poder acceder a su región crítica.


Si la ficha se pierde debe ser regenerada, pero es difícil detectar su perdida:

La cantidad de tiempo entre las apariciones sucesivas de la ficha en la red no está determinada, por ello es difícil decidir si está la ficha se ha perdido por algún error en un proceso o si es que está aún retenida por un proceso que está haciendo un uso intensivo de recursos.

La falla de un proceso es detectada cuando su vecino intenta sin éxito pasarle la ficha. Se lo debe eliminar del grupo y pasar la ficha al siguiente proceso activo. Todos los procesos deben mantener la configuración actual del anillo.

Bueno, espero haber sido claro explicando este algoritmo. Y para cerrar el post aquí les dejo el link de descarga del proyecto de simulación realizado en Netbeans.