slr(1).cpp

编译原理SLR(1)语法分析器

#include <iostream>
#include <fstream>
using namespace std;

const int maxn=100;
const int ERROR=1000000000;

int binary[31]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,
16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,
8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824};

struct G
{
    char left;
    char right[100];  
    int l;
}g[maxn];

struct G_EXTEND
{
    char left;
    char right[100];
    int l;
    int dot_pos;
}g_extend[maxn*maxn];

struct C
{
    int item[maxn];
    bool mark[maxn];
    int l;
}c[maxn];
int c_len;

char Vt[maxn],Vn[maxn],Vhash[128];
int g_cnt,vt_cnt,vn_cnt,g_extend_cnt;
int first_v[128];
int go[maxn][128];
struct FLO
{
    int t;
    int start;
}follow[128];

int ACTION[maxn*maxn][128],GOTO[maxn*maxn][128];
int State_S[maxn];
char Sign_S[maxn],a[maxn];

void FIRST()
{
    bool visited[maxn],changed[128];
    memset(first_v,0,sizeof(first_v));
    for(int i=0;i<vt_cnt;i++)
    {
        first_v[Vt[i]]+=binary[i];
    }
    
    int flag;
    while(1)
    {
        flag=0;
        for(int i=0;i<g_cnt;i++)
        {
      //     cout<<g[i].left<<"->"<<g[i].right<<' ';
      //      cout<<first_v[g[i].left]<<' '<<first_v[g[i].right[0]]<<' '<<(first_v[g[i].left]&first_v[g[i].right[0]])<<endl;
        if(g[i].left!=g[i].right[0] && first_v[g[i].right[0]] &&  !(first_v[g[i].left]&first_v[g[i].right[0]]) )
        {
            first_v[g[i].left]+=first_v[g[i].right[0]];
            flag=1; 
        }
        }
        if(!flag) break;
    }
/*    for(int i=0;i<vn_cnt;i++)
    {
        for(int ii=0;ii<31;ii++) 
          if(first_v[Vn[i]]&binary[ii]) cout<<Vt[ii]<<' ';
        cout<<Vn[i]<<' '<<first_v[Vn[i]]<<endl;
    }*/
}

void FOLLOW()
{
    FIRST();
    memset(follow,0,sizeof(follow));
    follow[Vn[0]].start=1;
    for(int i=0;i<g_cnt;i++)
    {
       for(int j=0;j<g[i].l-1;j++)
       if(!(follow[g[i].right[i]].t&first_v[g[i].right[j+1]]))
       {
            follow[g[i].right[j]].t+=first_v[g[i].right[j+1]];
            if(follow[g[i].right[j+1]].start) follow[g[i].right[j]].start=follow[g[i].right[j+1]].start;
        }
    }
    
   /* for(int i=0;i<vn_cnt;i++)
    {
        cout<<Vn[i]<<' ';
        for(int j=0;j<31;j++) if(follow[Vn[i]].t&binary[j]) cout<<Vt[j]<<' ';
        if(follow[Vn[i]].start) cout<<"# ";
        cout<<follow[Vn[i]].t<<endl;
    }*/
    
    
    
    while(1)
    {
        int flag=0;
        for(int i=0;i<g_cnt;i++)
        if(g[i].right[g[i].l-1]>='A' && g[i].right[g[i].l-1]<='Z')
        {
        if( follow[g[i].left].t && !(follow[g[i].right[g[i].l-1]].t&follow[g[i].left].t))
        {
            flag=1;
            follow[g[i].right[g[i].l-1]].t+=follow[g[i].left].t;
        }
        else if(follow[g[i].left].start==1&&follow[g[i].right[g[i].l-1]].start==0)
        {
            flag=1;
            follow[g[i].right[g[i].l-1]].start=1;
        }
        }
        if(!flag) break;
    }
    
    for(int i=0;i<vn_cnt;i++)
    {
        cout<<Vn[i]<<' ';
        for(int j=0;j<31;j++) if(follow[Vn[i]].t&binary[j]) cout<<Vt[j]<<' ';
        if(follow[Vn[i]].start) cout<<"# ";
        cout<<follow[Vn[i]].t<<endl;
    }
}

