GREIBACH.cpp_

//-------------------------------------------------------------------------
// 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();
}