compile3.cpp

一个不算完整的编译器实现

#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<fstream>
#include<algorithm>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;

//-------------------------------------------------------------------------------------
//语义分析所需结构及静态常量变量声明
//-------------------------------------------------------------------------------------
#define max_table 10000
//变量符号表最大个数
#define SHIFT 4
//哈希函数移位数目
static int offset=0;//偏移地址
static int level=-1;//函数的层数
//-------------------------------------------------------------------------------------
FILE *middlefile;
struct ParseTreeNode//分析树的结点
{
	string name;
	string value;
	vector<int> next;
};
//-------------------------------------------------------------------------------------
struct table_var
{//变量符号表结构
	string name;//名字
    int address;
	string type;//类型属性
	int value;//值属性
	int lineno;//行号
	int level;//层号
	table_var* next;
	table_var(){next=NULL;type="";}
};
struct table_funct
{//过程/函数符号表结构
	string name;//名字属性
	string re_type;//返回值类型属性
    int re_value;//返回值
	int size_param;//参数个数
	vector<string> param_type;//记录参数类型
	int lineno;//行号
	int level;//层号
	table_funct* next;
	table_funct(){next=NULL;size_param=0;}
};
static table_var* tableVar[max_table];//变量符号表
static table_funct* tableFunct[max_table];//函数/过程符号表
static stack<string>stack_type;
//-------------------------------------------------------------------------------------
void show_parse_tree(ofstream &puttree,vector<ParseTreeNode> &parse_tree,int level,int nodenum,bool *has)
{//level表示层数
    int i;
	for(i=0;i<level-1;i++)
	{
        if(has[i])//要画竖线的时候
        {
            puttree << "  │ ";
        }
        else
        {
            puttree << "    ";
        }
    }
    for(;i<level;i++)
    {
        if(has[i])
        {
            puttree << "  ├─";
        }
        else puttree << "  └─";
    }
	puttree << parse_tree[nodenum].value << endl;
	for(int i=parse_tree[nodenum].next.size()-1;i>=0;i--)
	{
		int next=parse_tree[nodenum].next[i];
		if(i>0) has[level]=true;
		else has[level]=false;
		show_parse_tree(puttree,parse_tree,level+1,next,has);
	}
}
/*生成中间代码，已知一棵已经建立好的分析树 
struct ParseTreeNode{
    string name;
	string value;
	vector<int> next; 
}
vector<ParseTreeNode> parse_tree;//分析树

首先传递的是根结点的地址 
*/
//-----------------------------------------------------------------------
int inum=0;                 //函数中语句的个数 
int temp_num=0;             //中间变量的个数 
int label_num=0;
void generate(ParseTreeNode &BT,vector<ParseTreeNode> &parse_tree){
     //--------------处理一般的语句------------------
     if(BT.name=="call"){
       int where_is_ID;
       for(int i=0;i<BT.next.size();i++){
         if(parse_tree[BT.next[i]].name=="ID"){
           where_is_ID=i;  
         }       
       }
       /*  BT.next[where_is_ID]是ID子结点的号，parse_tree[BT.next[where_is_ID]]  
        *　是ID子结点，parse_tree[BT.next[where_is_ID]].next[0]是放终结符的结点 
        *  号，parse_tree[parse_tree[BT.next[where_is_ID]].next[0]].name是IDstring 
        */
       fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s\n",inum,"CALL",parse_tree[BT.next[where_is_ID]].value.c_str(),"-","-");
       inum++;                    
     }
     if(BT.name=="factor"){
       if(BT.next.size()==3){//说明是 factor ( expression )语句
         int where_is_expr;
         for(int i=0;i<3;i++){
           if(parse_tree[BT.next[i]].name=="expression"){
             where_is_expr=i;
             break;
           }
         }
         generate(parse_tree[BT.next[where_is_expr]],parse_tree); //处理expression的情况
       }
       else if(parse_tree[BT.next[0]].name=="var"){    //说明是 factor var语句
         if(parse_tree[BT.next[0]].next.size()==1){    //说明是 var ID语句
           fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s%d\n",inum,"=",parse_tree[parse_tree[BT.next[0]].next[0]].value.c_str(),"-","buctcs2005_",temp_num);
           temp_num++;
           inum++;
         }else{                                        //说明是 var ID [ expression ]语句
           int where_is_expr;
           int where_is_ID;
           for(int i=0;i<4;i++){
             if(parse_tree[parse_tree[BT.next[0]].next[i]].name=="expression")
               where_is_expr=i;
             if(parse_tree[parse_tree[BT.next[0]].next[i]].name=="ID")
               where_is_ID=i;        
           }
           generate(parse_tree[parse_tree[BT.next[0]].next[where_is_expr]],parse_tree);
           fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s%d %-11.11s%d\n",inum,"[]=",parse_tree[parse_tree[BT.next[0]].next[where_is_ID]].value.c_str(),"buctcs2005_",temp_num-1,"buctcs2005_",temp_num);
           inum++;
           temp_num++;     
         }
       }
       else if(parse_tree[BT.next[0]].name=="call"){        //说明是 factor call语句
         generate(parse_tree[BT.next[0]],parse_tree);
       }
       else if(parse_tree[BT.next[0]].name=="constant"){    //说明是 factor constant 语句
          if(parse_tree[parse_tree[BT.next[0]].next[0]].name=="NUM"){
            fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s%d\n",inum,"=",parse_tree[parse_tree[BT.next[0]].next[0]].value.c_str(),"-","buctcs2005_",temp_num);
            temp_num++;
            inum++;
          }
          if(parse_tree[parse_tree[BT.next[0]].next[0]].name=="true"||parse_tree[parse_tree[BT.next[0]].next[0]].name=="false"){
            fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s%d\n",inum,"=",parse_tree[parse_tree[BT.next[0]].next[0]].value.c_str(),"-","buctcs2005_",temp_num);
            temp_num++;
            inum++;
          }
       }
     }
     if(BT.name=="unary-expression"){
        if(BT.next.size()==1){  //说明是 unary-expression factor语句
          generate(parse_tree[BT.next[0]],parse_tree);
        }else{                  //说明是unary-expression unaryop unary-expression语句
          int where_is_unary_expr;
          int where_is_unaryop;
          for(int i=0;i<2;i++){
            if(parse_tree[BT.next[i]].name=="unary-expression"){
              where_is_unary_expr=i;
            } 
            if(parse_tree[BT.next[i]].name=="unaryop"){
              where_is_unaryop=i;                                
            }       
          }
          generate(parse_tree[BT.next[where_is_unary_expr]],parse_tree);
          fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s %-11.11s%d\n",inum,parse_tree[parse_tree[BT.next[where_is_unaryop]].next[0]].value.c_str(),"buctcs2005_",temp_num-1,"-","buctcs2005_",temp_num);
          temp_num++;
          inum++;
        }
     }
     if(BT.name=="term"){
        if(BT.next.size()==1){                 //说明是term unary-expression语句 
             generate(parse_tree[BT.next[0]],parse_tree);                
        } else{                                //说明是term term mulop unary-expression语句 
          int where_is_unary_expr;
          int where_is_term;
          int where_is_mulop;
          for (int i=0;i<3;i++){
            if(parse_tree[BT.next[i]].name=="term")
              where_is_term=i;
            if(parse_tree[BT.next[i]].name=="unary-expression")
              where_is_unary_expr=i;
            if(parse_tree[BT.next[i]].name=="mulop")
              where_is_mulop=i;    
          }
          int opr_temp;
          generate(parse_tree[BT.next[where_is_term]],parse_tree);
          opr_temp=temp_num-1;
          generate(parse_tree[BT.next[where_is_unary_expr]],parse_tree);
          fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s%d %-11.11s%d\n",inum,parse_tree[parse_tree[BT.next[where_is_mulop]].next[0]].value.c_str(),"buctcs2005_",opr_temp,"buctcs2005_",temp_num-1,"buctcs2005_",temp_num);
          inum++;
          temp_num++;
        }  
     }
     if(BT.name=="additive-expression"){
        if(BT.next.size()==1){              //说明是additive-expression term语句     
          generate(parse_tree[BT.next[0]],parse_tree);
        }else{                              //说明是additive-expression additive-expression addop term  语句 
          int where_is_add_expr;
          int where_is_addop;
          int where_is_term;
          for (int i=0;i<3;i++){
            if(parse_tree[BT.next[i]].name=="additive-expression")
              where_is_add_expr=i;
            if(parse_tree[BT.next[i]].name=="addop")
              where_is_addop=i;
            if(parse_tree[BT.next[i]].name=="term")
              where_is_term=i;    
          }
          int oper_temp;
          generate(parse_tree[BT.next[where_is_add_expr]],parse_tree);
          oper_temp=temp_num-1;
          generate(parse_tree[BT.next[where_is_term]],parse_tree);
          fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s%d %-11.11s%d\n",inum,parse_tree[parse_tree[BT.next[where_is_addop]].next[0]].value.c_str(),"buctcs2005_",oper_temp,"buctcs2005_",temp_num-1,"buctcs2005_",temp_num);
          temp_num++;
          inum++;
        }                       
     }
     if(BT.name=="simple-expression"){
       if(BT.next.size()==1){         //说明是simple-expression additive-expression语句 
            generate(parse_tree[BT.next[0]],parse_tree);
       } else{                        //说明是simple-expression additive-expression relop additive-expression语句 
          int where_is_add_expr1;
          int where_is_relop;
          int where_is_add_expr2;
          int times=0;
          for(int i=0;i<3;i++) {
            if (parse_tree[BT.next[i]].name=="additive-expression"&&times==0){
                   where_is_add_expr1=i;
                   times++;                                                  
            }
            if (parse_tree[BT.next[i]].name=="additive-expression"&&times==1){
                  where_is_add_expr2=i;                                                      
            }
            if(parse_tree[BT.next[i]].name=="relop"){
              where_is_relop=i;
            }
          } 
          int oper_temp;
          generate(parse_tree[BT.next[where_is_add_expr1]],parse_tree) ;
          oper_temp=temp_num-1;
          generate(parse_tree[BT.next[where_is_add_expr2]],parse_tree) ;
          fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s%d %-11.11s%d\n",inum,parse_tree[parse_tree[BT.next[where_is_relop]].next[0]].value.c_str(),"buctcs2005_",oper_temp,"buctcs2005_",temp_num-1,"buctcs2005_",temp_num);
          temp_num++;
          inum++;
       }                          
     }
     if(BT.name=="var"){
           if(BT.next.size()==1){    //说明是 var ID语句
           fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s%d\n",inum,"=",parse_tree[BT.next[0]].value.c_str(),"-","buctcs2005_",temp_num);
           temp_num++;
           inum++;
         }else{                                        //说明是 var ID [ expression ]语句
           int where_is_expr;
           int where_is_ID;
           for(int i=0;i<4;i++){
             if(parse_tree[BT.next[i]].name=="expression")
               where_is_expr=i;
             if(parse_tree[BT.next[i]].name=="ID")
               where_is_ID=i;        
           }
           generate(parse_tree[BT.next[where_is_expr]],parse_tree);
           fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s%d %-11.11s%d\n",inum,"[]=",parse_tree[BT.next[where_is_ID]].value.c_str(),"buctcs2005_",temp_num-1,"buctcs2005_",temp_num);
           inum++;
           temp_num++;     
         }                
     }
     if(BT.name=="expression"){
       if(BT.next.size()==1){   //说明是expression simple-expression语句
         if(parse_tree[BT.next[0]].name=="simple-expression"){
             generate(parse_tree[BT.next[0]],parse_tree);
         }
       }else{                   //说明expression var = expression语句
           int where_is_var;
           int where_is_expression;
           for(int i=0;i<3;i++){
             if(parse_tree[BT.next[i]].name=="var")
               where_is_var=i;
             if(parse_tree[BT.next[i]].name=="expression")
               where_is_expression=i;
           } 
           generate(parse_tree[BT.next[where_is_var]],parse_tree);
           generate(parse_tree[BT.next[where_is_expression]],parse_tree);
           if(parse_tree[BT.next[where_is_var]].next.size()==1){
             fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s %-11.11s\n",inum,"=","buctcs2005_",temp_num-1,"-",parse_tree[parse_tree[BT.next[where_is_var]].next[0]].value.c_str());
             inum++;
           }else{
             fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s %-11.11s%d\n",inum,"=","buctcs2005_",temp_num-1,"-","buctcs2005_",temp_num-2);
             inum++;     
           }
        }
     }
     if(BT.name=="return-stmt"){
       if(BT.next.size()==2){                  //说明是 return-stmt return ;语句
         fprintf(middlefile,"%-6d %-11.11s %-11.11s %-11.11s %-11.11s\n",inum,"RETURN","-","-","-");
       }else{                                  //说明是return-stmt return expression语句
         int where_is_expression;
         for(int i=0;i<2;i++){
           if(parse_tree[BT.next[i]].name=="expression"){
             where_is_expression=i;
           }  
         }
         generate(parse_tree[BT.next[where_is_expression]],parse_tree);
         fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %-11.11s %-11.11s\n",inum,"RETURN","buctcs2005_",temp_num-1,"-","-");
         inum=0;
       }
       
     } 
     if(BT.name=="selection-stmt"){
       if(BT.next.size()==5){       // 说明是selection-stmt if ( expression ) statement 语句                              
         int where_is_expr;
         int where_is_stmt;
         for(int i=0;i<5;i++){
           if(parse_tree[BT.next[i]].name=="expression")
                where_is_expr=i;
           if(parse_tree[BT.next[i]].name=="statement")
                where_is_stmt=i;     
         }
         int judge_num;
         string l1="Lable";
         generate(parse_tree[BT.next[where_is_expr]],parse_tree);
         judge_num=temp_num-1;
         fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %s%-5d %-6s\n",inum,"IF_F","buctcs2005_", judge_num,l1.c_str(),label_num,"-"  );
         inum++;
         generate(parse_tree[BT.next[where_is_stmt]],parse_tree);
         fprintf(middlefile,"%s%d\n",l1.c_str(),label_num);
         label_num++;
       }
     }
     if(BT.name=="iteration-stmt"){//说明是iteration-stmt while ( expression ) statement语句 
         int where_is_expr;
         int where_is_stmt;
         for(int i=0;i<5;i++){
           if(parse_tree[BT.next[i]].name=="expression")
             where_is_expr=i;
           if(parse_tree[BT.next[i]].name=="statement")
             where_is_stmt=i;        
         }              
         int judge_num;
         string l1="Lable";
         string l2="Lable";
         fprintf(middlefile,"%s%d\n",l1.c_str(),label_num);
         generate(parse_tree[BT.next[where_is_expr]],parse_tree) ;
         judge_num=temp_num-1;
         fprintf(middlefile,"%-6d %-11.11s %-11.11s%d %s%-5d %-11.11s\n",inum,"IF_F","buctcs2005_",judge_num,l2.c_str(),label_num+1,"-");
         inum++; 
         
         generate(parse_tree[BT.next[where_is_stmt]],parse_tree) ;
         fprintf(middlefile,"%-6d %s %s%-5d %-11.11s %-11.11s\n",inum,"GOTO",l1.c_str(),label_num , "-","-" );
         inum++;
         fprintf(middlefile,"%s%d\n",l2.c_str(),label_num+1);
         label_num+=2;
     }
     //--------------寻找一般的语句------------------
     if(BT.name=="expression-stmt"){//说明是expression-stmt expression ;
                                    //expression-stmt ;语句 
       if(BT.next.size()==2){
         int where_is_expr;
         for(int i=0;i<2;i++)
           if(parse_tree[BT.next[i]].name=="expression")
             where_is_expr=i;
         generate(parse_tree[BT.next[where_is_expr]],parse_tree);                   
       }                               
     }
     if(BT.name=="statement"){
     /*说明是statement expression-stmt
      *　　statement compound-stmt
      *　　statement selection-stmt
      *　　statement iteration-stmt
      *　　statement return-stmt语句 
      */
         generate(parse_tree[BT.next[0]],parse_tree);                  
     }
     if(BT.name=="statement-list"){
        /*说明是 statement-list statement-list statement
            statement-list #(不予处理)语句 
        */
        if(BT.next.size()==2){
          int where_is_stmt_list;
          int where_is_stmt;
          for(int i=0;i<2;i++){
            if(parse_tree[BT.next[i]].name=="statement")
              where_is_stmt=i;
            if(parse_tree[BT.next[i]].name=="statement-list") 
              where_is_stmt_list=i;
          }
          generate(parse_tree[BT.next[where_is_stmt_list]],parse_tree);
          generate(parse_tree[BT.next[where_is_stmt]],parse_tree); 
        }      
     }
     if(BT.name=="compound-stmt"){//说明是compound-stmt { local-declarations statement-list }语句 
        int where_is_loc_dec;   //local-declarations 可以不处理，因为声明语句不生成中间代码 
        int where_is_stmt_list; 
        for(int i=0;i<4;i++){
          if(parse_tree[BT.next[i]].name=="local-declarations") 
            where_is_loc_dec=i;
          if(parse_tree[BT.next[i]].name=="statement-list")
            where_is_stmt_list=i;      
        } 
        generate(parse_tree[BT.next[where_is_stmt_list]],parse_tree) ;
                       
     }
     //函数的处理情况 
     if (BT.name=="fun-declaration"){//说明是fun-declaration type-specifier ID ( params ) compound-stmt语句
       int where_is_ID;
       int where_is_com_stmt;
       for(int i=0;i<6;i++){
         if(parse_tree[BT.next[i]].name=="ID")
           where_is_ID=i;
         if(parse_tree[BT.next[i]].name=="compound-stmt") 
           where_is_com_stmt=i;       
       }
       string ID_temp;
       ID_temp=parse_tree[BT.next[where_is_ID]].value;
       fprintf(middlefile,"%s\n",ID_temp.c_str());
       generate(parse_tree[BT.next[where_is_com_stmt]],parse_tree);
       temp_num=0;
       inum=0;
     }
     if(BT.name=="declaration"){
       if(parse_tree[BT.next[0]].name=="fun-declaration"){
         generate(parse_tree[BT.next[0]],parse_tree) ;    }                      
     }
     if(BT.name=="declaration-list"){ //declaration-list declaration-list declaration
                                      //declaration-list declaration
         if(BT.next.size()==1)
           generate(parse_tree[BT.next[0]],parse_tree) ;                            
         else {
           int where_is_dec_list;
           int where_is_dec;
           for(int i=0;i<2;i++){
             if(parse_tree[BT.next[i]].name=="declaration-list")
                   where_is_dec_list=i;
             if(parse_tree[BT.next[i]].name=="declaration")
                   where_is_dec=i;          
           }  
          
           generate(parse_tree[BT.next[where_is_dec_list]],parse_tree)   ;
            generate(parse_tree[BT.next[where_is_dec]],parse_tree)   ;
         }
     }
     if(BT.name=="program"){
          generate(parse_tree[BT.next[0]],parse_tree) ;                       
     }
}


