compile.cpp

编译原理课程设计大作业PL0文法简易编译器

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "ctype.h"

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

typedef int BOOL;

#define cxmax 2000
#define amax 16383

#define imax 100 /* length of identifier table */
#define tmax 100 /* length of type table */
#define lmax 10  /* maximum level */
#define al 10  /* length of identifiers */
#define norw 27  /* number of reserverd words */

/* standard function */
#define fabs 0
#define fsqr 1
#define fodd 2
#define fchr 3
#define ford 4
#define fwrite 5
#define fwriteln 6
#define fread 7
#define freadln 8
#define feoln 9

/* standard types */
#define intip 1
#define booltip 2
#define chartip 3
#define realtip 4

/*指令码*/
typedef enum opcode{
	add, neg, mul, divd, remd, div2, rem2, eqli, neqi, lssi,
		leqi, gtri, geqi, dupl, swap, andb, orb,
		load, stor, hhalt, wri, wrc, wrl, rdi, rdc, rdl, eol,
		ldc, ldla, ldl, ldg, stl, stg, move, copy, addc, mulc,
		jump, jumpz, call, adjs, sets, pexit, inc, dec
}opcode;

/*指令结构体*/
typedef struct instr{
	opcode op;
	int a;
}instr;

/*词法类别*/
typedef enum symbol{pl0=-1,
ident, number, sstring, plus, minus, star, lbrack, rbrack,
colon, eql, neq, lss, leq, gtr, geq, lparen, rparen, comma, 
semicolon, period, becomes,
beginsym, endsym, ifsym, thensym, elsesym, whilesym, dosym,
casesym, repeatsym, untilsym, forsym, tosym, downtosym,
notsym, divsym, modsym, andsym, orsym, constsym, varsym,
typesym, arraysym, ofsym, recordsym, funcsym,procsym,cstring
}symbol;

/*变量类型*/
typedef enum idkind{
	konst, varbl, field, tipe, funkt
}idkind;

/*类型的种类，简单的，数组，记录类型*/
typedef enum tpkind{
	simple, arrays, records
}tpkind;

typedef char alfa[al+1];

instr code[cxmax + 1];
int m[amax + 1];

/*词法分析相关全局变量*/
char ch;
int cc = 0, ll = 0;
char line[129];
symbol sym;
alfa id;
char string[imax];
int num;
char str[81];
int slen;
/*alfa word[norw + 1];*/
int cx;
int lev;
int dx;
BOOL labeled;
int nl; /* as namelist[-1] */
int namelist[lmax];
int ix, tx; /* indices in tables */

/* identifier table */
typedef struct ITAB{
	alfa name;
	int link;
	int tip;
	idkind kind;
	union{
		int val; /*常量类型的值*/
		struct{
			int vlevel;
			int vadr;
			BOOL refpar;
		};   /*变量类型的属性*/
		int offset; /*域类型的偏移地址*/
		struct{
			int flevel;
			int fadr;
			int lastpar;
			int resultadr;
			BOOL inside;
		};   /*函数类型的属性*/
	};
}ITAB;
ITAB itab[imax + 1];

/* type table */
typedef struct TTAB{
	int size;
	tpkind kind;
	union{
		struct{
			int low;
			int high;
			int elemtip;
		}; /*数组类型的属性*/
		int fields; /*记录类型最后一个域的地址*/
	};
}TTAB;
TTAB ttab[tmax + 1];

/*保留字*/
static struct{
	alfa name;
	symbol lex;
}word[] = {
	{" ", pl0},
	{"begin", beginsym },
	{ "end", endsym },
	{ "if", ifsym },
	{ "then", thensym },
	{ "else", elsesym },
	{ "while", whilesym },
	{ "do", dosym },
	{ "case", casesym },
	{ "repeat", repeatsym },
	{ "until", untilsym },
	{ "for", forsym },
	{ "to", tosym },
	{ "downto", downtosym },
	{ "not", notsym },
	{ "div", divsym },
	{ "mod", modsym },
	{ "and", andsym },
	{ "or", orsym },
	{ "const", constsym },
	{ "var", varsym },
	{ "type", typesym },
	{ "array", arraysym },
	{ "of", ofsym },
	{ "record", recordsym },
	{ "function", funcsym },
	{ "procedure", procsym }
};

FILE * source;
BOOL eof_flag = FALSE;

symbol search()
{
	int i;
	for(i = norw; i >= 1; i--)
	{
		if(strcmp(id, word[i].name) == 0)
			return word[i].lex;
	}
	return ident;
}

void error(int n)
{
	int i;
	for(i = 0; i < ll; i++)
		putchar(line[i]);
	for(i = 0; i <= cc - 1; i++)
		putchar(' ');
	printf("^\n");
	printf("error %d detected\n", n);
	exit(1);
}

