parse.cpp

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

/*
 *	file:  parse.cpp
 */
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include "Parse.h"

#define match(x) lookahead=lex.gettoken()

Parse::Parse(Lex &L,Cmd &C):lex(L),cmd(C)
      ,STARTNONT(10000),Null(-100),SHARP(0)
{
    nVns=STARTNONT;
    nVts=0;
    nRules=0;
    nSymbols=0;
    nerror=0;

    S=-1;

    insert_Vts(string("@sharp"),0,0,-1,-1);
    //Vts.push_back("@sharp");

    insert_ruler(vector<sint32>(),0,0,1);
    //P.resize(1);

    /*************/
    //of_cpp.open( (cmd.get_ifname()+"_out.cpp").c_str() );
    //if(!of_cpp)
    //{
    //    err_msg<<"打开文件 _out.cpp 错误.";
    //    fatal();
    //}
    //fdefine.open( "fdefine.cpp" );
    //if(!fdefine)
    //{
    //    err_msg<<"打开文件 fdefine.cpp 错误.";
    //    fatal();
    //}
    //faction.open( "faction.cpp" );
    //if( !faction )
    //{
    //    err_msg<<"打开文件 faction.cpp 错误.";
    //    fatal();
    //}


    string output(cmd.get_ifname()+".out.txt");
    foutput.open( output.c_str() );
    if(!foutput)
    {
        err_msg<<"打开文件 "<< output <<" 错误!请检查错误原因,然后重试.";
        fatal();
    }

}

//返回非 -1 表示 str不存在于Vns中,否则返回其所在的下标
inline sint32 
Parse::isinVns(const string& str)
{   
    std::vector<std::string>::const_iterator row
        = std::find(Vns.begin(),Vns.end(),str);
    return row==Vns.end() ? -1 : ( (sint32)(row - Vns.begin())+STARTNONT );
}

inline sint32
Parse::isinVts(const string& str)
{
    std::vector<std::string>::const_iterator row
        = std::find(Vts.begin(),Vts.end(),str);
    return row==Vts.end() ? -1 : (sint32)(row - Vts.begin());
}


inline sint32
Parse::insert_Vts(const string &val, const sint32 cur_assoc,
                  const sint32 cur_prec,const sint32 unionval,
                  const sint32 number)
{
    nVts++;
    nSymbols++;
    Vts.push_back(val);
    tUnion.push_back(unionval);
    tPrec.push_back(cur_prec);
    tAssoc.push_back(cur_assoc);
    tNumVal.push_back(number);
     
    return nVts-1;
}

inline sint32
Parse::insert_Vns(const string &val,const sint32 unionval)
{
    /*
     *	检查当前符号是否已经存在.
     */
    nVns++;
    nSymbols++;
    Vns.push_back(val);
    nontUnion.push_back(unionval);
    // 
    return nVns-1;
}

inline sint32
Parse::insert_ruler(const vector<sint32> &rule,const sint32 prec,
                    const sint32 assoc , const sint32 lineno)
{// 返回当前产生式在P中的位置.
    /*
     *	检查当前产生式是否已经存在,如果已经存在则提示错误信息.
         ...没做...
     */
    // check ...

    nRules++;
    P.push_back(rule);
    rAssoc.push_back(assoc);
    rPrec .push_back(prec);
    rline .push_back(lineno);
    return nRules - 1;
}


//spec  : defines MARK rules tail
//            ;
Void
Parse::spec()
{
    lookahead=lex.gettoken();
    defines();
    if(Lex::MARK==lookahead)
    {
        match(Lex::MARK);
        rules();
        tail();
    }
    else
    {// do errors.
        err_msg<<"规则定义缺少 '%%' 标记.";
        showErr();
    }
    if(Lex::END!=lookahead || lex.nerror+nerror > 0)
    {
        //err_msg<<"共有 "<< lex.nerror+nerror <<" 个错误,语法分析失败.";
        //fatal();
        cout<<"共有 "<< lex.nerror+nerror <<" 个错误,语法分析失败.";
        exit(1);
    }
}

/*
tail  : MARK eat_up_rest
| // empty (检测,如果不是文件末尾则出错)
;
*/
Void
Parse::tail()
{
    if(Lex::MARK==lookahead)
    {// 将剩余的部分输出到 of_cpp 文件中.
        eat_up_rest();
    }
    else if(Lex::END!=lookahead)
    {
        err_msg<<"缺少 '%%' 标记.";
        showErr();
    }
}

Void
Parse::eat_up_rest()
{// 将文法文件的剩余部分写入 of_cpp 的尾部.
    of_cpp<<"\n#line "<<lex.lineno<<" \""<<cmd.get_ifname()<<"\"\n";
    char buf[101];
    register uint32 count=0;
    do{
        lex.pf.get(buf,sizeof(buf)/sizeof(buf[0]),Lex::ENDOFFILE);
        count=lex.pf.gcount();
        of_cpp.write(buf,count);
    }while(sizeof(buf)/sizeof(buf[0])-1 == count);

    lookahead=0;
}

