[转贴]算符优先文法的算法

gladrain

/*描述： 从文法文件中读入终结符、非终结符、开始符、文法，输出FIRSTVT集，LASTVT集和算符优先矩阵

注释都没写，看以后有必要了再写吧；）不好的编程习惯，该打#￥…—
这是〈编译原理〉课的一道作业，已交予老师， 切莫COPY去唬弄老师哦；）
*/


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

const int VN_SIZE = 10;
const int MATIX_SIZE = 80;
struct VnNode {
        char vnName;
        string firstVtSet,nextVnFirst;
        string lastVtSet,nextVnLast;
        bool hasFinded;
} Vn[ VN_SIZE ] ;

void Debug( int vnNum )
{
        cout << endl << "Debuging..." << endl;
        for ( int i=0; i<vnNum; i++ ) {
                cout << "name:" << Vn.vnName << "  firstVtSet:" << Vn.firstVtSet << "  nextVnFirst:" << Vn.nextVnFirst   
                         << "   lastVtSet:" << Vn.lastVtSet << "   nextVnLast:" << Vn.nextVnLast << endl;
        }
        cout << "Debug ends" << endl;
        getchar();
}
void DoWithOneLine( string & nextVn, string & vtSet,string temp )
{
        bool flag = true;
        for ( int j=3; j<temp.length(); j++ ) {
                if ( isupper(temp[j]) ) {
                        nextVn += temp[j];
                        if ( j+1 >= temp.length() ) break;
                        if ( temp[j+1] != '|' )
                                vtSet += temp[j+1];
                        while ( true ) {
                                if ( temp[j] == '|' ) {
                                        flag = false;
                                        break;
                                }
                                if ( j >= temp.length() ) {
                                        flag = true;
                                        break;
                                }
                                j++;
                        }
                        if (flag) break;
                        else continue;
                } else {
                        vtSet += temp[j];
                        while ( true ) {
                                if ( temp[j] == '|' || j >= temp.length() ) break;
                                j++;
                        }
                }
        }
}
void Reverse( string & s )
{
        int n = s.length();
        char t;
        for( int i=0; i<n/2; i++ ) {
                t = s;
                s = s[n-i-1];
                s[n-i-1] = t;
        }
}
bool GetDirectSet( int & vnNum, string & vnSet, string & vtSet, char & startN, string & precept )
{
        void DoWithOneLine( string & nextVn, string & vtSet,string temp);
        void Reverse( string & s );
        ifstream inFile;
        string temp;
        int i;
        
        inFile.open("opg_test.txt");
        getline(inFile,temp);
        if ( temp != ";Vn" ) {
                return false;
        }
        getline(inFile,temp);
        while ( !temp.empty() ) {
                vnSet += temp;
                getline(inFile,temp);
        }
        getline(inFile,temp);
        if ( temp != ";Vt" ) {
                return false;
        }
        getline(inFile,temp);
        while ( !temp.empty() ) {
                vtSet += temp;
                getline(inFile,temp);
        }
        getline(inFile,temp);
        if ( temp != ";S" ) {
                return false;
        }
        getline(inFile, temp);
        startN = temp[0];
        inFile >> temp;
        if ( temp != "" ) {
                return false;
        }
        i=-1;
        while ( inFile >> temp ) {
                if ( !isupper(temp[0]) ) {
                        return false;
                }
                i++;
                Vn.vnName = temp[0];
                if ( temp[1] != '-' || temp[2] != '>' ) {
                        return false;
                }
                precept += temp.substr(3)+"|";
                DoWithOneLine( Vn.nextVnFirst,Vn.firstVtSet,temp );//Get directed firstvt set
                Reverse( temp=temp.substr(3) );
                temp = "   " + temp;
                DoWithOneLine( Vn.nextVnLast,Vn.lastVtSet,temp );//Get directed lastvt set
               
        }
        inFile.close();
        vnNum = i+1;
        return true;
}

void BufSort( string & a )
{
        int i,j,flag,t;
        int n = a.length();
        for ( i=0; i<n-1; i++ ) {
                flag = 0;
                for( j=0; j<n-1-i; j++ )
                        if( a[j]>a[j+1] ) {
                                t = a[j];
                                a[j] = a[j+1];
                                a[j+1] = t;
                                flag = 1;
                        }
                if ( !flag )
                        return;
        }
}