void EXTEND_G()
{
    memset(g_extend,0,sizeof(g_extend));
    g_extend[0].left='$';
    g_extend[0].right[0]=g[0].left;
    g_extend[0].l=1;
    g_extend[0].dot_pos=0;
    
    g_extend[1].left='$';
    g_extend[1].right[0]=g[0].left;
    g_extend[1].l=1;
    g_extend[1].dot_pos=1;
    
    g_extend_cnt=2;
    for(int i=0;i<g_cnt;i++)
    {
        for(int j=0;j<=g[i].l;j++)
        {
            g_extend[g_extend_cnt].left=g[i].left;
            strcpy(g_extend[g_extend_cnt].right,g[i].right);
            g_extend[g_extend_cnt].l=g[i].l;
            g_extend[g_extend_cnt].dot_pos=j;
            g_extend_cnt++;
        }
    }
    
    for(int i=0;i<g_extend_cnt;i++)
    {
        cout<<i<<' '<<g_extend[i].left<<"->";
        for(int j=0;j<g_extend[i].l;j++)
        {
            if(j==g_extend[i].dot_pos) cout<<'.'<<g_extend[i].right[j];
            else cout<<g_extend[i].right[j];
        }
        if(g_extend[i].l==g_extend[i].dot_pos) cout<<'.';
        cout<<endl;
    }
}

void CLOSURE(C& temp)
{
    int s=0;
    while(1)
    {
        int flag=0;
        int templ=temp.l;
        for(int i=s;i<temp.l;i++)
        {
            int t=temp.item[i];
            if(g_extend[t].dot_pos!=g_extend[t].l &&
            g_extend[t].right[g_extend[t].dot_pos]>='A' && g_extend[t].right[g_extend[t].dot_pos]<='Z')
            {
                for(int j=0;j<g_extend_cnt;j++)
                if(g_extend[j].left==g_extend[t].right[g_extend[t].dot_pos] && g_extend[j].dot_pos==0
                   && !temp.mark[j])
                {
               /*      cout<<i<<' '<<j<<' '<<g_extend[j].left<<' '<<g_extend[j].right<<endl;
                     system("pause");*/
                     flag=1;
                     temp.mark[j]=1;
                     temp.item[temp.l++]=j;
                }
            }
        }
        s+=templ;
        if(!flag) break;
    }
    
  /*  cout<<c[k].l<<endl;
    for(int i=0;i<c[k].l;i++)
    {
        cout<<c[k].item[i]<<' ';
    }
    cout<<endl;*/
}

C GO(int k,char x)
{
    C temp;
    temp.l=0;
    memset(temp.mark,0,sizeof(temp.mark));
    for(int i=0;i<c[k].l;i++)
    {
        int t=c[k].item[i];
        if(g_extend[t].dot_pos!=g_extend[t].l &&
           g_extend[t].right[g_extend[t].dot_pos]==x && !temp.mark[t+1])
        {
            temp.item[temp.l++]=t+1;
            temp.mark[t+1]=1;
            CLOSURE(temp);
        }
    }
    return temp;
}

int BelongToC(C temp)
{
    for(int i=0;i<c_len;i++)
    {   
        int flag=0;
        if(c[i].l==temp.l)
        {
            for(int j=0;j<g_extend_cnt;j++) 
            {
          /*      cout<<i<<' '<<j<<' '<<c[i].mark[j]<<' '<<temp.mark[j]<<endl;*/
                if(c[i].mark[j]!=temp.mark[j]) {flag=1;break;}
            }
            
            if(!flag) return i;
        }
    }
    return -1;
}

void show(C temp)
{
    for(int i=0;i<temp.l;i++)
    {
        cout<<g_extend[temp.item[i]].left<<"->";
        for(int j=0;j<g_extend[temp.item[i]].l;j++)
        {
            if(j==g_extend[temp.item[i]].dot_pos) cout<<'.'<<g_extend[temp.item[i]].right[j];
            else cout<<g_extend[temp.item[i]].right[j];
        }
        if(g_extend[temp.item[i]].l==g_extend[temp.item[i]].dot_pos) cout<<'.';
        cout<<endl;
    } 
    cout<<endl;
}

