[转帖]我先来发个。 算符优先文法的算法（大三编译课作业三）

gladrain

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

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


#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;fstream&gt;
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 &lt;&lt; endl &lt;&lt; "Debuging..." &lt;&lt; endl;
        for ( int i=0; i&lt;vnNum; i++ ) {
                cout &lt;&lt; "name:" &lt;&lt; Vn.vnName &lt;&lt; "  firstVtSet:" &lt;&lt; Vn.firstVtSet &lt;&lt; "  nextVnFirst:" &lt;&lt; Vn.nextVnFirst  
                         &lt;&lt; "   lastVtSet:" &lt;&lt; Vn.lastVtSet &lt;&lt; "   nextVnLast:" &lt;&lt; Vn.nextVnLast &lt;&lt; endl;
        }
        cout &lt;&lt; "Debug ends" &lt;&lt; endl;
        getchar();
}
void DoWithOneLine( string &amp; nextVn, string &amp; vtSet,string temp )
{
        bool flag = true;
        for ( int j=3; j&lt;temp.length(); j++ ) {
                if ( isupper(temp[j]) ) {
                        nextVn += temp[j];
                        if ( j+1 &gt;= temp.length() ) break;
                        if ( temp[j+1] != '|' )
                                vtSet += temp[j+1];
                        while ( true ) {
                                if ( temp[j] == '|' ) {
                                        flag = false;
                                        break;
                                }
                                if ( j &gt;= temp.length() ) {
                                        flag = true;
                                        break;
                                }
                                j++;
                        }
                        if (flag) break;
                        else continue;
                } else {
                        vtSet += temp[j];
                        while ( true ) {
                                if ( temp[j] == '|' || j &gt;= temp.length() ) break;
                                j++;
                        }
                }
        }
}
void Reverse( string &amp; s )
{
        int n = s.length();
        char t;
        for( int i=0; i&lt;n/2; i++ ) {
                t = s;
                s = s[n-i-1];
                s[n-i-1] = t;
        }
}
bool GetDirectSet( int &amp; vnNum, string &amp; vnSet, string &amp; vtSet, char &amp; startN, string &amp; precept )
{
        void DoWithOneLine( string &amp; nextVn, string &amp; vtSet,string temp);
        void Reverse( string &amp; 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 &gt;&gt; temp;
        if ( temp != "" ) {
                return false;
        }
        i=-1;
        while ( inFile &gt;&gt; temp ) {
                if ( !isupper(temp[0]) ) {
                        return false;
                }
                i++;
                Vn.vnName = temp[0];
                if ( temp[1] != '-' || temp[2] != '&gt;' ) {
                        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 &amp; a )
{
        int i,j,flag,t;
        int n = a.length();
        for ( i=0; i&lt;n-1; i++ ) {
                flag = 0;
                for( j=0; j&lt;n-1-i; j++ )
                        if( a[j]&gt;a[j+1] ) {
                                t = a[j];
                                a[j] = a[j+1];
                                a[j+1] = t;
                                flag = 1;
                        }
                if ( !flag )
                        return;
        }
}

int AddVt( string &amp; iVtSet, string jVtSet )
{
        bool same,hasAdd;
        int i,j;
        hasAdd = false;
        for( i=0; i&lt;jVtSet.length(); i++ ) {
                same = false;
                for( j=0; j&lt;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&lt;vnNum; i++ ) {
                                for( j=0; j&lt;Vn.nextVnFirst.length(); j++ ) {
                                        for( k=0; k&lt;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&lt;vnNum; i++ ) {
                                for( j=0; j&lt;Vn.nextVnLast.length(); j++ ) {
                                        for( k=0; k&lt;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 &amp; );
        cout &lt;&lt; endl &lt;&lt; "该文法的FirstVtSet为：" &lt;&lt; endl;
        for ( int i=0; i&lt;vnNum; i++ ) {
                BufSort( Vn.firstVtSet );
                cout &lt;&lt; Vn.vnName &lt;&lt; " : " &lt;&lt; Vn.firstVtSet &lt;&lt; endl;
        }
}
void PrintLastVtSet( int vnNum )
{
        void BufSort( string &amp; );
        cout &lt;&lt; endl &lt;&lt; "该文法的LastVtSet为：" &lt;&lt; endl;
        for ( int i=0; i&lt;vnNum; i++ ) {
                BufSort( Vn.lastVtSet );
                cout &lt;&lt; Vn.vnName &lt;&lt; " : " &lt;&lt; Vn.lastVtSet &lt;&lt; endl;
        }
}
int fVnPos( char vn, int vnNum ) {
        for( int i=0; i&lt;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 &gt;= 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&lt;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&lt;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 &lt; pP.length() &amp;&amp; !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&lt;precept.length(); i++ ) {
                if ( precept == '|' ) {
                        if ( i-j&gt;1 ) {
                                if ( !AnalyzeThisPiecePrecept( precept.substr(j,i-j), vtSet, vnNum, matix ) )
                                        return false;
                        }
                        j = i+1;
                }
        }
        if ( i-j&gt;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 &lt;&lt; "\n★:优于　☆:低于　◎:同级" &lt;&lt; endl &lt;&lt; "  | ";
        for( int m=0; m&lt;vtSet.length() ; m++ ) {
                cout &lt;&lt; vtSet[m] &lt;&lt; "   " ;
        }
        for( m=0; m&lt;vtSet.length(); m++ ) {
                cout &lt;&lt; endl &lt;&lt; vtSet[m] &lt;&lt; " | ";
                for( int n=0; n&lt;vtSet.length(); n++ ) {
                        switch ( matix[m][n] ) {//★◎☆
                        case 'G': cout &lt;&lt; "★  "; break;
                        case 'L': cout &lt;&lt; "☆  "; break;
                        case 'E': cout &lt;&lt; "◎  "; break;
                        default:  cout &lt;&lt; "    ";  
                        }
                }

        }
}
int main()
{
        bool GetDirectSet( int &amp;, string &amp;, string &amp;, char &amp;, string &amp; 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 &lt; MATIX_SIZE; mm ++ ) {
                for ( int nn = 0; nn &lt; MATIX_SIZE; nn ++ ) {
                        matix[ mm ][ nn ] = ' ';
                }                        
        }


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

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

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

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

;Vt
(
)
;
i

;S
S


S-&gt;D(R)
R-&gt;R|P
P-&gt;S|i
D-&gt;i

希望感兴趣的同学一块讨论，我还会陆续把我大二时写的一些小程序发上来</FONT>