ll1-yuyi.cpp

ll(1)语义分析器

#include <iostream.h>
#include <stdio.h>
#include <stack>
#include<stdlib.h>
#define  m  20//first集的大小
#define rulenum 34//产生式数目
#define vnnum 20//非终节符的数目
#define vtnum 24//终节符的数目

struct gram//产生式数据结构
{	
	int right[m];//右部产生式编号串
	int length;//右部长度
	int left;//左部节点编号
};
struct gram rulegram[rulenum]={{{1,10,11,32,12},5,31 },{{34,33},2,32},{{34,33},2,33},{{24},0,33},
	{{11,32,12},3,34},{{36,45,3},3,35},{{2},1,36},{{35,34},2,34},
	{{4,45,5},3,37},{{37,34,6},3,38},{{38,34},2,34},{{10,15,46,13},4,34},{{39,40,13},3,34},
	{{22},1,39},{{10,41},2,40},{{14,10,41},3,41},{{24},0,41},{{17,45,18},3,42},{{7},1,42},
	{{8},1,42},{{10,43,46},3,42},{{21},1,43},{{16,42,44},3,44},{{24},0,44},{{42,44},2,45},
	{{48,47},2,46},{{19,48,47},3,47},{{24},0,47},{{50,49},2,48},{{20,50,49},3,49},{{24},0,49},
	{{17,46,18},3,50},{{10},1,50},{{9},1,50}};//所有产生式，rulenum为产生式编号

int first[rulenum][m]={{1},{11,2,4,22,10},{11,2,4,22,10},{24},{11},{2},{2},{2},{4},{4},{4},
	{10},{22},{22},{10},{14},{24},{17},{7},{8},{10},{21},{16},{24},{17,7,8,10},{17,10,9},
	{19},{24},{17,10,9},{20},{24},{17},{10},{9}};//初始化first集

int follow[vnnum][m]={{0},{0},{12},{0},{0},{0},{0},{0},{0},{0},{13},{0},{0},
		    {18,3,5,13},{0},{0},{18,13,16,3,5},{0},{18,16,13,19,3,5},{0}};//初始化follow集

char  VNname[vnnum]={'K','L','M','S','U','W','C','F','T','D','N','V','O','A','B','E','G','H','R','P'};//用于保存非终结符编号
char  VTname[vtnum][m]={"func","while","do","if","then","else","ture","false","const",
						"id","{","}",";",",","=","&","(",")","+","*","<","int","$","empty"}; //用于保存终结符编号

int LL1table[vnnum][vtnum];//预测分析表的结构

//分析栈
struct stacktype
{
	int set[100];
	int top;
};
struct stacktype stack;
int idstr[100]; //纪录标示符
int idtop=0;  //纪录标示符的位置
int nfirst=0; //第一个标示符的位置
int nlast=0;  //最后一个标示符的位置
struct valtype //计算型标示符的属性类型
{
	int place[100];
	int top;
};
struct valtype eval, gval, hval, rval, pval;
char * newvari[10]={"t1","t2","t3","t4","t5","t6","t7","t8","t9","t10"};//中间代码
int varicount=0;
struct codetype  //四元组类型
{
	char act[10];
	char op1[10];  //第一个操作数
	int num1;
	char op2[10]; //第二个操作数
	int num2;
	char result[10];
	int temp;   //下一个跳转语句
};
struct codetype code[100];
int nextquad=0;  //下一个四元组标号
int whead, uhead, mquad;
char ttype[10],relop_op[10];
struct entrytype  //符号表类型
{
	char idname[10];
	int addr;
	char type[10];
};
struct entrytype symbol[100];
int stop=0;
struct toktype  //tok字类型
{
	int id;
	int entry;
};
struct toktype tok[100];
int top=0;
struct digittype //常数表类型
{
	int value;
	int entry;
};
struct digittype digit[100];
struct varnext  //非终结符的下一个跳转语句的结构类型
{
	int tnext[10];
	int ttop;
	int fnext[10];
	int ftop;
};
struct varnext vnext[20];
struct vartype   //声明语句中的标示符
{
	char type[10];
	int addr[100];
	int top;
};
struct vartype dlist;
struct idtype
{
	int entry[100];
	int top;
};
struct idtype idstack;//纪录遇到的标示符

//初始化预测分析表
void initiate()
{
	int i=0,j;
	for (i;i<vnnum;i++)
	{
		for (j=0;j<vtnum;j++)
		{
			LL1table[i][j]=-1;//初始化为－1
		}
	}
}
//构造预测分析表
void createtype()
{
	int i=0,b;
	for (i;i<rulenum;i++)//
	{
		int flag=0;
		for (int j=0;j<m;j++)
		{
			if (first[i][j]==24)//如果first集中有空产生式
				flag=1;		
		}
		if (flag==1)
		{
			for (int k=0;k<m;k++)
			{
				b=follow[rulegram[i].left-31][k];//	有空产生式看follow集
				if(b!=0)
				LL1table[rulegram[i].left-31][b-1]=i;//填分析表	
			}
		}
		else//无空产生式看first集
		{
			for (int k=0;k<m;k++)
			{
				b=first[i][k];
				if(b!=0)
				LL1table[rulegram[i].left-31][b-1]=i;//填分析表		
			}

		}
	}
}

