编译原理.c

编译原理中ＰＬ／０程序的编译过程．用Ｃ写的

/*编译和运行环境
* 1 Visual C++ 6.0, Visual C++.NET和Visual C++.NET 2003
* WinNT,Win2000,WinXP and Win2003
* 2 gcc version 3.3.2 20031022(Red Hat Linux 3.3.2-1)
*    Redhat Fedora core 1
*    Intel 32 platform
* 使用方法：
* 运行后输入PL/0源程序文件名
* 回答是否输出虚拟机代码
* 回答是否输出名字表
* fa.tmp输出虚拟机代码
* fa1.tmp输出源文件及各自对应的地址
* fa2.tmp输出结果
* fas.tmp输出名字表
*/
# include<stdio.h>
# include"pl0.h"
# include"string.h"
/*解释执行时使用的栈*/
# define stacksize 500
int main()
{
	bool nxtlev[symnum];
	printf("Input pl/0 file?");
	scanf("%s",fname);
	fin=fopen(fname,"r");
	if(fin)
	{
		printf("List object code? (Y/N)");
		scanf("%s",fname);
		listswitch=(fname[0]=='y'||fname[0]=='Y');
		printf("List symbol table? (Y/N)");
		scanf("%s",fname);
		tableswitch=(fname[0]=='y'||fname[0]=='Y');
		fa1=fopen("fal.fmp","w");
		fprintf(fa1,"Input pl/0 file?");
		fprintf(fa1,"%s\n",fname);
		init();
		err=0;
		cc=cx=ll=0;
		ch=' ';
		if(-1!=getsym())
		{
			fa=fopen("fa.tmp","w");
			fas=fopen("fas.tmp","w");
			addset(nxtlev,declbegsys,statbegsys,symnum);
			nxtlev[period]=true;
			if(-1==block(0,0,nxtlev))
			{
				fclose(fa);
				fclose(fa1);
				fclose(fas);
				fclose(fin);
				printf("\n");
				return 0;
			}
			fclose(fa);
			fclose(fa1);
			fclose(fas);
			if(sym!= period)
			{
				error(9);
			}
			if(err==0)
			{
				fa2=fopen("fa2.tmp","w");
				interpret();
				fclose(fa2);
			}
			else
			{
				printf("Errors in pl/0 program");
			}
		}
		fclose(fin);     
	}
	else
	{
		printf("Can't open file! \n");
	}
	printf("\n");
	return 0;
}
/*
 *初始化
 */
void init()
{
	int i;
	/*设置单字符符号*/
	for(i=0;i<=255;i++)
	{
		ssym[i]=nul;
	}
	ssym['+']=plus;
	ssym['-']=minus;
	ssym['*']=times;
	ssym['/']=slash;
	ssym['(']=lparen;
	ssym[')']=rparen;
	ssym['=']=eql;
	ssym[',']=comma;
	ssym['.']=period;
	ssym['#']=neq;
	ssym[';']=semicolon;
	/*设置保留字名字，按照字母顺序，便于折半查找*/
	strcpy(&word[0][0],"begin");
    strcpy(&word[1][0],"call");
	strcpy(&word[2][0],"const");
	strcpy(&word[3][0],"do");
	strcpy(&word[4][0],"end");
	strcpy(&word[5][0],"if");
	strcpy(&word[6][0],"odd");
	strcpy(&word[7][0],"procedure");
	strcpy(&word[8][0],"read");
	strcpy(&word[9][0],"then");
	strcpy(&word[10][0],"var");
	strcpy(&word[11][0],"while");
	strcpy(&word[12][0],"write");
	/*设置保留字符号*/
	wsym[0]=beginsym;
	wsym[1]=callsym;
	wsym[2]=constsym;
	wsym[3]=dosym;
	wsym[4]=endsym;
	wsym[5]=ifsym;
	wsym[6]=oddsym;
	wsym[7]=procsym;
	wsym[8]=readsym;
	wsym[9]=thensym;
	wsym[10]=varsym;
 	wsym[11]=whilesym;
	wsym[12]=writesym;
	/*设置指令名称*/
	strcpy(&mnemonic[lit][0],"lit");
	strcpy(&mnemonic[opr][0],"opr");
	strcpy(&mnemonic[lod][0],"lod");
	strcpy(&mnemonic[sto][0],"sto");
	strcpy(&mnemonic[cal][0],"cal");
	strcpy(&mnemonic[inte][0],"inte");
	strcpy(&mnemonic[jmp][0],"jmp");
	strcpy(&mnemonic[jpc][0],"jpc");
	/*设置符号集*/
	for(i=0;i<symnum;i++)
	{
		declbegsys[i]=false;
		statbegsys[i]=false;
		facbegsys[i]=false;
	}
	/*设置声明开始符号集*/
	declbegsys[constsym]=true;
    declbegsys[varsym]=true;
	declbegsys[procsym]=true;
	/*设置语句开始符号集*/
	statbegsys[beginsym]=true;
	statbegsys[callsym]=true;
	statbegsys[ifsym]=true;
	statbegsys[whilesym]=true;
	/*设置因子开始符号集*/
	facbegsys[ident]=true;
	facbegsys[number]=true;
	facbegsys[lparen]=true;
}
/*
 *用数组实现集合的集合运算
 */
