Checks Wirth–Weber precedence relationship. This is an old piece of code I wrote in university - this is scary but it works.

wirth-weber-prcedence-relationship.c

/******************************************************************/
/*                                                                */
/*     Dodatok do kyrsovoji robotu "Gramatuku peredyvannja".      */
/*     Programa realizyje algorutm 'perenos-zfortka'              */
/*     perevirjaje nalezhnist' vvedenoji                          */
/*     stri4ku do zadanoji gramatuku.                             */
/*                                                                */
/******************************************************************/


#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <windows.h>
#include <string.h>

#define rozmir 300         //Zadae rozmiru masuviv


/*******************OPUS ZMINNUH***********************/

char	M_prav[rozmir][rozmir],			//Masuv pravul
		M_neterm[rozmir],				//Masuv neterminaliv
		M_term[rozmir],					//Masuv terminaliv
		M_nts[2 * rozmir + 1],			//Masuv terminalu+neterminalu+$(dlja vuzna4enja porjadky v tabluci vidnowen')
		DividedRules[rozmir][rozmir],	//Masuv rozdilenuh pravul po sumvoly '|'
		Zgortka[rozmir],				//Osnova w4o zgortaet'sja
		L[rozmir][rozmir],				//Masuv livovuvodumuh sumvoliv
		R[rozmir][rozmir],				//Masuv pravovuvodumuh sumvoliv
		M_Virt_Weber[rozmir][rozmir][5],	//Matrucja vidnowen' Virta-Webera
		Str[rozmir],					//Stri4ka w4o vvodut'sja dlja perevirku
		DivRule[rozmir][rozmir],		//Masuv podilenogo pravula po sumvoly '|'
		Magazun[rozmir],				//Magazun
		ch;								//Dopomizhnuj sumvol

int		N,								//Kil'kist' neterminaliv
		T,								//Kil'kist' terminaliv
		gg=0,
		PrRozbir[rozmir];				//Masuv poslidovnosti rozbory

bool	pr,								//Praporec'
		gram_pered = 0;					//Praporec' - 4u je gramatuka - gramatukojy peredyvannja

/*******************OPUS FYNKCIJ************************/

bool	Check_Rule(char[]);		//Fynkcija perevirku vvedenogo pravula
void	FormLR();				//Fynkcija formyvannja masuvy pravo- ta livo- vuvodumuh sumvoliv
void	FormVirtWeber();		//Fynkcija formyvannja matruci Virta-Webera
int		SearchSymb(char);		//Fynkcija powyky sumvoly v masuvi M_nts - povertaje porjadkovuj nomer
void	OutPutVirtWeber();		//Fynkcija vuvody matruci Virta-Webera
void	OutPutLR();				//Fynkcija vuvody matruci pravo- ta livo- vuvodumuh sumvoliv
void	InPutNeterminalu();		//Fynkcija vvody neterminaliv
void	InPutPravula();			//Fynkcija vvody pravul gramatuku
bool	PerevirkaGramatuku();	//Fynkcija perevirku 4u vvedena gramatuka - prostogo peredyvannja
bool	PerenosZgortka(char[]);	//Fynkcija w4o perevirjaje vvedny stri4ky na nalezhnist' gramatuci
int		DivideRules();			//Fynkcija podily pravul za znakom '|' ta zanesennja jih v masuv
void	NuleAllData();			//Fynkcija anyljyvannja vsih danuh
void	NuleStrData();			//Fynkcija anyljyvannja danuh w4o stosyjyt'sja stri4ku
int		f(char, char);			//Fynkcija f - vuriwyje 4u perenosutu 4u zgortatu 4u pomulka
int		g(char, char []);		//Fynkcija g - zgortaje osnovy do neterminala za pevnum pravulom


/************************MAIN***************************/

