pl0c.c

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

/* 初始化 */
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]),"int");
	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;
}


/* 生成一项名字表 */
void enter(enum object k, /* 名字种类const,var or procedure */
		   int* ptx, /* 名字表尾指针的指针，为了可以改变名字表尾指针的值，以后所有的ptx都是这样 */
		   int lev, /* 名字所在的层次,，以后所有的lev都是这样 */
		   int* pdx /* dx为当前应分配的变量的相对地址，分配后要增加1，所以使用指针，以后所有的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;
		case procedur: /*　过程名字　*/
					table[(*ptx)].level=lev;
					break;
	}
}

/* 查找名字的位置 */
/* 找到则返回在名字表中的位置，否则返回0 */
int postion(char* idt, /* 要查找的名字 */
			int tx /* 当前名字表尾指针 */
		   )
{
	int i;
	strcpy(table[0].name,idt);
	i=tx;
	while(strcmp(table[i].name,idt)!=0)i--;
	return i;
}

/* 常量声明处理 */
int constdeclaration(int* ptx,
					 int lev,
					 int* pdx)
{
	if(sym==ident)
	{
		getsymdo;
		if(sym==eql||sym==becomes)
		{
			if(sym==becomes)error(1); /* 把=写成了:= */
			getsymdo;
			if(sym==number)
			{
				enter(constant,ptx,lev,pdx);
				getsymdo;
			}
			else error(2); /* 常量说明=后应是数字 */
		}
		else error(3); /* 常量说明标识后应是= */
	}
	else error(4); /* const后应是标识 */
	return 0;
}

/* 变量声明处理 */
int vardeclaration(int* ptx,int lev,int* pdx)
{
	if(sym==ident)
	{
		enter(variable,ptx,lev,pdx); /* 填写名字表 */
		getsymdo;
	}
	else error(4); /* var后应是标识 */
	return 0;
}

/* 输出代码 */
void listcode(int cx0)
{
	int i;
	if(listswitch)
	{
		for(i=cx0;i<cx;i++)
		{
			printf("%d %s %d %d\n",i,mnemonic[code[i].f],code[i].l,code[i].a);
			fprintf(fa,"%d %s %d %d\n",i,mnemonic[code[i].f],code[i].l,code[i].a);
		}
	}
}