int inset(int e,bool *s)
{
	return s[e];
}
int addset(bool *sr,bool *s1,bool *s2,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		sr[i]=s1[i]||s2[i];
	}
	return 0;
}
int subset(bool *sr,bool *s1,bool *s2,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		sr[i]=s1[i]&&(! s2[i]);
	}
	return 0;
}
int mulset(bool *sr,bool *s1,bool *s2,int n)
{
	int i;
	for(i=0;i<n;i++)
	{
		sr[i]=s1[i]&&s2[i];
	}
	return 0;
}
/*
 *出错处理，打印出错位置和错误编码
 */
void error(int n)
{
	char space[81];
	memset(space,32,81);
	space[cc-1]=0;//出错时当前符号已经读完，所以cc-1
	printf("****%s!%d\n",space,n);
	fprintf(fa1,"****%s!%d\n",space,n);
	err++;
}
/*
 *漏掉空格，读取一个字符。
 *
 *每次读一行，存入line缓冲区，line被getsym取空后再读一行
 *
 *被函数getsym调用
 */
int gech()
{
	if(cc==ll)
	{
		if(feof(fin))
		{
			printf("program incomplete");
			return -1;
		}
		ll=0;
		cc=0;
		printf("%d",cx);
		fprintf(fa1,"%d",cx);
		ch=' ';
		while(ch!=10)
		{
			//fscan(fin,"%c",&ch);
			if(EOF==fscanf(fin,"%c",&ch))
			{
				line[ll]=0;
				break;
			}
			printf("%c",ch);
			fprintf(fa1,"%c",ch);
			line[ll]=ch;
			ll++;
		}
		printf("\n");
		fprintf(fa1,"\n");
	}
	ch=line[cc];
	cc++;
	return 0;
}
/*
 *词法分析,获取一个符号
 */
int getsym()
{
	int i,j,k;
	while(ch==' '||ch==10||ch==9) /*忽略空格,换行和TAB*/
	{
		getchdo;

	}
	if(ch>'a'&&ch<='z')    /*名字或保留字以a..z开头*/
	{
		k=0;
		do
		{
			if(k<al)
			{
				a[k]=ch;
				k++;
			}
			getchdo;
		}while(ch>'a'&&ch<='z'||ch>'0'&&ch<='9');
		a[k]=0;
		strcpy(id,a);
		i=0;
		j=norw-1;
		do                              /*搜索当前符号是否为保留字*/
		{
			k=(i+j)/2;
			if(strcmp(id,word[k])<=0)
			{
				j=k-1;
			}
			if(strcmp(id,word[k])>=0)
			{
				i=k+1;
			}
		}while(i<=j);
		if(i-1>j)
		{
			sym=wsym[k];
		}
		else
		{
			sym=ident;           /*搜索失败,则是名字或数字*/
		}
	}
	else
	{
		if(ch>='0'&&ch<='9')              /*检测是否为数字:以0..9开头*/
		{
			k=0;                
			num=0;
			sym=number;
            do
			{
				num=10*num+ch-'0';
				k++;
				getchdo;
			}while(ch>='0'&&ch<='9');      /*获取数字的值*/
			k--;
			if(k>nmax)
			{
				error(30);
			}
		}
		else
		{
			if(ch==':')          /*检测赋值符号*/
			{
				getchdo;
			   if(ch=='=')
			   {
				sym=becomes;
				getchdo;
			   }
			   else
			   {
				   sym=nul;           /*不能识别的符号*/
			   }
			}
			else
			{
				if(ch=='<')            /*检测大于或小于等于符号*/
				{
					getchdo;
				    if(ch=='=')
					{
						sym=leq;
					    getchdo;
					}
					else
					{
						sym=lss;
					}
				}
				else
				{
					if(ch=='>')      /*检测大于或大于等于符号*/
					{
						getchdo;
					    if(ch=='=')
						{
							sym=geq;
						    getchdo;
						}
					    else
						{
						    sym=gtr;
						}
					}
				    else
					{
						sym=ssym[ch];    /*当符号不满足上述条件时,全部按照单字符符号处理*/
					    //getchdo;
					   //richard
					   if(sym!=period)
					   {
						   getchdo;
					   }
					   //end richard
					}
				}
			}
		}
	}
	return 0;
}
/*
 *生成虚拟机代码
 *
 *x:instruction.f;
 *y:instruction.l;
 *z:instruction.a;
 */
