FIN DE SEMESTRE
June 16, 2007 3:07 am General, Parsing, ProgramaciónA que no saben qué? Llegó fin de semestre y la semana y media para los exámenes (recuperaciones, extraordinarios), por lo tanto, como soy relisto xD estuve esta semana sin navegar mucho :P.
Resumiendo las materias (copiando a la madona):
Matemáticas V: :):):):(:(:(
Teoría de la Computación: :):):):):):)
Desarrollo sustentable: :):):):):):)
IO: >:( N/A
Circuitos: :):):):):(:(
Como sea, me llevo buenos cimientos sobre analizadores sintácticos, circuitos y matemáticas xD (que realmente fueron las únicas materias rescatables). Lo bueno es que la semana que viene ya prácticamente se termino todo, dos días más para extraordinarios y se acabo 
(no pregunten si me llevo extras de mate XD).
Bueno, hoy tengo mucho sueño O.o y les comparto un pequeño programa (que se puede pasar a POO y demás yerbas, pero por el tiempo encima, ps 
que pasa de un gramática libre de contexto a la FNC (forma normal de chomsky) con algunas restricciones :P.
El código es:
/**
Descripcion: Convierte a forma normal de chomsky.
Ejemplo:
Gramatica:
A -> Ac Donde: A - Es un no terminal
A -> w Ac - Es la derivacion del no terminal A
Gramatica en Forma Normal de Chomsky:
A -> AZ
A -> w
Z -> c
Notas:
1) Los terminales deben ser de un solo caracter.
2) Como terminales acepta a-z y +,-,*,/,%,( y ).
3) Las derivaciones no deben contener espacios.
**/
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
typedef char cadena[80];
struct g{
char nterminal;
cadena derivacion;
};
g gramatica[20];
g fnc[30];
int pos=0;
int pos2=0;
int convertir();
int sprReglasUnitarias();
int verificar();
int duplicidad(char,int,int);
int crear(int,char,int,int);
int eliminar(char,int);
int terminal(int,int);
int noTerminal(int,int);
int main(){
system("CLS");
cout<<"Escribe una gramatica: "<<endl;
cout<<"Para terminal: $"<<endl;
do{
cout<<"No terminal: "; cin>>gramatica[pos].nterminal;
gramatica[pos].nterminal=toupper(gramatica[pos].nterminal);
if(gramatica[pos].nterminal!='$'){
cout<<"Derivacion: "; cin>>gramatica[pos].derivacion;
pos++;
}
else{
break;
}
}while(pos<20);
system("CLS");
cout<<"La gramatica es:"<<endl;
for(int j=0; j<pos; j++){
cout<<gramatica[j].nterminal<<" - > "
<<gramatica[j].derivacion<<endl;
}
convertir();
cout<<"La gramatica en FNC:"<<endl;
for(int j=0; j<pos2; j++){
cout<<fnc[j].nterminal<<" - > "
<<fnc[j].derivacion<<endl;
}
system("PAUSE");
return 0;
}
int convertir(){
// Suprime reglas unitarias
sprReglasUnitarias();
// Verifica y da formato a la forma normal de chomsky
verificar();
return 0;
}
int sprReglasUnitarias(){
char tmp;
int indice;
// Elimina no terminales no productivos
for(int j=0; j<pos; j++){
if( strlen(gramatica[j].derivacion)==1 ){
for(int x='A'; x<='Z' ; x++){
if(gramatica[j].derivacion[0]==x){
indice=j;
tmp=gramatica[j].derivacion[0];
gramatica[j].derivacion[0]='\0';
eliminar(tmp,indice);
}
}
}
}
for(int j=0; j<pos; j++){
if(gramatica[j].derivacion[0]!='\0'){
fnc[pos2].nterminal=gramatica[j].nterminal;
strcpy(fnc[pos2].derivacion,gramatica[j].derivacion);
pos2++;
}
}
return 0;
}
int eliminar(char tmp, int indice){
cadena string;
for(int j=0; j<pos; j++){
if( tmp==gramatica[j].nterminal){
strcpy(string,gramatica[j].derivacion);
gramatica[j].derivacion[0]='\0';
strcpy(gramatica[indice].derivacion,string);
}
}
return 0;
}
int verificar(){
const int indice=0;
int longitud=0;
for(int j=0; j<pos2; j++){
longitud=strlen(fnc[j].derivacion);
if(longitud==1){ //OK
if( terminal(indice,j) ) continue;
}
else if(longitud==2){
if( noTerminal(indice,j) && noTerminal(indice+1,j) ) continue;
else if( noTerminal(indice,j) && terminal(indice+1,j) ){ //OK
if( duplicidad(fnc[j].derivacion[indice+1],j,indice+1) ){
crear(2,fnc[j].derivacion[indice+1],j,indice+1);
}
j=-1;
}
else if( terminal(indice,j) && noTerminal(indice+1,j) ){ //OK
if( duplicidad(fnc[j].derivacion[indice],j,indice) ){
crear(2,fnc[j].derivacion[indice],j,indice);
}
j=-1;
}
else if( terminal(indice,j) && terminal(indice+1,j) ){ //OK
if( duplicidad(fnc[j].derivacion[indice],j,indice) ){
crear(2,fnc[j].derivacion[indice],j,indice);
}
if( duplicidad(fnc[j].derivacion[indice+1],j,indice+1) ){ //OK
crear(2,fnc[j].derivacion[indice+1],j,indice+1);
}
j=-1;
}
}
else if(longitud>2){
if( noTerminal(indice,j) ){ //OK
crear(1,fnc[j].derivacion[indice+1],j,indice);
j=-1;
}
else if( terminal(indice,j) ){ //OK
if( duplicidad(fnc[j].derivacion[indice],j,indice) ){
crear(2,fnc[j].derivacion[indice],j,indice);
}
j=-1;
}
}
}
return 0;
}
int crear(int operacion, char simbolo, int j, int indice){
static int num=90;
char ltr;
char* str=NULL;
char ch=num;
switch(operacion){
// Crea nuevo no terminal a partir de otro no terminal
// y lo restante a la derecha.
case 1:
{
//Crea nuevo no terminal
str=strchr(fnc[j].derivacion,simbolo);
strcpy(fnc[pos2].derivacion,str);
fnc[pos2].nterminal=ch;
num--;
pos2++;
//Da formato correspondinte
ltr=fnc[j].derivacion[indice];
fnc[j].derivacion[0]=ltr;
fnc[j].derivacion[1]=fnc[pos2-1].nterminal;
fnc[j].derivacion[2]='\0';
}
break;
// Crea nuevo no terminal eliminando un terminal
case 2:
{
//Crea un nuevo no terminal
fnc[pos2].derivacion[0]=simbolo;
fnc[pos2].nterminal=ch;
num--;
pos2++;
//Da formato correspondinte
fnc[j].derivacion[indice]=fnc[pos2-1].nterminal;
}
break;
}
delete str;
return 0;
}
int noTerminal(int indice,int j){
for(int x='A'; x<='Z' ; x++){
if(fnc[j].derivacion[indice]==x) return 1;
}
return 0;
}
int terminal(int indice,int j){
for(int x='a'; x<='z' ; x++){
if(fnc[j].derivacion[indice]==x) return 1;
}
//OK
if( fnc[j].derivacion[indice]=='+' ) return 1;
else if ( fnc[j].derivacion[indice]=='-' ) return 1;
else if ( fnc[j].derivacion[indice]=='*' ) return 1;
else if ( fnc[j].derivacion[indice]=='/' ) return 1;
else if ( fnc[j].derivacion[indice]=='%' ) return 1;
else if ( fnc[j].derivacion[indice]=='(' ) return 1;
else if ( fnc[j].derivacion[indice]==')' ) return 1;
else return 0;
}
int duplicidad(char simbolo,int j,int indice){
for (int x=0; x<pos2; x++){
if( strlen(fnc[x].derivacion) == 1){
if( simbolo == fnc[x].derivacion[0] ){
fnc[j].derivacion[indice]=fnc[x].nterminal;
return 0;
}
}
}
return 1;
}
Documento sobre el algoritmo:
Algoritmo_FNC
Ya estaré pensando en poner más programas sobre parsing y haber si los paso a POO.
Nos vemos :P, dejen comentarios U_U :P..
Califica el tema:
(1 votes, average: 1 out of 5)
Loading ...Temas Relacionados:
October 28th, 2008 at 3:52 am
¿No tienes la recetita de la Forma Normal de Graibach?
October 28th, 2008 at 4:16 am
Hola Memo, no, no la tengo. Pero, checa un programa que se llama kakuy, ahí viene la descripción de muchos algoritmos. Comenté algo por acá: http://soullost.org/gnulinux/usando-graphviz-para-hacer-graficas/
November 23rd, 2008 at 8:19 pm
Ese software está genial!