void main()
{
	//Zadajemo rozmiru vikna konsoli ta rozmiru byfera ekrana w4ob moglu vmistutus' rezyl'tatu
	COORD BufCoord = {500, 1000};
	SetConsoleScreenBufferSize(GetStdHandle(STD_OUTPUT_HANDLE), BufCoord);
	SMALL_RECT WinRect = {0, 0, 89, 50};
    SMALL_RECT* WinSize = &WinRect;
	SetConsoleWindowInfo(GetStdHandle(STD_OUTPUT_HANDLE), true, WinSize);

	//Zagolovok
	cout<<"\t\tREALIZACIJA ALGORUTMY PERENOS-ZGORTKA\n\n"
		<<"Programa perevirjaje nalezhnist' vvedenoji stri4ku do zadanoji gramatuku.\n";
	
	//Vvid gramatuku
	InGr:InPutNeterminalu();
	InPutPravula();
	
	//Formyvannja matruc' LR ta Virta-Webera
	FormLR();
	FormVirtWeber();

	//Perevirka 4u vvedena gramatuka je gramatukojy prostogo peredyvannja
	if(!PerevirkaGramatuku()) {NuleAllData(); goto InGr;}

	//Vuvid matruc' livo-, prav- vuvodumuh sumvoliv ta matruci Virta-Webera
	OutPutLR();
	OutPutVirtWeber(); 
	
	//Vvid stri4ku
	InSt:cout<<"\nVvedit' stri4ky sumvoliv";
	vvid: cout<<"\n>";
	cin>>Str;

	//Perevirka stri4ku na najavnist' nedopystumuh sumvoliv
	for(unsigned int j = 0; j < strlen(Str); j++) if(Str[j] == '$' || Str[j] == '|' || (Str[j] >= 'A' && Str[j] <= 'Z')) 
	{cout<<"Stri4ka mistut' nedopystumi sumvolu(veluki literu ,'$' abo '|')"; goto vvid;}
	
	//Perevirka stri4ku za algorutmom "Perenos-zgortka"
	if(PerenosZgortka(Str)) cout<<"\n\nVvedena stri4ka nalezhut' danij gramatuci.";
	else cout<<"\n\nVvedena stri4ka ne nalezhut' danij gramatuci.";
	
	//W4o robutu dali?
	cout<<"\n\nVvedit' '1'<Enter> - w4ob vvestu inwy stri4ky."
		<<"\nVvedit' '2'<Enter> - w4ob vvestu inwy gramatuky."
		<<"\nVvedit' '3'<Enter> - w4ob vujtu z programu\n";
	Go: cout<<">";
	cin>>ch;
	switch(ch)
	{
		case '1':	NuleStrData(); goto InSt;				//Anyljyvatu dani w4o stosyjyt'sja stri4ku ta perejtu do vvody novoji
		case '2':	NuleAllData(); goto InGr;//Anyljyvatu vsi dani ta perejtu do vvody gramatuku
		case '3':	break;		//Vuhid z programu
		default:	goto Go;	//Jakw4o inwuj sumvol to na Go
	}
}



/*********************REALIZACIJA FYNKCIJ*********************/

bool Check_Rule(char Rule[rozmir])
{
	if(Rule[0] == '|') 
	{
		cout<<"!!!Pomulka vvody. Pravulo ne mozhe po4unatus' sumvolom '|'!!!\n"; 
		return 0;
	}

	if(Rule[strlen(Rule) - 1] == '|') 
	{
		cout<<"!!!Pomulka vvody. Pravulo ne mozhe zakin4yvatus' sumvolom '|'!!!\n"; 
		return 0;
	}

	for(unsigned int j = 0; j < strlen(Rule); j++)
	{
		if(Rule[j] == '$') 
		{																//Sumvol '$' - vukorustovyjet'sja
			cout<<"!!!Pomulka vvody. Pravulo mistut' sumvol '$'!!!\n";  //jak kincevuj marker
			return 0;
		}
		if(Rule[j] == '|')
			if(Rule[j - 1] == '|' || Rule[j + 1] == '|' ) 
			{
				cout<<"!!!Pomulka vvody. Vvedeno sumvol '|' kil'ka raziv pidrjad!!!\n";  
				return 0;
			}


		if(Rule[j] >= 'A' && Rule[j] <= 'Z')   
		{
			pr = 0;
			for(int k = 0; k < N; k++)
				if(Rule[j] == M_neterm[k]) pr = 1;						//Jakw4o vvelu nevidomuj neterminal
			if(pr != 1) {cout<<"!!!Pomulka vvody. Vvedenuj nevidomuj neterminal!!!\n"; return 0;}
		}
		else
			if(Rule[j] != '|') 
			{
				pr = 0;
				for(int k = 0;k < T; k++) 
				if(M_term[k] == Rule[j])				//Zapusyjemo v masuv terminalu
					pr = 1;
				if(pr == 0) 
					M_term[T++] = Rule[j];
			}
	}
	return 1;
}//Check_Rule