void LR0Set()
{
    EXTEND_G();
    c_len=0;
    memset(c,0,sizeof(c));
    c[0].item[0]=0;
    c[0].l++;
    c[0].mark[0]=1;
    c_len=1;
    CLOSURE(c[0]);
    
    memset(go,0,sizeof(go));
    int s=0;
    while(1)
    {
        int templ=s;
        int flag=0;
        for(int i=s;i<c_len;i++)
        {
            for(int j=0;j<vn_cnt;j++)
            {
                C temp=GO(i,Vn[j]);
          /*      cout<<Vn[j]<<' ';
                show(temp);
                cout<<BelongToC(temp)<<endl;*/
            //  system("pause");
                if(temp.l!=0)
                {
                    int t=BelongToC(temp);
                    if(t==-1)
                    {
                        go[i][Vn[j]]=c_len;
                        c[c_len++]=temp;
                        cout<<i<<' '<<Vn[j]<<' '<<c_len-1<<endl;
                        show(c[c_len-1]);
                //        system("pause");
                    }
                    else go[i][Vn[j]]=t;
                }
            }
            
            for(int j=0;j<vt_cnt;j++)
            {
                C temp=GO(i,Vt[j]);
                if(temp.l!=0)
                {
                    int t=BelongToC(temp);
                    if(t==-1)
                    {
                        go[i][Vt[j]]=c_len;
                        c[c_len++]=temp;
                        cout<<i<<' '<<Vt[j]<<' '<<c_len-1<<endl;
                        show(c[c_len-1]);
               //         system("pause");
                    }
                    else go[i][Vt[j]]=t;
                }
            }
       /*     cout<<i<<":  "<<endl<<endl<<endl;
            for(int ii=0;ii<c_len;ii++)
            {
                cout<<ii<<":"<<endl;
                show(c[ii]);
                system("pause");
            }*/
        }
        if(!flag) break;
        s+=templ;
    }
    for(int i=0;i<c_len;i++)
      for(int j=0;j<128;j++)
      if(go[i][j]) 
    {
        cout<<i<<' '<<char(j)<<' '<<go[i][j]<<endl;
    }
}

int Find_G(G_EXTEND temp)
{
    for(int i=0;i<g_cnt;i++)
    {
        if(strcmp(g[i].right,temp.right)==0) return i+1;
    }
}

void SLR1Grid()
{
    memset(ACTION,0,sizeof(ACTION));
    memset(GOTO,0,sizeof(GOTO));
    
 /*   for(int i=0;i<128;i++)
    if(follow[i].t)
    {
        cout<<char(i)<<' '<<follow[i].t<<endl;
    }
    system("pause");*/
    for(int i=0;i<c_len;i++)
      {
         for(int j=0;j<vt_cnt;j++)
            ACTION[i][Vt[j]]=ERROR;
         for(int j=0;j<vn_cnt;j++)
            GOTO[i][Vn[j]]=ERROR;            
      }
    
    for(int i=0;i<c_len;i++)
      for(int j=0;j<c[i].l;j++)
      {
            int t=c[i].item[j];
            if(g_extend[t].left=='$' && g_extend[t].dot_pos==g_extend[t].l)
            {
                    ACTION[i]['#']=0;
            }
            else if(g_extend[t].dot_pos==g_extend[t].l)
            {
              //  cout<<t<<' '<<g_extend[t].left<<"->"<<g_extend[t].right<<endl;
                int jj=Find_G(g_extend[t]);
                for(int k=0;k<vt_cnt-1;k++)
                  if(follow[g_extend[t].left].t && (follow[g_extend[t].left].t&binary[k]) )
                  {
//                        cout<<follow[g_extend[t].left].t<<' '<<Vhash[k]<<' '<<(follow[g_extend[t].left].t&Vhash[k])<<endl;
                  //      cout<<i<<' '<<Vt[k]<<' '<<jj<<endl;
                        ACTION[i][Vt[k]]=-jj;
                  }
                if(follow[g_extend[t].left].start)  
                {
                    //cout<<i<<' '<<'#'<<' '<<jj<<endl;
                    ACTION[i]['#']=-jj;
                }
                //system("pause");
                       
            }
            else
            {
                if(g_extend[t].right[g_extend[t].dot_pos]<'A' || g_extend[t].right[g_extend[t].dot_pos]>'Z')
                {
                 /*   cout<<i<<' '<<g_extend[t].right[g_extend[t].dot_pos]<<' '<<go[i][g_extend[t].right[g_extend[t].dot_pos]]<<endl;
                    system("pause");*/
                    ACTION[i][g_extend[t].right[g_extend[t].dot_pos]]=go[i][g_extend[t].right[g_extend[t].dot_pos]];
                }
                else
                {
                    GOTO[i][g_extend[t].right[g_extend[t].dot_pos]]=go[i][g_extend[t].right[g_extend[t].dot_pos]];
                }
            }
      }
      
    cout<<"    ";
    for(int j=0;j<vt_cnt;j++) cout<<Vt[j]<<"  ";  
    for(int j=0;j<vn_cnt;j++) cout<<Vn[j]<<"  ";
    cout<<endl;
    
    for(int i=0;i<c_len;i++)
    {
        cout<<i<<"  ";
      for(int j=0;j<vt_cnt;j++)
      {
            if(ACTION[i][Vt[j]]>=0) cout<<' '<<ACTION[i][Vt[j]]<<' ';
            else cout<<ACTION[i][Vt[j]]<<' ';
      }
      for(int j=0;j<vn_cnt;j++)
      {
            cout<<' '<<GOTO[i][Vn[j]]<<' ';
      }
      cout<<endl;
    }
    
}


