/*

Autor: Marcin Jedrzejewski (s1525)

Data: 08-12-2002	

O programie:	
	Program oblicza postac normalna Chomskiego dla podanej gramatyki
	bezkontekstowej. 
	Kompilowane pod Microsoft Visual C++ 6.0 oraz pod Red Hatem 8.0 przy 
	pomocy g++.

format danych wejsciowych:
	
	Gramatyka   := Produkcje
	Produkcje   := Produkcja | Produkcja '\n' Produkcje
	Produkcja   := Nieterminal W '->' W Opis W
	Opis        := X | X W '|' W Opis
	X           := Terminal | Nieterminal | Terminal X | Nieterminal X 
	Terminal    := { [a-z0-9] } | '<e>' 
	Nieterminal := { [A-Z] }
	W           := { [\n ]* - białe znaki } 

wiecej o tym zadaniu tutaj:
	http://www.mimuw.edu.pl/~walen/pjwstk/jfa/zadanie1.html
*/

#pragma warning( disable : 4786 )

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <list>
#include <cassert>
#include <strstream>
#include <fstream>

using namespace std;

typedef list<string> OpisProdukcji;

struct production {
	string prod_name;
	OpisProdukcji opis;
};


typedef list<production> Gramatyka;

Gramatyka grammar;

//zawiera informacje czy dany nieterminal juz jest wykorzystywany np.: 
// nt_taken['A']==0 oznacza ze mozna dodac "A0" a
// nt_taken['A']==1 oznacza ze mozna dodac "A1" itd.
int nt_taken[256]={0};

// funkcje pomocnicze
int IsTerminal(string str);
void AddProdReplaceTerms(string term);
int ReplaceStringInOpis(OpisProdukcji &opis, string str1, string str2);
string GenProdName();

// glowne funkcje 
void ParseInput();
void SubstTerminals();
void EleminateEpsilonTerms();
void EleminateTransProds();
void UnrollProds();
void SortAndUnique();
void PrintGrammar();

int main(int argc, char* argv[])
{
	ParseInput();	
	SubstTerminals();	     // A->a daje A->B , B->a	
	EleminateEpsilonTerms(); // A->aBb i B-><e> daje A->ab	
	EleminateTransProds();   // A->B i B->t daje A->t
	UnrollProds();           // A->ABC zamien na A->AX i X->BC	
	SortAndUnique();
	PrintGrammar();		
	return 0;
}

void ParseInput()
{
	string bufor="";
	string tmpstr;
	
	//wrzuc gramatyke do bufora
	//fstream fs;
	//fs.open("test1.txt",ios::in);
	while( cin/*fs*/.good() )
	{
		std::getline(cin/*fs*/,tmpstr,'\n');	
		bufor+=tmpstr+"\n";
		tmpstr="";
	}
	
	//Parsuj wejscie, i umiesc wszystkie produkcje w zmiennej (liscie) grammar
	// typu Gramatyka. Kazda produkcja jest reprezentowana nastepujaco
	// nietermial -> opis1
	// nietermial -> opis2
	//         ...	
	
	string prev_str;			//zbiera elementy opisu
	string possible_prod;		//pamieta ostatni znak, ktory moze byc
								// poczatkiem produkcji
	production last_prod;		//aktualnie wypelniana produkcja
	for(int i=0;i<bufor.size();i++)
	{	
		//znaleziono nowa produkcje
		if(bufor[i]=='-' && bufor[i+1]=='>')
		{						
			prev_str="";
			i++;				
			last_prod.prod_name=possible_prod;
			nt_taken[possible_prod[0]]=1;
			continue;
		}
		
		//nowy opis aktualnej produkcji
		if(bufor[i]=='|' || bufor[i]=='\n')
		{
			if( prev_str.empty() ) continue;
			//cout << last_prod_name << " -> " << prev_str << endl;
			last_prod.opis.clear();
			
			for(int n=0;n<prev_str.size();n++)
			{
				//akceptuje tylko np.: S-><e> albo S-><e><e><e>
				// S->a<e> zamiania na S->a
				if(prev_str[n]=='<') //mamy "(<e>)*"
				{
					if (prev_str.size()-n==3 && last_prod.opis.size()==0)	//
						last_prod.opis.push_back("<e>");
					n+=2;
				}
				else				
				{
					nt_taken[prev_str[n]]=1;
					last_prod.opis.push_back(string("")+prev_str[n]);				
				}
			}
		
			grammar.push_back(last_prod);
			prev_str="";
			continue;
		}
		
		//zbiera opis do string'a
		if(bufor[i]!='\n' && bufor[i]!=' ')
		{
			possible_prod=bufor[i];
			prev_str+=bufor[i];
		}
	}
	
}


bool compp(production const& a, production const& b)
{
    return a.prod_name.compare(b.prod_name)==-1;
}

