first.cpp

编译原理中的First集与 Follow集生成程序

#include "first.h"
#include <algorithm>
using std::find;


inline Void
First::unique(array &v)
{// 对无序的数组 v 进行排序并且移除其中的重复元素.
    std::sort(v.begin(),v.end());
    v.erase(std::unique(v.begin(),v.end()),v.end());
}

/* 根据化简后的文法规则生成相应的 first set. */
Void
First::crt_First()
{
    // 编译原理及实践(P126)
    first_set.resize(nVns - STARTNONT);

#ifdef _DEBUG //检验产生式的合法性.

    assert(nVns-STARTNONT == nSymbols - nVts);

    for( sint32 i=0;i< nRules ; ++i )
    {
        if ( P2[i]==True)
            assert(P[ i ].size() >= 1);
    }

#endif

    Bool        changes=True;

    vector<uint32> SetsSize(first_set.size(),0);

    while(changes)
    {
        changes=False;
        array::iterator pos,pos2;

        for( sint32 i=0;i<nRules;++i )
        {//for each production
            if ( False == P2[i] )
                continue;

            array &cur_rule = P[ i ];

            // 当前产生式的左值.
            sint32  cur_L_val= cur_rule[0] - STARTNONT;

            if(cur_rule.size() <= 1)
            { // if is a empty ruler.
                pos=cur_rule.end();
            }
            else
                pos=cur_rule.begin()+1;

            register
                Bool Continue=True;

            while( Continue && pos != cur_rule.end() )
            {//for each production's item.
                
                sint32 cur_val = *pos;

                if ( cur_val < STARTNONT )
                {// 终结符
                    first_set[ cur_L_val ].push_back(cur_val);
                    Continue=False;
                }
                else
                {
                    array &tmp = first_set[cur_val - STARTNONT];

                    // 由于任意时刻 first_set 中的元素已序,而且 Null 的
                    // 值为负,因此如果存在 Null 则它在数组的第一个位置.

                    if ( !tmp.empty() && Null == tmp[0] )
                    {
                        pos2=tmp.begin()+1;
                    }
                    else
                    {
                        pos2=tmp.begin();
                        Continue=False;
                    }

#ifdef _DEBUG
                    for ( array::iterator iter=pos2;iter != tmp.end();++iter)
                        assert( *iter != Null );
#endif

                    first_set[cur_L_val].insert(first_set[cur_L_val].end() ,
                                                pos2 , tmp.end());
                }
                ++pos;

            }// while

            if ( Continue )
            {
                first_set[ cur_L_val ].push_back(Null);
            }
            
            uint32 &cur_set_size=SetsSize[cur_L_val];
            if( cur_set_size != first_set[ cur_L_val ].size())
            {
                assert(cur_set_size < first_set[cur_L_val].size());

                unique(first_set[ cur_L_val ]);

                if(cur_set_size != first_set[ cur_L_val ].size())
                {// 如果去掉重复元素后大小还不相等则有新元素加入

                    cur_set_size = first_set[ cur_L_val ].size();
                    changes=True;   // 置被改变状态标记.
                }
            }

        }// for(pos_p)

    }// while(true=Changes)

#ifdef _DEBUG

    /* 验证 first 集的合法性,正常情况下集合应该
       有序,并且每个集合至少有一个元素*/

    for(sint32 i=0;i<first_set.size();++i)
    {
        if( True == Vn2[ i ] )
        {
            assert(first_set[i].size()>0);
            for (sint32 j=1;j<first_set[i].size();++j)
                assert(first_set[i][j-1]<first_set[i][j]);
        }
    }

#endif

}


inline First::array
First::get_First(array & v)
{
    return get_First(v.begin(),v.end());
}

/* 求序列 begin ... end 的first set. */
First::array
First::get_First(const array::iterator &begin,
                 const array::iterator &end)
{
    if(begin==end)
    {
        return array();
    }
    Bool Continue=True;
    array   tmp;

    array::iterator pos=begin,pos2;

    while(Continue && pos!=end )
    {
        if (*pos < STARTNONT)
        { // 如果 *pos 是终结符.

            if( Null != *pos )
            {
                tmp.push_back(*pos);
                Continue=False;
            }
        }
        else
        {
            array &tmp2=first_set[ *pos - STARTNONT ]; //get_First(*pos);

            // first_set 内的元素已序.
            if( !tmp2.empty() && Null == tmp2[0] )
            {// 在 tmp2[0] 中含有 Null,跳过.

                pos2=tmp2.begin() + 1;
            }
            else // if(!tmp2.empty())
            {
                pos2=tmp2.begin() ;
                Continue=False;
            }

            tmp.insert(tmp.end(), pos2 ,tmp2.end());
        }

        ++pos;
    }

#ifdef _DEBUG

    for(sint32 i=0;i<tmp.size();++i)
        assert(tmp[i]!=Null);

#endif

    if (Continue)
    { // first 集含有空.
        tmp.push_back(Null);
    }

    unique(tmp);

    return tmp;
}

