ll1.c

lex files for given decription used as assignment in compiler design

	printf("\n");
#endif
}


void getFirstVn(){
	int ifChanged,ifgetnull,i,j,LeftID;
	IDNode *pt1,*pt2,*pt3;

	ifChanged = 1;
	while(ifChanged){
		ifChanged = 0;
		for(i=0;i<=Line_Num;i++){
			pt1=*(ppro+i);pt2=pt1->next;
			LeftID=pt1->ID;
			if(pt2->ID>=200){/*x->a OR x->&*/
				ifChanged = insert2link(FirstVn+LeftID-100,pt2,0)||ifChanged;
			}
			else{
				pt3 = getFirstExp(pt2,&ifgetnull);
				ifChanged = add2link(FirstVn+LeftID-100,pt3,1,0)||ifChanged;
				if(ifgetnull){		/*getFirstExp() returns no '&',but uses ifgetnul to mark if it should contain '&'*/
					pt2 = CreateNewIDNode;
					pt2->ID=getVtID('&');pt2->next=NULL;
					ifChanged = insert2link(FirstVn+LeftID-100,pt2,1)||ifChanged;
				}
			}
		}/*for*/
	}
/*#ifdef DEBUG	
	for(j=0;j<Vn_ID_next-100;j++){
			pt1 = FirstVn[j];
			printf("%d.",j);
			while(pt1){
				printf("%c-",Vt[pt1->ID-200].Tch);
				pt1=pt1->next;
			}
			printf("END\n");
	}
#endif*/
}

void getFirstRight(){/*get the first set of the right part of the expression*/
	int i,ifgetnull;
#ifdef DEBUG
	int j;
#endif
	IDNode *pt;
	for(i=0;i<=Line_Num;i++){
		pt=ppro[i]->next;
		pt = getFirstExp(pt,&ifgetnull);
		if(pt) add2link(FirstRight+i,pt,1,1);
		if(ifgetnull){		/*getFirstExp() returns no '&',but uses ifgetnul to mark if it should contain '&'*/
			pt = CreateNewIDNode;
			pt->ID=getVtID('&');pt->next=NULL;
			insert2link(FirstRight+i,pt,1);
		}
	}
#ifdef DEBUG
	for(j=0;j<=Line_Num;j++){
			pt = FirstRight[j];
			printf("%d.",j);
			while(pt){
				printf("%c-",Vt[pt->ID-200].Tch);
				pt=pt->next;
			}
			printf("END\n");
	}
#endif
}

void getFollow(){/*get follow set*/
	IDNode *pt1,*pt2;
	int i,LeftID,ifgetnull;/*mark if can =>&*/
	int mark;/*nots whether change*/
	/*add '#' to Vt&Follow(S)*/
	Vt[Vt_ID_next-200].ID = Vt_ID_next;
	Vt[Vt_ID_next-200].Tch = '#';
	Vt_ID_next++;
	pt1 = CreateNewIDNode;
	pt1->ID = getVtID('#');pt1->next = NULL;
	Follow[0] = pt1;
	/*stage 2*/
	mark = 1;
	while(mark){/*changed*/
		mark = 0;
		for(i=0;i<=Line_Num;i++){
			pt1 = ppro[i]->next;
			LeftID = ppro[i]->ID;
			while(pt1){/*pt1!=NULL,to scan from the head to the tail in one link*/
				if((pt1->ID>=100)&&(pt1->ID<200)){/*Vn*/
					pt2 = getFirstExp(pt1->next,&ifgetnull);/*get first set of the right part of itself*/
					if(pt2) mark = add2link(Follow+pt1->ID-100,pt2,1,0)||mark;
					if(ifgetnull){				/*FOLLOW(A) is contained in FOLLOW(B)*/
						mark = add2link(Follow+pt1->ID-100,Follow[LeftID-100],0,0);
					}
				}/*if*/
				pt1 = pt1->next;
			}
		}
	}
#ifdef DEBUG
	for(i=0;i<Vn_ID_next-100;i++){
			pt1 = Follow[i];
			printf("%d.",i);
			while(pt1){
				printf("%c-",Vt[pt1->ID-200].Tch);
				pt1=pt1->next;
			}
			printf("END\n");
	}
#endif
}

