/*編譯和運(yùn)行環(huán)境
* 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
* 使用方法：
* 運(yùn)行后輸入PL/0源程序文件名
* 回答是否輸出虛擬機(jī)代碼
* 回答是否輸出名字表
* fa.tmp輸出虛擬機(jī)代碼
* fa1.tmp輸出源文件及各自對(duì)應(yīng)的地址
* fa2.tmp輸出結(jié)果
* fas.tmp輸出名字表
*/
# include<stdio.h>
# include"pl0.h"
# include"string.h"
/*解釋執(zhí)行時(shí)使用的棧*/
# 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;
	/*設(shè)置單字符符號(hào)*/
	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;
	/*設(shè)置保留字名字，按照字母順序，便于折半查找*/
	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");
	/*設(shè)置保留字符號(hào)*/
	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;
	/*設(shè)置指令名稱(chēng)*/
	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");
	/*設(shè)置符號(hào)集*/
	for(i=0;i<symnum;i++)
	{
		declbegsys[i]=false;
		statbegsys[i]=false;
		facbegsys[i]=false;
	}
	/*設(shè)置聲明開(kāi)始符號(hào)集*/
	declbegsys[constsym]=true;
    declbegsys[varsym]=true;
	declbegsys[procsym]=true;
	/*設(shè)置語(yǔ)句開(kāi)始符號(hào)集*/
	statbegsys[beginsym]=true;
	statbegsys[callsym]=true;
	statbegsys[ifsym]=true;
	statbegsys[whilesym]=true;
	/*設(shè)置因子開(kāi)始符號(hào)集*/
	facbegsys[ident]=true;
	facbegsys[number]=true;
	facbegsys[lparen]=true;
}
/*
 *用數(shù)組實(shí)現(xiàn)集合的集合運(yùn)算
 */
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;
}
/*
 *出錯(cuò)處理，打印出錯(cuò)位置和錯(cuò)誤編碼
 */
void error(int n)
{
	char space[81];
	memset(space,32,81);
	space[cc-1]=0;//出錯(cuò)時(shí)當(dāng)前符號(hào)已經(jīng)讀完，所以cc-1
	printf("****%s!%d\n",space,n);
	fprintf(fa1,"****%s!%d\n",space,n);
	err++;
}
/*
 *漏掉空格，讀取一個(gè)字符。
 *
 *每次讀一行，存入line緩沖區(qū)，line被getsym取空后再讀一行
 *
 *被函數(shù)getsym調(diào)用
 */
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;
}
/*
 *詞法分析,獲取一個(gè)符號(hào)
 */
int getsym()
{
	int i,j,k;
	while(ch==' '||ch==10||ch==9) /*忽略空格,換行和TAB*/
	{
		getchdo;

	}
	if(ch>'a'&&ch<='z')    /*名字或保留字以a..z開(kāi)頭*/
	{
		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                              /*搜索當(dāng)前符號(hào)是否為保留字*/
		{
			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;           /*搜索失敗,則是名字或數(shù)字*/
		}
	}
	else
	{
		if(ch>='0'&&ch<='9')              /*檢測(cè)是否為數(shù)字:以0..9開(kāi)頭*/
		{
			k=0;                
			num=0;
			sym=number;
            do
			{
				num=10*num+ch-'0';
				k++;
				getchdo;
			}while(ch>='0'&&ch<='9');      /*獲取數(shù)字的值*/
			k--;
			if(k>nmax)
			{
				error(30);
			}
		}
		else
		{
			if(ch==':')          /*檢測(cè)賦值符號(hào)*/
			{
				getchdo;
			   if(ch=='=')
			   {
				sym=becomes;
				getchdo;
			   }
			   else
			   {
				   sym=nul;           /*不能識(shí)別的符號(hào)*/
			   }
			}
			else
			{
				if(ch=='<')            /*檢測(cè)大于或小于等于符號(hào)*/
				{
					getchdo;
				    if(ch=='=')
					{
						sym=leq;
					    getchdo;
					}
					else
					{
						sym=lss;
					}
				}
				else
				{
					if(ch=='>')      /*檢測(cè)大于或大于等于符號(hào)*/
					{
						getchdo;
					    if(ch=='=')
						{
							sym=geq;
						    getchdo;
						}
					    else
						{
						    sym=gtr;
						}
					}
				    else
					{
						sym=ssym[ch];    /*當(dāng)符號(hào)不滿足上述條件時(shí),全部按照單字符符號(hào)處理*/
					    //getchdo;
					   //richard
					   if(sym!=period)
					   {
						   getchdo;
					   }
					   //end richard
					}
				}
			}
		}
	}
	return 0;
}
/*
 *生成虛擬機(jī)代碼
 *
 *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");      /*程序過(guò)長(zhǎng)*/
		return -1;
	}
	code[cx].f=x;
	code[cx].l=y;
	code[cx].a=z;
	cx++;
	return 0;
}
/*
 *測(cè)試當(dāng)前符號(hào)是否合法
 *
 *在某一部分(如一條語(yǔ)句,一個(gè)表達(dá)式)將要結(jié)束時(shí)我們希望下一個(gè)符號(hào)屬于某個(gè)集合
 *(該部分的后跟符號(hào)),test負(fù)責(zé)這項(xiàng)檢測(cè),而且負(fù)責(zé)當(dāng)前需要的符號(hào)集合和補(bǔ)救用的集合(如之前未完成部分的后跟
 *符號(hào)),以及檢測(cè)不通過(guò)時(shí)的錯(cuò)誤號(hào)
 *
 *s1:我們需要的符號(hào)
 *s2:如果不是我們需要的,則需要一個(gè)補(bǔ)救用的集合
 *n:錯(cuò)誤號(hào)
 */