void read()//读token字
{
	FILE    *fp1,*fp2,*fp3;   
	int i=0;
    fp1=fopen("token.txt","r");   
    if(fp1==NULL)   
    {   
        printf("Cannot   open   the   file!");   
        exit(0);   
    }   
    while(fscanf(fp1,"%d%d",&tok[i].id,&tok[i].entry)!=EOF)   
    {   
	   i++;
    }  
    fclose(fp1);
	tok[i].id=23;//串尾放$符
	tok[i].entry=-1;
	fp2=fopen("fuhao.txt","r");
	if(fp2==NULL)   
    {   
         printf("Cannot   open   the   file!");   
         exit(0);   
    }   
	i=0;
    while(fscanf(fp2,"%s%d",symbol[i].idname,&symbol[i].addr)!=EOF)   
    {   
		i++;
    }  
	stop=i;
    fclose(fp2);
	fp3=fopen("digit.txt","r");
	if(fp3==NULL)   
    {   
       printf("Cannot   open   the   file!");   
       exit(0);   
    } 
	i=0; 
    while(fscanf(fp3,"%d%d",&digit[i].entry,&digit[i].value)!=EOF)   
    {   
		i++;
    }  
   fclose(fp3);
	//初始化
   for(i=0;i<20;i++)
   {
		vnext[i].ttop=0;
		vnext[i].ftop=0;
   }
   idstack.top=-1;
   eval.top=-1;
   gval.top=-1;
   hval.top=-1;
   rval.top=-1;
   pval.top=-1;
   return;
}
void emit(char* s, char* s1,int t1, char* s2, int t2,char* s3, int t)
{
	strcpy(code[nextquad].act,s);
	strcpy(code[nextquad].op1,s1);
	strcpy(code[nextquad].op2,s2);
	strcpy(code[nextquad].result,s3);
	code[nextquad].num1=t1;
	code[nextquad].num2=t2;
	code[nextquad].temp=t;
	nextquad++;
}
void outcode()
{
	int i;
	FILE* ffu;

	printf("输出四元组\n");
	for(i=0;i<nextquad;i++)
	{
		if(code[i].num1==-1)
		{
			if(code[i].num2==-1)
			{
				if(strcmp(code[i].result,"")==0)
					printf("%d(%s,%s,%s,%d)\n",i,code[i].act,code[i].op1,code[i].op2,code[i].temp);
				else
					printf("%d(%s,%s,%s,%d)\n",i,code[i].act,code[i].op1,code[i].op2,code[i].result);
			}
			else
			{
				if(strcmp(code[i].result,"")==0)
					printf("%d(%s,%s,%d,%d)\n",i,code[i].act,code[i].op1,code[i].num2,code[i].temp);
				else
					printf("%d(%s,%s,%d,%d)\n",i,code[i].act,code[i].op1,code[i].num2,code[i].result);
			}
		}
		else
		{
			if(code[i].num2==-1)
			{
				if(strcmp(code[i].result,"")==0)
					printf("%d(%s,%d,%s,%d)\n",i,code[i].act,code[i].num1,code[i].op2,code[i].temp);
				else
					printf("%d(%s,%d,%s,%d)\n",i,code[i].act,code[i].num1,code[i].op2,code[i].result);
			}
			else
			{
				if(strcmp(code[i].result,"")==0)
					printf("%d(%s,%d,%d,%d)\n",i,code[i].act,code[i].num1,code[i].num2,code[i].temp);
				else
					printf("%d(%s,%d,%d,%d)\n",i,code[i].act,code[i].num1,code[i].num2,code[i].result);
			}
		}
	}

	if((ffu=fopen("fu.txt","w"))==NULL)
	{
		printf("file cannot open\n");
		exit(0);
	}
	for(i=0;i<stop;i++)
		fprintf(ffu,"%6s%6d%6s\n",symbol[i].idname,symbol[i].addr,symbol[i].type);
	fclose(ffu);
}
//回填函数
void backpatch(int p, int t)
{
	int r, q=p;
	while(q!=0)
	{
		r=code[q].temp;
		code[q].temp=t;
		q=r;
	}
}
//连接函数
int merge(int p1, int p2)
{
	int p;
	
	if(p2==0)
		return p1;
	else
	{
		p=p2;
		while(code[p].temp!=0)
			p=code[p].temp;
		code[p].temp=p1;
		return p2;
	}
}

