四元式序列转换虚拟机目标代码.doc

四元式序列转换虚拟机目标代码
一、实验目的
1、熟悉和掌握四元式序列转换成目标代码的原理
2、设计一个程序，能使给定的任一四元式转换成虚拟目标代码。
二、实验步骤
1、需求分析
(1)、产生四元式序列翻译方案设计
对于产生四元式序列的翻译方案的设计，以下面的作为例子
关于赋值语句的四元式序列的翻译方案
S::=id=E{p:=lookup(id.name);
if p≠NULL then genquad(＇::＇,E.place,＇＇*p.place)
else error}
E::=E1+E2{E.place:=newtemp;
Fenquad(＇+＇, E1 .place, E2 .place,E.place)}
E::= E1 * E2 { E.place:=newtemp;
Fenquad(＇*＇, E1 .place, E2 .place,E.place)}
　　 E::= - E1 {E.place:=newtemp;
Genquad(＇NEG＇, E1.place,＇＇,E.place)}
E::=( E1){E.place:= E1 .place}
E::=id{p:=lookup(id.name);
if p≠NULL then E.place:=*p.place
else error}
其中，过程genquad(op,x,y,z)功能是生成四元式：
op
x
y
z
(2)、四元式生成目标代码
从四元式序列生成目标代码的工作的主要问题是运算分量与计算结果的存取问题，在生成目标指令时，要考虑四元式中运算分量是在寄存器中还是在内存中。当在寄存器中时，以后还会被使用否，等等。例如，对于四元式
- x y z
如果x和y都不在寄存器中，则可生成下列目标指令：
MOV x, Ri
SUB y, Ri
计算结果z在寄存器Ri中。如果寄存器Ri与寄存器Rj分别包含x与y。及x 与y的值分别在寄存器Ri 与Rj，且此四元式后不再引用x，可以为其生成目标指令：
SUB Rj ， Ri
计算结果z在Ri中。如果寄存器Ri包含x而y在内存单元，且此四元式后不再以用x，可以生成目标指令：
SUB y, Ri
或者
MOV y, Rj
SUB Rj , Ri
计算结果z仍然在Ri中
所以，生成目标代码时应考察四元式及其上下文。针对具体情况生成合适的目标指令
3、程序的源程序
(1)、source.cpp
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<fstream.h>
#include"source.h"
void change_to_source(ofstream ptemp,char*s,DLNode*dl,struct four **temp,int &Rcount,char*item1,char *item2,int i);
char karray[][4]={"+","-"," ","-","*","/"," ","<",">","<=",">=",":=","<>","go","[]="};
char array[17][7]={"add","sub","mov","neg","mpy","div","cmp","cj<","cj>","cj<=","cj>=","cj=","cj<>","goto","itof","return","call"};
struct four
{
char item[4][4];
struct four*next;
};
void init_array0(char ay[][4],int length);
void init_four(struct four **head)
{
*head=new struct four();
(*head)->next=NULL;
init_array0((*head)->item,4);
}
void add_four(struct four**fr,char parray[][4],int length)
{ struct four*temp=(*fr);
struct four*t;
while(temp->next!=NULL)
temp=temp->next;
t=new struct four();
t->next=NULL;
for(int i=0;i<length;i++)
{
strcpy(t->item[i],parray[i]);
}
temp->next=t;
}
int change_style(char* item)
{
for(int i=0;i<15;i++)
{
if(strcmp(item,karray[i])==0)
return i;
}
return -1;
}
void add_char(char *sym,int len,char ch)
{
int i=0;
while(i<len&&sym[i]!='\0')
i++;
sym[i]=ch;
}
void add_array(char array0[][4],int index,char *array1)
{
strcpy(array0[index],array1);
}
void init_array1(char*pch,int len)
{
int i=0;
while(i<len&&pch[i]!='\0')
{
pch[i]='\0';
i++;
}
}
void change(char* s,char ch,int count)
{
//char temp[5];
char temp2[5];
init_array1(s,5);
//数字转换字符
_itoa(count,temp2,10);
s[0]=ch;
strcat(s,temp2);
}
void init_array0(char ay[][4],int length)
{
for(int i=0;i<length;i++)
{
init_array1(ay[i],4);
}
}
void get_from(FILE*fp,struct four*fr)
{
int ch;
char array0[4][4];
char array1[4];
int count=0;
init_array1(array1,4);
init_array0(array0,4);

while((ch=fgetc(fp))!=EOF)
{
while(ch==' '&&ch!=EOF)
ch=fgetc(fp);
while(ch!=' '&&ch!='\n'&&ch!=EOF)
{
add_char(array1,4,ch);
ch=fgetc(fp);
}
while(ch==' '&&ch!=EOF) //+ a b t1
ch=fgetc(fp);
if(ch!=' '&&ch!='\n'&&ch!=EOF)
{
add_array(array0,count,array1);
count=(++count)%4;
fseek(fp,-1,SEEK_CUR);
init_array1(array1,4);
}
if(ch=='\n')
{
add_array(array0,count,array1);

add_four(&fr,array0,4);
count=0;
init_array1(array1,4);
init_array0(array0,4);
}
}
}
void convertor(ofstream ptemp,struct four**fr,DLNode*dl)
{
int i;
char s[6];
struct four**temp=fr;
int Rcount=0;
char item1[4],item2[4];
while((*temp)->next!=NULL)
{
//char karray[][3]={"+","-"," ","-","*","/"," ","<",">","<=",">=",":=","<>","go"};
i=change_style((*temp)->next->item[0]);
if(i==-1)
break;
else
change_to_source(ptemp,s,dl,temp,Rcount,item1,item2,i);
(*temp)=(*temp)->next;
}
}
void output(struct four*head)
{ struct four*temp=head;
while(temp->next!=NULL)
{ for(int i=0;i<4;i++)
cout<<temp->next->item[i]<<" ";
cout<<endl;
temp=temp->next;
}
}
void main()
{
FILE*fp=fopen("four.txt","r");
ofstream tempp("temp.txt");
FILE*fp2=fopen("result.txt","a+");
struct four*head=new struct four();
init_four(&head);
DLNode*head2;
ListInitiate(&head2);
get_from(fp,head);
output(head);
convertor(tempp,&head,head2);//_itoa
if(fp==NULL)
{ cout<<"DDD"<<endl;
exit(0);
}
fclose(fp);
ListOutput(head2);
}
void change_to_source(ofstream ptemp,char*s,DLNode*dl,struct four **stemp,int &Rcount,char*item1,char *item2,int i)
{
struct four *temp=(*stemp);
if(empty(dl))
{
ptemp<<"mov "<<temp->next->item[1]<<" , "<<"R"<<Rcount<<endl;
ptemp<<array[i]<<" "<<temp->next->item[2]<<" , "<<"R"<<Rcount<<endl;
change(s,'R',Rcount);
ListInsert(dl,s,temp->next->item[3]);
}
else
{
DLNode *p=dl;
init_array1(item1,4);
while(p->prior!=dl)
{
if(strcmp(temp->next->item[1],p->prior->destion)!=0)
{
p=p->prior;
}
else
{
strcpy(item1,p->prior->source);
break;
}
}
p=dl;
init_array1(item2,4);
while(p->prior!=dl)
{
if(strcmp(temp->next->item[2],p->prior->destion)!=0)
{
p=p->prior;
}
else
{
strcpy(item2,p->prior->source);
break;
}
}
if(item1[0]!='\0')
{
if(item2[0]!='\0')//////////////////////////
ptemp<<array[i]<<" "<<item1<<" , "<<item2<<endl;
else
ptemp<<array[i]<<" "<<item1<<" , "<<temp->next->item[2]<<endl;
}
else
{
if(item2[0]!='\0')
ptemp<<array[i]<<" "<<temp->next->item[1]<<" , "<<item2<<endl;
else
{
Rcount++;
ptemp<<"mov "<<temp->next->item[1]<<" , "<<"R"<<Rcount<<endl;
ptemp<<array[i]<<" "<<temp->next->item[2]<<" , "<<"R"<<Rcount<<endl;
change(s,'R',Rcount);//
ListInsert(dl,s,temp->next->item[3]);
}
}
change(s,'R',Rcount);
ListInsert(dl,s,temp->next->item[3]);
}
}
(2)、source.h
#include<stdlib.h>
#include<string.h>
struct node
{
char source[4];
char destion[4];
struct node *next;
struct node *prior;
};
typedef struct node DLNode;
int ListInitiate(DLNode**head)
{
*head=new DLNode();
if((*head)==NULL)
return 0;
(*head)->prior=*head;
(*head)->next=*head;
return 1;
}
int ListInsert(DLNode*head,char s[],char d[])
{
DLNode*p,*s0;
p=head->next ;
while(p->next!=head)
p=p->next;
s0=new DLNode();
if(s==NULL)
return 0;
strcpy(s0->source,s);
strcpy(s0->destion,d);
s0->prior=p->prior;
p->prior->next=s0;
s0->next=p;
p->prior=s0;
return 1;
}
bool empty(DLNode*head)
{
if(head->next==head)
return true;
return false;
}

//int ListDelete(
void ListOutput(DLNode*head)
{ DLNode*temp=head;
while(temp->next!=head)
{
cout<<"source "<<temp->next->source<<" ";
cout<<"destion "<<temp->next->destion<<endl;
temp=temp->next;
}
}
(3)、输入的四元式
+ a b t1
+ a c t2
- c d t4
+ t1 t2 t3
* d e t5
/ t2 t3 t5
- t1 t4 t6
- e f t7
: = a b
(4)、运行产生的结果
mov a , R0
add b , R0
mov a , R1
add c , R1
mov c , R2
sub d , R2
add R0 , R1
mov d , R3
mpy e , R3
div R1 , R2
sub R0 , R2
mov e , R4
sub f , R4
mov a , R5
cj= b , R5