int test(bool* s1,bool *s2,int n)
{
	if(inset(sym,s1))
	{
		error(n);
	    /*當(dāng)檢測(cè)不通過(guò)時(shí),不停獲取符號(hào),直到它屬于需要的集合或補(bǔ)救的集合*/
	   while(!inset(sym,s1)&&(!inset(sym,s2)))
	   {
		   getsymdo;
	   }
	}
	return 0;
}
/*
 *編譯程序主體
 *
 *lev:當(dāng)前分程序所在層
 *tx:名字表當(dāng)前尾指針
 *fsys:當(dāng)前模塊后跟符號(hào)集合
 */
int block(int lev,int tx,bool *fsys)
{
	int i;
	int dx;                           /*名字分配到的相對(duì)地址*/
	int tx0;                          /*保留初始地址 tx*/
    int cx0;                         /*保留初始 cx*/
	bool nxtlev[symnum];             /*在下級(jí)函數(shù)的參數(shù)中，符號(hào)集合均為值參，但由于使用數(shù)組
	                                    實(shí)現(xiàn)，傳遞進(jìn)來(lái)的是指針，為防止下級(jí)函數(shù)改變上級(jí)函數(shù)的
	                                    集合，開(kāi)辟新的空間傳遞給下級(jí)函數(shù)*/
	dx=3;
	tx0=tx;
	table[tx].adr=cx;
	gendo(jmp,0,0);
	if(lev>levmax)
	{
		error(32);
	}
    do
	{
		if(sym==constsym)               /*受到常量聲明符號(hào)，開(kāi)始處理常量聲明*/
		{
			getsymdo;
		
		do
		{
			constdeclarationdo(&tx,lev,&dx);     /*dx的值被constdeclaration改變，使用指針*/
			while(sym==comma)
			{
				getsymdo;
				constdeclarationdo(&tx,lev,&dx);
			}
			if(sym==semicolon)
			{
				getsymdo;
			}
			else
			{
				error(5);      /*漏掉了逗號(hào)或者分號(hào)*/
			}
		}while(sym==ident);
	}
	if(sym==varsym)        /*收到變量聲明符號(hào),開(kāi)始處理變量聲明*/
    {
		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)           /*收到過(guò)程聲明符號(hào),開(kāi)始處理聲明過(guò)程*/
	{
		getsymdo;
		if(sym==ident)
		{
			enter(procedur,&tx,lev,&dx);    /*記錄過(guò)程名字*/
 			getsymdo;
		}
		else
		{
			error(4);                     /*prcedure后應(yīng)為標(biāo)識(shí)符*/
		}
		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;               /*遞歸調(diào)用*/
		}
		if(sym==semicolon)
		{
			getsymdo;
            memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);
			nxtlev[ident]=true;
			nxtlev[procsym]=true;
			testdo(nxtlev,fsys,6);
		}
		else
		{
			error(5);            /*漏掉了分號(hào)*/
		}
	}
	memcpy(nxtlev,statbegsys,sizeof(bool)*symnum);
    nxtlev[ident]=true;
    nxtlev[period]=true;
	testdo(nxtlev,declbegsys,7);
	}while(inset(sym,declbegsys));                       /*直到?jīng)]有聲明*/
    code[table[tx0].adr].a=cx;                          /*開(kāi)始生成當(dāng)前過(guò)程代碼*/
	table[tx0].adr=cx;                                  /*當(dāng)前過(guò)程代碼地址*/
	table[tx0].size=dx;                                 /*聲明部分中每增加一條聲明都會(huì)給dx增加1，聲明
	                                                      部分已經(jīng)結(jié)束，dx就是當(dāng)前過(guò)程數(shù)據(jù)的size*/
	cx0=cx;                                            
	gendo(inte,0,dx);                                    /*生成分配內(nèi)存代碼*/
	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");
	}
	/*語(yǔ)句后跟符號(hào)為分號(hào)或end*/
	memcpy(nxtlev,fsys,sizeof(bool)*symnum);          /*每個(gè)后跟符號(hào)集和都包含上層后跟符號(hào)
	                                                    集合，以便補(bǔ)救*/
	nxtlev[semicolon]=true;
	nxtlev[endsym]=true;
	statementdo(nxtlev,&tx,lev);
	gendo(opr,0,0);                                   /*每個(gè)過(guò)程出口都要使用的釋放數(shù)據(jù)段指令*/
	memset(nxtlev,0,sizeof(bool) *symnum);            /*分程序沒(méi)有補(bǔ)救集合*/
	testdo(fsys,nxtlev,8);                            /*檢測(cè)后跟符號(hào)正確性*/
	listcode(cx0);                                    /*輸出代碼*/
	return 0;
}
/*
 *在名字表中加入一項(xiàng)
 *
 *k:名字種類(lèi)const ,var or procedure
 *ptx:名字表尾指針的指針，為了可以改變名字表尾指針的值
 *lev:名字所在的層次，以后所有的 lev 都是這樣
 *pdx:dx 為當(dāng)前應(yīng)分配的變量的相對(duì)地址，分配后要增加1
 */
 void enter(enum object k,int *ptx,int lev,int *pdx)
 {
	 (*ptx)++;
	 strcpy(table[(*ptx)].name,id);                  /*全局變量id中已存有當(dāng)前名字的名字*/
	 table[(*ptx)].kind=k;
	 switch(k)   
	 {
	       case constant:                              /*常量名字*/
			 if(num>amax)
			 {
				 error(31);                          /*數(shù)越界*/
				 num=0;
			 }
			  table[(*ptx)].val=num;
			  break;
	     case variable:                                  /*變量名字*/
			 table[(*ptx)].level=lev;
			 table[(*ptx)].adr=(*pdx);
			 (*pdx)++;
			 break;