int gen(enum fct x,int y,int z)
{
	if(cx>=cxmax)
	{
		printf("Program too long");      /*程序过长*/
		return -1;
	}
	code[cx].f=x;
	code[cx].l=y;
	code[cx].a=z;
	cx++;
	return 0;
}
/*
 *测试当前符号是否合法
 *
 *在某一部分(如一条语句,一个表达式)将要结束时我们希望下一个符号属于某个集合
 *(该部分的后跟符号),test负责这项检测,而且负责当前需要的符号集合和补救用的集合(如之前未完成部分的后跟
 *符号),以及检测不通过时的错误号
 *
 *s1:我们需要的符号
 *s2:如果不是我们需要的,则需要一个补救用的集合
 *n:错误号
 */
int test(bool* s1,bool *s2,int n)
{
	if(inset(sym,s1))
	{
		error(n);
	    /*当检测不通过时,不停获取符号,直到它属于需要的集合或补救的集合*/
	   while(!inset(sym,s1)&&(!inset(sym,s2)))
	   {
		   getsymdo;
	   }
	}
	return 0;
}
/*
 *编译程序主体
 *
 *lev:当前分程序所在层
 *tx:名字表当前尾指针
 *fsys:当前模块后跟符号集合
 */
int block(int lev,int tx,bool *fsys)
{
	int i;
	int dx;                           /*名字分配到的相对地址*/
	int tx0;                          /*保留初始地址 tx*/
    int cx0;                         /*保留初始 cx*/
	bool nxtlev[symnum];             /*在下级函数的参数中，符号集合均为值参，但由于使用数组
	                                    实现，传递进来的是指针，为防止下级函数改变上级函数的
	                                    集合，开辟新的空间传递给下级函数*/
	dx=3;
	tx0=tx;
	table[tx].adr=cx;
	gendo(jmp,0,0);
	if(lev>levmax)
	{
		error(32);
	}
    do
	{
		if(sym==constsym)               /*受到常量声明符号，开始处理常量声明*/
		{
			getsymdo;
		
		do
		{
			constdeclarationdo(&tx,lev,&dx);     /*dx的值被constdeclaration改变，使用指针*/
			while(sym==comma)
			{
				getsymdo;
				constdeclarationdo(&tx,lev,&dx);
			}
			if(sym==semicolon)
			{
				getsymdo;
			}
			else
			{
				error(5);      /*漏掉了逗号或者分号*/
			}
		}while(sym==ident);
	}
	if(sym==varsym)        /*收到变量声明符号,开始处理变量声明*/
    {
		getsymdo;
		do
		{
			vardeclarationdo(&tx,lev,&dx);
			while(sym==comma)
			{
				getsymdo;
				vardeclarationdo(&tx,lev,&dx);
			}
			if(sym==semicolon)
			{
				getsymdo;
			}
			else
			{
				error(5);
			}
		}while(sym==ident);
	}
	while(sym==procsym)           /*收到过程声明符号,开始处理声明过程*/
	{
		getsymdo;
		if(sym==ident)
		{
			enter(procedur,&tx,lev,&dx);    /*记录过程名字*/
 			getsymdo;
		}
		else
		{
			error(4);                     /*prcedure后应为标识符*/
		}
		if(sym==semicolon)
		{
			getsymdo;
		}
		else
		{
			error(5);                  /*漏掉了分量*/
		}
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		nxtlev[semicolon]=true;
		if(-1==block(lev+1,tx,nxtlev))
		{
			return -1;               /*递归调用*/
		}
		if(sym==semicolon)
		{
			getsymdo;
            memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);
			nxtlev[ident]=true;
			nxtlev[procsym]=true;
			testdo(nxtlev,fsys,6);
		}
		else
		{
			error(5);            /*漏掉了分号*/
		}
	}
	memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);
    nxtlev[ident]=true;
    nxtlev[period]=true;
	testdo(nxtlev,declbegsys,7);
	}while(inset(sym,declbegsys));                       /*直到没有声明*/
    code[table[tx0].adr].a=cx;                          /*开始生成当前过程代码*/
	table[tx0].adr=cx;                                  /*当前过程代码地址*/
	table[tx0].size=dx;                                 /*声明部分中每增加一条声明都会给dx增加1，声明
	                                                      部分已经结束，dx就是当前过程数据的size*/
	cx0=cx;                                            
	gendo(inte,0,dx);                                    /*生成分配内存代码*/
	if(tableswitch)                                      /*输出名字表*/
	{
		printf("TABLE:\n");
		if(tx0+1 > tx)
		{
			printf("NULL\n");
		}
		for(i=tx0+1;i<tx;i++)
		{
			switch(table[i].kind)
			{
			   case constant:
				   printf("%d const %s",i,table[i].name);
				   printf("val=%d\n",table[i].val);
				   fprintf(fas,"%d const %s",i,table[i].name);
                   fprintf(fas,"val=%d\n",table[i].val);
				   break;
			   case variable:
				   printf("%d var%s",i,table[i].name);
				   printf("lev=%d addr=%d\n",table[i].level,table[i].adr);
				   fprintf(fas,"%d var%s",i,table[i].name);
				   fprintf(fas,"lev=%d addr=%d\n",table[i].level,table[i].adr);
				   break;
			   case procedur:
				   printf("%d proc%s",i,table[i].name);
				   printf("lev=%d addr=%d size=%d\n",table[i].level,table[i].adr,table[i].size);
                   fprintf(fas,"%d proc%s",i,table[i].name);
				   fprintf(fas,"lev=%d addr=%d size=%d\n",table[i].level,table[i].adr,table[i].size);
				   break;
			}
		}
		printf("\n");
	}
	/*语句后跟符号为分号或end*/
	memcpy(nxtlev,fsys,sizeof(bool)*symnum);          /*每个后跟符号集和都包含上层后跟符号
	                                                    集合，以便补救*/
	nxtlev[semicolon]=true;
	nxtlev[endsym]=true;
	statementdo(nxtlev,&tx,lev);
	gendo(opr,0,0);                                   /*每个过程出口都要使用的释放数据段指令*/
	memset(nxtlev,0,sizeof(bool) *symnum);            /*分程序没有补救集合*/
	testdo(fsys,nxtlev,8);                            /*检测后跟符号正确性*/
	listcode(cx0);                                    /*输出代码*/
	return 0;
}
/*
 *在名字表中加入一项
 *
 *k:名字种类const ,var or procedure
 *ptx:名字表尾指针的指针，为了可以改变名字表尾指针的值
 *lev:名字所在的层次，以后所有的 lev 都是这样
 *pdx:dx 为当前应分配的变量的相对地址，分配后要增加1
 */
 void enter(enum object k,int *ptx,int lev,int *pdx)
 {
	 (*ptx)++;
	 strcpy(table[(*ptx)].name,id);                  /*全局变量id中已存有当前名字的名字*/
	 table[(*ptx)].kind=k;
	 switch(k)   
	 {
	       case constant:                              /*常量名字*/
			 if(num>amax)
			 {
				 error(31);                          /*数越界*/
				 num=0;
			 }
			  table[(*ptx)].val=num;
			  break;
	     case variable:                                  /*变量名字*/
			 table[(*ptx)].level=lev;
			 table[(*ptx)].adr=(*pdx);
			 (*pdx)++;
			 break;