#include <stdio.h>
#include <iostream.h>
 
struct buf
{
char* x;
buf() { x = 0;}
~buf() { del(); }
int get_len() 
{ 
    if (x == 0) return 0; 
    int i; 
    for(i=0; x[i]!='\0'; i++); 
    return i;
    }
    
void print() 
{ 
     if (x == 0) return; 
     int i; 
     for(i=0;x[i]!='\0';i++)
      printf("%c", x[i]); 
      }
      
void add(char a) 
{ 
     if (x == 0)
      { 
           x = new char[2]; 
           x[0] = a;
            x[1] = '\0'; 
            } 
            else 
            { 
                 int sz = get_len(); 
                 char* temp = new char[sz+1]; 
                 int i; 
                 for(i=0;i<sz;i++) 
                 temp[i] = x[i];  
                 temp[i] = a; 
                 temp[i+1] = '\0';  
                 x = temp; 
                 } 
                 }
                 
void del() 
{ 
     if (x == 0) return; 
     else delete[]x; 
     x = 0;
     }
};
 
struct nt
{
char* a;
struct nt* next;
struct nt* prev;
 
nt() 
{ 
     a = 0; next = 0; prev = 0; 
     }
     
void add(char* a1) 
{  
     if (a1 == 0) return; 
     int i; 
     for(i=0; a1[i]!='\0'; i++); 
     a = new char [i+1]; 
     int j; 
     for(j=0; j< i; j++) 
     a[j] = a1[j]; 
     a[j] = '\0'; 
     }
     
void add_next(char* a1) 
{ 
     struct nt* k = this; 
     while (k->next != 0) k = k->next;
      k->next = new struct nt(); 
      k->next->add(a1); 
      k->next->prev = k; 
      }
      
void print()  
{ 
     struct nt* k = this; 
     while (k->next != 0) 
     { 
           printf("%s\n", k->a); 
           k = k->next; 
           } 
           printf("%s\n", k->a); 
            printf("\n"); 
            }
};
 
struct t
{
char* a;
struct t* next;
struct t* prev;
 
t() 
{ 
    a = 0; next = 0; prev = 0; 
    }
    
void add(char* a1) 
{  
     if (a1 == 0) return; 
     int i; 
     for(i=0; a1[i]!='\0'; i++); 
     a = new char [i+1]; 
     int j; 
     for(j=0; j< i; j++) 
     a[j] = a1[j]; 
     a[j] = '\0'; 
     }
     
void add_next(char* a1) 
{ 
     struct t* k = this; 
     while (k->next != 0) k = k->next; 
     k->next = new struct t(); 
     k->next->add(a1); 
     k->next->prev = k;;
     }
void print()  
{ 
     struct t* k = this; 
     while (k->next != 0) 
     { 
           printf("%s\n", k->a); 
           k = k->next; 
           } 
           printf("%s\n", k->a); 
            printf("\n"); }
};
 
struct rule
{
char* a;
char* b;
struct rule* next;
struct rule* prev;
 
rule() 
{ 
       a = 0; b = 0; next = 0; prev = 0;
       }
       
void add(char* a1, char* b1) 
{  
if (a1 == 0 || b1 == 0) return; 
int i; 
for(i=0; a1[i]!='\0'; i++); 
a = new char [i+1]; 
int j; 
for(j=0; j< i; j++) 
a[j] = a1[j]; 
a[j] = '\0'; 
for(i=0; b1[i]!='\0'; i++); 
b = new char [i+1]; 
for(j=0; j< i; j++) 
b[j] = b1[j]; 
b[j] = '\0'; 
}
 
void add_next(char* a1, char* b1) 
{ 
     struct rule* k = this; 
     while (k->next != 0) k = k->next; 
     k->next = new struct rule(); 
     k->next->add(a1, b1); 
     k->next->prev = k;;
     }
 
void print()  
{ 
     struct rule* k = this; 
     while (k->next != 0) 
     { 
           printf("%s %s\n", k->a, k->b); 
           k = k->next; 
           } 
           printf("%s %s\n", k->a, k->b); 
           printf("\n"); }
};
 
struct table
{
struct rule* a;
 
table() { a = 0;}
};
 
struct st
{
char* a;
struct st* next;
struct st* prev;
 
st() 
{ 
     a = 0; next = 0; prev = 0; 
     }
     
void add(char* a1) 
{  
     if (a1 == 0) return; 
     int i; 
     for(i=0; a1[i]!='\0'; i++); 
     a = new char [i+1]; 
     int j; for(j=0; j< i; j++) 
     a[j] = a1[j]; 
     a[j] = '\0'; 
     }
     
void add_next(char* a1) 
{ 
     struct st* k = this; 
     while (k->next != 0) k = k->next; 
     k->next = new struct st(); 
     k->next->add(a1); 
     k->next->prev = k;
     }
 
void print()  
{ 
     struct st* k = this; 
     if (k == 0) return; 
     while (k->next != 0) 
     { 
           printf("%s\n", k->a); 
           k = k->next; 
           } 
           if (a!=0) printf("%s\n", k->a);  
           printf("\n"); }
};
 