Void
Parse::eat_up_union()
{//将union的定义拷贝到变量 union_define 中 .
    static Bool once=True;
    if (!once)
    {
        err_msg<<"'%union' 多重定义.";
        showErr();
    }
    else
        once=False;

    sint32 count=0;
    sint32 c;
    while((c=lex.pf.get())!='{')
        if('\n'==c)
            lex.lineno;

    lex.pf.unget();
    union_define="";
    do{
        c=lex.pf.get();
        if('{'==c)
            ++count;
        else if('}'==c)
            --count;
        else if('\n'==c)
            ++lex.lineno;
        else if(Lex::ENDOFFILE==c)
        {
            err_msg<<"未终结的 '%union' 定义.";
            fatal();
        }
        union_define+=(char)c;
    }while(count!=0);
}

Bool
eat_up_comment(ostream & out,istream &in,uint32 &lineno, 
               const sint32 Eof=-1)
{ // 假定已经是以 '/*' 或 '//' 开头的注释,从下一个字符开始读取 直到 '*/'.
    register sint32 c;

    out.put(in.get());
    c=in.get();
    out.put(c);

    if('*'==c)
    {// c's comment.
        register Bool Continue=True;
        do
        {
            while((c=in.get()) != '*' && '\n' != c
                    && Eof !=c )
                out.put(c);

            if('*'==c && (in.peek()=='/'))
                Continue=False;

            else if('\n'==c)
                ++ lineno;
            
            else if('*'==c && (in.peek()!='/'))
                ;

            else // if( Eof == c )
                return False;

            out.put(c);
            if(!Continue)
                out.put(in.get());//写入 '/'.
        } while(Continue);
    }
    else
    {// c++'s comment. 不考虑'\' 续行.
        while( '\n'!=(c=in.get()) && Eof != c )
            out.put(c);
        if('\n'==c)
            ++ lineno;
        else
            return False;
        out.put('\n');
    }
    return True;
}

/**************************************************
*从输入 in 中读取从 " 到下一个 " 的内容到 out 中, *
*如果遇到行尾的 '\'续行符,则行号加1,下一行继续当作*
*字符串处理,如果遇到 Eof 则返回 False,否则返回True*/
Bool
eat_up_string(ostream & out,istream &in,uint32 &lineno, 
              const sint32 Eof=-1)
{
    register Bool instring=True;
    register sint32 c;

    out.put(in.get()); // write '\"'

    while(instring)
    {
        while( '\"'!=(c=in.get()) && '\\'!= c 
           && '\n'!=c && Eof != c )
        {
            out.put(c);
        }
        out.put(c);

        if('\"'==c)
            instring=False;

        else if('\\'==c)
        {
            c=in.get();
            if('\"' == c || '\\'==c)    // 转义
                out.put(c);

            else if('\n'==c) // 续行
                out.put('\n'),
                ++ lineno;

            else             // 其它
                in.unget();
        }

        else if('\n'==c)
            ++ lineno,
            instring=False;

        else // if(Eof == c)
            return False;
    } // while(instring)
    return True;
}

Void
Parse::eat_up_defs()
{// read lex.pf until '%}'
    /** 注意 字符串及注释中的内容应该忽略 **/
    register Bool incomment=False,
             instring=False,
             Continue=True;
    ofstream &file=fdefine;
    register sint32 c;
    file<<"\n#line "<<lex.lineno<<" \""<<cmd.get_ifname()<<"\"\n";
    while(Continue)
    {
        c=lex.pf.get();
        if('/'==c)
        {
            if('/'==lex.pf.peek() || '*'==lex.pf.peek())
            {
                lex.pf.unget();
                if (!eat_up_comment(fdefine,lex.pf,lex.lineno,Lex::ENDOFFILE))
                {
                    err_msg<<"在注释中出现错误.";
                    fatal();
                }
            }
            else
                fdefine.put(c);


        }
        else if('%'==c)
        {
            //file.put(c);
            if('}'!=lex.pf.peek())
                continue;
            else
                lex.pf.get(),//file.put(lex.pf.get()),
                Continue=False;
        }
        else if('\"'==c)
        { // string.
            lex.pf.unget();
            if(!eat_up_string(fdefine,lex.pf,lex.lineno,Lex::ENDOFFILE))
            {
                err_msg<<"文件非法终止.";
                fatal();
                Continue=False;
            }

        }
        else if('\n'==c)
            file.put(c),
            ++lex.lineno;
        else if(Lex::ENDOFFILE==c)
        {
            err_msg<<"未终结的 '%{' 定义.";
            fatal();
        }
        else
            file.put(c);
    }// while(Continue)
    lookahead=Lex::RCURL;
}

/*
defines: // empty
|   START    ID                 defines
|   UNION    eat_up_union       defines
|   LCURL    eat_up_defs RCURL  defines
|   TOKEN    symtype            nlist
|   LEFT     symtype            nlist
|   RIGHT    symtype            nlist
|   NANASSOC symtype            nlist
|   TYPE     symtype            nlist2
;
*/
Void
Parse::defines()
{
    register sint32 curPrec=0;  //优先级(0表示未指定优先级)
    register sint32 index;
    register Bool   Continue=True;
    string stype;               // 

    while(Continue)
    {
        Continue=True;

        switch(lookahead)
        {
        case Lex::LCURL:
            eat_up_defs();
            //Continue=True;
            match(Lex::RCURL);
            break;

        case Lex::TOKEN: