parse.cpp

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

            match(Lex::TOKEN);

            index=symtype();

            nlist(index,0,0);
            break;

        case Lex::LEFT:
        case Lex::RIGHT:
        case Lex::NONASSOC:
            ++curPrec;          // current precedence.
            match(lookahead);

            index=symtype();

            nlist(index,lookahead,curPrec);
            break;

        case Lex::TYPE:
            match(Lex::TYPE);
            index=symtype();

            nlist2(index);
            break;

        case Lex::START:
            match(Lex::START);
            if(Lex::ID == lookahead)
            {
                index=isinVns(lex.strval);
                
                if(index == -1)
                { // 如果开始符号没有事先定义.
                    S=insert_Vns(lex.strval,-1);
                    //nontUnion.push_back(-1);
                }
                else
                {
                    S=index;
                }

                match(Lex::ID);
            }
            else
            {//error
                err_msg<<"\"%start\"后缺少标识符.";
                fatal();
            }
            //defines();
            break;

        case Lex::UNION:
            eat_up_union();
            Continue=True;
            match(Lex::UNION);
            break;

        default:
            Continue=False;
            break;
        }//switch(lookahead)
    }// while(Continue)
}

//symtype:  /* empty */
//    |   '<' eat_up_symtype '>'
//    ;
sint32
Parse::symtype()
{ // 返回值为 -1 表明不存在 <xxx>定义.
    if('<'==lookahead)
    {// 将 "<xx>" 中的全部内容读入stype中.
        string sval;
        sint32 index;

        register c=lex.pf.get();
        sval.clear();
        while('>'!=c && Lex::ENDOFFILE!=c)
        {
            sval+=c;
            c=lex.pf.get();
        }
        if(Lex::ENDOFFILE==c)
        {
            err_msg<<"非正常的文件结束.";
            fatal();
        }
//        if( !sval.empty() )
        // 不管 “<xx>”中是否有内容均将其插入sUnion中。
        // 因此注释 if  判断语句。
        { 
            vector<string>::const_iterator iter =
                 std::find(sUnion.begin(),sUnion.end(),sval);
            if( iter==sUnion.end() )
            {
                sUnion.push_back(sval);
                index=sUnion.size()-1;
            }
            else
                index=iter - sUnion.begin();
        }
        //else
        //{
        //    index = -1;
        //}
        match('<');
        return index;
    }// if
    else
        return -1;
}

//nlist : factor
//    |   factor nlist
//    |   factor ',' nlist
//    ;
//factor: ID
//    |   ID NUM       /* there has a error for TYPE */
//    |   ASC
//    |   ASC NUM
//    ;

Void
Parse::nlist(const sint32 stype , sint32 cur_assoc ,sint32 cur_prec)
{ // assoc=0 表示未指定结合率.prec=0 表示未指定优先级.
    register sint32 index;
    while(Lex::ID == lookahead || Lex::ASC == lookahead)
    {
        index=isinVts(lex.strval);
        if(-1 == index)
        {
            index = insert_Vts(lex.strval,cur_assoc,cur_prec,
                               stype,lex.numval);

            //tPrec.push_back(cur_prec);
            //tAssoc.push_back(cur_assoc);
            //tNumVal.push_back(-1); // -1 表示未指定值.
            //tUnion.push_back(stype);
        }
        else
        { // 符号重定义.
            tPrec[index]=cur_prec;
            tAssoc[index]=cur_assoc;
            //tNumVal[index]= -1;
            tUnion[index]=stype;
        }

        match(lookahead);
        if(Lex::NUM == lookahead)
        {
            tNumVal[index]=lex.numval;
            match(Lex::NUM);
        }
        if(',' == lookahead)
            match(',');

    }// while()
}

//nlist2 : factor2
//    |    factor2 nlist2
//    |    factor2 ',' nlist2
//    ;
//factor2: ID
//    |    ASC
//    ;
Void
Parse::nlist2(const sint32 stype)
{// 在%type定义中,如果出现终结符则仅给其 union值域赋值,否则作为非终结符处理.
    register sint32 index;
    if( -1 == stype )
    {
        err_msg<<"关键字 '%type' 后必须包含 '<xxx>' 说明.";
        showErr();
    }
    while( Lex::ID == lookahead || Lex::ASC==lookahead )
    {
        if ( Lex::ASC==lookahead )
        {
            if( (index=isinVts(lex.strval)) == -1)
                insert_Vts(lex.strval,0,0,stype,lex.numval);
            else
                tUnion[index] = stype;
        }
        else
        {
            if((index=isinVts(lex.strval)) != -1)
            { // 已定义的终结符 ID
                tUnion[index] = stype;
            }
            else
            { // 未定义的非终结符ID
                index=isinVns(lex.strval);
                if( -1 == index )
                {
                    index=insert_Vns(lex.strval,stype);
                // nontUnion.push_back(stype);
                }
                else
                {
                    nontUnion[index-STARTNONT]=stype;
                }         
            }
        }
        match(Lex::ID);
    }// while()
}

//rules : ID ':' rbodys ';' rules
//    | /* empty */
//    ;
Void
Parse::rules()
{
    register sint32 index;
    string rlval;   // the rule's left value.
    while( Lex::ID == lookahead )
    {
        rlval=lex.strval;

        match(Lex::ID);
        if( ':' == lookahead )
        {
        /* 检查 ID 是否属于终结符集,是则错误
         */
            if (isinVts(rlval)!=-1)
            {
                err_msg<<"终结符\""<<rlval<<"\"不能作为产生式左部.";
                showErr();
            }
            index = isinVns(rlval);
            if ( -1 == index )
                index = insert_Vns(rlval,-1);

            /****/
            if ( S < STARTNONT )
                S=index;
            /****/

            match(':');

            assert ( index >= STARTNONT );

            rbodys(index);

            if(';'==lookahead)
                match(';');
            else
            {
                err_msg<<"规则定义缺少 ';' .";
                showErr();
            }

        }
        else
        {   // 如果不匹配,则忽略剩余的符号直到下一个 ';'
            err_msg<<"规则定义缺少 ':' .";
            showErr();
            while( ';' != lookahead &&
                   Lex::ENDOFFILE != lookahead)
            {
                match(lookahead);
            }
            if(Lex::ENDOFFILE == lookahead)
            {
                err_msg<<"非正常的文件结束.";
                fatal();
            }
            match(';');   // read next symbol.
        }// else
    }// while
}

//rbodys: '|' rbody prec rbodys
//    |   ID  rbody prec rbodys
//    |   ASC rbody prec rbodys
//    |   '{' rbody prec rbodys
//    |   PREC      prec rbodys /* 处理由 %prec 指定优先级的空产生式.*/
//    |   ';'                   /* 处理分号前边可能产生的空产生式*/
//    ;
Void
Parse::rbodys(const sint32 rl_ID)
{
    register Bool   Continue=True;
    register sint32 tLast;  // 每个产生式的最后一个终结符.
    register sint32 tPrecedence;  // 通过 %prec 关键字指定的终结符.
             sint32 thisruleno;  // 产生式所在行.
             sint32 assoc,precedence;
             Bool   FirstTime=True;

             // 是否已经存在了动作.主要用于处理 %prec ID 前边同时
             // 进行动作说明时的冲突处理.
             Bool   IsHaveAct=False;
    while(Continue)
    {
        vector<sint32>  rule;   //识别出的规则.
        rule.push_back(rl_ID);
        thisruleno = lex.lineno;
        IsHaveAct  = False ;
        tLast      = -1;

        switch(lookahead)
        {
        case '|':

            if(True==FirstTime)
            { // expr : | ;
                insert_ruler(rule,0,0,thisruleno);
            }

            match('|');
            thisruleno=lex.lineno;
            //break;
        case Lex::ID:
        case Lex::ASC:
        case '{':

            tLast=rbody(rule,IsHaveAct);

        case Lex::PREC:

            FirstTime=False;

            tPrecedence=prec(rule,IsHaveAct);
            if( -1 == tLast )
            { // 
                assoc=0;
                precedence=0;
            }
            else
            { // 将终结符 tLast 的优先级与结合率转移给产生式.
                assoc=tAssoc[tLast];
                precedence =tPrec [tLast];
            }
            if( -1 != tPrecedence )
            { // 如果存在 %prec 指定产生的优先级.
                // assoc=tAssoc[tPrecedence];
                precedence =tPrec [tPrecedence];
            }

            if( !IsHaveAct )
            {
                /*
                 *	如果产生没有定义动作,在这里进行相应的处理.
                 */
            }

            insert_ruler(rule,precedence,assoc,thisruleno);
            if( ';'==lookahead )
                return;
            break;

        case ';': // 正常结束.
            
            assert(rule.size()==1);

            // 插入此空产生式.
            insert_ruler(rule,0,0,thisruleno);
            //Continue=False;
            return ;

        default:
            //err_msg<<"在规则定义中使用了不正确的符号 "<<lex.strval.c_str()<<" .";
            //fatal();

            //match(lookahead);// read next token.
            Continue=False;
            break;
        }// switch
    }// while
}

//rbody : /* empty */
//    |   ID  rbody
//    |   ASC rbody
//    |   '{' eat_act '}'           /* common action*/
//    |   '{' eat_act '}' ID  rbody /* panel action */
//    |   '{' eat_act '}' ASC rbody /* panel action */
//    |   '{' eat_act '}' '{' rbody /* panel action */
//    ;
sint32
Parse::rbody(vector<sint32> &cur_rule,Bool &IsHaveAct)
{ // 如果不存在终结符则返回 -1.
    static sint32 panel_act_num=1;
    sint32   index;
    sint32   tLast=-1;
    register Bool   Continue=True;
    
//    cur_rule.resize(1); // cur_rule[0] 已经存放产生式的左部.
    IsHaveAct=False;
    while(Continue)
    {
        switch(lookahead)
        {
        case Lex::ID:

            index=isinVts(lex.strval);
            if(-1 == index )
            {// 如果不是终结符.
                index=isinVns(lex.strval);
                if(-1 == index) // 并且不在非终结符集中.
                    index=insert_Vns(lex.strval,-1); // 则插入.
            }
            else
            {
                tLast=index;
            }
            cur_rule.push_back(index);

            match(Lex::ID);
            break;

        case Lex::ASC: // !!!! '\188' '\295' '\x33' 等进行check.
            index=isinVts(lex.strval);
            if( -1 == index )
            {
                //index=insert_Vts(lex.strval,0,0,-1,-1);
                index=insert_Vts(lex.strval,0,0,-1,lex.numval);