scpascal.cpp

pascal编译器

firstTable[expression][0]=id;//expression
firstTable[expression][1]=num;
firstTable[expression][2]=lpare;
firstTable[expression][3]=rw_not;
firstTable[expression][4]=rw_true;
firstTable[expression][5]=rw_false;
firstTable[expression][6]=op_add;
firstTable[expression][7]=op_sub;

firstTable[procedure_statement][0]=id;//procedure_statement

firstTable[expression_list][0]=id;//expression_list
firstTable[expression_list][1]=num;
firstTable[expression_list][2]=lpare;
firstTable[expression_list][3]=rw_not;
firstTable[expression_list][4]=rw_true;
firstTable[expression_list][5]=rw_false;
firstTable[expression_list][6]=op_add;
firstTable[expression_list][7]=op_sub;

firstTable[simple_expression][0]=id;//simple_expression
firstTable[simple_expression][1]=num;
firstTable[simple_expression][2]=lpare;
firstTable[simple_expression][3]=rw_not;
firstTable[simple_expression][4]=rw_true;
firstTable[simple_expression][5]=rw_false;
firstTable[simple_expression][6]=op_add;
firstTable[simple_expression][7]=op_sub;

firstTable[term][0]=id;//term
firstTable[term][1]=num;
firstTable[term][2]=lpare;
firstTable[term][3]=rw_not;
firstTable[term][4]=rw_true;
firstTable[term][5]=rw_false;

firstTable[sign][0]=op_add;//sign
firstTable[sign][1]=op_sub;

firstTable[factor][0]=id;//factor
firstTable[factor][1]=num;
firstTable[factor][2]=lpare;
firstTable[factor][3]=rw_not;
firstTable[factor][4]=rw_true;
firstTable[factor][5]=rw_false;

firstTable[start][0]=rw_program;


}
struct transnode{
	int formula;//公式号
	int dot;	//点位置
	int forward; //向前搜索符号串
	transnode * next;//指向本结构的指针
};
	
//#define struct transnode* transnodePtr



static int Firstback[30];//Firstback[0]是指返回的值的个数初始化为0，后面的是返回的First值初始化为－1。


void First(struct transnode *ptr)        //求任意字符串First集合
{
	int PN;
	int flag=0;

	if (productions[ptr->formula].length < (ptr->dot)) 
		return;

	if (productions[ptr->formula].length == (ptr->dot)){
		Firstback[1+Firstback[0]]=ptr->forward;
		Firstback[0]=Firstback[0]+1;
		return;
	}

	PN = productions[ptr->formula].product[ptr->dot+1];//PN是点后的字符代码。

	if (PN == empty ) {//PN点后是空
		return;
	}
	

	if (!IsNT(PN)) {	//如果PN是终结符
		Firstback[1+Firstback[0]]=PN;//返回的是该终结符
		Firstback[0]=Firstback[0]+1;
		return;
	}

	if (IsNT(PN)){	//如果PN是非终结符
		for(int i = 0;firstTable[PN][i] != -1;i++){//检查First表是否该非终结符的First中可以为空
			if (firstTable[PN][i]==empty){//若有空置标志位
				flag=1;
			}
		}

		if (flag==0){//先前检查没有空
			int j;
			for(j = 0;firstTable[PN][j] != -1;j++){
				Firstback[j+1+Firstback[0]] = firstTable[PN][j];
			}
			Firstback[0]=Firstback[0]+j;
		}

		if (flag==1){//先前检查有空
			 struct transnode * tempptr = new struct transnode;
			 //printf("%d ",tempptr);
			 tempptr->formula = ptr->formula;
			 tempptr->forward = ptr->forward;
			 tempptr->dot = ptr->dot+1;
			 First(tempptr);//先递归求得为空以后的First
			 int j;
			 for(j = 0;firstTable[PN][j] != -1;j++){
				 if (firstTable[PN][j] != empty){
					 Firstback[j+1+Firstback[0]] = firstTable[PN][j];
				 }
			 }
			 Firstback[0]=Firstback[0]+j-1;
		}
	}
}

typedef struct transnode* transnodePtr;

