optimize.cpp

一个简单的类C语言的编译器的实现 可以参考学习编译原理的基本实现

#include<stdio.h>
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

//四元式flag用来区分jmp指令和非jmp指令的标志 jmp指令比较特殊，它的第四个域是整型
struct sentence
{
	char op[8];
	char argu1[8];
	char argu2[8];
	char result[8];
	int flag;            
	int jmpforth;        
};
struct point{
	int x,y;
};
vector<sentence> sen;
vector<int>in_list,out_list;
vector<bool>flagl,flags;
vector<point> point0;

bool  get_s(char*s,	FILE * fex);
int findinlist(int n,vector<int> & list);
void in_stock_optimize();
bool cmp1(const int & n1, const int & n2)
{
	return (n1<n2);
}
void pit(int n);
int optimize()
{
	
	FILE * fex,*F;
    sentence node;
	int look,i,j;
	bool flag;
	char c;
	
	if(fex = fopen("emit.txt","r+"))
		do 
		{
			if((flag =get_s(node.op,fex)))
			{
				if((flag =get_s(node.argu1,fex)))
				{
					if((flag =get_s(node.argu2,fex)))
					{
						if(((c = fgetc(fex)))>='0' && c <= '9')
						{
							ungetc(c,fex);
							node.flag = 1;
							fscanf(fex,"%d",&node.jmpforth);
							fgetc(fex);
						}
						else
						{
							ungetc(c,fex);
							node.flag = 0;
							flag =get_s(node.result,fex);
						}
						flags.push_back(true);
						sen.push_back(node);
						
					}
				}
			}
		}while(flag);
		in_list.push_back(0);
		for(i=0;i<sen.size();i++)
		{
			if((!strcmp(sen[i].op,"j<")) || (!strcmp(sen[i].op,"j")))
			{
				if(findinlist(i,out_list)==-1)
					out_list.push_back(i); 
				if(findinlist(i+1,in_list)==-1)
					in_list.push_back(i+1);
				if(findinlist(sen[i].jmpforth,in_list)==-1)
					in_list.push_back(sen[i].jmpforth);
				if(findinlist(sen[i].jmpforth-1,out_list)==-1)
					out_list.push_back(sen[i].jmpforth-1);
			}
			else if(!strcmp(sen[i].op,"end"))
			{
				out_list.push_back(i);
			}
		}
		for(i=0;i<in_list.size();i++)
		{
			flagl.push_back(false);
		}
		sort(in_list.begin(), in_list.end(), cmp1);
		sort(out_list.begin(), out_list.end(), cmp1);
		pit(0);
		for(j=0;j<flagl.size();j++)
		{
            if(flagl[j]==false)
			{
				in_list.erase(in_list.begin()+j);
				out_list.erase(out_list.begin()+j);
				flagl.erase(flagl.begin()+j);
				j--;
			}
		}
		F=fopen("source.asm","w");
        in_stock_optimize();
        int k=0;
		for(i=0;i<in_list.size();i++)
		{
    		fprintf(F,"t %d: \n",in_list[i]);
			for(j=in_list[i];j<=out_list[i];j++)
			{
				if(flags[j]==true)
				{
					if(sen[j].flag)      //是否为jmp产生式
					{
						if(!strcmp(sen[j].op,"j<"))
						{
							fprintf(F,"mov ax %s\n",sen[j].argu1);
							fprintf(F,"cmp ax %s\n",sen[j].argu2);
							fprintf(F,"jl  t %d\n",sen[j].jmpforth);
						}
						else if(!strcmp(sen[j].op,"j"))
						{
							fprintf(F,"jmp  t %d\n",sen[j].jmpforth);
						}
						else if(!strcmp(sen[j].op,"end"))
						{
							fprintf(F,"exit  \n");
						}
					}
					else
					{
						if(!strcmp(sen[j].op,"="))
						{
							fprintf(F,"mov ax %s\n",sen[j].argu1);
							fprintf(F,"mov %s ax\n",sen[j].result);
						}
						else if(!strcmp(sen[j].op,"+"))
						{
							fprintf(F,"mov ax %s\n",sen[j].argu1);
							fprintf(F,"add ax %s\n",sen[j].argu2);
							fprintf(F,"mov %s ax\n",sen[j].result);
						}
						else if(!strcmp(sen[j].op,"*"))
						{
							fprintf(F,"mov ax %s\n",sen[j].argu1);
							fprintf(F,"mul ax %s\n",sen[j].argu2);
							fprintf(F,"mov %s ax\n",sen[j].result);
						}
						else if(!strcmp(sen[j].op,"-"))
						{
							fprintf(F,"mov ax %s\n",sen[j].argu1);
							fprintf(F,"neg ax %s\n",sen[j].argu2);
							fprintf(F,"mov %s ax\n",sen[j].result);
						}
					}
					k++;
				}
			}
		}
		fclose(F);
		return 1;
}
int findinlist(int n,vector<int> & list)
{
    int i;
    for(i=0;i<list.size();i++)
	{
		if(n== list[i])
		{
			return i;
		}
	}
	
	return	-1;
}
bool  get_s(char*s,	FILE * fex)
{
	char c;
	int i=0;
	
	while((c = fgetc(fex))!=',' && c != '\n' && c != EOF)
	{
		s[i]=c;
		i++;
	}
	s[i]='\0';
	if(c == EOF)
		return false;
	return true;
}
void pit(int n)
{
	point node1;
	if(!strcmp(sen[out_list[n]].op,"j<"))
	{
		flagl[n]=true;
		node1.x=n;
		if((node1.y=findinlist(sen[out_list[n]].jmpforth,in_list))!=-1)
		{
			point0.push_back(node1);

			if(node1.y<flagl.size()&&flagl[node1.y]==false)
			{
				pit(node1.y);
			}
		}
		node1.x=n;
		if((node1.y=findinlist(out_list[n]+1,in_list))!=-1)
		{
			point0.push_back(node1);
			if(node1.y<flagl.size()&&flagl[node1.y]==false)
			{
				pit(node1.y);
			}
		}
	}
	else if(!strcmp(sen[out_list[n]].op,"j"))
	{
		node1.x=n;
		flagl[n]=true;
		if((node1.y=findinlist(sen[out_list[n]].jmpforth,in_list))!=-1)
		{
			point0.push_back(node1);
			if(node1.y<flagl.size()&&flagl[node1.y]==false)
			{
				pit(node1.y);
			}
		}
	}
	else
	{
		node1.x=n;
		int loof = out_list[n]+1;
		flagl[n]=true;
		if((node1.y=findinlist(out_list[n]+1,in_list))!=-1)
		{
			point0.push_back(node1);
			if(node1.y<flagl.size()&&flagl[node1.y]==false)
			{
				pit(node1.y);
			}
		}
	}
}
void in_stock_optimize()
{
     
	char temp[8];
	int look1,look2,look3,look,j,k;
	for(int i=0;i<in_list.size();i++)
	{
		for(j=in_list[i];j<=out_list[i];j++)
		{
			if(sen[j].flag==0)
			{
				look=out_list[i];
				look1=sen[j+1].flag;
				look2=strcmp(sen[j+1].result,sen[j].result);
            for(k=j+1;k<=out_list[i]&&sen[k].flag==0&&strcmp(sen[k].result,sen[j].result);k++)
			{
				if((!strcmp(sen[j].argu1,sen[k].argu1))&&(!strcmp(sen[j].argu2,sen[k].argu2)))
				{
			       	look=out_list[i];
				    look1=sen[k+1].flag;
				    look2=strcmp(sen[k+1].result,sen[k].result);
					for(int u=k+1;u<=out_list[i]&&sen[u].flag==0&&strcmp(sen[u].result,sen[k].result);u++)
					{
                            strcpy(temp,sen[k].result);
                            strcpy(temp,sen[u].argu1);
                           if(!strcmp(sen[u].argu1,sen[k].result))
						   {
							   strcpy(sen[u].argu1,sen[j].result);
						   }
						   else if(!strcmp(sen[u].argu2,sen[k].result))
						   {
							   strcpy(sen[u].argu2,sen[j].result);
						   }
					}
					flags[k]=false;
				}
			}
			}
		}
	}
}