pl0c.c

编译原理关于PL0文法的实现

#include <stdio.h>
#include "e:\pl0c.h"
#include "string.h"

/* 解释执行时使用的栈 */
#define stacksize 500

int main()
{
	bool nxtlev[symnum];
	init(); /* 初始化 */
	fas=fopen("fas.tmp","w");
	fa1=fopen("fa1.tmp","w");
	printf("Input file? ");
	fprintf(fa1,"Input file? ");
	scanf("%s",fname); /* 输入文件名 */
	fin=fopen(fname,"r");
	if(fin)
	{
		fprintf(fa1,"%s\n",fname);
		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');
		err=0;
		cc=cx=ll=0;
		ch=' ';
		kk=al-1;
		printf("Wait Please...\n");

		if(-1!=getsym())
		{
			fa=fopen("fa.tmp","w");
			fa2=fopen("fa2.tmp","w");
			addset(nxtlev,declbegsys,statbegsys,symnum);
			nxtlev[period]=true;
			if(-1==block(0,0,nxtlev)) /* 调用编译程序 */
			{
				fclose(fa);
				fclose(fa1);
				fclose(fin);
				printf("\n");
				return 0;
			}
			fclose(fa);
			fclose(fa1);
			if(sym!=period)error(9);
			if(err==0)interpret(); /* 调用解释执行程序 */
			else
			{
				printf("Errors in pl/0 program");
			}
		}
		fclose(fin);
	}
	else
	{
		printf("Can't open file!\n");
		fprintf(fa1,"Can't open file!\n");
		fclose(fa1);
	}
	fclose(fas);
	printf("\n");
	return 0;
}

/*
 *用数组实现集合的集合运算
 */
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 getch()
{
	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)
	    {
			//fscanf(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==13) /* 忽略空格、换行和回车 */
	{
		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;
					}
				}
			}
		}
	}
	return 0;
}

/* 生成虚拟机代码 */
int gen(enum fct x, /* f */
		int y, /* l */
		int z /* a */
		)
{
	if(cx>cxmax)
	{
		printf("Program too long"); /* 程序过长 */
		return -1;
	}
	code[cx].f=x;
	code[cx].l=y;
	code[cx].a=z;
	cx++;
	return 0;
}

int test(bool* s1, /* 当前符号应属于的集合 */
		 bool* s2, /* 为恢复正常语法分析工作的符号集合 */
		 int n) /* 错误号 */
{
	if(!inset(sym,s1))
	{
		error(n);
		/* 当检测不通过时，不停获取符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止 */
		while((!inset(sym,s1))&&(!inset(sym,s2)))
		{
			getsymdo;
		}
	}
	return 0;
}

/* 语法、语义分析程序 */
int block(int lev, /* 当前分程序所在层 */
		  int tx, /* 名字表当前尾指针 */
		  bool* fsys /* 当前模块后跟符号集合 */
		 )
{
	int i;
	int dx; /* 名字分配到的相对地址 */
	int tx0; /* 保留初始tx */
	int cx0; /* 保留初始cx */
	bool nxtlev[symnum]; /* 在下级函数的参数中，
							符号集合均为值参，但由于使用数租实现，
							传递进来的是指针，为防止下级函数改变
							上级函数的集合，开辟新的空间传递给
							下级函数，之后所有的nxtlev都是这样 */
	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); /* procedure后应为标识符 */
			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;
		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;
}

/* 解释程序 */
void interpret()
{
	int p,b,t; /* 指令指针，指令基址，栈顶指针 */
	struct instruction i; /* 存放当前指令 */
	int s[stacksize]; /* 栈 */
	printf("start pl0\n");
	t=0;b=0;p=0;
	s[0]=s[1]=s[2]=0;
	do
	{
		i=code[p]; /* 读当前指令 */
		p++;
		switch(i.f)
		{
			case lit: /* 将a的值取到栈顶 */
					s[t]=i.a;
					t++;
					break;
			case opr: /* 数学、逻辑运算 */
					switch(i.a)
					{
						case 0:
								t=b;
								p=s[t+2];
								b=s[t+1];
								break;
						case 1:
								s[t-1]=-s[t-1];
								break;
						case 2:
								t--;
								s[t-1]=s[t-1]+s[t];
								break;
						case 3:
								t--;
								s[t-1]=s[t-1]-s[t];
								break;
						case 4:
								t--;
								s[t-1]=s[t-1]*s[t];
								break;
						case 5:
								t--;
								s[t-1]=s[t-1]/s[t];
								break;
						case 6:
								s[t-1]=s[t-1]%2;
								break;
						case 8:
								t--;
								s[t-1]=s[t-1]==s[t];
								break;
						case 9:
								t--;
								s[t-1]=s[t-1]!=s[t];
								break;
						case 10:
								t--;
								s[t-1]=s[t-1]<s[t];
								break;
						case 11:
								t--;
								s[t-1]=s[t-1]>=s[t];
								break;
						case 12:
								t--;
								s[t-1]=s[t-1]>s[t];
								break;
						case 13:
								t--;
								s[t-1]=s[t-1]<=s[t];
								break;
						case 14:
								printf("%d",s[t-1]);
								fprintf(fa2,"%d",s[t-1]);
								t--;
								break;
						case 15:
								printf("\n");
								fprintf(fa2,"\n");
								break;
						case 16:
								printf("?");
								fprintf(fa2,"?");
								scanf("%d",&(s[t]));
								fprintf(fa2,"%d\n",s[t]);
								t++;
								break;
					}
					break;
			case lod: /* 取相对当前过程的数据基地址为a的内存的值到栈顶 */
					s[t]=s[base(i.l,s,b)+i.a];
					t++;
					break;
			case sto: /* 栈顶的值存到相对当前过程的数据基地址为a的内存 */
					t--;
					s[base(i.l,s,b)+i.a]=s[t];
					break;
			case cal: /* 调用子过程 */
					s[t]=base(i.l,s,b); /* 将父过程基地址入栈 */
					s[t+1]=b; /* 将本过程基地址入栈，此两项用于base函数 */
					s[t+2]=p; /* 将当前指令指针入栈 */
					b=t; /* 改变基地址指针值为新过程的基地址 */
					p=i.a; /* 跳转 */
					break;
			case inte: /* 分配内存 */
					t+=i.a;
					break;
					case jmp: /* 直接跳转 */
					p=i.a;
					break;
			case jpc: /* 条件跳转 */
					t--;
					if(s[t]==0)p=i.a;
					break;
		}
	}
	while(p!=0);
	fclose(fa2);
}