/*
	Sortuje produkcje, po nazwie produkcji
*/
void SortAndUnique()
{
	grammar.sort(compp);
	//grammar.unique(notequalto);
}

/*
	Wypisuje gramatyke w postaci normalnej chomskiego na standardowe wyjscie
	-do poprawnego dzialania wymaga aby gramatyka byla wczesniej posortowana
*/
void PrintGrammar()
{	
	Gramatyka::iterator prev_itor=grammar.begin();

	for(Gramatyka::iterator itor3=grammar.begin(); itor3!=grammar.end(); ++itor3)
	{
		//wypisz nazwe produkcji, 
		if(prev_itor->prod_name.compare(itor3->prod_name)!=0 ||
			itor3==grammar.begin())
		{
			if(itor3!=grammar.begin())
				cout << "\n";
			cout << (*itor3).prod_name << " -> " ;
		}
		else
		{
			cout <<  " | " ;
		}

		//wypisz opis produkcji
		for(OpisProdukcji::iterator itor2=(*itor3).opis.begin();
			itor2!=(*itor3).opis.end();++itor2)
		{
			cout << (*itor2);
		}
		
		prev_itor=itor3;
	}

	cout << endl;
}

/*
	Normalizacja
	Krok 1: podmiana nieterminali w miejsce terminali
	        dodaje tez nowe produkcje typu: nieterminal -> terminal
*/
void SubstTerminals()
{
	string str,pname;
	char tab[256]={0};//zeby nie powielac takich samych produkcji
					  // ktore moga powstac z produkcji typu A->a albo B->1

	//wykonuj dla kazdej produkcji
	for(Gramatyka::iterator itor=grammar.begin(); itor!=grammar.end(); ++itor)
	{				
		production pr = (*itor);

		//
		pname = (*itor).prod_name;
		for(OpisProdukcji::iterator itor2=(*itor).opis.begin();
			itor2!=(*itor).opis.end(); ++itor2)
		{	
			str=*itor2;	//element opisu produkcji np.: "<e>",'a','A'..	

			if(tab[str[0]]>0)
				continue;
			
			tab[str[0]]++;

			//jesli jest terminalem, to nastepuje podmiana
			if( IsTerminal(str) == 1 )
			{	
				AddProdReplaceTerms(str);
			}
			
		}		
	}
}

/*
	zamienia wszystkie wystapienia str1 w opisie produkcji na str2
*/
int ReplaceStringInOpis(OpisProdukcji &opis, string str1, string str2)
{
	int num=0; //ile podmieniono
	for(OpisProdukcji::iterator itor=opis.begin(); itor!=opis.end(); ++itor)
	{
		if((*itor).compare(str1)==0)
		{
			num++;
			(*itor)=str2;
		}
	}
	return num;
}

/*
	zwraca :
	 0 - jesli <e>
	 1 - jesli terminal
	-1 - jesli nieterminal
*/
int IsTerminal(string str)
{
	if (str.compare("<e>")==0)
		return 0;
	
	//jesli np.: "A1", gdzie A1 jest nieterminalem
	if (str.size()>1)
		return -1;
	
	//jesli 'a' | '0' ..
	if (islower(str[0]) || isdigit(str[0])/*(str[0]>='0' && str[0]<='9')*/ )	
		return 1;
	
	return -1;
}

/*
	Zamienia wszystkie wystapienia terminala term w opisach produkcji
	znajdujących się w gramatyce. Opis ten musi byc dluzszy niz 1.
	Na koncu dodaje nowa produkcje <wygenerowany_nieterminal> -> term .
*/
void AddProdReplaceTerms(string term)
{
	int count=0;
	production newprod;
	
	newprod.opis.push_back(term);
	newprod.prod_name=GenProdName();
	
	for(Gramatyka::iterator itor=grammar.begin(); 
	itor!=grammar.end(); ++itor)
	{
		if((*itor).opis.size()>1)
		{
			count+=ReplaceStringInOpis((*itor).opis, term, newprod.prod_name);
		}
	}
	
	//if(count>0)
	grammar.push_front(newprod);	
}

/*
	Generuje nowa nazwe dla nieterminala, posluguje sie
	tablica	nt_taken,
*/
string GenProdName()
{
	string out_prod;
	int max_ind='A';
	
	for( int i='A';i<='Z';i++)
	{
		if (nt_taken[max_ind] > nt_taken[i])
			max_ind=i;
	}
	
	out_prod=(char)max_ind;
	
	if ( nt_taken[max_ind] > 0)
	{		
		char buf[15]={0};
		strstream(buf,14) << nt_taken[max_ind];
		out_prod+=buf;		
	}
	nt_taken[max_ind]++;
	
	return out_prod;
}

