follow.h

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

#include "DATA.h"

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;
    }
}



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;
        }
    }
    
    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;
    }
    
   
}