void s0()//k
{
	backpatch(vnext[1].tnext[vnext[1].ttop],nextquad);
	emit("end","",-1,"",-1,"",0);
}
void s1()//L->SM
{
	vnext[1].tnext[++vnext[1].ttop]=merge(vnext[3].tnext[vnext[3].ttop],vnext[2].tnext[vnext[2].ttop]);
}
void s2()//M->SM
{
	vnext[2].tnext[++vnext[2].ttop]=merge(vnext[3].tnext[vnext[3].ttop],vnext[2].tnext[vnext[2].ttop]);
	vnext[3].ttop--;
}
void s3()//M->epsilon
{
	vnext[2].tnext[++vnext[2].ttop]=0;
}
void s4()//s->{l}
{
	vnext[3].tnext[vnext[3].ttop]=vnext[1].tnext[vnext[1].ttop];
}
void s5()//u->wbdo
{
	backpatch(vnext[14].tnext[vnext[14].ttop],nextquad);
	vnext[4].tnext[++vnext[4].ttop]=vnext[14].fnext[vnext[14].ftop];
	uhead=whead;
}
void s6()//w->while
{
	whead=nextquad;
}
void s7()//s->us
{
	backpatch(vnext[3].tnext[vnext[3].ttop],uhead);
	emit("j","",-1,"",-1,"",uhead);
	vnext[3].tnext[vnext[3].ttop]=vnext[4].tnext[vnext[4].ttop];
}
void s8()//c->ifbthen
{
	backpatch(vnext[14].tnext[vnext[14].ttop],nextquad);
	vnext[6].tnext[vnext[6].ttop]=vnext[14].fnext[vnext[14].ftop];
}
void s9()//f->cselse
{
	int q=nextquad;
	emit("j","",-1,"",-1,"",0);
	vnext[7].tnext[vnext[7].ttop]=merge(vnext[3].tnext[vnext[3].ttop],q);
	backpatch(vnext[6].tnext[vnext[6].ttop],nextquad);
}
void s10()//s->fs
{
	vnext[3].tnext[vnext[3].ttop]=merge(vnext[7].tnext[vnext[7].ttop],vnext[3].tnext[vnext[3].ttop]);
}
void s11()//s->id-e;
{
	int p, t;
	p=idstack.entry[idstack.top];
	t=eval.place[eval.top];
	idstack.top--;
	eval.top--;
	
	if(t/1000==0)
		emit("=",symbol[p].idname,-1,"",-1,"",t);
	else if(t/1000==1)
		emit("=",symbol[p].idname,-1,"",-1,symbol[t-1000].idname,0);
	else if(t/1000==2)
		emit("=",symbol[p].idname,-1,"",-1,newvari[t-2000],0);
	else
		printf("error\n");
	vnext[3].tnext[++vnext[3].ttop]=0;
	vnext[3].fnext[++vnext[3].ftop]=0;
}
void s12()//S->td
{
	int i;
	strcpy(dlist.type,ttype);
	for(i=1;i<=dlist.top;i++)
		strcpy(symbol[dlist.addr[i]].type,dlist.type);
	idstack.top=idstack.top-(nlast-nfirst+1);
}
void s13()//t->int
{
	strcpy(ttype,"int");
	nfirst=top;
}
void s14()//d->idn
{
	dlist.addr[++dlist.top]=tok[nfirst].entry;
}
void s15()//n->,idn
{
	int i;
	if(nlast!=nfirst)
	{
		for(i=nlast;i>=nfirst+2;i=i-2)
			dlist.addr[++dlist.top]=tok[i].entry;
	}
}
void s16()//n->epsilon
{
	nlast=top-1;
}
void s17()//v->(b)
{
	vnext[11].tnext[vnext[11].ttop]=vnext[14].tnext[vnext[14].ttop];
	vnext[11].fnext[vnext[11].ftop]=vnext[14].fnext[vnext[14].ftop];
}
void s18()//v->true
{
	vnext[11].tnext[++vnext[11].ttop]=nextquad;
	emit("j","",-1,"",-1,"",0);
}
void s19()//v->flase
{
	vnext[11].fnext[++vnext[11].ftop]=nextquad;
	emit("j","",-1,"",-1,"",0);	
}
void s20()//v->id relop e
{
	int p, t;
	vnext[11].tnext[++vnext[11].ttop]=nextquad;
	vnext[11].fnext[++vnext[11].ftop]=nextquad+1;
	p=idstack.entry[idstack.top];
	t=eval.place[eval.top];
	idstack.top--;
	eval.top--;
	
	if(t/1000==0)
		emit(relop_op,symbol[p].idname,-1,"",t,"",0);
	else if(t/1000==1)
		emit(relop_op,symbol[p].idname,-1,symbol[t-1000].idname,-1,"",0);
	else if(t/1000==2)
		emit(relop_op,symbol[p].idname,-1,newvari[t-2000],-1,"",0);
	else
		printf("error\n");
	emit("j","",-1,"",-1,"",0);
}
void s21()//relop-><
{
	strcpy(relop_op,"<");
}
void s22()//a->&va
{
	backpatch(vnext[11].tnext[vnext[11].ttop-1],vnext[11].tnext[vnext[11].ttop]);
	vnext[13].tnext[vnext[13].ttop]=vnext[11].tnext[vnext[11].ttop];
	vnext[13].fnext[vnext[13].ftop]=merge(vnext[11].fnext[vnext[11].ftop],vnext[13].fnext[vnext[13].ftop]);
}
void s23()//a->epsilon
{
	vnext[13].tnext[++vnext[13].ttop]=nextquad;	
}
void s24()//b->va
{