Skip to content

Instantly share code, notes, and snippets.

@thatwist

thatwist/wirth-weber-prcedence-relationship.c

Last active March 30, 2018 12:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save thatwist/f170e8607958fcfa59786c24eea0389d to your computer and use it in GitHub Desktop.
Save thatwist/f170e8607958fcfa59786c24eea0389d to your computer and use it in GitHub Desktop.
Download ZIP
Checks Wirth–Weber precedence relationship. This is an old piece of code I wrote in university - this is scary but it works.
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment