parse.h

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

/*
 *	file:  parse.h
 */
#if _MSC_VER >1200  /* msvc6 or later */
#pragma once
#endif

#ifndef __PARSE_H_
#define __PARSE_H_

#include <string>
#include <vector>
#include <set>
#include <fstream>
#include <iostream>
#include <sstream>
#include <exception>
#include <utility>
#include <cassert>
#include "types.h"
#include "lex.h"
#include "cmd.h"

using std::wcout;
using std::cout;
using std::endl;

using std::ostringstream;
using std::ostream;
using std::istream;
using std::string;
using std::exception;
using std::vector;
using std::set;
using std::ofstream;

class Parse
{
protected:
    typedef vector<vector<sint32> >
        biarray;
    typedef vector< sint32 >
        array;

public: // data

    /* 终结符结合率值 (0表示没有设置结合率)*/
    enum Assoc{NON_ALLOC=1,L_ALLOC,R_ALLOC};

    vector<string> Vns;     //非终结符字符串集

    /* Vts[0]存放文件结束标志'#'  */
    vector<string> Vts;     //终结符字符串集
    sint32 nVns;            //非终结符数
    sint32 nVts;            //终结符数
    sint32 S;               // Start Symbol
    biarray P;              //每一维数组的第0下标为产生式左部

    // P2 中存放产生式的编号,Vn2及Vt2中存放非终结符及终结符编号.
//    set<sint32> Vt2,Vn2,P2;
    vector<Bool > Vn2,Vt2,P2;
    uint32 nVns2,nVts2,nSymbols2,nRules2;
    ////////////////////////////////////////////////


    sint32 lookahead;       // 向前查看符号 

    sint32 nSymbols;        // 全部符号数
    sint32 nRules;          // 规则数
    
    vector< sint32 >
        rPrec,tPrec;        // 规则及终结符的优先级(值为0表示未指定)

    vector< sint32 >
        rAssoc,tAssoc;      // 规则及终结符的结合性(值为0表示未指定)

    vector< sint32 >
        tNumVal;            // 声明token时指定的值. e.g. %token ID 222
                            // 值为 -1 表示未指定.

    vector< sint32 > rline;   // 规则所在行号.
    vector< sint32 > actline; //


    // 存放 terminal and nonterminal的union域值索引,如果值为 -1 表示
    // 不存在 union 值域.
    vector< sint32 >  tUnion; // symbol's union value.
    vector< sint32 >  nontUnion;
    vector< string >  sUnion; // 存放 union 值域字符串值.

    biarray first_set;
    biarray follow_set;

    Lex & lex;
    Cmd & cmd;
public: // function
    Parse(Lex &L,Cmd &C);

    Void start_parse();

    //求序列begin~end的first集
    vector<sint32> get_First(const array::iterator &begin,
                             const array::iterator &end);

    //求序列v的first集.
    inline
        vector<sint32> get_First(vector<sint32> &v);

    //求文法中token的first集.
    vector<sint32> get_First(const sint32 token);

    //求文法中token的follow集.
    inline
        vector<sint32> get_Follow(sint32 token);
    void        print_First();      //打印first集
    void        print_Follow();     //打印follow集
    void        print_Rulers(); //打印产生式
    void        print_Terminals();   //打印终结符
    void        print_Nonterminals();//打印非终结符

    Void
        Parse::show_Rule(const sint32 n,ostream &out);
    inline Void
        Parse::show_Symbol(const sint32 sym , ostream &out);
    /***********************************/

    Void clear()
    {//有必要时删除主要的数组以释放空间
        P.clear();
        Vns.clear();
        Vts.clear();
    }

    Void fatal();
private:  // function
    Void        crt_First();  //Create First Set.
    Void        crt_Follow(); //Create Follow Set.
    Void        reduce();       //文法化简.

    //// 语法分析器扫描器(递归下降法)
    Void spec();
    Void defines();
    Void rules();
    Void tail();
    Void nlist(const sint32 , sint32 cur_assoc=0 ,sint32 cur_prec=0);
    Void nlist2(const sint32);
    Void rbodys(const sint32);
    sint32 rbody(vector<sint32>&rule,Bool &IsHaveAct);
    sint32 prec(const vector<sint32>&rule, Bool &IsHaveAct);

    Void eat_up_rest();
    Void eat_up_union();
    Void eat_up_defs();
    Void eat_act(const vector<sint32> &cur_rule);
    sint32
        symtype();
    Bool match(sint32 token);
    inline sint32 
        insert_Vts(const string &val, const sint32 cur_assoc,
                   const sint32 cur_prec,const sint32 unionval,
                   const sint32 number);
    inline sint32 
        insert_Vns(const string &val, const sint32 unionval);
    inline sint32
        insert_ruler(const vector<sint32> & rule,const sint32 cur_prec,
                     const sint32 cur_assoc,const sint32 lineno);

    inline sint32
        isinVts(const string&);
    inline virtual sint32
        isinVns(const string&);

    sint32 r_check(sint32 r);   // 检查文法规则 r 是否与别的文法产生重复
    //////////////////////////////
    void showErr();

public://private:  // data
    ofstream of_cpp;  // output file of source file.
    ofstream of_h;    // output file of header file.
    ofstream foutput; // 
    ofstream fdefine;   // C语言定义部分.
    ofstream faction;   // 动作存放文件.
    
    uint32   nerror;
    ostringstream err_msg;
    string union_define;

protected:
    const sint32 STARTNONT; // 非终结符的起始位置.
    const sint32 Null ;//= -100;
    const sint32 SHARP;//=0; // '#' 

    sint32      size(const vector<Bool> &vec);
};

#endif /* __PARSE_H_ */