int PinPtr(transnodePtr p,transnodePtr ptr){			//查看节点p是否在ptr指示的链表中存在
	while(ptr != NULL){
		if ((p->formula == ptr->formula)&&
			(p->dot == ptr->dot)&&(p->forward == ptr->forward)){
			return 1;
		}else{
			ptr = ptr->next;
		}
	}
	return 0;
}
void Insert(struct transnode *ptr,struct transnode * newnode){  //在ptr指示的链表中插入一个新的结点
	struct transnode *fnode ;
	fnode = ptr;
	if (!PinPtr(newnode,ptr)){
		while (fnode->next != 0) {//一直搜索至最后的节点
			fnode=fnode->next;
		}

		fnode->next=newnode;
		newnode->next=0;
	}
}
int lengthof(struct transnode* p){		//计算结点数目
	int x = 0;
	while(p != NULL){
		x++;
		p = p->next;
	}
	return x;
}

struct transnode * closure(struct transnode *ptr){			//求ptr所指生成式的闭包
	int PN;
	struct transnode *aptr;
	aptr=ptr;
	while (aptr != 0){
		PN = productions[aptr->formula].product[aptr->dot+1];//PN是点后的字符代码。
		
		{//该程序块执行对First返回值初始化的任务
			int i;
			Firstback[0]=0;
			for(i = 1;i < 30;i++)
			Firstback[i] = -1;
		}

		//if (productions[ptr->formula].length <= (ptr->dot)); //若点在最后，PN没有,不作动作

		//if ((PN < 8)&&(PN>3)) ;	//如果PN是终结符,不作动作

		if (IsNT(PN)){
			struct transnode * tempptr = new struct transnode;
			//printf("%d ",tempptr);
			tempptr->formula = aptr->formula;
			tempptr->forward = aptr->forward;
			tempptr->dot = aptr->dot+1;
			First(tempptr);
			
			int i,j;
			for(i = 0;i < LENOFPRODUCTIONS; i++){
				if (productions[i].product[0]==PN)
					for(j = 0;j < Firstback[0];j++){
						struct transnode * newnode = new struct transnode;
						//printf("%d ",newnode);
						newnode->formula = i;//新建的节点公式号是从productions[i].product[1]搜索来
						newnode->dot = 0;//新建的节点点位置在0处
						newnode->forward = Firstback[j+1];//新建的向前搜索符号串是算得得First
						Insert(ptr,newnode);//在ptr指向的链表中插入新的一项newnode
					}
			}
		}
		int cc = lengthof(ptr);
		aptr=aptr->next;
	}
	return ptr;
}
//以上是closure（）部分的定义，下面开始初始化分析表
#define	MAX	1000	
//状态栈的定义
int stateStack[MAX];
int point = 0; 
int push(int x){					//进栈函数
	if (point == MAX){
		return 0;
	}else{
		stateStack[point] = x;
		point++;
		return 1;
	}
}
int pop(int x){						//出栈函数
	point = point-x;
	if (point<0){
		point = point+x;
		return 0;
	}else{
		return 1;
	}
}
int top(int x){					//找栈顶
	int i = point-x;
	if (i<0){
		printf("Not so many element in the stack");
		return -1;
	}else{
		return i;
	}
}
void printStack(){				//打印栈
	int i;
	for (i=0;i<point;i++){
		printf("%d",stateStack[i]);
	}
	printf("\n");
}

void printTop(int x){		//打印栈顶
	int i;
	for (i = top(x);i<point;i++){
		printf("%d",stateStack[i]);
	}
	printf("\n");
}

//actionTable和gotoTable分析表的结构定义
#define shift	0
#define reduce	1
#define acc	2
//#define	error	3
#define ok		4
#define MAXSTATES 1000

struct reduceInfo{
	int	formula;
	int	length;
	int leftsym;
};						//归约信息的结构
union actioninfo{
	int state;
	struct reduceInfo ri;
	void (*p)();
};						//action表的信息
struct actionItem{
	int typ;
	union actioninfo ai; 
};						//action表结点
struct actionItem actionTable[MAXSTATES][NUMOFSYMBOLS];

int	numofstates = 0;

union gotoinfo{
	int state;
	void (*p)();
};					//goto表的信息
struct gotoItem{
	int typ;
	union gotoinfo gi;
};					//goto表的结点
struct gotoItem gotoTable[MAXSTATES][NUMOFSYMBOLS];


struct LR1node{
	int length;
	transnodePtr tp;
};					//LR1项目状态集的头结点.

struct LR1node LR1[MAX];
int numofLR1 = 0;