void SLRDFA()
{
    int top_state(0),top_sign(0),i=0;
    memset(State_S,0,sizeof(State_S));
    memset(Sign_S,0,sizeof(Sign_S));
    while(cin>>a){
    top_state=0;
    top_sign=0;
    i=0;
    a[strlen(a)]='#';
    State_S[top_state++]=0;
    Sign_S[top_sign++]='#';
    cout<<"State          Sign          A"<<endl;
    while(1)
    {
        if(ACTION[State_S[top_state-1]][a[i]]>0 && ACTION[State_S[top_state-1]][a[i]]!=ERROR)
        {
            State_S[top_state]=ACTION[State_S[top_state-1]][a[i]];
            top_state++;
            Sign_S[top_sign++]=a[i];
            i++;
        }
        else if(ACTION[State_S[top_state-1]][a[i]]<0)
        {
            int t=-ACTION[State_S[top_state-1]][a[i]];
            t--;
            top_state-=g[t].l;
            top_sign-=g[t].l;
            State_S[top_state]=GOTO[State_S[top_state-1]][g[t].left];
            top_state++;
            Sign_S[top_sign]=g[t].left;
            top_sign++;
        }
        else if(ACTION[State_S[top_state-1]][a[i]]==0)
        {
            cout<<"ACCEPTED"<<endl;
            break;
        }
        else {cout<<"ERROR!"<<endl;break;}
        
        for(int j=0;j<top_state;j++) cout<<State_S[j];
        for(int j=0;j<15-top_state;j++) cout<<' ';
        for(int j=0;j<top_sign;j++) cout<<Sign_S[j];
        for(int j=0;j<14-top_sign;j++) cout<<' ';
        for(int j=i;j<strlen(a);j++) cout<<a[j];
        cout<<endl;
    }
}
}
 

void getalph(char t,char* str)
{
    if(Vhash[t]==-1)    
    {
        Vn[vn_cnt]=t;
        Vhash[t]=vn_cnt;
        vn_cnt++;
    }
    for(int i=0;i<strlen(str);i++)
    if(Vhash[str[i]]==-1)
    {
        if(str[i]>='A' && str[i]<='Z')
        {
            Vn[vn_cnt]=str[i];
            Vhash[str[i]]=vn_cnt;
            vn_cnt++;
        }
        else
        {
            Vt[vt_cnt]=str[i];
            Vhash[str[i]]=vt_cnt;
            vt_cnt++;
        }

    }
 /*   cout<<vt_cnt<<' ';
    for(int i=0;i<vt_cnt;i++)
    {
        cout<<Vt[i]<<' ';
    }
    cout<<endl;
    for(int i=0;i<vn_cnt;i++)
    {
        cout<<Vn[i]<<' ';
    }
    cout<<endl;
    system("pause");*/
}

void init()
{
    char str[100];
    int i,k,flag;
    ifstream in("1.in");
    g_cnt=0;
    vt_cnt=0;
    vn_cnt=0;
    memset(Vhash,-1,sizeof(Vhash));
    while(in.getline(str,100))
    {
        flag=0;
        i=3;
        while(i<strlen(str))
        {
            g[g_cnt].left=str[0];
            int j=0;
            while(str[i]!='|' && i<strlen(str))
            {
                g[g_cnt].right[j++]=str[i];
                i++;
            }
            g[g_cnt].l=j;
            g_cnt++;
            i++;
        }   
    }
    for(i=0;i<g_cnt;i++)
    {
        getalph(g[i].left,g[i].right);
    } 
    Vt[vt_cnt++]='#';
    
    
    for(i=0;i<g_cnt;i++)
    {
        cout<<g[i].left<<"->"<<g[i].right<<endl;
    }
    for(int i=0;i<vt_cnt;i++)
    {
        cout<<Vt[i]<<' ';
    }
    cout<<endl;
    for(int i=0;i<vn_cnt;i++)
    {
        cout<<Vn[i]<<' ';
    }
    cout<<endl;
}



int main()
{
    init();
    FOLLOW();
    LR0Set();
    SLR1Grid();
    SLRDFA();
    system("pause");
}
/*
E->E+T
E->T
T->T*F
F->(E)
F->i
*/