/*
	Eliminuje z gramatyki produkcje typu <nieterminal>->epsilon .
*/
void EleminateEpsilonTerms()
{
	//znajdz produkcje typu "S -> <e>"
	for(Gramatyka::iterator itor=grammar.begin(); itor!=grammar.end(); )
	{
		//<e> zawsze bedzie jedynym elementem opisu, 
		if ( (*itor).opis.size()>1 )
		{
			++itor;
			continue;
		}
		
		string str = (*itor).opis.front();
		string prod=(*itor).prod_name;
		
		//usun jesli znaleziono, epsilon
		if ( str.compare("<e>")==0 ) 
		{			
			grammar.erase(itor++);
		}
		else
		{
			++itor;
			continue;
		}
		
		//powiel wszystkie produkcje zawierajace ten <nieterminal>,
		// i usun z nich go
		for(Gramatyka::iterator it=grammar.begin(); 
			it!=grammar.end(); ++it)
		{
			//sprawdz czy ta produkcja zawiera nieterminal (prod)
			// ktory ma sie zamienic na epsilon
			OpisProdukcji::iterator fnd = find_if((*it).opis.begin(), (*it).opis.end(),
				bind2nd(equal_to<string>(), prod) );
			
			//jesli nie znaleziono takiego nieterminala
			if (fnd == (*it).opis.end()) continue;			
			
			//jesli znaleziono, zrob kopie tej produkcji
			production newprod;
			newprod.opis.clear();
			copy((*it).opis.begin(),(*it).opis.end(),back_inserter(newprod.opis));			
			newprod.prod_name=(*it).prod_name;
			
			//usun nieterminale, ktore zamienily by sie na epsilon
			for(OpisProdukcji::iterator itr=newprod.opis.begin(); itr!=newprod.opis.end();)
			{
				string s1=(*itr);
				if((*itr).compare(prod)==0)
				{
					newprod.opis.erase(itr++);
				}
				else
				{
					++itr;
				}
			}
			
			//dodaj nowa produkcje o ile ma jakis opis
			if (newprod.opis.size()>0)
				grammar.push_back(newprod);
		}
	}
}

/*
	Jesli A->B i B-><opis> naleza do gramatyki, to A-><opis> rowniez.
	Procedura ta usuwa wszystkie A->B tego typu i zastepuje je A-><opis>.
*/
void EleminateTransProds()
{
	//znajdz produkcje typu "A -> B"
	for(Gramatyka::iterator itor=grammar.begin(); itor!=grammar.end(); )
	{		
		if (itor->opis.size()>1)
		{
			++itor;
			continue;
		}
		
		//jesli w opisie terminal, to pomin
		if (IsTerminal(itor->opis.front())==1)
		{
			++itor;
			continue;
		}
				
		production prod=(*itor);
		//usun ta produkcje
		grammar.erase(itor++);

		//jesli jest to produkcja typu A->A to tylko ja usun
		if (prod.prod_name.compare(prod.opis.front())==0)
		{		    
			continue;
		}
		
		string to_be_replaced = prod.opis.front();
		
		//znajdz wszystkie produkcje o nazwie prod.opis[0]
		// i swtorz nowa produkcje prod.prod_name -> nowa_znaleziona.opis
		for(Gramatyka::iterator it=grammar.begin(); it!=grammar.end();++it)
		{
			string ts=it->prod_name;
			if(it->prod_name.compare(to_be_replaced)!=0)			
				continue;
			
			prod.opis.clear();
            prod.opis=it->opis;
			//copy(it->opis.begin(), it->opis.end(), back_inserter(prod.opis));	
			grammar.push_back(prod);
		}
	}
}


/*
	Zamienia produkcje typu A->BCDE na A->BX, X->CY, Y->DE
*/
void UnrollProds()
{
	//znajdz produkcje typu A->ABC..
	for(Gramatyka::iterator itor=grammar.begin(); itor!=grammar.end(); )
	{		
		if (itor->opis.size()<=2)
		{
			++itor;
			continue;
		}

		//zrob kopie
		production prod=(*itor);
		production newprod;

		//usun ta produkcje
		grammar.erase(itor++);

		string last_pname;

		last_pname=prod.prod_name;
		
		OpisProdukcji::iterator pit = prod.opis.begin();
		for(int n=0; n<prod.opis.size()-2; n++)
		{
			newprod.prod_name = last_pname;
			last_pname=GenProdName();	//pobierz nowy symbol produkcji
			newprod.opis.clear();
			newprod.opis.push_back( *pit );
			newprod.opis.push_back( last_pname );
			++pit;
			grammar.push_back(newprod);
		}

		//add last two elements
		newprod.prod_name = last_pname;
		newprod.opis.clear();
		newprod.opis.push_back( *pit++ );		
		newprod.opis.push_back( *pit );					
		grammar.push_back(newprod);

	}
}