int main()
{  
    Init();
    cout << "文法G[S']:" << endl;
    node *temp = G[0].Getdata();
    closure(temp);
    I[0].show();
    GO(I[0],"a");
    GO(I[0],"b");
    GO(I[0],"A");
    GO(I[1],"A");  
    for(int i = 0; i < n4; i++)
    {
        if(i_temp[i].Getdata())
        copy_item(i_temp[i],I[i]);  
    }     
    
    for(int i = 0; i < n4; i++)
    {
        if(I[i].Getdata())
        {
        cout << i <<endl;
        I[i].show();
        cout << "ID:" << I[i].GetID() << "  符号：" << I[i].getSingal() <<" 规约标志："<<I[i].getFlag()<< "  上ID：" << I[i].GetUppoint()<<endl;
        }
    }
        
    make_DFA();       //构造 G[S']活前缀的DFA
    for(int i = 1; i < 5; i++)
    {
        make_GotoForm(I[i]);
    }
    make_ActionForm();    
    cout << "ACTION表" << endl;
    for(int i = 0; i < 5; i++)
    {   cout << i << ":  ";
        for(int j = 0; j <3; j++)
        {
            cout << ACTION[i][j].first << ACTION[i][j].second << "         " ;
            if(j == 2)
            cout << endl;
        }
    }        
    
    cout << "GOTO表" << endl;    
    for(int i = 0; i <= 4; i++)
    cout << GOTO[i] << endl;
    
    for(int i = 1; i < n4; i++)
    if(item[i].point != 0)
    cout << item[i].data << "->" << item[i].data1 << "  " << item[i].point << endl;
    
    node *first = G[0].Getdata();
    for(int i = 1; i < n4; i++)
    {
       if( Same_check(item[i],first) )
       {
           cout <<"找到了！"<< endl;
           cout << first->data << "->" << first->data1 << "  " << first->point << endl;
       }    
   }    
    cout << "DFA" << endl;
    for(int i = 0; i < 5; i++)
    cout << "    " << i ;
    cout << endl;
    for(int i = 0; i < 5; i++)
    { cout << i <<": ";
        for(int j = 0; j < 5; j++)
        {  
            cout << DFA[i][j].flags << DFA[i][j].first << DFA[i][j].second << "  ";
            if(j == 4)
            cout << endl;
        }
    }


   // ifstream constructor opens the file
   ifstream inClientFile( "c.txt", ios::in );

   if ( !inClientFile ) {
      cerr << "File could not be opened\n";
      exit( 1 );
   }
   while ( inClientFile >> line)
   cout << line << endl;
       
    if(control())
        cout <<"编译成功！"<<endl;
    else cout << "有语法错误！" << endl;    
    system("PAUSE");    
    return 0;
}

void Init()
{
    T[0] = "a";             //终极符
    T[1] = "b";             //终极符
    N[0] = "A";             //非终极符  
    G[0].Insert("S'","A",0,0);//文法
    G[1].Insert("A","aA",0,0);
    G[2].Insert("A","b",0,0);
    G[0].Insert("A","aA",0,0);
    G[0].Insert("A","b",0,0);
    G_temp[0].Insert("S'","A",0,0);
    G_temp[1].Insert("A","aA",0,0);
    G_temp[2].Insert("A","b",0,0);
   
    for(int i = 0; i < n4; i++)
    {
        I[i].setID(i);                   //设置每个项目集的ID号
        i_temp[i].setID(i);              //备份
    }    
}    