//输出为增加项目集规范族和对goTable的设置


int compare(transnodePtr p1,transnodePtr p2){		//判断p1,p2所指链表是否完全相同
	transnodePtr p;
	p = p1;
	while(p != NULL){
		if (!(PinPtr(p,p2))){
			return 0;
		}
		p = p->next;
	}
	p = p2;
	while(p != NULL){
		if (!(PinPtr(p,p1))){
			return 0;
		}
		p = p->next;
	}
	return 1;
}
int findinLR1(transnodePtr ptr,int b){				//找新生LR1项目规范族是否已经存在
	int i;
	for (i = 0; i<numofLR1; i++){
		if (LR1[i].length == b){
			if (i == 335){
				printf("");
			}
			if (compare(ptr,LR1[i].tp)){
				return i;
			}
		}
	}
	return numofLR1;
}

void gofrom(int I){					//从LR1状态分析中状态迁移函数
	int flag[MAX];
	int i,ax,bx,cx;
	transnodePtr p,newPtr;
	transnodePtr ptr = NULL;

	
	if (I == 11){
		printf("");
	}
	for (i=0; i<MAX; i++){
		flag[i] = 0;
	}
	while(1){
		i = 0;
		p = LR1[I].tp;
		while ((flag[i] != 0) && (p->next != NULL)){
			p = p->next;
			i++;
		}
		
		if (flag[i] == 0){
			flag[i] = 1;
			//判断是否可做closure
			if (p->dot < productions[p->formula].length){
				//newPtr = (transnodePtr)malloc(sizeof(struct transnode));
				newPtr = new struct transnode;
				//printf("%d ",newPtr);
				newPtr->formula = p->formula;
				newPtr->dot = p->dot+1;
				newPtr->forward = p->forward;
				newPtr->next = NULL;
				ptr = newPtr;
				ax = productions[p->formula].product[(p->dot)+1];
				while (p->next != NULL) {
					p = p->next;
					++i;
					if (flag[i] == 0){
						if (p->dot<productions[p->formula].length){
							if (ax == productions[p->formula].product[(p->dot)+1]){
								//newPtr = (transnodePtr)malloc(sizeof(struct transnode));
								newPtr = new struct transnode;
								//printf("%d ",newPtr);
								newPtr->formula = p->formula;
								newPtr->dot = p->dot+1;
								newPtr->forward = p->forward;
								newPtr->next = ptr;
								ptr = newPtr;
								flag[i] = 1;
							}
						}
					}
				}
				ptr = closure(ptr);
				bx = lengthof(ptr);
				cx = findinLR1(ptr,bx);
				if (cx == numofLR1){
					if (numofLR1 == 405){
						printf("");
					}
					//printf("%d come from %d\n",numofLR1,I);
					if (numofLR1 == 11){
						printf("from %d",I);
					}
					numofLR1++;
					LR1[cx].length = bx;
					LR1[cx].tp = ptr;
				}
				//goTable[I,a] = c;
				if (IsNT(ax)){
					gotoTable[I][ax].typ = ok;
					gotoTable[I][ax].gi.state = cx;
				}else{
					actionTable[I][ax].typ = shift;
					actionTable[I][ax].ai.state = cx;
				}
			}
			else{
				
				if ((p->formula == 0) && (p->forward == DOLLAR)){
					actionTable[I][DOLLAR].typ = acc;
				}else{
					actionTable[I][p->forward].typ = reduce;
					actionTable[I][p->forward].ai.ri.formula = p->formula;
					actionTable[I][p->forward].ai.ri.length = productions[p->formula].length;
					actionTable[I][p->forward].ai.ri.leftsym = productions[p->formula].product[0];
				}
				continue;
			}
		}else{
			break;
		}
	}
}

void InitLR1(){				//初始化LR1项目规范集
	int i;
	for (i=0;i<MAX;i++){
		LR1[i].length = 0;
		LR1[i].tp = NULL;
	}
	
	transnodePtr ptr;

	ptr = new struct transnode;

	ptr->formula = 0;
	ptr->dot = 0;
	ptr->forward = DOLLAR;
	ptr->next = NULL;
	ptr = closure(ptr);
	LR1[0].length = lengthof(ptr);
	LR1[0].tp = ptr;
	numofLR1 = 1;

	i = 0;
	while(i<numofLR1){