/*
 * PL/0 complier program for win32 platform (implemented in C)
 *
 * The program has been test on Visual C++ 6.0, Visual C++.NET and
 * Visual C++.NET 2003, on Win98, WinNT, Win2000, WinXP and Win2003
 *
 * 使用方法：
 * 運(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)");   /* 是否輸出虛擬機(jī)代碼 */
		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("fa1.tmp", "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))   /* 調(diào)用編譯程序 */
			{
				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();    /* 調(diào)用解釋執(zhí)行程序 */
				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è)置指令名稱 */
	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");

	/* 設(shè)置符號(hào)集 */
	for (i=0; i<symnum; i++)
	{
		declbegsys[i] = false;
		statbegsys[i] = false;
		facbegsys[i] = false;
	}

	/* 設(shè)置聲明開始符號(hào)集 */
	declbegsys[constsym] = true;
	declbegsys[varsym] = true;
	declbegsys[procsym] = true;

	/* 設(shè)置語句開始符號(hào)集 */
	statbegsys[beginsym] = true;
	statbegsys[callsym] = true;
	statbegsys[ifsym] = true;
	statbegsys[whilesym] = true;

	/* 設(shè)置因子開始符號(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 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)
			//richard
			if (EOF == fscanf(fin,"%c", &ch))
			{
				line[ll] = 0;
				break;
			}
			//end richard
			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;

	/* the original version lacks "\r", thanks to foolevery */
	while (ch==' ' || ch==10 || ch==13 || 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 {    /* 搜索當(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 = 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"); /* 程序過長 */
		return -1;
	}
	code[cx].f = x;
	code[cx].l = y;
	code[cx].a = z;
	cx++;
	return 0;
}


/*
* 測(cè)試當(dāng)前符號(hào)是否合法
*
* 在某一部分（如一條語句，一個(gè)表達(dá)式）將要結(jié)束時(shí)時(shí)我們希望下一個(gè)符號(hào)屬于某集?* （該部分的后跟符號(hào)），test負(fù)責(zé)這項(xiàng)檢測(cè)，并且負(fù)責(zé)當(dāng)檢測(cè)不通過時(shí)的補(bǔ)救措施，
* 程序在需要檢測(cè)時(shí)指定當(dāng)前需要的符號(hào)集合和補(bǔ)救用的集合（如之前未完成部分的后跟
* 符號(hào)），以及檢測(cè)不通過時(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è)不通過時(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)來的是指針，為防止下級(jí)函數(shù)改變上級(jí)函數(shù)的集合，開辟新的空?							傳遞給下級(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)，開始處理常量聲明 */
		{
			getsymdo;

			/* the original do...while(sym == ident) is problematic, thanks to calculous */
			/* do { */
			constdeclarationdo(&tx, lev, &dx);  /* dx的值會(huì)被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)，開始處理變量聲明 */
		{
			getsymdo;

			/* the original do...while(sym == ident) is problematic, thanks to calculous */
			/* 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) /* 收到過程聲明符號(hào)，開始處理過程聲明 */
		{
			getsymdo;

			if (sym == ident)
			{
				enter(procedur, &tx, lev, &dx); /* 記錄過程名字 */
				getsymdo;
			}
			else
			{
				error(4);   /* procedure后應(yīng)為標(biāo)識(shí)符 */
			}

			if (sym == semicolon)
			{
				getsymdo;
			}
			else
			{
				error(5);   /* 漏掉了分號(hào) */
			}

			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;
		testdo(nxtlev, declbegsys, 7);
	} while (inset(sym, declbegsys));   /* 直到?jīng)]有聲明符號(hào) */

	code[table[tx0].adr].a = cx;    /* 開始生成當(dāng)前過程代碼 */
	table[tx0].adr = cx;            /* 當(dāng)前過程代碼地址 */
	table[tx0].size = dx;           /* 聲明部分中每增加一條聲明都會(huì)給dx增加1，聲明部分已經(jīng)結(jié)束，dx就是當(dāng)前過程數(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");
	}

	/* 語句后跟符號(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è)過程出口都要使用的釋放數(shù)據(jù)段指令 */
	memset(nxtlev, 0, sizeof(bool)*symnum); /*分程序沒有補(bǔ)救集合 */
	testdo(fsys, nxtlev, 8);                /* 檢測(cè)后跟符號(hào)正確性 */
	listcode(cx0);                          /* 輸出代碼 */
	return 0;
}

/*
* 在名字表中加入一項(xiàng)
*
* k:      名字種類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;
	case procedur:  /*　過程名字　*/
		table[(*ptx)].level = lev;
		break;
	}
}

/*
* 查找名字的位置.