void make_DFA()                          //构造 G[S']活前缀的DFA
{
    for(int i = 0; i < 5; i++)           //初始化DFA表
    DFA[i][0].flags = 0;
    for(int i = 1; i < 5; i++)
    {  
       //对该项目集自身的关系进行分析
       if(I[i].getFlag()!= 1)            //若该项目集是非规约项目集
       {   
           node *dfa_temp1;
           //node *dfa_temp2;
           dfa_temp1 = DFA_check(i_temp[i],"a");
           //dfa_temp2 = DFA_check(i_temp[i],"b");
           //I[1].show();
           //cout << dfa_temp1->data <<"->" << dfa_temp1->data1 << dfa_temp1->point <<endl;
           if( I[i].Find(dfa_temp1))     //若找到了
           {
               //cout << "++&&&&&&&&&&++" << endl;
               DFA[i][1].flags = 1;
               DFA[i][1].first = "a";
               DFA[i][1].second = I[i].GetID();
           }
           /*    
           if( !k && I[i].Find(dfa_temp2))     //若找到了
           {
               k = 1;
               DFA[i][1].flags = 1;
               DFA[i][1].first = "b";
               DFA[i][1].second = I[i].GetID();
           }
           */
       }
       copy_item(I[i],i_temp[i]);        //还原数据
       //////////////////////////////////////////////////////////
       if(I[i].getFlag()== 1)            //若该项目集是规约项目集  
       {
           for(int j = 0; j < 5; j++)
              DFA[I[i].GetID()][j].flags = 0;
       }                                          
       //对该项目集与其他的项目集之间的关系进行分析
       DFA[I[i].GetUppoint()][I[i].GetID()].flags = 1;
       DFA[I[i].GetUppoint()][I[i].GetID()].first = I[i].getSingal();
       DFA[I[i].GetUppoint()][I[i].GetID()].second = I[i].GetID();
   }
        
    for(int i = 2; i < 5; i++)
    {   
       
       //for(int j = 1; j < i-1; j++)
       //{   
           //int i = 2;
           int j = 1;
           node *p = i_temp[i].Getdata();
           (p->point)--;
           if( I[j].Find(p) )                //若找到相同的项目
           {   //cout <<"++&&&&&&&&++" << endl;
               DFA[j][i].flags = 1;
               DFA[j][i].first = I[i].getSingal();
               DFA[j][i].second = I[i].GetID();
           }
           copy_item(I[i],i_temp[i]);        //还原数据
       //}    
    }                                         
}

void make_ActionForm()                      //填写action表
{
    cout << "调用make_ActionForm" << endl;
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            cout << DFA[i][j].flags << "    ";
            if(j == 4)cout << endl;
            if(DFA[i][j].flags == 1)         //若该元素有效
            {
                //cout << "1111111" << endl;
                int k = DFA[i][j].second;
                node *DFA_temp = I[k].Getdata();
                if( I[k].getFlag() != 1 )    //若该项目集是非规约项目集
                {
                    //cout << "222222222" << endl;
                    if( I[k].getSingal() == "a" )
                    {
                        ACTION[i][0].second = I[k].GetID();
                        ACTION[i][0].first = "s";
                    }  
                        
                }
                
                if( I[k].getFlag() == 1 )    //若该项目集是规约项目集
                {
                    if( I[k].getSingal() == "b" )
                    {   
                        //cout << "222222222" << endl;
                        ACTION[i][1].second = I[k].GetID();
                        ACTION[i][1].first = "s";
                    }
                    //cout << "3333333333" << endl;
                    if( DFA_temp->data == "S'" )
                    {
                        //cout << "444444444" << endl;
                        ACTION[I[k].GetID()][2].first = "acc";
                    }
                    else
                    {
                        //cout << "555555555" << endl;
                        for( int p = 0; p < 3; p++ )
                        {
                            ACTION[I[k].GetID()][p].first = "r";
                            int h = 0;
                            while(h < 3)
                            {
                                node *tp = i_temp[k].Getdata();
                                tp->point = 0;
                                if( G_temp[h].Find(tp) )
                                   ACTION[I[k].GetID()][p].second = h;
                                h++;
                                copy_item(I[k],i_temp[k]);  //还原数据
                            }
                        }    
                    }         
                }      
            }
        }                 
    }    
}

void make_GotoForm(linklist &l)         //填写goto表
{
    if( (l.getFlag() == 1) )           //若该项目集是规约项目集
     {
          if( (l.getSingal() == N[0]) )
          {
             GOTO[l.GetUppoint()] = l.GetID();
          }
     }  
}    
    