struct grammar
{
struct nt* lnt;
struct t* lt;
struct table* ltable;
struct st* lst;
struct rule* rl;
 
grammar() 
{ 
          lnt = 0; lt = 0; ltable = 0; lst = 0; rl = 0; 
          }
 
void print() 
{ 
     lnt->print(); 
     lt->print();
      lst->print();
       rl->print(); 
       }
 
void parse_a(char* a)
{
struct buf bf;
int i;
int state = 0;
for (i=0, state = 0; a[i]!='\0'; i++)
{
switch(a[i])
{
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z': case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z': 
bf.add(a[i]); 
printf("a bf: "); 
bf.print(); 
printf("\n"); 
break;
case ';':  
switch(state) 
{ 
case 0: if (lnt == 0) 
{  
     lnt = new nt(); 
     lnt->add(bf.x); 
     } 
     else 
     { 
          lnt->add_next(bf.x);
          } 
          bf.del(); 
          break; 
case 1: 
     if (lt == 0) 
     {
            lt = new t(); 
            lt->add(bf.x); 
            } 
            else 
            { 
                 lt->add_next(bf.x);
                 } 
                 bf.del(); 
                 break; 
case 2: 
     if (ltable == 0) 
     {
                ltable = new table(); 
                } 
                bf.del();  
                break; 
case 3: 
     if (lst == 0) 
     {
             lst = new st(); 
             lst->add(bf.x); 
             } 
             else 
             { 
                  lst->add_next(bf.x);
                  } 
                  bf.del();  
                  break; 
default:
         break; 
         } 
state++; 
break;
case ',': 
switch(state) 
{ 
case 0: 
     if (lnt == 0) 
     {  
             lnt = new nt(); 
             lnt->add(bf.x); 
             } 
             else 
             { 
                  lnt->add_next(bf.x);
                  } 
                  bf.del();
                   break; 
case 1: 
     if (lt == 0) 
     {
            lt = new t(); 
            lt->add(bf.x); 
            } 
            else 
            { 
                 lt->add_next(bf.x);
                 }
                  bf.del(); 
                   break; 
case 2: 
     if (ltable == 0) 
     {
                ltable = new table();
                 } 
                 bf.del(); 
                  break; 
case 3: 
     if (lst == 0) 
     {
             lst = new st(); 
             lst->add(bf.x); 
             } 
             else 
             { 
                  lst->add_next(bf.x);
                  } 
                  bf.del();  
                  break; 
default: break; } break;
case ' ': break;
default: break;
}
}
}
 
void parse_b(char* b)
{ 
struct buf bf;
struct buf bf2;
int i;
int state = 0;
for (i=0, state = 0; b[i]!='\0'; i++)
{
switch(b[i])
{
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': case 'G': case 'H': case 'I': case 'J': case 'K': case 'L': case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R': case 'S': case 'T': case 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z': case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'g': case 'h': case 'i': case 'j': case 'k': case 'l': case 'm': case 'n': case 'o': case 'p': case 'q': case 'r': case 's': case 't': case 'u': case 'v': case 'w': case 'x': case 'y': case 'z': 
switch (state)
{
case 0: bf.add(b[i]); printf("bf: "); bf.print(); printf("\n"); break;
case 2: bf2.add(b[i]); printf("bf2: ");  bf2.print(); printf("\n"); break;
default: break;
}
break;
case ';':  if (rl == 0) {  rl = new rule(); rl->add(bf.x, bf2.x); } else { rl->add_next(bf.x, bf2.x);} bf.del(); bf2.del(); state = 0; break;
case ',':  if (rl == 0) {  rl = new rule(); rl->add(bf.x, bf2.x); } else { rl->add_next(bf.x, bf2.x);} bf.del(); bf2.del(); state = 0;  break; 
case ' ': break;
case '-': switch (state) { case 0: state = 1; break; default: break; } break;
case '>': switch (state) { case 1: state = 2; break; default: break; } break;
case '|':  if (rl == 0) {  rl = new rule(); rl->add(bf.x, bf2.x); } else { rl->add_next(bf.x, bf2.x);} bf2.del();  break;
default: break;
}
}
}
void parse(char* a, char* b){ parse_a(a); parse_b(b);}
 
};
 
struct automata
{
struct t* alpha;
struct nt* q;
struct st* st;
 
automata() { alpha = 0; q = 0; st = 0;}
};
 
int main()
{
///char* gram = "S,C,D;0,1;P;S;\0";
///char* p = "S->1C|0D;C->0D|0S; D->1C|1S|0;\0";
char* gram = "S,A,B,C;a, b, c;P;S;\0";
char* p = "S->aA|bB|aC;A->bA|bB|c; B->aA|cC|b; C->bB|bC|a;\0";
 
struct grammar x;
x.parse(gram, p);
x.print();
 
struct automata x1;
x1.alpha = x.lt;
x1.q = x.lnt;
x1.st =  x.lst;
 
system("pause");
return 0;
}