void FormLR()
{
	//krok #1  -  formyjemo L ta R
	for(int i = 0; i < N; i++)
	{
		int Li = 1, Ri = 1;
		L[i][0] = M_prav[i][0];
		R[i][0] = M_prav[i][strlen(M_prav[i]) - 1];
		for(unsigned int j = 0; j < strlen(M_prav[i]); j++)
			if (M_prav[i][j] == '|')
			{
				pr = 0;
				for(int k = 0;k < Li; k++) 
				if(L[i][k] == M_prav[i][j + 1]) 
					pr = 1;
				if(pr == 0) 
					L[i][Li++] = M_prav[i][j + 1];
				pr = 0;
				for(k = 0;k < Ri; k++) 
				if(R[i][k] == M_prav[i][j - 1]) 
					pr = 1;
				if(pr == 0) 
					R[i][Ri++] = M_prav[i][j - 1];
			}
	}

	//krok #2  -  Dopovnjyjemo L ta R sumcolamu z inwuh pravul jaki vuvodjat'sja z vzhe vkljy4enuh neterminaliv
	krok2: char Lr[rozmir][rozmir], Rr[rozmir][rozmir];
	for(i = 0; i < N; i++) 
		for(unsigned int j = 0; j < strlen(L[i]); j++) Lr[i][j] = L[i][j];
	for(i = 0; i < N; i++) 
		for(unsigned int j = 0; j < strlen(R[i]); j++) Rr[i][j] = R[i][j];
	for(i = 0; i < N; i++)
	{
		for(unsigned int j = 0; j < strlen(L[i]); j++)
			if(L[i][j] >= 'A' && L[i][j] <= 'Z')
			{
				for(int k = 0; k < N; k++)
					if(L[i][j] == M_neterm[k]) break;
				for(unsigned int m = 0; m < strlen(L[k]); m++)
				{
					pr = 0;
					for(unsigned int l = 0;l < strlen(L[i]); l++) 
					if(L[i][l] == L[k][m]) 
						pr = 1;
					if(pr == 0) 
						L[i][strlen(L[i])] = L[k][m];
				}
			}
		for(j = 0; j < strlen(R[i]); j++)
			if(R[i][j] >= 'A' && R[i][j] <= 'Z')
			{
				for(int k = 0; k < N; k++)
					if(R[i][j] == M_neterm[k]) break;
				for(unsigned int m = 0; m < strlen(R[k]); m++)
				{
					pr = 0;
					for(unsigned int l = 0;l < strlen(R[i]); l++) 
					if(R[i][l] == R[k][m]) 
						pr = 1;
					if(pr == 0) 
						R[i][strlen(R[i])] = R[k][m];
				}
			}
	}

	//krok #3  -  perevirjajemo 4u wos' zminulos' pislja kroky #2 - jakw4o ni - vuhid, jakw4o tak - to na krok #2
	pr = 0;
	for(i = 0; i < N; i++) 
		for(unsigned int j = 0; j < strlen(L[i]); j++) 
			if(L[i][j] != L[i][j]) pr = 1;
	for(i = 0; i < N; i++) 
		for(unsigned int j = 0; j < strlen(R[i]); j++) 
			if(R[i][j] != R[i][j]) pr = 1;
	if(pr == 1) goto krok2;
}//FormLR


int SearchSymb(char c)
{
	for(int k = 0; k < N; k++)
		if(c == M_neterm[k]) return k;
	for(k = 0; k < T; k++)                    //Porjadkovuj nomer sumvoly c v masuvi N+T+'$'
		if(c == M_term[k]) return k + N; 
	if(c == '$') return T + N;
	return -1;
}//SearchSymb