//----------------------------------------------------------------------------------------------------------------------
//                                       语义分析部分
//----------------------------------------------------------------------------------------------------------------------
void sematic_init()
{//符号表初始化
	memset(tableVar,0,sizeof(tableVar));
	memset(tableFunct,0,sizeof(tableFunct));
	while(!stack_type.empty())
		stack_type.pop();
}
//哈希函数
int hash_funct(string name)
{
	int index=0;
	for(int i=0;i<name.length();i++)
	{
		index=((index<<SHIFT)+name[i])%max_table;
	}
	return index;
}
void p_error(string s)
{
	ofstream sematic_error;
    sematic_error.open("system\\error.txt");
	sematic_error<<s<<endl;
	sematic_error.close();
	exit(0);
}
void sematic_success(string s)
{
	ofstream sematic_suc;
	sematic_suc.open("system\\error.txt");
	sematic_suc<<s;
	sematic_suc.close();
}
/*1program declaration-list*/
/*2declaration-list declaration-list declaration */
/*3declaration-list declaration*/
/*4declaration var-declaration*/
/*5declaration fun-declaration*/
/*6var-declaration type-specifier ID ;*/
void typeID(string name)
{
	//查找type-specifier
    int index2=hash_funct("type-specifier"); 
    table_var* temp1=tableVar[index2];
	while(temp1!=NULL)
	{