void getSelect(){/*get SELECT sets*/
	int i,LeftID,ifgetnull;
#ifdef DEBUG
	IDNode *pt1;
#endif
	for(i=0;i<=Line_Num;i++){
		LeftID = ppro[i]->ID;
		add2link(Select+i,FirstRight[i],0,0);	/*copy firstright to select,the 4th para=0 in order not to copy '&'*/
		getFirstExp(ppro[i]->next,&ifgetnull); /*check if the right part can get NULL*/
		if (ifgetnull) 
			add2link(Select+i,Follow[LeftID-100],0,0);	/*if can get NULL,add follow to select*/
	}
#ifdef DEBUG
	for(i=0;i<=Line_Num;i++){
			pt1 = Select[i];
			printf("%d.",i);
			while(pt1){
				printf("%c-",Vt[pt1->ID-200].Tch);
				pt1=pt1->next;
			}
			printf("END\n");
	}
#endif
}



void printSets(){
	int i,num;
	char ch;
	IDNode *pt;
	printf("\nFirst set of the right part:\n");/*first*/
	for(i=0;i<=Line_Num;i++){
		printf("FIRST(");
		pt = ppro[i]->next;
		PrintLink(pt,0);
		printf(")={");
		pt = FirstRight[i];
		PrintLink(pt,',');
		printf("}\n");
	}
	printf("Press any key to continue...\n");
	getch();
	printf("\nFollow set of Vn:\n");			/*follow*/
	for(i=0;i<Vn_ID_next-100;i++){
		printf("FOLLOW(%c)={",Vn[i].Nch);
		pt = Follow[i];
		PrintLink(pt,',');
		printf("}\n");
	}
	printf("Press any key to continue...\n");
	getch();
	printf("\nSelect set of expression:\n");	/*select*/
	for(i=0;i<=Line_Num;i++){
		printf("SELECT(");
		printf("%c->",Vn[ppro[i]->ID-100].Nch);
		pt = ppro[i]->next;
		PrintLink(pt,0);
		printf(")={");
		pt = Select[i];
		PrintLink(pt,',');
		printf("}\n");
	}
	printf("Press any key to continue...\n");
	getch();
}
void judgeLL1(){/*decide whether this is LL(1)*/
    int i,j,ID1,ID2,t;
	IDNode *pt;
	ifLL1=1;		/*assume it is LL1(1),if not,ifLL1 will be changed to 0 in future*/
	printf("\nThe judging of LL(1) is below:\n");
	for(i=0;i<Line_Num;i++){
		ID1 = ppro[i]->ID;
		for(j=i+1;j<=Line_Num;j++){
			ID2 = ppro[j]->ID;
			if(ID1==ID2){
				pt = ppro[i];
				printf("SELECT(%c->",Vn[pt->ID-100].Nch);	
				PrintLink(pt->next,0);
				pt = ppro[j];
				printf(")^SELECT(%c->",Vn[pt->ID-100].Nch);
				PrintLink(pt->next,0);
				printf(")={");
				PrintLink(Select[i],',');
				printf("}^{");
				PrintLink(Select[j],',');
				printf("}=");
				t = ifCross(Select[i],Select[j]);		/*ifCross judge if two links has same nodes,if yes,print out in form of {a,b,c,...}*/
				if(t){
					ifLL1 = 0;
					printf("!=NULL\n");
				}
				else printf("NULL\n");
				}
			}
	}
	if(ifLL1){
		printf("\nThis is LL(1)!\nPress any key to continue...\n");	/*output the result*/
		getch();
	}
	else {
		printf("\nThis is NOT LL(1)!\nPress any key to exit...\n");
		getch();
		exit(0);
	}	
}
void set_tb_cell(pa_table tb,int VnID,int VtID,IDNode *pExp){/*set a cell of the table*/
	int i,j;
	for(i=0;i<tb.row_num;i++){
		if (*(tb.row_info+i)==VnID) break; /*get the row*/
	}
	for(j=0;j<tb.col_num;j++){
		if (*(tb.col_info+j)==VtID) break;/*get the col*/
	}
	*(tb.ptb+tb.col_num*i+j) = pExp;		/*set the pointer*/
}

