/*
  To construct FIRST and FOLLOW set
  This part plays a key role up-bottom anlysis. 
  And it is the most difficult part to code.
    start on 6.5
   plan finish on 6.7  
                       by Math Frog 
  */
#include "global.h"
// import global variable 

elem symbol[MAXSIZE];

list<string> coProduction[MAXLINE];

list<string> cofirst; // to hold the tempory first set
                      // for the production list X1X2...Xn
const int CNT = 2;// scan times
const int _CNT = 3;
int colineno = 0; // lineno of the new grammer

void getName()
{
   int i = 0;
   list<string>::iterator iter = VN.begin();
   while(iter != VN.end())
   symbol[i++].name = *iter++; // get name of each symbol
}

/*
** build first set for each non-terminals ** 
   finished on 6.6    Math Frog
*/
void buildFirst()
{
string hold1,hold2,hold3;
list<string> hold; // hold for getting separete production
int save1,save2; // save position  
int cnt = 0;
int mark;
bool flag; 
list<string>::iterator iter,tmp;
getName();
////////////////// first scan ////////////////////////
///////// using rule one and two ////////////////////
for(int i = 0;i < lineno;i++){
   iter = production[i].begin();
  // for tempory search
   hold1 = *iter; // it's the non-terminal
   iter++;
   iter++; // move backward for two step to get iter point to the 
          //  right of the produciton
   tmp = iter; // use tmp now
   hold2 = *tmp; // hold for seaching
while(true){
    if(isIn(hold2,VT) || hold2 == ee){
       for(int k = 0;k < VN.size();k++)
          if(symbol[k].name == hold1 && !isIn(hold2,symbol[k].first))
             symbol[k].first.push_back(hold2); 
        }
      while(tmp != production[i].end()){
          if(*tmp == "|"){
             tmp++;
             hold2 = *tmp;
             break;
           }
           tmp++;
        }
        if(tmp == production[i].end())
         break;
    } 
  
} 
      // second scan for the production A->X1..Xk
   /////////// second scan ///////////////////////////
  ///////// use the third rule ///////////////////////
  
while(cnt < CNT){ // for at most two times can get the first set
for(int line = 0;line < colineno;line++) {
   mark = 0;
    // in fact , this pass can be added to the first scan 
   hold1 = coProduction[line].front(); // save for searching
    iter = coProduction[line].begin();
   iter++;
   iter++; // move backward to the first of the right
   flag = true; // set flag true
while(flag == true && iter != coProduction[line].end()){
       hold2 = *iter;
   if((isIn(hold2,VT) && mark == 0 ) || hold2 == ee) // if the current symbol is a terminal 
       {mark++;  break ; }
       // add it directly
      // just ingore it
   else{ // the current symbol is a non-terminal
       for(int _i = 0;_i < VN.size();_i++) 
         if(hold1 == symbol[_i].name)
           { save1 = _i;   break; }
        for(int _j = 0;_j < VN.size();_j++) 
          if(hold2 == symbol[_j].name)
             {save2 = _j; break;}
     if(isIn(hold2,VT) && !isIn(hold2,symbol[save1].first) & hold2 != ee) 
        symbol[save1].first.push_back(hold2);
      // after found the position ,let us copy it
        else{ 
         tmp = symbol[save2].first.begin();
        while(tmp != symbol[save2].first.end()){
          hold3 = *tmp;
          if(!isIn(hold3,symbol[save1].first) && hold3 != ee)
           symbol[save1].first.push_back(hold3);
           tmp++;
        }  
       }
      }   
        if(!isIn(ee,symbol[save2].first)) 
          flag = false; // set flag to false to end the loop
        iter++; // move backward
        if(flag == true && !isIn(ee,symbol[save1].first)) 
        symbol[save1].first.push_back(ee); // add e to the first
    }  
   }
   cnt++;
  }
}
//////////////////////////////////////////////
/////////// BUild FOLLOW Set finished on 6.8
////                ** Math Frog  ** /////////
/////////////////////////////////////////////
void buildFollow()
{
   list<string>::iterator iter,it,copy;
   int save,save1,save2;
   int cnt = 0;
   symbol[0].follow.push_back("$");
  while(cnt < _CNT){
    for(int line = 0;line < colineno;line++){
        iter = coProduction[line].begin();
        for(int k = 0;k < VN.size();k++)
         if(*iter == symbol[k].name)
           {save = k;break;} 
         iter++;
         iter++;
while(iter != coProduction[line].end()){
     if(isIn(*iter,VN)){
           //// compute Xi+1Xi+2 ..Xn  ////////////////
       for(int i = 0;i < VN.size();i++)
            if(symbol[i].name == *iter)
              {save1 = i;break;}
   if(iter == --(coProduction[line].end()))
        {cofirst.push_back(ee); }
        else{
           it = iter;
            it++;
         while(it != coProduction[line].end()){
             if(isIn(*it,VT))
               {cofirst.push_back(*it);break;}
            else{
             for(int j = 0;j < VN.size();j++)
                   if(symbol[j].name == *it)
                     {save2 = j;break;}     
             for(copy = symbol[save2].first.begin();copy != symbol[save2].first.end();copy++)
                     if(!isIn(*copy,cofirst))
                        cofirst.push_back(*copy); 
             }
           if(!isIn(ee,symbol[save2].first)) break;
              it++;
             }
          }
         for(copy = cofirst.begin();copy != cofirst.end();copy++)
               if(!isIn(*copy,symbol[save1].follow) && *copy != ee)
                 symbol[save1].follow.push_back(*copy); 
        if(isIn(ee,cofirst)){
         for(copy = symbol[save].follow.begin();copy != symbol[save].follow.end();copy++)
           if(!isIn(*copy,symbol[save1].follow) && *copy != ee)
             symbol[save1].follow.push_back(*copy); 
           }   
         }  
        cofirst.erase(cofirst.begin(),cofirst.end()); 
          iter++;
         }
      } // the loop for(;;)
     cnt++;
   } // scan times
}
void printFirst()
{
cout << "***********************************" << endl;
  cout << "** The FIRST sets are as follow **"<< endl;
  cout << "***********************************" << endl;
  for(int i_ = 0;i_ < VN.size();i_++){
  list<string>::iterator iter = symbol[i_].first.begin();
    cout << "FIRST" << "( " << symbol[i_].name << " ) = " << "{ ";
    while(iter != symbol[i_].first.end()){
       cout << *iter;
     if(iter != --symbol[i_].first.end())
       cout << ",";  // the output formation use my precious 3 minutes  :(
       iter++;
       }
       cout << " }" << endl;
   }
    cout << "***********************************" << endl;
    cout << endl;
}

  void printFollow()
{
cout << "***********************************" << endl;
cout << "** The FOLLOW sets are as follow **" << endl;
cout << "***********************************" << endl;
   for(int i = 0;i  < VN.size();i++){
   list<string>::iterator iter = symbol[i].follow.begin();
   cout << "Follow" << "( " << symbol[i].name << " ) = " << "{ ";
   while(iter != symbol[i].follow.end()){
    cout << *iter;
    if(iter != --symbol[i].follow.end())
     cout << ",";
     iter++;
   }
   cout << " }" << endl;
}
  cout << endl;
}