void getch()
{
	if (cc == ll)
	{
		memset(line, 0, 129);
		if(feof(source))
		{
			fprintf(stderr, "program incomplete\n");
			exit(0);
		}
		ll = 0;
		cc = 0;
		while(!feof(source) && (ch = getc(source)) != '\n')
		{
			line[ll] = ch;
			ll++;
		}
		if(ch == '\n')
		{
			line[ll] = ch;
			ll++;
		}
	}
	ch = line[cc];
	cc++;
}

void getsym()
{
	int k;
	int strend;
	while(ch == ' ' || ch == '\t' || ch == '\n')
		getch();
	if(isalpha(ch))
	{
		memset(id, 0, al+1);
		k = 0;
		do{
			if(k != al)
			{
				id[k] = ch;
				k++;
			}
			getch();
		}while(isalnum(ch));
		sym = search();
	}
	else if(ch=='\"')
	{
		k=0;
		do{
			getch();
			string[k]=ch;
			k++;
		}while(ch!='\"');
		sym=cstring;
	}
	else if(isdigit(ch))
	{
		num = 0;
		sym = number;
		do{
			num = 10 * num + (ch - '0');
			getch();
		}while(isdigit(ch));
	}
	else if(ch == ':')
	{
		getch();
		if(ch == '=')
		{
			getch();
			sym = becomes;
		}
		else
			sym = colon;
	}
	else if(ch == '>')
	{
		getch();
		if(ch == '=')
		{
			getch();
			sym = geq;
		}
		else
			sym = gtr;
	}
	else if(ch == '<')
	{
		getch();
		if(ch == '=')
		{
			getch();
			sym = leq;
		}
		else if(ch == '>')
		{
			getch();
			sym = neq;
		}
		else
			sym = lss;
	}
	else if(ch == '.')
	{
		getch();
		if(ch == '.')
		{
			getch();
			sym = colon;
		}
		else
			sym = period;
	}
	else if(ch == '\\')
	{
		slen = 0;
		strend = FALSE;
		sym = sstring;
		do{
			if(cc == ll)
				error(101);
			getch();
			if(ch == '\\')
			{
				getch();
				if(ch == '\\')
				{
					str[slen] = ch;
					slen++;
				}
				else
					strend = TRUE;
			}
			else
			{
				str[slen] = ch;
				slen++;
			}
		}while(strend == FALSE);
		if(slen == 0)
			error(102); /*不允许空字符串*/
		str[slen++] = '\0';
	}
	else if(ch == '+')
	{
		getch();
		sym = plus;
	}
	else if(ch == '-')
	{
		getch();
		sym = minus;
	}
	else if(ch == '*')
	{
		getch();
		sym = star;
	}
	else if(ch == '(')
	{
		getch();
		sym = lparen;
	}
	else if(ch == ')')
	{
		getch();
		sym = rparen;
	}
	else if(ch == '[')
	{
		getch();
		sym = lbrack;
	}
	else if(ch == ']')
	{
		getch();
		sym = rbrack;
	}
	else if(ch == '=')
	{
		getch();
		sym = eql;
	}
	else if(ch == ',')
	{
		getch();
		sym = comma;
	}
	else if(ch == ';')
	{
		getch();
		sym = semicolon;
	}
	else if(ch == '{')
	{
		do{
			getch();
		}while(ch != '}');
		getch();
		getsym();
	}
	else
		error(104);
}

void check(symbol s)
{
	if(sym != s)
		error(s);
}

void skip(symbol s)
{
	check(s);
	getsym();
}

/*将符号串登记入符号表*/
void enter(alfa id, idkind k, int t)
{
	int j;
	if(ix == imax)
		error(104);
	else
	{
		ix++;
		strcpy(itab[0].name, id);
		if(lev == -1)
			j = nl;
		else
			j = namelist[lev];
		while(strcmp(itab[j].name, id) != 0)
			j = itab[j].link;
		if(j != 0)
			error(105);
		else
		{
			strcpy(itab[ix].name, id);
			if(lev == -1)
				itab[ix].link = nl;
			else
				itab[ix].link = namelist[lev];
			itab[ix].tip = t;
			itab[ix].kind = k;
			
			if(lev == -1)
				nl = ix;
			else
				namelist[lev] = ix;
		}
	}
}

/*在符号表中查找符号，返回位置*/
int position()
{
	int i , j;
	strcpy(itab[0].name, id);
	i = lev;
	do{
		if(i == -1)
			j = nl;
		else
			j = namelist[i];
		while(strcmp(itab[j].name, id) != 0)
			j = itab[j].link;
		i = i - 1;
	}while(i >= -1 && j == 0);
	if(j == 0)
		error(106);
	return j;
}