node *DFA_check(linklist &l, string s)
{
    int k = 0;
    node *tp = NULL;
    node *temp = l.Getdata();
    while(temp && !k)
    {  
        if(temp->data1[0] == s[0] && (temp->data1[1]) && (temp->point == 1))
        {
            k = 1;
            tp = temp;
            if(temp->point == 3)          //项目为规约项目
            temp->rule = 1;
            else  tp->point = tp->point + 1;
        }
       
        temp = temp->next;
    }
    return tp;
}   
   
node *check(linklist &l, string s)
{
    int k = 0;
    node *tp = NULL;
    node *temp = l.Getdata();
    while(temp && !k)
    {   //l项目集中存在字符串S
        if(temp->data1 == s)
        {
            k = 1;      
            tp = temp;                    
            temp->rule = 1;              //项目为规约项目
            tp->point = tp->point + 1;
        }      
        else if(temp->data1[0] == s[0] && (temp->data1[1]) )
        {
            k = 1;
            tp = temp;
            if(temp->point == 3)          //项目为规约项目
            temp->rule = 1;
            else  tp->point = tp->point + 1;
        }
        else if(temp->data1[1] == s[0] && (temp->point) > 1)
        {
            k = 1;
            tp = temp;        
            temp->rule = 1;               //项目为规约项目
            tp->point = tp->point + 1;
        }
        temp = temp->next;
    }

    if(tp != NULL)                        
    {
        for(int i = 1; i < n4; i++)      //进行项目查找
        {
            if( Same_check(item[i],tp) ) //若有相同的项目存在
                tp = NULL;     
        }    
    }
    
    if(tp != NULL)                      //若没有相同的项目,进行项目注册
    {
        int counter = number;
        item[counter].data = tp->data;
        item[counter].data1 = tp->data1;
        item[counter].point = tp->point;
        number++;
    }
        
    return tp;    
}   
    
void GO(linklist &l, string s)
{
    node *g_temp;
    int i ;
    int kk = 1;
    g_temp = check(l,s);
    if( g_temp!= NULL && l.getFlag()!= 1 )
    {   
        for(i = 0; i < n4; i++)
        {
            if(I[i].Getdata()== NULL)
            {
                I[i].setSingal(s);                  //设置符号标志位
                I[i].setUppoint(l.GetID());         //设置父ID
                i_temp[i].setSingal(s);
                i_temp[i].setUppoint(l.GetID());
            }    
                
        }    
        closure(g_temp);
    }     
}

//生成新的项目集   
void closure(node *pp)                //P为新项目集中的第一项目
{   
    cout << endl;
    if(!I[0].Getdata())              //项目I0为空时，生成项目集I[0]
    {
          I[0].Insert(pp->data,pp->data1,left,0);
          I[0].setUppoint(0);
          i_temp[0].Insert(pp->data,pp->data1,left,0);
          i_temp[0].setUppoint(0);
          node *temp;
          temp = pp->next;
          while(temp)
          {
              if(temp->data == pp->data1)
              {
                  I[0].Insert(temp->data,temp->data1,left,0);
                  i_temp[0].Insert(temp->data,temp->data1,left,0);
              }          
              temp = temp -> next;
          }
    }
    int j = 1;  
    int k = 1;
    while(j < n4 && k)
    {
            if(!I[j].Getdata())              //若I[j]为空
            {
                k = 0;
                new_item (j,pp);
            }  
            ++j;           
    }     

}

void new_item(int j,node *pp)
{
    
    if(pp)
    {
        int temp_rule = pp->rule;
        if(pp->point != 0)
        {
            if(!I[j].Getdata())        //项目I[j]为空时
            {   
                I[j].Insert( pp->data,pp->data1,pp->point,pp->rule );//插入项目pp
                i_temp[j].Insert( pp->data,pp->data1,pp->point,pp->rule );//备份项目集
       
                if(temp_rule)          //若项目pp是规约项目
                {
                    I[j].setFlag();        //标记该项目集为规约项目集
                    i_temp[j].setFlag();   //备份项目集
                }    
                
                if(pp->data1[1] == pp->data[0] && temp_rule != 1)
                {
                    I[j].Insert( pp->data,pp->data1,(pp->point)-1,pp->rule );
                    //备份项目集
                    i_temp[j].Insert( pp->data,pp->data1,(pp->point)-1,pp->rule );
                }    
                
                if(temp_rule != 1)
                {  
                    pp = pp->next;
                    while(pp)              
                    {
                        I[j].Insert(pp->data,pp->data1,pp->point,pp->rule);
                        //备份项目集
                        i_temp[j].Insert(pp->data,pp->data1,pp->point,pp->rule);
                        pp = pp->next;
                    }
                }
            }
        }      
    }
}