void FormVirtWeber()
{
	//  *=
	for(int i = 0; i < N; i++)
		for(unsigned int j = 0; j < strlen(M_prav[i]) - 1; j++)
			//if( M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(M_prav[i][j + 1])] != '>'
				//&& M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(M_prav[i][j + 1])] != '<')
				M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(M_prav[i][j + 1])]
				[strlen(M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(M_prav[i][j + 1])])] = '=';
			//else
				//gram_pered = 1;
			// *= - dlja vsih sumvoliv w4o stojat' pory4 krim '|'
	

	//  <*
	for(i = 0; i < N; i++)
	{
		//if( M_Virt_Weber[N + T][SearchSymb(M_prav[i][0])] != '='
			//&& M_Virt_Weber[N + T][SearchSymb(M_prav[i][0])] != '>')
			M_Virt_Weber[N + T][SearchSymb(M_prav[i][0])]
				[strlen(M_Virt_Weber[N + T][SearchSymb(M_prav[i][0])])] = '<';
		//else
			//gram_pered = 1;
			// <* - dlja sumvoly '$'(po4atok pravula) ta perwogo sumvola pravula


		for(unsigned int j = 0; j < strlen(M_prav[i]) - 1; j++)
			if(M_prav[i][j] != '|' && M_prav[i][j + 1] != '|')
			{
				if(M_prav[i][j + 1] >= 'A' && M_prav[i][j + 1] <= 'Z')
					for(unsigned int k = 0; k < strlen(L[SearchSymb(M_prav[i][j + 1])]); k++)
						//if( M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(L[SearchSymb(M_prav[i][j + 1])][k])] != '='
							//&& M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(L[SearchSymb(M_prav[i][j + 1])][k])] != '>')
							M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(L[SearchSymb(M_prav[i][j + 1])][k])]
							[strlen(M_Virt_Weber[SearchSymb(M_prav[i][j])][SearchSymb(L[SearchSymb(M_prav[i][j + 1])][k])])] = '<';
						//else
							//gram_pered = 1;
						// <* - dlja par aB, a nalezhut'(NuT), B nalezhut' luwe N
			}
			else
				if(M_prav[i][j] == '|')
						//if( M_Virt_Weber[N + T][SearchSymb(M_prav[i][j + 1])] != '='
							//&& M_Virt_Weber[N + T][SearchSymb(M_prav[i][j + 1])] != '>')
							M_Virt_Weber[N + T][SearchSymb(M_prav[i][j + 1])]
							[strlen(M_Virt_Weber[N + T][SearchSymb(M_prav[i][j + 1])])] = '<';
						//else
							//gram_pered = 1;
						//<* - dlja sumvoly '$'(po4atok pravula) ta perwogo sumvola pravula vrahovyjy4u '|'
	}



	//  *>
	for(i = 0; i < N; i++)
	{
		//if( M_Virt_Weber[SearchSymb(M_prav[i][strlen(M_prav[i]) - 1])][N + T] != '='
			//&& M_Virt_Weber[SearchSymb(M_prav[i][strlen(M_prav[i]) - 1])][N + T] != '<')
			M_Virt_Weber[SearchSymb(M_prav[i][strlen(M_prav[i]) - 1])][N + T]
			[strlen(M_Virt_Weber[SearchSymb(M_prav[i][strlen(M_prav[i]) - 1])][N + T])] = '>';
		//else
			//gram_pered = 1;
			// *> - dlja sumvoly '$'(kinec' pravula) ta ostann'ogo sumvola pravula


		for(unsigned int j = 0; j < strlen(M_prav[i]) - 1; j++)
			if(M_prav[i][j] != '|' && M_prav[i][j + 1] != '|')
			{
				if(M_prav[i][j] >= 'A' && M_prav[i][j] <= 'Z')
				{
					if(M_prav[i][j + 1] < 'A' || M_prav[i][j + 1] > 'Z')
						for(unsigned int k = 0; k < strlen(R[SearchSymb(M_prav[i][j])]); k++)
								//if( M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])][SearchSymb(M_prav[i][j + 1])] != '='
									//&& M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])][SearchSymb(M_prav[i][j + 1])] != '<')
									M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])][SearchSymb(M_prav[i][j + 1])]
									[strlen(M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])][SearchSymb(M_prav[i][j + 1])])]  = '>';
								//else
									//gram_pered = 1;
								// *> - dlja par Ba, a nalezhut'(NuT), B nalezhut' luwe N


					else
						for(unsigned int k = 0; k < strlen(R[SearchSymb(M_prav[i][j])]); k++)
							for(unsigned int l = 0; l < strlen(L[SearchSymb(M_prav[i][j + 1])]); l++)
								//if( M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])]
											//[SearchSymb(L[SearchSymb(M_prav[i][j + 1])][l])] != '='
									//&&M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])]
											//[SearchSymb(L[SearchSymb(M_prav[i][j + 1])][l])]		!= '<')
										M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])]
											[SearchSymb(L[SearchSymb(M_prav[i][j + 1])][l])]
										[strlen(M_Virt_Weber[SearchSymb(R[SearchSymb(M_prav[i][j])][k])]
											[SearchSymb(L[SearchSymb(M_prav[i][j + 1])][l])])]          = '>';
								//else
									//gram_pered = 1;
								// *> - dlja par BA, a nalezhut'luwe N, B nalezhut' luwe N	
				}
			}
			else
				if(M_prav[i][j] == '|')
					//if( M_Virt_Weber[SearchSymb(M_prav[i][j - 1])][N + T] != '='
						//&&M_Virt_Weber[SearchSymb(M_prav[i][j - 1])][N + T] != '<')
						M_Virt_Weber[SearchSymb(M_prav[i][j - 1])][N + T]
						[strlen(M_Virt_Weber[SearchSymb(M_prav[i][j - 1])][N + T])]  = '>';
					//else 
						//gram_pered = 1;
					//*> - dlja sumvoly '$'(kinec' pravula) ta ostann'ogo sumvola pravula vrahovyjy4u '|'


					
	}
}//Form_Virt_Weber