int AddVt( string & iVtSet, string jVtSet )
{
        bool same,hasAdd;
        int i,j;
        hasAdd = false;
        for( i=0; i<jVtSet.length(); i++ ) {
                same = false;
                for( j=0; j<iVtSet.length(); j++ ) {
                        if( iVtSet[j] == jVtSet ) { same = true; break; }
                }
                if( !same ) {
                        iVtSet += jVtSet;
                        hasAdd = true;
                }
        }
        if( hasAdd ) return 1;
    return 0;
}
void CalculateFirstVtSet( int vnNum )
{
        int onceMore ;
        int cycleTime;
        int i,j,k;

        cycleTime = 1;
        while( cycleTime!=2 ) {
                cycleTime = 0;
                onceMore = 1;
                while( onceMore || cycleTime!=2 ) {
                        onceMore = 0;
                        for( i=0; i<vnNum; i++ ) {
                                for( j=0; j<Vn.nextVnFirst.length(); j++ ) {
                                        for( k=0; k<vnNum; k++ ) {
                                                if ( Vn[k].vnName == Vn.nextVnFirst[j] )
                                                        onceMore += AddVt( Vn.firstVtSet,Vn[k].firstVtSet );
                                        }
                                }
                        }
                        if( onceMore == 0 ) {
                                cycleTime++ ;
                                //Debug( vnNum );
                        } else {
                                cycleTime = 0;
                        }
                }
        }
}
void CalculateLastVtSet( int vnNum )
{
        int onceMore ;
        int cycleTime;
        int i,j,k;

        cycleTime = 1;
        while( cycleTime!=2 ) {
                cycleTime = 0;
                onceMore = 1;
                while( onceMore || cycleTime!=2 ) {
                        onceMore = 0;
                        for( i=0; i<vnNum; i++ ) {
                                for( j=0; j<Vn.nextVnLast.length(); j++ ) {
                                        for( k=0; k<vnNum; k++ ) {
                                                if ( Vn[k].vnName == Vn.nextVnLast[j] )
                                                        onceMore += AddVt( Vn.lastVtSet,Vn[k].lastVtSet );
                                        }
                                }
                        }
                        if( onceMore == 0 ) {
                                cycleTime++ ;
                                //Debug( vnNum );
                        } else {
                                cycleTime = 0;
                        }
                }
        }
}
void PrintFirstVtSet( int vnNum )
{
        void BufSort( string & );
        cout << endl << "该文法的FirstVtSet为：" << endl;
        for ( int i=0; i<vnNum; i++ ) {
                BufSort( Vn.firstVtSet );
                cout << Vn.vnName << " : " << Vn.firstVtSet << endl;
        }
}
void PrintLastVtSet( int vnNum )
{
        void BufSort( string & );
        cout << endl << "该文法的LastVtSet为：" << endl;
        for ( int i=0; i<vnNum; i++ ) {
                BufSort( Vn.lastVtSet );
                cout << Vn.vnName << " : " << Vn.lastVtSet << endl;
        }
}
int fVnPos( char vn, int vnNum ) {
        for( int i=0; i<vnNum; i++ ) {
                if ( vn == Vn.vnName )
                        return i;
        }
        return -1;
}
bool AnalyzeThisPiecePrecept( string pP, string vtSet, int vnNum, char matix[MATIX_SIZE][MATIX_SIZE] )
{
        int fVnPos( char, int );

        int i = -1 ;
        int pos;
        int vnPos;
        for(;;) {
                i++;
                if ( i+1 >= pP.length() ) break;
                if ( isupper(pP) ) {
                        if ( isupper(pP[i+1]) ) return false;
                        pos = vtSet.find(pP[i+1]);
                        if ( (vnPos = fVnPos(pP,vnNum)) == -1 )  return false;
                        for ( int k=0; k<Vn[vnPos].lastVtSet.length(); k++ ) {
                                if ( matix[ vtSet.find( Vn[vnPos].lastVtSet[k] ) ][pos] == ' ' || matix[ vtSet.find( Vn[vnPos].lastVtSet[k] ) ][pos] == 'G'  )
                                        matix[ vtSet.find( Vn[vnPos].lastVtSet[k] ) ][pos] = 'G';
                                else return false;
                        }
                } else {
                        pos = vtSet.find(pP);
                        if ( isupper( pP[i+1] ) ) {                                
                                if ( (vnPos = fVnPos(pP[i+1],vnNum)) == -1 )  return false;
                                for ( int k=0; k<Vn[vnPos].firstVtSet.length(); k++ ) {
                                        if ( matix[pos][ vtSet.find( Vn[vnPos].firstVtSet[k] ) ] == ' ' || matix[pos][ vtSet.find( Vn[vnPos].firstVtSet[k] ) ] =='L' )
                                                matix[pos][ vtSet.find( Vn[vnPos].firstVtSet[k] ) ] = 'L';
                                        else return false;
                                }
                        } else {
                                if ( matix[pos][vtSet.find(pP[i+1])] == ' ' || matix[pos][vtSet.find(pP[i+1])] == 'E' )
                                        matix[vtSet.find(pP)][vtSet.find(pP[i+1])] = 'E';
                                else return false;
                        }
                        if ( i+2 < pP.length() && !isupper(pP[i+2]) ) {
                                if ( matix[pos][vtSet.find(pP[i+2])] == ' ' || matix[pos][vtSet.find(pP[i+2])] == 'E' )
                                        matix[pos][vtSet.find(pP[i+2])] = 'E';
                                else return false;
                        }

                }
               
        }
        return true;
}
bool MakePriorityMatrix( string precept,  string vtSet, int vnNum, char matix[MATIX_SIZE][MATIX_SIZE] )
{
        bool AnalyzeThisPiecePrecept( string pP, string vtSet, int vnNum, char matix[MATIX_SIZE][MATIX_SIZE] );
        int i,j;
        for ( i=0, j=0; i<precept.length(); i++ ) {
                if ( precept == '|' ) {
                        if ( i-j>1 ) {
                                if ( !AnalyzeThisPiecePrecept( precept.substr(j,i-j), vtSet, vnNum, matix ) )
                                        return false;
                        }
                        j = i+1;
                }
        }
        if ( i-j>1 ) {
                if ( !AnalyzeThisPiecePrecept( precept.substr(j,i-j), vtSet, vnNum, matix ) )
                        return false;
        }
        return true;
}
void PrintPriorityMatix( string vtSet, char matix[MATIX_SIZE][MATIX_SIZE] )
{
        cout << "\n★:优于　☆:低于　◎:同级" << endl << "  | ";
        for( int m=0; m<vtSet.length() ; m++ ) {
                cout << vtSet[m] << "   " ;
        }
        for( m=0; m<vtSet.length(); m++ ) {
                cout << endl << vtSet[m] << " | ";
                for( int n=0; n<vtSet.length(); n++ ) {
                        switch ( matix[m][n] ) {//★◎☆
                        case 'G': cout << "★  "; break;
                        case 'L': cout << "☆  "; break;
                        case 'E': cout << "◎  "; break;
                        default:  cout << "    ";   
                        }
                }

        }
}
int main()
{
        bool GetDirectSet( int &, string &, string &, char &, string & precept );
        void Debug( int );
        void CalculateFirstVtSet( int );
        void CalculateLastVtSet( int );
        void PrintFirstVtSet( int vnNum );
        void PrintLastVtSet( int vnNum );
        bool MakePriorityMatix( string , string, int, char matix[MATIX_SIZE][MATIX_SIZE] );
        void PrintPriorityMatix( string vtSet, char matix[MATIX_SIZE][MATIX_SIZE] ) ;

        int vnNum = 0;
        string vnSet,vtSet;
        string precept;
        char startN;

        char matix[MATIX_SIZE][MATIX_SIZE];
        for( int mm = 0; mm < MATIX_SIZE; mm ++ ) {
                for ( int nn = 0; nn < MATIX_SIZE; nn ++ ) {
                        matix[ mm ][ nn ] = ' ';
                }                        
        }


        if ( !GetDirectSet( vnNum, vnSet, vtSet, startN, precept ) ) {
                cerr << endl << "文法文件出错！程序退出！" << endl;
                return -1;
        }
        CalculateFirstVtSet( vnNum );
        CalculateLastVtSet( vnNum );
        PrintFirstVtSet( vnNum );
        PrintLastVtSet( vnNum );

        getchar();
        
        //cout << vnSet << endl << vtSet << endl << startN << endl << precept << endl;
        BufSort ( vtSet );
        vtSet += '#';
        precept += '#';
        precept += startN;
        precept += '#';
        
        if ( !MakePriorityMatrix( precept, vtSet, vnNum, matix ) ) {
                cerr << endl << "该文法非算符优先文法，不能生成算符优先矩阵！" ;
                getchar();
                return -1;
        }

        PrintPriorityMatix( vtSet, matix ) ;
        
        getchar();
               
        return 0;
}

还须在相同文件夹下建立文件：opg_test.txt
内容为：（例）
;Vn
R
S
P
D

;Vt
(
)
;
i

;S
S


S->D(R)
R->R|P
P->S|i
D->i