bool Same_check(node &p, node *q)         //查找是否有相同的项目    
{
    if( q != NULL )
    if( (p.point == q->point) && (p.data1 == q->data1) && (p.data == q->data) )
        return true;                      //若找到相同的，返回1  
    return false;                   
}   

void copy_item(linklist &list1,linklist &list2)    //复制
{
    node *temp1 = list1.Getdata();
    node *temp2 = list2.Getdata();
    while(temp1)
    {
        if(temp1->point != temp2->point)
           temp2->point = temp1->point;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
}  

bool control()                  //语法分析主控程序
{
    int l_num = 0;
    int b_num = 0;
    int num = 1;
    int length = 0;
    int row = 0;
    int team = 0;
    int i = 0;
    string s;
    int control_flags = 1;
    S.Push(0,"#");
    while( control_flags )
    {  
            cout << "显示栈的状态！" << endl;
            S.show();
            team = S.get()->data;
            cout << team << endl;
            int k = length;
            s = line[k];
            switch(s[0])
            {
                case 'a':   row = 0;
                            break;
                case 'b':   row = 1;
                            break;
                case '#':   row = 2;
                            break;
                default:    cout << "出错！" << endl;
                            break;
            }
            i = ACTION[team][row].second;
           if( ACTION[team][row].first == "s" )         //移入
           {   
               S.Push( ACTION[team][row].second , s );
               length++;
           }
                      
           else if( ACTION[team][row].first == "r" )   //规约
           {   
               if( G_temp[i].Getdata()->data1 == S.get()->data1 )     //找到相应的规则式
               {
                   num = 1;
                   S.Pop();
                   S.Push( GOTO[S.get()->data] , G_temp[row].Getdata()->data );
               }
               
               else if(G_temp[i].Getdata()->data1.size() == 2 && G_temp[i].Getdata()->data1[1] == S.get()->data1[0] )//找到相应的规则式
               {
                   node1 s_temp;
                   s_temp.data = S.get()->data;
                   s_temp.data1 = S.get()->data1;
                   num = 1;
                   S.Pop();
                   if( G_temp[i].Getdata()->data1[0] == S.get()->data1[0] )
                   {
                       if( S.get()->data != 0)
                       S.Pop();
                       S.Push( GOTO[S.get()->data] , G_temp[i].Getdata()->data );
                   }
                   else
                       S.Push( s_temp.data, s_temp.data1 ); //还原栈的数据
                        
               }  
               if( num == 0 )return false;  

           }         
           else if( ACTION[team][row].first == "acc" )
               return true;                 
           else return false;             
    }  
}

/*----------------------node.h------------------------*/
#ifndef NODE_H
#define NODE_H

#include<string>
using namespace std;

struct node
{
    int point;                      //点的位置
    int rule;                       //项目是否为规约项目的标志
    string data;
    string data1;
    node *next;
};

class linklist
{
    public:
        linklist();
        ~linklist();
        void Insert(string,string,int,int);//插入函数
        int Find(node*);            //寻找函数
        void show();
        void setSingal(string);             
        string getSingal();         //获取标志位的长度
        int getSize();              //获取链表的长度
        void setFlag();             //设置规约标志
        int getFlag();              //获取规约标志位
        node *Getdata();            //获取head指针
        int setUppoint(int);        //设置父ID号
        int GetUppoint();           //获取父ID号
        int setID(int);             //设置自身的ID
        int GetID();                //获取自身的ID
    private:
        string singal;                
        node *head;                 //链表的头指针
        node *last;                 //链表的末尾指针                    
        int size;                   //链表中元素个数
        int flag;                   //是否为规约项目集的标志位
        int uppoint;                //记录父ID号
        int id;                     //自身的ID号
};

#endif

/*------------node1.h------------*/
#ifndef NODE1_H
#define NODE1_H

#include<string>
using namespace std;
struct node1
{
    int data;
    string data1;
    node1 *next;
};

class stack
{
    private:
        node1 *top;
        int size;
    
    public:
        stack();
        ~stack();
        void Push(int,string);
        void Pop();
        node1 *get();
        void show();
};

#endif

/*------------------linkstack.cpp------------*/
#include<iostream>
#include<string>
#include"node1.h"
using namespace std;

stack :: stack()
{
    top = new node1;
    top->next = NULL;
    int size = 0;
}    

stack :: ~stack()
{
    node1 *p;
    while(top)
    {
        p = top;
        top = top -> next;
        delete p;
    }
}

void stack :: Push(int x,string y)
{
    node1 *p = new node1;
    if( p == NULL) cout << "空间分配失败！" << endl;
    else
    {
        p -> data = x;
        p -> data1 = y;
        p -> next = top;
        top = p;
        size++;
    }    
}
void stack :: Pop()
{
    node1 *p = top;
    top = top -> next;
    delete p;
    size--;
}


node1 *stack :: get()
{
    return top;
}

node1 *get_next()
{
    ;
}
   
void stack :: show()
{
    node1 *p = top;
    while(p -> next)
    {
        cout << p -> data << " " << p -> data1 << endl;
        p = p -> next;       
    }
}

/*-----------------linklist.cpp------------------*/
#include<iostream>
#include<string>
#include"node.h"
using namespace std;


linklist :: linklist()
{
    last = head = NULL;
    flag = 0;  
    size = 0;
    singal = '/0';
    id = -1;
    uppoint = -1;
}

  

linklist :: ~linklist()
{
    node *p;
    p = head;
    while(head)
    {
        p = head;
        head = head -> next;
        delete p;
    }
}

void linklist :: Insert(string str1,string str2,int i,int k)
{
    node *p;
    p = new node;
    p -> data = str1;
    p -> data1 = str2;
    p -> point = i;
    p -> rule = k;
    if(head == NULL)          //链表为空时
    {
        p -> next = head;
        head = p;
        last = head;
        last -> next = NULL;
    }                        //链表非空时
    last -> next = p;
    p -> next = NULL;
    last = p;
    size++;
}

int linklist :: Find(node *p)
{
    int k = 0;
    node *q;
    q = head;
    
    if( p != NULL )
    {
        while( !k && q)
        {   //若找到 ,返回1
             if( (p->data == q->data) && (p->data1 == q->data1) && (p->point == q->point))  
             {
                 k = 1;
             }
             q = q -> next;  
        }
    }    
    return k;     
}

void linklist :: show()
{
    node *p;
    p = head;
    if(head != NULL)
    {
        while(p)
        {
            switch(p->point)
            {
            case 0:
                cout << p->data << "->" << p->data1 << endl;
                break;
            case 1:
                cout << p->data << "->."<< p->data1 << endl;
                break;
            case 2:
                cout << p->data << "->"<< p->data1[0] <<"." << p->data1[1]<< endl;
                break;
            case 3:
                cout << p->data << "->" << p->data1 << "." << endl;
                break;
            default:
                break;
            }               
        p = p->next;
        }
    }    
}

int linklist :: getFlag()
{
    return flag;
}

void linklist :: setFlag()
{
    flag = 1;
}
          
string linklist :: getSingal()
{
    return singal;
}  

int linklist :: getSize()
{
    return size;
}
      
void linklist :: setSingal(string chr)
{
    singal = chr;
}  

node *linklist :: Getdata()
{
    return head;
}

int linklist :: setUppoint(int i)
{
    uppoint = i;
}    
           
int linklist :: GetUppoint()   
{
    return uppoint;
}

int linklist :: setID(int i)
{
    id = i;
}    

int linklist :: GetID()  
{
    return id;
}