by1.cpp

LR(1)分析器,当输入不同的文法就进行相应的文法分析

/*
  Name: LR(1)分析器的构造 
  Author: wangrui 
  Date: 07-06-07
  Description: 输入文法，构造出相应的LR(1)分析器 
*/
#include"iostream"
using namespace std;


char G[20][20];     //use a matrix to store grammar G
int  length[20];    //length use to store each formula's length
int  number = 0;
bool character[30];
bool first_vn[30][150];

void Read_G()
{
    cin >> number;   //user should give the number of formula first
    for(int i = 0; i < number; i++){
        char temp;
        int j = 0;
        do{
            cin >> temp;
            G[i][j++] = temp;
        }while(temp != '$');
        length[i] = --j;
    }
}

void get_first(){
    bool flag1;
    do{ 
        flag1 = false;
        for(int i = 0; i < number; i++){
           int t = 1;
           bool flag2 = false;
           do{
               flag2 = false;
               if (G[i][t] >= 'A' && G[i][t] <= 'Z'){
                      for(int k = 0; k < 64; k++)
                          if(first_vn[G[i][t]-'A'][k] == true && !first_vn[G[i][0]-'A'][k]){
                             first_vn[G[i][0]-'A'][k] = true;
                             flag1 = true;
                          }
                      for(int k = 91; k < 128; k++)
                          if(first_vn[G[i][t]-'A'][k] == true && !first_vn[G[i][0]-'A'][k]){
                             first_vn[G[i][0]-'A'][k] = true;
                             flag1 = true;
                          }
                      if(first_vn[G[i][t]-'A'][64] == true){
                          t++;
                          flag2 = true;
                      }
                }
                else if(!first_vn[G[i][0]-'A'][G[i][t]]){
                      first_vn[G[i][0]-'A'][G[i][t]] = true;
                      flag1 = true;
                }
           }while(flag2 && t < length[i]);
           if(t == length[i])
                first_vn[G[i][0]-'A'][26] = true;
        }
        
    }while(flag1);
}


/*
closure(I)
*/


int main()
{
    for(int i = 0; i< 150; i++)
        character[i] = false;
    for(int i = 0; i < 30; i++)
        for(int j = 0; j < 150; j++)
                first_vn[i][j] = false;

    Read_G();        //read G and put the number of formula into count
    get_first();     //each vn's first_set
    
    
    /*
    for(int i = 0; i < 26;i++){
        for(int j = 0; j < 65; j++)
           if(first_vn[i][j])
                printf("(%c %c)  ",i+'A',j);
        for(int j = 91; j < 128; j++)
           if(first_vn[i][j])
                printf("(%c %c)  ",i+'A',j);   
        printf("\n");
    }
    
    for(int i = 0; i < number; i++){
        for(int j = 0; j < length[i]; j++){
                cout << G[i][j]<<" ";
        }
        cout << endl;
    }
    */
}