IDNode* get_tb_cell(pa_table tb,int VnID,int VtID){	/*get a cell of the table that VnID,VtID points to*/
	int i,j;
	for(i=0;i<tb.row_num;i++){
		if (*(tb.row_info+i)==VnID) break; /*get the row*/
	}
	for(j=0;j<tb.col_num;j++){
		if (*(tb.col_info+j)==VtID) break;/*get the col*/
	}
	return *(tb.ptb+tb.col_num*i+j);
}

void printtb(pa_table tb){
	/*first line*/
	int i,j,r,l;
	char ch;
	IDNode *pt;
	r=tb.row_num;
	l=tb.col_num;
	printf("\n\t ");
	for(j=0;j<l;j++)
		printf("\t%c  ",Vt[*(tb.col_info+j)-200].Tch);
	printf("\n");
	for(i=0;i<r;i++){
		printf("\t%c   ",Vn[*(tb.row_info+i)-100].Nch);/*the first line*/
		for(j=0;j<l;j++){
			printf("   ");/*3 blanks*/
			pt = *(tb.ptb+i*tb.col_num+j);/*get the content*/
			if(pt!=NULL){	/*in case NULL*/
				printf("->");
				while(pt){
					if(pt->ID>=200)
						ch = Vt[pt->ID-200].Tch;
					else ch = Vn[pt->ID-100].Nch;
					printf("%c",ch);
					pt = pt->next;
				}
			}
			else printf(" 0 ");
			printf("   ");
		}
		printf("\n");
	}
}
pa_table getpa_table(){/*get the table for analyzation table*/
	int i,j,r,l,VnID,VtID;
	IDNode *pExp,*ps,**ppt;
	pa_table pat;
	/*initialization*/
	r=pat.row_num = Vn_ID_next-100;
	l=pat.col_num = Vt_ID_next-200-1;	/*'1' means to get rid of '&',which is not Vt but be included in Vt for convinence*/
	ppt = pat.ptb = (IDNode**)malloc(sizeof(IDNode*)*r*l);
	for(i=0;i<r;i++)
		for(j=0;j<l;j++,ppt++)
			*ppt = NULL;	;/*initialization*/
	pat.row_info = (int*)malloc(sizeof(int)*r);
	pat.col_info = (int*)malloc(sizeof(int)*l);
	for(i=0;i<r;i++){
		*(pat.row_info+i) = Vn[i].ID;
	}
	for(i=0,j=0;i<l+1;i++){
		if (Vt[i].Tch=='&') continue;/*remember to ignore '&'*/
		else {
			*(pat.col_info+j) = Vt[i].ID;
			j++;
		}
	}
	/*set*/
	for(i=0;i<=Line_Num;i++){
		pExp = ppro[i];
		VnID = pExp->ID;	/*Vn*/
		pExp = pExp->next;	/*pExp*/
		ps = Select[i];
		while(ps){ /*scan select[]*/
			VtID = ps->ID;
			set_tb_cell(pat,VnID,VtID,pExp);
			ps = ps->next;
		}
	}
	return pat;
}
int analyzing(pa_table tb,char *str){/*analyse the string*/
	int i,step=0;
	char X,a,ch;
	IDNode *p;
	char ti[100];/*used to transform the expression X->x1x2...xn to xn...x2x1*/
	initstack();/*initialization*/
	push('#');push(Vn[0].Nch);/*send '#','S' into stack*/
	/*output first line*/
	printf(" STEP\tSTACK\t\tREMAINING STRING\tACTION\n");
	a = *str++;
	while(1){
		/*output each line*/
		step++;
		if(step%20==0){
			printf("Press any key to continue...\n");
			getch();
		}
		printf("%d\t",step);
		printStack();/*output the stack in char*/
		printf("\t\t");
		printf("%15s",str-1);	/*output the input string*/
		printf("\t\t");
		X = pop();
		if((getID(X)>=200)&&(X!='#')){	/*Vt*/
			if(X==a){			/*match?*/
				printf("%c MATCH\n",a);
				a = *str++;
				continue;
			}
			else{
				printf("Error!\n");
				return 0;
			}
		}
		else if(X == '#'){	/*X='#'?*/
			if(X==a){			/*accept?*/
				printf("ACCEPT!\n");
				return 1;
			}
			else{
				printf("Error!\n");
				return 0;
			}
		}
		else{
			p = get_tb_cell(tb,getID(X),getID(a));
			if(p){/*has expression*/
				/*push them  into the stack adversely*/
				printf("%c->",X);
				i=0;
				while(p){
					if(p->ID>=200) ch = Vt[p->ID-200].Tch;
					else ch = Vn[p->ID-100].Nch;
					printf("%c",ch);
					if (ch=='&') break;		/*'&' must not be pushed into stack*/
					ti[i++] = ch;
					p = p->next;
				}
				printf("\n");
				for(i--;i>=0;i--){
					push(ti[i]);
				}
				continue;
			}
			else{				/*no expression*/
				printf("Error!\n");
				return 0;
			}
		}
	}
}
void ll1(){
	FILE *fp;
	pa_table tb;
	char str[100],strt[100],ch;
startc:
	
	printf("Judge file by pressing 2,else to EXIT\n");
	ch=getch();
	if(ch=='1'){
		printf("DEMO1 of NO LL(1) by pressing 1,DEMO2 of LL(1) by pressing 2,else to return to the main menu\n");
		ch=getch();
		if(ch == '1'){
			strcpy(str,"demo1.dat");
		}
		else if(ch=='2'){
			strcpy(str,"demo2.dat");
		}
		else goto startc;
	}
	else if(ch=='2'){
		printf("\nPress any key to continue...\n");
		getch();
		printf("Input the file path&name,for example:c:\\demo1.dat\n");
		scanf("%s",str);		
	}
	else exit(0);
#ifdef DEBUG
	printf("%s\n",str);
#endif
	fp = fopen(str,"r");
	
	if(!fp){
		getcwd(strt,100);				/*add the function of adding to current dir to file name,in case that user enters only file name without path*/
		strcat(strt,"\\");
		strcat(strt,str);
		fp = fopen(strt,"r");
		if(!fp) {
			printf("FILE OPEN ERROR!\n Retry!\n");
			goto startc;
		}
	}
	initiate();
	File_Input(fp);
	fp = fopen(str,"r");
	File_Print(fp);
	fclose (fp);	
#ifdef DEBUG
	debugprint();
#endif
	getNULLVn();
	getFirstVn();
	getFirstRight();
	getFollow();
	getSelect();
	printSets();
	judgeLL1();
	if(ifLL1) {
		tb = getpa_table();
		printf("\nPredict Analyzation Table:\n");
		printtb(tb);
		printf("Press any key to continue...\n");
		getch();
anotherstr:	
		printf("\nPlease enter the input string:(make sure to end up with '#')\n");
		scanf("%s",str);
		analyzing(tb,str);

		printf("Press 1 to input another string,else key to exit\n");
		ch = getch();
		if(ch=='1') goto anotherstr;
		else exit(0);
	}
}
main(){
	ll1();
}