inline First::array
First::get_First(const sint32 token)
{
    assert(token>=1);//第一个有效终结符是从1开始存放的. 0位置存放'#'

    if(token < STARTNONT || token==Null)
    {
        return array(1,token);
    }
    else
    {
        return first_set[token-STARTNONT];
    }
}


Void
First::crt_Follow()
{
    follow_set.resize( nVns - STARTNONT );

    array SetsSize( follow_set.size() , 0);
    array tmp;

    // 往开始符号所在 follow 集合
    // 放入'#'号. '#' 存放在nVts[0].

    follow_set[S - STARTNONT].push_back(SHARP);

    Bool  changes=True;
    while(changes)
    {
        changes=False;

        sint32 i=0;
        for ( i=1 ; i<P.size() ; ++i )
        {//for each production

            if ( P2 [ i ] == False )
            { // 如果是无用产生,直接跳过.
                
                continue;
            }

            sint32 cur_L_val = P[i][0] - STARTNONT ;

            array::iterator pos,pos2;

            if (P[i].size() <= 1)
            { // 空产生式不用处理.

                pos=P[i].end();
            }
            else
                pos=P[i].begin()+1;

            for( ; pos!=P[i].end() ; ++pos)
            {//for each production's item.

                if( *pos < STARTNONT )
                    continue;//终结符不用求follow set.

                sint32 cur_val = *pos - STARTNONT ;

                if(pos+1 == P[i].end())
                {//处理 B->αA 的情况.

                    if( cur_val != cur_L_val )// 不为 A->αA 的情况.
                    {
                        follow_set[ cur_val ].insert(
                            follow_set[ cur_val ].end(),
                            follow_set[ cur_L_val ].begin(),
                            follow_set[ cur_L_val ].end()
                            );

                        unique(follow_set[ cur_val ]);
                    }
                }
                else
                {
                    assert( *pos >= STARTNONT && pos+1 != P[i].end());

                    tmp = get_First( pos+1,P[i].end() );

                    //pos2=std::find(tmp.begin(),tmp.end(),Null);
                    //if( pos2!=tmp.end() )// && *pos!=P[i][0])
                    //    tmp.erase(pos2);

                    if ( !tmp.empty() && Null == tmp[0] )
                    { // A->αB r 并且 r 包含 Null ,B != A 的情况.
                        if (cur_val != cur_L_val)
                        {
                            follow_set[ cur_val ].insert(
                                follow_set[ cur_val ].end(),
                                follow_set[ cur_L_val ].begin(),
                                follow_set[ cur_L_val ].end()
                                );
                        }
                        pos2 = tmp.begin() + 1;
                    }
                    else
                    {
                        pos2 = tmp.begin();
                    }

                    follow_set[ cur_val ].insert(
                        follow_set[ cur_val ].end(),
                        pos2,
                        tmp.end()
                        );
                    unique(follow_set[ cur_val ]);//防止数据膨胀
                }

            }// for(pos)
        }//for (sint32 i)
        //这里不用统一地对所有follow_set求unique()
    
        for(i=0;i < follow_set.size();++i)
        {
            if( SetsSize[i] != follow_set[i].size() )
            {
                SetsSize[i] = follow_set[i].size();
                changes=True;
            }
        }

    }// while

}

inline First::array&
First::get_Follow(const sint32 token)
{
    //只能求非终结
    //符的follow set.
    assert(token >=STARTNONT );
    return (follow_set[ token - STARTNONT ]);
}

Void
First::print_Version(string version)
{
    foutput<<endl<<version<<endl;
}

Void
First::print_First()
{
    foutput<<endl<<endl<<endl<<"First sets:"<<endl<<endl;
    sint32 i,j;
    for( i=0;i<first_set.size();++i)
    {   
        if ( Vn2[ i ]!=False )
        { // 只显示有效非终结符的集合.
            foutput<<Vns[i]<<":\n\t";
            for( j=0;j<first_set[i].size();++j)
            {
                if (first_set[i][j]==Null)
                    foutput<<"@Null ";
                else
                    foutput<<Vts[first_set[i][j]]<<' ';
            }
            foutput<<endl;
        }
    }
}

Void
First::print_Follow()
{
    foutput<<endl<<endl<<endl<<"Follow sets:"<<endl<<endl;
    uint32 i,j;
    for( i=0;i<follow_set.size();++i)
    {   
        if (Vn2[ i ]!=False )
        { // 只显示有效非终结符的集合.
            foutput<<Vns[i]<<":\n\t";
            for(j=0;j<follow_set[i].size();++j)
            {   
                if(follow_set[i][j]==Null)
                    assert(0);
                else
                    foutput<<Vts[follow_set[i][j]]<<' ';
            }
            foutput<<endl;
        }
    }
}