# include <iostream.h>
# include <fstream.h>
# include <ctype.h>
# include <string.h>
# include <conio.h>
# include <stdio.h>

struct child
{
    char st[5];
    child *lnk;
};

struct NTS
{
    char symb;
        int nul;
    child *part;
    NTS *nxt;
    char fst[10];
    char flo[10];
};

NTS *head;
ifstream gram;
char str[5];
int i, isnul;

void main()
{
        void pro_fst(NTS *);
        char * pro_flo(char);
        void parse_proc();
    char str1[5];
    char str2[5];

    NTS  *tmp;
    head = new NTS;
    head->nxt=NULL;
tmp = head;

    gram.open("c:\\gram3.txt",ios::in);
child *def;

    gram >> str1;
    while(!gram.eof())
         {
        gram >> str2;
 
        if(!strcmp(str2,"::="))
        {
            tmp->nxt = new NTS;
                    tmp->nxt->symb = str1[0];
                        tmp->nxt->nul = 0;
                    strcpy(tmp->nxt->fst,"\0");
                        strcpy(tmp->nxt->flo,"\0");
            tmp->nxt->part = new child;
            def = tmp->nxt->part;
            while(1)
            {
                gram >> str1;
                        if(!strcmp(str1,"#"))
                                    tmp->nxt->nul = 1;
                strcpy(def->st,str1);
                if(gram.eof())
                    break;
                         
gram >> str2;
                if(str2[0] == '|')
                {
                    def->lnk = new child;
                    def = def->lnk;
                }
                elsebreak;
            }
            def->lnk = NULL;
            tmp = tmp->nxt;
            tmp->nxt = NULL;
            strcpy(str1,str2);
        }
    }
gram.close();
NTS *hd = head->nxt; 
while(hd != NULL)
    {
            i= isnul = 0 ;
        strcpy(str,"\0");
         pro_fst(hd);
        hd = hd->nxt;
     }
hd = head->nxt;
strcpy(hd->flo,"$");
while(hd != NULL)
    {    strcat(hd->flo,pro_flo(hd->symb));
    hd = hd->nxt;
        }
parse_proc();
getch();
delete [] head;
}
void pro_fst (NTS *nod)
{
child * tp_ch;
NTS * tm_nt;

int j=0;
    tp_ch = nod->part;
start:
    if (j>=strlen(tp_ch->st))
    {
        str[i++] = '#';
        goto end;
    }
    if(isupper(tp_ch->st[j]))           
    {
        tm_nt = nod->nxt;
        while(tm_nt->symb != tp_ch->st[j])
            tm_nt = tm_nt->nxt;
        pro_fst(tm_nt);
    if(isnul == 1)
{
            isnul = 0;
            str[--i] = '\0';
                    j = j+1;
            goto start;
                }
               }
else
        str[i++] = tp_ch->st[0];
    if(tp_ch->st[0] == '#')
        isnul = 1;
end:
    if(tp_ch->lnk != NULL)
    {
    tp_ch = tp_ch->lnk;
        goto start;
    }
           str[i] = '\0';
strcpy(nod->fst,str);
}

char * pro_flo(char ch_nt)
{
NTS *list;
child *tmp;
list = head->nxt;
int i,k=0,flag;
char *str_flo;
str_flo = newchar[10];
str_flo[0] = '\0';
 
while (list != NULL)
{
        tmp = list->part;
again:
    for (i=0;i<strlen(tmp->st);i++)
        {
         if(tmp->st[i]== ch_nt)
             {
                        flag = 1;
                      char nxt_ch =tmp->st[i+1];
               if(isupper(nxt_ch))
                {
                     flag = 0;
                   NTS *node = head->nxt;
                         while(node != NULL)
                                {
                                   if(nxt_ch == node->symb)
                                    {
                       for(int x=0;x<strlen(node->fst);x++) 
                            {
                                      if(node->fst[x] == '#')
                                             flag = 1;
                                        else
                                       str_flo[k++] = node->fst[x];
                                                }
                                     break;
                                   }
                   node = node->nxt;
                           }
                        str_flo[k] = '\0';
                            }           
             elseif (isprint(nxt_ch))
                            {
           str_flo[k++] = nxt_ch;
                str_flo[k] = '\0';
                    flag = 0;
                            }                
if(flag == 1)
                            strcat(str_flo,list->flo);
                break;
                   }
            }
if (tmp->lnk != NULL)
            {
                tmp = tmp->lnk;
            goto again;
            }
else
                list = list->nxt;
}
return (str_flo);
}
int ssm=0, csm=0;
char final[30] = "\0";