void OutPutVirtWeber()
{
	for(int i = 0; i < N; i++) M_nts[i] = M_neterm[i];
	for(i = 0; i < T; i++) M_nts[N + i] = M_term[i];
	M_nts[N + T] = '$';
	cout<<"\n\n\t   TABLUCJA VIDNOWEN' PEREDYVANNJA";
	cout<<"\n\n\t"<<(char)(218);
	for(i = 0; i < N + T + 1; i++)
		cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(194);
	cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(191)<<"\n\t"<<(char)(179)<<"   \t"<<(char)(179);

	for(i = 0; i < N + T + 1; i++)
		cout<<" "<<M_nts[i]<<"  \t"<<(char)(179);
	cout<<"\n";

	cout<<"\t"<<(char)(195);
	for(i = 0; i < N + T + 1; i++)
		cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(197);			
	cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(180)<<"\n\t";		
																			
	for(i = 0; i < N + T + 1; i++)											
	{
		cout<<(char)(179)<<"  "<<M_nts[i]<<"  \t"<<(char)(179);			// (char)(***) - dlja
		for(int j = 0; j < N + T + 1; j++)							// vuvody sumvoliv
			cout<<" "<<M_Virt_Weber[i][j]<<"  \t"<<(char)(179);		// granuc' tabluci
		if(i == N + T) break;
		cout<<"\n\t"<<(char)(195);
		for(int k = 0; k < N + T + 1; k++)
			cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(197);
		cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(180)<<"\n\t";
	}
	cout<<"\n\t"<<(char)(192);
	for(i = 0; i < N + T + 1; i++)
		cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(193);
	cout<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(196)<<(char)(217)<<"\n";
}//OutPutVirtWeber


void OutPutLR()
{
	cout<<"\n\n\t   TABLUCJA PRAVO- TA LIVO- VUVODUMUH SUMVOLIV:\n\n";
	cout<<"\t"<<(char)(201);
	for(int i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(203);
	for(i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(203);
	for(i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(187)<<"\n";
	cout<<"\t"<<(char)(186)<<"\t\t"<<(char)(186)<<"\tL(G)\t"<<(char)(186)<<"\tR(G)\t"<<(char)(186)<<"\n ";
	for(i = 0; i < N; i++)
	{
		cout<<"\t"<<(char)(204);for(int j = 0; j < 15; j++) cout<<(char)(205); cout<<(char)(206);
		for(j = 0; j < 15; j++) cout<<(char)(205); cout<<(char)(206);
		for(j = 0; j < 15; j++) cout<<(char)(205); cout<<(char)(185);
		cout<<"\n\t"<<(char)(186)<<"\t"<<M_neterm[i]<<"\t"<<(char)(186)<<"\t"
			<<L[i]<<"\t"<<(char)(186)<<"\t"<<R[i]<<"\t"<<(char)(186)<<"\n ";
	}
	cout<<"\t"<<(char)(200);
	for(i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(202);
	for(i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(202);
	for(i = 0; i < 15; i++) cout<<(char)(205);cout<<(char)(188)<<"\n";
}//OutPutLR


void InPutNeterminalu()
{
	cout<<"\nVvedit' neterminal'ni sumvolu gramatuku G(N, T, P, S) (luwe veluki literu) - \n"
		<<"dlja zakin4ennja vvody vvedit' krapky>\n";
	while(1)
	{
		gocin: cin>>ch;
		if(ch == '.') break;
		if(ch < 'A' || ch > 'Z') {cout<<"!!!Pomulka vvody(luwe veluki latuns'ki literu)!!!\n"; goto gocin;}
		pr = 0;
		for(int i = 0; i < N; i++) 
			if(M_neterm[i] == ch) 
				pr = 1;				//Jakw4o vvedenuj neterminal vzhe je v gramatuci - to prosto ignoryvatu cej vvid
		if(pr == 0) 
			M_neterm[N++] = ch;
	}
	if (N == 0) goto gocin;
}//InPutNeterminalu


void InPutPravula()
{
	cout<<"\n\nVvedit' pravula gramatuku(rozdiljyva4 - sumvol '|')\n"
		<<"vukorustovyjte byd'-jaki sumvolu okrim sumvoly '$'>\n";
	for(int i = 0; i < N; i++)
	{
		goRule:cout<<M_neterm[i]<<"->";
		cin>>M_prav[i];
		if(!Check_Rule(M_prav[i])) goto goRule;		//Jakw4o vvedeno nepravul'ne pravulo - to perejtu vvid w4e raz
	}
}//InPutPravula


bool PerevirkaGramatuku()
{
	int n = DivideRules();
	pr = 0;
	if(gram_pered) pr = 1;
	for(int i = 0; i < n - 1; i++)
	{
		for(int j = i + 1; j < n; j++)				//Perevirjajemo 4u je v gramatuci odnakovi pravula
			if(!strcmp(DividedRules[i], DividedRules[j])) pr = 1;
	}
	if(pr == 1)
		{
			cout<<"\n!!!Vvedena gramatuka ne je gramatukojy prostogo peredyvannja!!!";
			return 0;
		}
	return 1;
}//PerevirkaGramatuku


bool PerenosZgortka(char Str[rozmir])
{
	Magazun[0] = '$';				//Zapusyjemo v magazun '$' - jak perwuj sumvol
	Str[strlen(Str)] = '$';			//Zapusyjemo v stri4ky '$' - jak ostannij sumvol
	int m = 0;
	unsigned int i = 0;
	cout<<"perenos  ";
	while(i < strlen(Str))
	{
		cout<<"("<<Magazun<<", ";
		for(unsigned int n = i; n < strlen(Str); n++)	//Formyjemo vuvid
			cout<<Str[n];								//poslidovnosti dij algorutmy 
		cout<<", ";										//($S1...Sm, a1...an$, p1...pr)
		//if(PrRozbir[0] == 0) cout<<"0";					
		//else
		//for(int l = 0; l < m; l++)
		//	cout<<PrRozbir[l];
		cout<<gg<<");\n";
		gg = 0;
		
		// Perenos
		if(f(Magazun[strlen(Magazun) - 1], Str[i]) == 1)
		{
			Magazun[strlen(Magazun)] = Str[i];
			i++;
			cout<<"perenos  ";
			continue;
		}

		//Zgortka
		if(f(Magazun[strlen(Magazun) - 1], Str[i]) == 2)
		{
			memset(Zgortka, NULL, sizeof(Zgortka));        //Zanyljyjemo masuv Zgortka
			for(int j = strlen(Magazun) - 1; j > 0; j--)				//Wykajemo livuj kinec' osnovu ('<*')
				if(M_Virt_Weber[SearchSymb(Magazun[j - 1])][SearchSymb(Magazun[j])][0] == '<') break;

			if(M_Virt_Weber[SearchSymb(Magazun[j - 1])][SearchSymb(Magazun[j])][0] == '<') //Jakw4o znajwlu osnovy
			{
				for(unsigned int k = j; k < strlen(Magazun); k++)
					Zgortka[k - j] = Magazun[k];					//Kopijyjemo osnovy v masuv Zgortka 
				
				if(g(Magazun[j - 1], Zgortka) == -1) {cout<<"pomulka  ";return 0;}//Peredajemo na zgortannja
				else
				{
					//PrRozbir[m++] = g(Magazun[j - 1], Zgortka) + 1;		//Jakwo4 vdalos' zgornytu
					gg = g(Magazun[j - 1], Zgortka) + 1;
					Magazun[j] = M_neterm[g(Magazun[j - 1], Zgortka)];	//peretvorjyjemo osnovy v neterminal
					for(unsigned int p = j + 1; p < rozmir; p++) Magazun[p] = NULL;								
				}
			}
			else return 0;
			cout<<"zgortka  ";
			continue;
		}

		//Dopysk
		if(f(Magazun[strlen(Magazun) - 1], Str[i]) == 3)
		{
			if(Magazun[strlen(Magazun) - 2] == '$') 
			{
				cout<<"dopysk  ";
				return 1;
			}
			else
				return 0;
		}

		//Pomulka
		if(f(Magazun[strlen(Magazun) - 1], Str[i]) == 0)
		{
			cout<<"pomulka  ";
			return 0;
		}
	}
	return 0;
}//PerenosZgortka

int	f(char c1, char c2)
{
	//0 - pomulka
	//1 - perenos
	//2 - zgortka
	//3 - dopysk
	if(c1 == M_neterm[0] && c2 == '$') return 3;	//Perevirka 4u ($S, $) - maje vuw4uj priorutet
	
	if(	M_Virt_Weber[SearchSymb(c1)][SearchSymb(c2)][0] == '=' || 
		M_Virt_Weber[SearchSymb(c1)][SearchSymb(c2)][0] == '<') return 1;
	
	if(	M_Virt_Weber[SearchSymb(c1)][SearchSymb(c2)][0] == '>') return 2;
	return 0;
}//f

int	g(char c, char S[rozmir])		//Sumvol c - zliva vid zgortku
{
	//-1 - pomulka
	//i - nomer neterminala
	if(M_Virt_Weber[SearchSymb(c)][SearchSymb(S[0])][0] == '<')	
	{
		pr = 0;
		if(strlen(S) > 1)									//Jakw4o y zgortci bil'we odnogo sumvoly
			for(unsigned int j = 0; j < strlen(S) - 1; j++)	//to perevirjajemo 4u vukonyjet'sja *= mizh sumvolamu
				if(M_Virt_Weber[SearchSymb(S[j])][SearchSymb(S[j + 1])][0] != '=') return -1;
		
		for(int i = 0; i < N; i++)
		{
			memset(DivRule, NULL, sizeof(DivRule));
			int l = 0; 
			int k = 0;
			for(unsigned int j = 0; j < strlen(M_prav[i]); j++)
			{
				if(M_prav[i][j] == '|') {l = 0; k++;}
				else 
				{
					DivRule[k][l++] = M_prav[i][j];			//Dilumo po4ergovo vsi pravula w4ob vuzna4utu
					if(j == strlen(M_prav[i]) - 1) k++;		//v jakuj neterminal treba peretvorutu zgortky
				}
			}
			for(int m = 0; m < k; m++)
				if(!strcmp(DivRule[m], Zgortka))	//Porivnjyjemo pravulo ta zgortky
					return i;						//Jakw4o vonu rivni to povernytu nomer pravula tobto neterminaly
		}
	}
	return -1;
}//g


int DivideRules()
{
	memset(DividedRules, NULL, sizeof(DividedRules));
	int k = 0;
	for(int i = 0; i < N; i++)
	{
		int l = 0;
		for(unsigned int j = 0; j < strlen(M_prav[i]); j++)
		{
			if(M_prav[i][j] == '|') 
			{
				l = 0; 
				k++;
			}												//Jakw4o znajwlu '|' - podil
			else 
			{
				DividedRules[k][l++] = M_prav[i][j];
				if(j == strlen(M_prav[i]) - 1) k++;
			}
		}
	}
	return k;
}//DividedRules


void NuleAllData()
{
	NuleStrData();
	N = 0;
	T = 0;
	pr = 0;
	ch = 0;
	gram_pered = 0;
	memset(M_prav, NULL, sizeof(M_prav));            //Zanyljyjemo kozhen masuv
	memset(M_neterm, NULL, sizeof(M_neterm));
	memset(M_term, NULL, sizeof(M_term));
	memset(M_nts, NULL, sizeof(M_nts));
	memset(DividedRules, NULL, sizeof(DividedRules));
	memset(L, NULL, sizeof(L));
	memset(R, NULL, sizeof(R));
	memset(M_Virt_Weber, NULL, sizeof(M_Virt_Weber));
}//NuleAllData


void NuleStrData()
{
	memset(DivRule, NULL, sizeof(DivRule));			//Zanyljyjemo luwe ti masuvu
	memset(Magazun, NULL, sizeof(Magazun));			//jaki stosyjyt'sja
	memset(PrRozbir, NULL, sizeof(PrRozbir));		//vvody ta robotu z stri4kojy
	memset(Zgortka, NULL, sizeof(Zgortka));
	memset(Str, NULL, sizeof(Str));
}//NuleStrData