/* 语句处理 */
int statement(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */
{
	int i,cx1,cx2;
	bool nxtlev[symnum]; /*　意义见block函数 */

	if(sym==ident) /* 准备按照赋值语句处理 */
	{
		i=postion(id,*ptx);
		if(i==0)error(11); /* 变量未找到 */
		else
		{
			if(table[i].kind!=variable)
			{
				error(12); /* 赋值语句格式错误 */
				i=0;
			}
		}
		getsymdo;
		if(sym==becomes)
		{
			getsymdo;
		}
		else error(13); /* 检测赋值符号 */
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		expressiondo(nxtlev,ptx,lev); /* 处理赋值符号右侧表达式 */
		if(i!=0)
		{
			gendo(sto,lev-table[i].level,table[i].adr); /* expression将执行一系列指令，但最终结果将会保存在栈顶，执行sto命令完成赋值 */
		}
	}
	else
	{
		if(sym==readsym) /* 准备按照read语句处理 */
		{
			getsymdo;
			if(sym!=lparen)error(34); /* 格式错误，应是左括号 */
			else
			{
				do
				{
					getsymdo;
					if(sym==ident)i=postion(id,*ptx); /* 查找要读的变量 */
					else i=0;
					if(i==0)error(35); /* read()中应是声明过的变量名 */
					else
					{
						gendo(opr,0,16); /* 生成输入指令，读取值到栈顶 */
						gendo(sto,lev-table[i].level,table[i].adr); /* 储存到变量 */
					}
					getsymdo;
				}while(sym==comma); /* 一条read语句可读多个变量 */
			}
			if(sym!=rparen)
			{
				error(33); /* 格式错误，应是右括号 */
				while(!inset(sym,fsys)) /* 出错补救，直到收到上层函数的后跟符号 */
				getsymdo;
			}
			else
			{
				getsymdo;
			}
		}
		else
		{
			if(sym==writesym) /* 准备按照write语句处理，与read类似 */
			{
				getsymdo;
				if(sym==lparen)
				{
					do
					{
						getsymdo;
						memcpy(nxtlev,fsys,sizeof(bool)*symnum);
						nxtlev[rparen]=true;
						nxtlev[comma]=true; /* write的后跟符号为) or , */
						expressiondo(nxtlev,ptx,lev); /* 调用表达式处理，此处与read不同，read为给变量赋值 */
						gendo(opr,0,14); /* 生成输出指令，输出栈顶的值 */
					}while(sym==comma);
					if(sym!=rparen)error(33); /* write()中应为完整表达式 */
					else
					{
						getsymdo;
					}
				}
				gendo(opr,0,15); /* 输出换行 */
			}
			else
			{
				if(sym==callsym) /* 准备按照call语句处理 */
				{
					getsymdo;
					if(sym!=ident)error(14); /* call后应为标识符 */
					else
					{
						i=postion(id,*ptx);
						if(i==0)error(11); /* 过程未找到 */
						else
						{
							if(table[i].kind==procedur)
							{
								gendo(cal,lev-table[i].level,table[i].adr); /* 生成call指令 */
							}
							else error(15); /* call后标识符应为过程 */
						}
						getsymdo;
					}
				}
				else
				{
					if(sym==ifsym) /* 准备按照if语句处理 */
					{
						getsymdo;
						memcpy(nxtlev,fsys,sizeof(bool)*symnum);
						nxtlev[thensym]=true;
						nxtlev[dosym]=true; /* 后跟符号为then或do */
						conditiondo(nxtlev,ptx,lev); /* 调用条件处理（逻辑运算）函数 */
						if(sym==thensym)
						{
							getsymdo;
						}
						else error(16); /* 缺少then */
						cx1=cx; /* 保存当前指令地址 */
						gendo(jpc,0,0); /* 生成条件跳转指令，跳转地址未知，暂时写0 */
						statementdo(fsys,ptx,lev); /* 处理then后的语句 */
						code[cx1].a=cx; /* 经statement处理后，cx为then后语句执行完的位置，它正是前面未定的跳转地址 */
					}
					else
					{
						if(sym==beginsym) /* 准备按照复合语句处理 */
						{
							getsymdo;
							memcpy(nxtlev,fsys,sizeof(bool)*symnum);
							nxtlev[semicolon]=true;
							nxtlev[endsym]=true; /* 后跟符号为分号或end */

							/* 循环调用语句处理函数，直到下一个符号不是语句开始符号或收到end */
							statementdo(nxtlev,ptx,lev);
							while(inset(sym,statbegsys)||sym==semicolon)
							{
								if(sym==semicolon)
								{
									getsymdo;
								}
								else error(10); /* 缺少； */
								statementdo(nxtlev,ptx,lev);
							}
							if(sym==endsym)
							{
								getsymdo;
							}
							else error(17); /* 缺少end或； */
						}
						else
						{
							if(sym==whilesym) /* 准备按照while语句处理 */
							{
								cx1=cx; /* 保存判断条件操作的位置 */
								getsymdo;
								memcpy(nxtlev,fsys,sizeof(bool)*symnum);
								nxtlev[dosym]=true; /* 后跟符号为do */
								conditiondo(nxtlev,ptx,lev); /* 调用条件处理 */
								cx2=cx; /* 保存循环体的结束的下一个位置 */
								gendo(jpc,0,0); /* 生成条件跳转，但跳出循环的地址未知 */
								if(sym==dosym)
								{
									getsymdo;
								}
								else error(18); /* 缺少do */
								statementdo(fsys,ptx,lev); /* 循环体 */
								gendo(jmp,0,cx1); /* 回头重新判断条件 */
								code[cx2].a=cx; /* 反填跳出循环的地址，与if类似 */
							}
							memset(nxtlev,0,sizeof(bool)*symnum); /* 语句结束无补救集合 */
							testdo(fsys,nxtlev,19); /* 检测语句结束的正确性 */
						}
					}
				}
			}
		}
	}

	return 0;
}


/* 表达式处理 */
int expression(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */
{
	enum symbol addop; /* 用于保存正负号 */
	bool nxtlev[symnum];
	if(sym==plus||sym==minus) /* 开头的正负号，此时当前表达式被看作一个正的或负的项 */
	{
		addop=sym; /* 保存开头的正负号 */
		getsymdo;
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		nxtlev[plus]=true;
		nxtlev[minus]=true;
		termdo(nxtlev,ptx,lev); /* 处理项 */
		if(addop==minus)gendo(opr,0,1); /* 如果开头为负号生成取负指令 */
	}
	else /* 此时表达式被看作项的加减 */
	{
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		nxtlev[plus]=true;
		nxtlev[minus]=true;
		termdo(nxtlev,ptx,lev); /* 处理项 */
	}
	while(sym==plus||sym==minus)
	{
		addop=sym;
		getsymdo;
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		nxtlev[plus]=true;
		nxtlev[minus]=true;
		termdo(nxtlev,ptx,lev); /* 处理项 */
		if(addop==plus)
		{
			gendo(opr,0,2); /* 生成加法指令 */
		}
		else gendo(opr,0,3); /* 生成减法指令 */
	}
	return 0;
}

/* 条件处理 */
int condition(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */
{
	enum symbol relop;
	bool nxtlev[symnum];
	if(sym==oddsym) /* 准备按照odd运算处理 */
	{
		getsymdo;
		expressiondo(fsys,ptx,lev);
		gendo(opr,0,6); /* 生成odd指令 */
	}
	else
	{
		/* 逻辑表达式处理 */
		memcpy(nxtlev,fsys,sizeof(bool)*symnum);
		nxtlev[eql]=true;nxtlev[neq]=true;
		nxtlev[lss]=true;nxtlev[leq]=true;
		nxtlev[gtr]=true;nxtlev[geq]=true;
		expressiondo(nxtlev,ptx,lev);
		if(sym!=eql&&sym!=neq&&sym!=lss&&sym!=leq&&sym!=gtr&&sym!=geq)error(20);
		else
		{
			relop=sym;
			getsymdo;
			expressiondo(fsys,ptx,lev);
			switch(relop)
			{
				case eql:
						gendo(opr,0,8);
						break;
				case neq:
						gendo(opr,0,9);
						break;
				case lss:
						gendo(opr,0,10);
						break;
				case geq:
						gendo(opr,0,11);
						break;
				case gtr:
						gendo(opr,0,12);
						break;
				case leq:
						gendo(opr,0,13);
						break;
			}
		}
	}
	return 0;
}


/* 项处理 */
int term(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */
{
	enum symbol mulop; /* 用于保存乘除法符号 */
	bool nxtlev[symnum];
	memcpy(nxtlev,fsys,sizeof(bool)*symnum);
	nxtlev[times]=true;
	nxtlev[slash]=true;
	factordo(nxtlev,ptx,lev); /* 处理因子 */
	while(sym==times||sym==slash)
	{
		mulop=sym;
		getsymdo;
		factordo(nxtlev,ptx,lev);
		if(mulop==times)
		{
			gendo(opr,0,4); /* 生成乘法指令 */
		}
		else
		{
			gendo(opr,0,5); /* 生成除法指令 */
		}
	}
	return 0;
}

/* 因子处理 */
int factor(bool* fsys,int* ptx,int lev) /* 参数意义见block和enter函数 */
{
	int i;
	bool nxtlev[symnum];
	testdo(facbegsys,fsys,24); /* 检测因子的开始符号 */
	while(inset(sym,facbegsys)) /* 循环直到不是因子开始符号 */
	{
		if(sym==ident) /* 因子为常量或变量 */
		{
			i=postion(id,*ptx); /* 查找名字 */
			if(i==0)error(11); /* 名字未声明 */
			else
			{
				switch(table[i].kind)
				{
					case constant: /* 名字为常量 */
								gendo(lit,0,table[i].val); /* 直接把常量的值入栈 */
								break;
					case variable: /* 名字为变量 */
								gendo(lod,lev-table[i].level,table[i].adr); /* 找到变量地址并将其值入栈 */
								break;
					case procedur: /* 名字为过程 */
								error(21); /* 不能为过程 */
								break;
				}
			}
			getsymdo;
		}
		else
		{
			if(sym==number) /* 因子为数 */
			{
				if(num>amax)
				{
					error(31);
					num=0;
				}
				gendo(lit,0,num);
				getsymdo;
			}
			else
			{
				if(sym==lparen) /* 因子为表达式 */
				{
					getsymdo;
					memcpy(nxtlev,fsys,sizeof(bool)*symnum);
					nxtlev[rparen]=true;
					expressiondo(nxtlev,ptx,lev);
					if(sym==rparen)
					{
						getsymdo;
					}
					else error(22); /* 缺少右括号 */
				}
				test(fsys,facbegsys,23); /* 因子后有非法符号 */
			}
		}
	}
	return 0;
}

/* 通过过程活动记录基址求上l层过程的基址活动记录 */
int base(int l,int* s,int b)
{
	int b1;
	b1=b;
	while(l>0)
	{
		b1=s[b1];
		l--;
	}
	return b1;
}