/*描述： 從文法文件中讀入終結符、非終結符、開始符、文法，輸出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[i].vnName << "  firstVtSet:" << Vn[i].firstVtSet << "  nextVnFirst:" << Vn[i].nextVnFirst  
                         << "   lastVtSet:" << Vn[i].lastVtSet << "   nextVnLast:" << Vn[i].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[i];
                s[i] = 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 != ";P" ) {
                return false;
        }
        i=-1;
        while ( inFile >> temp ) {
                if ( !isupper(temp[0]) ) {
                        return false;
                }
                i++;
                Vn[i].vnName = temp[0];
                if ( temp[1] != '-' || temp[2] != '>' ) {
                        return false;
                }
                precept += temp.substr(3)+"|";
                DoWithOneLine( Vn[i].nextVnFirst,Vn[i].firstVtSet,temp );//Get directed firstvt set
                Reverse( temp=temp.substr(3) );
                temp = "   " + temp;
                DoWithOneLine( Vn[i].nextVnLast,Vn[i].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[i] ) { same = true; break; }
                }
                if( !same ) {
                        iVtSet += jVtSet[i];
                        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[i].nextVnFirst.length(); j++ ) {
                                        for( k=0; k<vnNum; k++ ) {
                                                if ( Vn[k].vnName == Vn[i].nextVnFirst[j] )
                                                        onceMore += AddVt( Vn[i].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[i].nextVnLast.length(); j++ ) {
                                        for( k=0; k<vnNum; k++ ) {
                                                if ( Vn[k].vnName == Vn[i].nextVnLast[j] )
                                                        onceMore += AddVt( Vn[i].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[i].firstVtSet ); 
                cout << Vn[i].vnName << " : " << Vn[i].firstVtSet << endl;
        }
}
void PrintLastVtSet( int vnNum ) 
{
        void BufSort( string & );
        cout << endl << "該文法的LastVtSet為：" << endl;
        for ( int i=0; i<vnNum; i++ ) {
                BufSort( Vn[i].lastVtSet ); 
                cout << Vn[i].vnName << " : " << Vn[i].lastVtSet << endl;
        }
}
int fVnPos( char vn, int vnNum ) {
        for( int i=0; i<vnNum; i++ ) {
                if ( vn == Vn[i].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[i]) ) {
                        if ( isupper(pP[i+1]) ) return false;
                        pos = vtSet.find(pP[i+1]);
                        if ( (vnPos = fVnPos(pP[i],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[i]);
                        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[i])][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[i] == '|' ) {
                        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

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