void parse_proc()
{
int Nt_fst(NTS *,char );
int Nt_flo(NTS *,char );
void insert(char *);

charstring[15];
cout << "Enter A String: ";
cin >> string;
strcat(string,"$");

final[csm] = head->nxt->symb;
NTS *tmp_nt;
child *nt_part;

while (1)
{
tmp_nt = head->nxt;

             if(!isupper(final[csm]))
                 { 
if(final[csm] != string[ssm])
                                goto error;
         csm++; ssm++;
                }

while(tmp_nt->symb!=final[csm] && tmp_nt != NULL)
                       tmp_nt = tmp_nt->nxt;

          if(tmp_nt == NULL)
                     goto error;
          nt_part = tmp_nt->part;

         if(Nt_fst(tmp_nt,string[ssm]))
            {
                    if(!isupper(nt_part->st[0]))
                           {
                while(nt_part->st[0] != string[ssm])
                       nt_part = nt_part->lnk;
                           ssm++;
                           }
                          insert(nt_part->st);
          }
              elseif(Nt_flo(tmp_nt,string[ssm]))
            {
                       for(int a=csm;a<strlen(final);a++)
                                final[a] = final[a+1];
          }
         
 
else
            {
error:    
        cout << "ERROR";
            break;
}    
 if(csm == strlen(final))
       {
               cout << " Entered Sring Is Valid ";
               break;
      }
}
}

void insert(char *str2)
{
char next[20]= "\0";
int x, y=0;
for (x=csm+1 ;x<strlen(final);x++,y++)
        next[y] = final[x];

for (x=csm,y=0;y<strlen(str2);x++,y++)
        final[x] = str2[y];

final[x] = '\0';
strcat(final,next);

if(!isupper(str2[0]))
        csm++;
}

int Nt_fst(NTS *nod,char a)
{
int ret=0;
for (int x=0;x<strlen(nod->fst);x++)
    {
            if(a == nod->fst[x])
                ret = 1;
        }
return(ret);
}

int Nt_flo(NTS *nod,char a)
{
int ret=0;
for (int x=0;x<strlen(nod->flo);x++)
    {
            if(a == nod->flo[x] && nod->nul == 1)
                ret = 1;
        }
return(ret);
}
 

/*****************
  Input Files:
******************

gram1.txt

E ::= TX
X ::= +TX | #
T ::= VY
Y ::= *VY | #
V ::= i | (E)


***************
   Output:
***************

E       TX
i(  |  $)  |
X       +TX     #
+#  |  $)  |
T       VY
i(  |  ++$)  |
Y       *VY     #
*#  |  ++$)  |
V       i       (E)
i(  |  **++$)  | 


Enter A String: i+i*i

            E                   i           E=> TX
            TX                  i           T=> VY
            VYX                 i               V=> i
            iYX                 +           Y=> #
            iX                  +           X=> +TX
            i+TX            i           T=> VY
            i+VYX           i           V=> i
            i+iYX               *           Y=> *VY
            i+i*VYX             i           V=> i
            i+i*iYX             $           Y=> #
            i+i*iX              $           X=> #
            i+i*I

Entered Sring Is Valid

***************/