//-------------------------------------------------------------------------
// Programa: Forma normal de Greibach
//
//
// Manera de ejecutarse:
// 2.- Dar enter cuando se termine
// 3.- Dar las producciones que genera cada una de las variables
// por separado (con enter)
// 4.- Dar enter cuando se termine
//
cciones)
// A1 ---------> A2 A3
// A2 ---------> A3 A1 | b
// A3 ---------> A1 A2 | a
//-------------------------------------------------------------------------
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream.h>
class conv_fn_greibach
{
public:
// forma normal de chomsky.
void genera_chomsky(void); // Genera la forma normal de chomsky.
void convierte_a_greibach(void); // Genera a la forma normal de greibach.
};
class producciones
{
public:
char *produccion;
producciones *sig;
producciones *ant;
void lee_producciones(void);
};
class gramatica
{
public:
char *nombre;
producciones *prods;
gramatica *sig;
gramatica *ant;
void lee_variables(void);
o
void genera_chomsky(void); // Genera la forma normal de chomsky.
void convierte_a_greibach(void); // Genera a la forma normal de greibach.
void imprime(void); // Imprime resultados.
};
class lista
{
public:
void append(char *, producciones *, gramatica *);
producciones *copia_lista(producciones *);
gramatica *invierte(gramatica *);
};
class correccion
{
public:
char *nombre;
correccion *sig;
correccion *ant;
void lista_a_corregir(char *); // Genera lista de variables a modificar
};
gramatica *inicio;
correccion *pri_correccion;
void gramatica::lee_variables(void)
{
gramatica *act = NULL, *ant = NULL;
conv_fn_greibach algoritmo;
producciones produce;
char *copia_nombre;
if (!(act = new gramatica))
{ cout << "\n No hay memoria"; return; }
gotoxy(40,18); cout << "<enter> para terminar";
inicio = act;
while (1)
{
cout << "\nNombre de variable: "; gets(copia_nombre);
if (copia_nombre[0] == '\0') break;
act->nombre = strdup(copia_nombre);
act->prods = NULL;
ant = act;
if (!(act = new gramatica))
{ cout << "\n No hay memoria"; break; }
ant->sig = act;
act->ant = ant;
}
inicio->ant = ant->sig = NULL;
delete act;
produce.lee_producciones();
algoritmo.verifica(); //<------- OK -------->
algoritmo.genera_chomsky(); //<------- OK -------->
//pri_correccion->nombre = "A3"; // linea temporal de prueba
algoritmo.genera_chomsky(); //<------- OK -------->
}
void producciones::lee_producciones(void)
{
producciones *ant=NULL, *act = NULL;
gramatica *gram = inicio;
int contador;
char *copia_produccion;
while(gram)
{
if (!(act = new producciones))
{ cout << "\n No hay memoria";
return;
}
gram->prods = act;
cout << "Nombre de la variable: " << gram->nombre;
contador = 1;
while(1)
{
cout << "\nProduccion {" << contador << "}: ";
gets(copia_produccion);
cout << copia_produccion;
if (copia_produccion[0] == '\0') break;
act->produccion= strdup(copia_produccion);
ant = act;
if (!(act = new producciones))
{ cout << "\n No hay memoria"; break; }
ant->sig = act;
act->ant = ant;
contador++;
copia_produccion = NULL;
}
ant->sig = NULL;
delete act;
gram = gram->sig;
}
}
void gramatica::imprime(void)
{
gramatica *gram = inicio;
producciones *prod;
while(gram)
{
cout << "\nVariable: {" << gram->nombre << "}";
cout << "\nProducciones: ";
prod = gram->prods;
cout << "{";
while(prod)
{
cout << prod->produccion;
prod = prod->sig;
if (prod) cout << " | ";
}
cout << "}";
gram = gram->sig;
}
}
int conv_fn_greibach::obten_numero(char *cadena)
{
return cadena[1];
}
void correccion::lista_a_corregir(char *variable)
{
correccion *act = NULL, *ant = NULL;
act = pri_correccion;
while(act) // Colocarse al final de la lista
{ ant = act; act = act->sig; }
if (!(act = new correccion))
{ cout << "\n No hay memoria"; return; }
if (!ant) //es el primero
{
pri_correccion = act;
act->ant = NULL;
}
else
{
ant->sig = act;
act->ant = ant;
}
act->sig = NULL;
act->nombre = strdup(variable);
}
void conv_fn_greibach::verifica()
{
gramatica *gram = inicio;
producciones *prod;
correccion modo;
conv_fn_greibach grei;
int numero1, numero2;
while(gram)
{
numero1 = grei.obten_numero(gram->nombre);
numero2 = grei.obten_numero(gram->prods->produccion);
if (numero1 > numero2) modo.lista_a_corregir(gram->nombre);
gram = gram->sig;
}
}
void conv_fn_greibach::genera_chomsky(void)
{
correccion *act_correc = NULL;
gramatica *act_gram = NULL;
gramatica algoritmo;
act_correc = pri_correccion;
while(act_correc)
{
act_gram = inicio;
while(act_gram)
{
if ((strcmp(act_correc->nombre, act_gram->nombre)) == 0)
{
algoritmo.corrige(act_gram->prods, act_gram);
break;
}
else
act_gram = act_gram->sig;
}
act_correc = act_correc->sig;
}
}
void gramatica::corrige(producciones *act_produccion, gramatica *act_gram)
{
conv_fn_greibach algoritmo, grei;
lista operacion;
gramatica gram;
char *nombre, *produccion;
int numero1, numero2;
strncpy(nombre, act_produccion->produccion, 2);
nombre[2] = '\0';
act_produccion->produccion++; //Eliminar
act_produccion->produccion++; //la variable
act_produccion->produccion++; //de la lista (el head)
operacion.append(nombre, act_produccion, act_gram); // unir NOMBRE al inicio de ACT_PRODUCCION
}
void lista::append(char *variable, producciones *act_produccion, gramatica *act_gram)
{
gramatica *gram = inicio;
producciones *prod=NULL, *primero=NULL, *ant=NULL;
lista auxiliar;
char *inserto, *copia, *produccion;
while(gram) // localizar al inicio de las producciones
{
copia = strdup(gram->nombre);
if ((strcmp(variable, copia)) == 0)
break;
gram = gram->sig;
}
primero = prod = auxiliar.copia_lista(gram->prods);
inserto = strdup(act_produccion->produccion);
while(prod)
{
produccion = strdup(prod->produccion);
strcat(produccion, " ");
strcat(produccion, inserto);
strcpy(prod->produccion, produccion);
ant = prod;
prod = prod->sig;
produccion = NULL;
}
ant->sig = act_produccion->sig;
act_produccion->sig->ant = ant;
//delete act_produccion;
}
producciones *lista::copia_lista(producciones *actual)
{
producciones *primero, *copia, *ant, *act;
char *copia_produccion;
if (!(copia = new producciones))
{ cout << "\n No hay memoria"; return NULL; }
primero = copia;
act = actual;
while(act)
{
strcpy(copia_produccion, act->produccion);
copia->produccion = strdup(copia_produccion);
ant = copia;
if (!(copia = new producciones))
{ cout << "\n No hay memoria"; break; }
ant->sig = copia;
copia->ant = ant;
copia_produccion = NULL;
act = act->sig;
}
ant->sig = NULL;
primero->ant = NULL;
delete copia;
return primero;
}
void conv_fn_greibach::convierte_a_greibach(void)
{
correccion *act_correc = NULL;
gramatica *gram = inicio;
lista operacion;
char *nueva_variable, *nombre;
act_correc = pri_correccion;
while(gram)
{
if (gram->nombre == act_correc->nombre) break;
gram = gram->sig;
}
nueva_variable = strdup(gram->prods->produccion); // obtiene la cabeza de la lista
gram->prods = gram->prods->sig; // elimina la cabeza de la lista
nueva_variable++; nueva_variable++; // elimina la
nueva_variable++; // primera variable
a la gramatica
operacion.append(nueva_variable, gram->prods, gram); // actualizar la produccion modificada
gram = operacion.invierte(inicio); // genera lista inversa
while(gram)
{
strncpy(nombre, gram->prods->produccion, 2);
nombre[2] = '\0';
gram->prods->produccion++; //Eliminar
gram->prods->produccion++; //la variable
gram->prods->produccion++; //de la lista (el head)
operacion.append(nombre, gram->prods, gram); // actualizar la produccion con la nueva variable
gram = gram->sig;
}
}
gramatica *lista::invierte(gramatica *gram)
{
gramatica *primero, *invertida, *ant;
if (!(invertida = new gramatica))
{ cout << "\n No hay memoria"; return NULL; }
invertida->sig = NULL;
while(gram)
{
invertida->nombre = gram->nombre;
ant = invertida;
if (!(invertida = new gramatica))
{ cout << "\n No hay memoria"; return NULL; }
invertida->sig = ant;
ant->ant = invertida;
gram = gram->sig;
}
delete invertida;
ant->ant = NULL;
return ant;
}
void main(void)
{
gramatica gram;
inicio = NULL;
pri_correccion = NULL;
clrscr();
gram.lee_variables(); //<------- OK -------->
gram.convierte_a_greibach();
gram.imprime(); //<------- OK -------->
cout << "\n<----- [ FIN ] Presiona una tecla ----->";
getch();
}