void gen(instr i)
{
	switch(i.op)
	{
	case dupl:
	case eol:
	case ldc:
	case ldla:
	case ldl:
	case ldg:
		dx = dx - 1;
		break;
	case add:
	case mul:
	case divd:
	case remd:
	case eqli:
	case neqi:
	case lssi:
	case leqi:
	case gtri:
	case geqi:
	case andb:
	case orb:
	case wrc:
	case rdi:
	case rdc:
	case stl:
	case stg:
	case jumpz:
		dx = dx + 1;
		break;
	case stor:
	case wri:
	case move:
		dx = dx + 2;
		break;
	case copy:
		dx = dx - i.a + 1;
		break;
	case adjs:
		dx = dx + i.a;
		break;
	}
	if(!(((i.op == addc || i.op == adjs) && (i.a == 0)) || ((i.op == mulc) && (i.a == 1))))
	{
		if(labeled)
		{
			code[cx] = i;
			cx = cx +1;
			labeled = FALSE;
		}
		else if(code[cx - 1].op == ldc && i.op == add)
		{
			code[cx - 1].op = addc;
		}
		else if(code[cx - 1].op == ldc && i.op == mul)
		{
			code[cx - 1].op = mulc;
		}
		else if(code[cx - 1].op == ldc &&  i.op == neg)
		{
			code[cx - 1].a = -code[cx - 1].a;
		}
		else if(code[cx - 1].op == ldc && code[cx - 1].a == 2 && i.op == divd)
		{
			code[cx - 1].op = div2;
		}
		else if(code[cx - 1].op == ldc && code[cx - 1].a == 2 && i.op == remd)
		{
			code[cx - 1].op = rem2;
		}
		else if(code[cx - 1].op == ldc && i.op == stor)
		{
			code[cx - 1].op = stg;
		}
		else if(code[cx - 1].op == ldc && i.op == load)
		{
			code[cx - 1].op = ldg;
		}
		else if(code[cx - 1].op == ldla && i.op == stor)
		{
			code[cx - 1].op = stl;
		}
		else if(code[cx - 1].op == ldla && i.op == load)
		{
			code[cx - 1].op = ldl;
		}
		else
		{
			code[cx] = i;
			cx = cx + 1;
		}
	}
}

void gen0(opcode op)
{
	instr i;
	i.op = op;
	gen(i);
}

void gen1(opcode op, int a)
{
	instr i;
	i.op = op;
	i.a = a;
	gen(i);
}

int codelabel()
{
	labeled = TRUE;
	return cx;
}

void address(int lv, int ad)
{
	if(lv == 0)
		gen1(ldc, ad);
	else if(lv == lev)
		gen1(ldla, ad - dx);
	else
	{
		gen1(ldl, -dx);
		while(lv + 1 != lev)
		{
			gen0(load);
			lv = lv + 1;
		}
		gen1(addc, ad);
	}
}

void addressvar(int ref)
{
	address(itab[ref].vlevel, itab[ref].vadr);
	if(itab[ref].refpar)
		gen0(load);
}

void mustbe(int x, int y)
{
	if(x != y)
	{
		if((ttab[x].kind == arrays) && (ttab[y].kind == arrays) && 
			(ttab[x].low == ttab[y].low) && (ttab[x].high == ttab[y].high))
			mustbe(ttab[x].elemtip, ttab[y].elemtip);
		else
			error(107);/*类型不匹配*/
	}
}

void expression(int * x);

void selector(int * t, int * ref)
{
	int j, x;
	*t = itab[*ref].tip;
	getsym();
	if(sym == period ||sym == lbrack)
	{
		addressvar(*ref);
		*ref = 0;
		while(sym == period || sym == lbrack)
		{
			switch(sym)
			{
			case period:
				if(ttab[*t].kind != records)
					error(108);
				else
				{
					getsym();
					check(ident);
					j = ttab[*t].fields;
					strcpy(itab[0].name, id);
					while(strcmp(itab[0].name, id) != 0)
						j = itab[j].link;
					if(j == 0)
						error(109);
					else
					{
						gen1(addc, itab[j].offset);
						*t = itab[j].tip;
						getsym();
					}
				}
				break;
			case lbrack:
				do{
					if(ttab[*t].kind != arrays)
						error(110);
					else
					{
						getsym();
						expression(&x);
						mustbe(intip, x);
						gen1(addc, -(ttab[*t].low));
						*t = ttab[*t].elemtip;
						gen1(mulc, ttab[*t].size);
						gen0(add);
					}
				}while(sym == comma);
				skip(rbrack);
				break;
			}
		}
	}
}

void varpar(int * t)
{
	int j;
	check(ident);
	j = position();
	selector(t, &j);
	if(j != 0)
		addressvar(j);