ll1.c

lex files for given decription used as assignment in compiler design

//IIT2006021
//Arunanshu Pandey
#include<iostream>
#include "stdlib.h"
#include "stdio.h"
#include <string.h> 
#include "ll.h"
#include "dir.h"
#include<conio.h>
using namespace std;
/*#define DEBUG*/

void initiate(){
	int i;

	Line_Num = -1;		/*special used in input*/
	Vn_ID_next = 100;   /*Vn 100...199*/
	Vt_ID_next = 200;   /*Vt 200...299*/
	for (i=0;i<100;i++){
		ppro[i]=NULL;
		Vn[i].ifgetnull = UNCERTAIN;
		FirstVn[i] = NULL;
		FirstRight[i] = NULL;
		Follow[i] = NULL;
		Select[i] = NULL;
	}
}
int getVnID(char ch){/*get the ID of Vn according to itselt*/
	int i=0;
	for (;i<Vn_ID_next-100;i++){
		if (Vn[i].Nch==ch) return Vn[i].ID;
	}
	return 0;
}

int getVtID(char ch){/*get the ID of Vt according to itselt*/
	int i=0;
	for (;i<Vt_ID_next-200;i++){
		if (Vt[i].Tch==ch) return Vt[i].ID;
	}
	return 0;
}

int getID(char ch){/*get the ID of V*/
	int i;
	i = getVnID(ch);
	if(i==0) i = getVtID(ch);
	return i;
}

int SeekoverVn(char ch){ /*scan vn, if ch in,then return its id,else return Vn_ID_next*/
	int i=0,r = Vn_ID_next;
	for (;i<Vn_ID_next-100;i++){
		if (ch == Vn[i].Nch){
			r = Vn[i].ID;
			break;
		}
	}
	return r;
}

int SeekoverVt(char ch){ /*scan vt, if ch in,then return its id,else return Vt_ID_next*/
	int i=0,r = Vt_ID_next;
	for (;i<Vt_ID_next-100;i++){
		if (ch == Vt[i].Tch){
			r = Vt[i].ID;
			break;
		}
	}
	return r;
}
Status File_Input (FILE *fp) { /*read file fp points to, get all fags,
and transform the oriental words to the form that the syntax analyser can read which is stored in ppro[]*/
	char ch;int idcurrent;
	int ifavailable;	/*notes whether to be transformed*/
	IDNode *pnewnode = NULL; /*pointer to the last node*/
	IDNode *pt;				/*temp pointer*/

	Line_Num = -1;

	ch = fgetc(fp);
	while (ch != EOF){
		ifavailable = 0;	/*to get ready*/
		if (ch=='|'){	/*for example S->AB|bC,'|' means a new expression*/
			ifavailable = 1;	/*notes to be transformed*/
			idcurrent = ppro[Line_Num]->ID;/*left part*/
			pnewnode = NULL;	/*a new expression*/		
		}
		else if ((ch>='A') && (ch<='Z')){
			idcurrent = SeekoverVn(ch); /*get the id of ch*/
			if (idcurrent==Vn_ID_next){
				Vn[Vn_ID_next-100].ID = Vn_ID_next;	/*add it in Vn*/
				Vn[Vn_ID_next-100].Nch = ch;
				Vn_ID_next++;
			}
			ifavailable = 1;	/*notes to be transformed*/
		}
		else if (ch=='\n'){/*carriage return*/
			pnewnode = NULL;
		}
		else if(ch!='>') {
			idcurrent = SeekoverVt(ch); /*get the id of ch*/
			if (idcurrent == Vt_ID_next){
				Vt[Vt_ID_next-200].ID = Vt_ID_next;	/*add it in Vt*/
				Vt[Vt_ID_next-200].Tch = ch;
				Vt_ID_next++;
			}
			ifavailable = 1;
		}
		if (ifavailable){/*to be transformed*/
			pt = CreateNewIDNode;
			pt->ID= idcurrent; pt->next= NULL;
			if (pnewnode == NULL){ /*notes CR*/
				Line_Num++;
				ppro[Line_Num] = pnewnode = pt;
			}
			else {
				pnewnode->next = pt;
				pnewnode = pt;
			}
		}
		ch = fgetc(fp);
	}
	return OK;
}

Status File_Print (FILE *fp) { /*print the file onto the screen*/
	char ch;
	printf("File Content: (Press any key to continue...)\n");
	getch();
	ch = fgetc(fp);
	while (ch!= EOF){
		printf("%c",ch);
		ch = fgetc(fp);	
	}
	printf("\nPress any key to continue...\n");
	getch();
}

#ifdef DEBUG
void debugprint(){
	int i;
	IDNode *pt;
	for (i=0;i<Vn_ID_next-100;i++){
	   printf (" %c  ",Vn[i].Nch);
	}
	printf ("\n");
	for (i=0;i<Vn_ID_next-100;i++){
	   printf ("%d ",Vn[i].ID);
	}
	printf("\n");
	for (i=0;i<Vt_ID_next-200;i++){
	   printf (" %c  ",Vt[i].Tch);
	}
	printf("\n");
	for (i=0;i<Vt_ID_next-200;i++){
	   printf ("%d ",Vt[i].ID);
	}
	printf("\n");

	for(i=0;i<=Line_Num;i++){
		pt = ppro[i];
		printf("%d.",i);
		while(pt){
			printf("%d-",pt->ID);
			pt=pt->next;
		}
		printf("END\n");
	}
}
#endif

int insert2link(IDNode **pdes,IDNode *pNode,int iffreeit){
	/*insert pNode to *pdes,with the order small to large*/
	/*no same 2, if can't insert,according to iffreeit,free pNode or not, and return 0,else return 1*/
	IDNode *ptd1,*ptd2,*pt=pNode;int cID;
	if(!iffreeit) {	/*if iffreeit==0,it means this node is in another link,i can't change it,so copy a new one*/
		pt = CreateNewIDNode;
		pt->ID=pNode->ID;
	}	
	pt->next = NULL;	/*to avoid error*/
	if(*pdes == NULL){/*insert directly*/
		*pdes = pt;
		return 1;}
	else if(pt->ID<=(*pdes)->ID){/*at the head*/
		if(pt->ID!=(*pdes)->ID){
			pt->next = *pdes;
			*pdes = pt;
			return 1;
		}
		else{
			if(iffreeit) free(pt);
			return 0;
		}
	}
	else{
		ptd1 = *pdes; ptd2 = ptd1->next;
		if(ptd2) cID = ptd2->ID;
		else cID = -1; /*if at the tail*/
		while(ptd2&&(pt->ID>cID)){
			ptd1 = ptd2; ptd2 = ptd2->next;
			if(ptd2) cID = ptd2->ID;
			else cID = -1;
		}
		if(pt->ID!=cID){
			pt->next = ptd2; ptd1->next = pt;
			return 1;
		}
		else {
			if(iffreeit) free(pt);
			return 0;
		}

	}
}


int add2link(IDNode **pdes,IDNode *psrc,int ifdelsrc,int ifcopyNULL){
	/*the return value notes if the *pdes is changed*/
	int mark=0,NULLID=getVtID('&');/*return value*/
	IDNode *ps = psrc,*pt;

	while(ps){
		if(ifcopyNULL||(ps->ID!=NULLID)){/*about '&'*/
			if(ifdelsrc) pt=ps;
			else {
			pt = CreateNewIDNode;
			pt->ID = ps->ID;
			}
			ps = ps->next;
			pt->next=NULL;
			mark=insert2link(pdes,pt,1)||mark;/*make sure mark is in the right*/
		}
		else ps = ps->next;
	}
	return mark;
}

void DeleteLink(IDNode *p){/*delete the link that p points to*/
	IDNode *pt;
	while(p){
		pt=p;
		p = p->next;
		free(pt);
	}
}

void DeleteAllVnExp(IDNode **pprotemp,int VnID){/*delet all Vn's expression*/
	IDNode *pt;
	int i;
	for(i=0;i<=Line_Num;i++){
		pt=*(pprotemp+i);
		if(pt&&(pt->ID==VnID)){
			DeleteLink(pt);
			*(pprotemp+i)=NULL;
		}
	}
}

void PrintLink(IDNode *pt,char ins){/*print Link,use ins to divide each character,if ins==0,the result will be consistant*/
	int num;
	char ch;
	while(pt){
			num = pt->ID;
			if(num>=200) 	ch = Vt[num-200].Tch;
			else ch = Vn[num-100].Nch;
			printf("%c",ch);
			if(ins&&pt->next) printf("%c",ins);
			pt = pt->next;
		}
}
int CheckVnNoExist(IDNode **pprotemp,int VnID){/*check whether Vn's expression exists.if no,mark it NO*/
	IDNode *pt;
	int i;
	for(i=0;i<=Line_Num;i++){
		pt=*(pprotemp+i);
		if(pt&&(pt->ID==VnID))
			return 0;
	}
	return 1;
}

IDNode* getFirstExp(IDNode *pExp,int *ifgetnull){
/*get First set of one expression that pExp points to,with no '&' in the return link*/
/*ifgetnull returns whether the exp can => &*/
	IDNode *phead=NULL;/*point to the new created link*/
	IDNode *pt;

	while(1){
		if(!pExp){/*get to the tail*/
			*ifgetnull = 1;
			return phead;
		}
		else if(pExp->ID>=200){
			pt = CreateNewIDNode;
			pt->ID = pExp->ID;pt->next = NULL;
			insert2link(&phead,pt,1);
			*ifgetnull=0;
			if (pExp->ID==getVtID('&')) *ifgetnull = 1;/*in case that S->&*/
			return phead;
		}
		else{/*Vn*/
			add2link(&phead,FirstVn[pExp->ID-100],0,0);
			if(Vn[pExp->ID-100].ifgetnull){
				pExp = pExp->next;
			}
			else{
				*ifgetnull = 0;
				return phead;
			}
		}
	}/*while*/
}

int ifCross(IDNode *p1,IDNode *p2){/*judge if p1 p2 has the same node,if has then print out in the form of {.,.,.}*/
	IDNode *pt1=p1,*pt2=p2;
	int ID1,ID2,mark=0,r=0;	/*mark notes if it's the first same character,used to control if print out ','*/
	while(pt1){
		ID1 = pt1->ID;
		while(pt2){
			ID2 = pt2->ID;
			if(ID1==ID2) {
				if(mark) printf(",");	/*if not the first, print ','*/
				else printf("{");
				printf("%c",Vt[ID1-200].Tch);
				mark = 1;
				r = r||1;				/*r stores the result*/
			}
			pt2 = pt2->next;
		}
		pt1 = pt1->next;
	}
	if(r) printf("}");					/*if not LL(1),print the remaining '}'*/
	return r;
}
void getNULLVn(){/*to decide the Vn that can deduct,the result is stored in Vn[] &*/
	int i,j,LeftID;
	IDNode **pprotemp=(IDNode**)malloc(sizeof(IDNode*)*(Line_Num+1));
	IDNode *pt1,*pt2;/*temp pointers*/
	int ifVnChanged; /*mark whether the ifgetnull changes in stage 3*/
	char ch; /*for printing*/

	for(i=0;i<=Line_Num;i++){
		*(pprotemp+i)=NULL;
	}
	/*Copy PProArray*/
	for(i=0;i<=Line_Num;i++){
		pt1=ppro[i];
		*(pprotemp+i) = pt2 = CreateNewIDNode;
		pt2->ID = pt1->ID;
		pt2->next = NULL;
		while(pt1->next!=NULL){
			pt1 = pt1->next;
			pt2->next = CreateNewIDNode;
			pt2 = pt2->next;
			pt2->ID = pt1->ID;
			pt2->next = NULL;
		}
	}
/*#ifdef DEBUG
	for(i=0;i<=Line_Num;i++){
		pt1 = pprotemp[i];
		printf("%d.",i);
		while(pt1){
			printf("%d-",pt1->ID);
			pt1=pt1->next;
		}
		printf("END\n");
	}
#endif*/
	/*The second stage*/
	for(i=0;i<=Line_Num;i++){
		pt1 = *(pprotemp+i);
		if(pt1) {/*in case that this link was deleted*/
			LeftID = pt1->ID;
			pt2 = pt1->next; /*point to the right part*/
			if(pt2->ID == getVtID('&')){
				Vn[LeftID-100].ifgetnull = YES;
				DeleteAllVnExp(pprotemp,LeftID);/*delet all Vn's expression*/
			}
			else while(pt2){
				if(pt2->ID >= 200){ /*Vt*/
					DeleteLink(pt1); /*Free all nodes*/
					*(pprotemp+i)=NULL;
					if (CheckVnNoExist(pprotemp,LeftID)) /*check whether Vn's expression exists if no,mark it NO*/
						Vn[LeftID-100].ifgetnull=NO;
					break;	/*stop while*/
				}
				pt2 = pt2->next;
			}
		}
/*#ifdef DEBUG
	for(j=0;j<=Line_Num;j++){
			pt1 = pprotemp[j];
			printf("%d.",j);
			while(pt1){
				printf("%d-",pt1->ID);
				pt1=pt1->next;
			}
			printf("END\n");
		}
		printf("%d\n",i);
#endif*/
	}
	/*The 3rd Stage*/
	ifVnChanged = YES;
	while(ifVnChanged == YES){
		ifVnChanged = NO;
		for(i=0;i<=Line_Num;i++){
			pt1 = *(pprotemp+i);
			if(pt1){/*not NULL*/
				LeftID = pt1->ID;
				pt2 = pt1->next;/*point to the right part*/
				while(pt2){/*not reach the tail*/
					if((pt2->ID>=100)&&(pt2->ID<200)){/*Vn*/
						switch(Vn[pt2->ID-100].ifgetnull){
							case YES: pt1->next = pt2->next;/*Delete Vn(&)*/
									free(pt2);
									pt2 = pt1->next;
									if((*(pprotemp+i))->next == NULL){/*the right NULL*/
										Vn[(*(pprotemp+i))->ID-100].ifgetnull=YES;
										ifVnChanged = YES;
										DeleteAllVnExp(pprotemp,LeftID);
										pt2 = NULL; /*force to end while*/
									}
									break;
							case NO:DeleteLink(*(pprotemp+i));
									*(pprotemp+i)=NULL;
									if(CheckVnNoExist(pprotemp,LeftID)){
										Vn[LeftID-100].ifgetnull = NO;
										ifVnChanged = YES;
									}
									pt2 = NULL; /*force to end while*/
									break;
							default:pt1=pt2;
									pt2=pt2->next;
						}
					}
					else{
						pt1=pt2;pt2=pt2->next;
					}
					}
				}
			}
	}
	free(pprotemp);
	/*printout*/
#ifdef DEBUG
	for (i=0;i<Vn_ID_next-100;i++)
		printf(" %c",Vn[i].Nch);
	printf("\n");
	for (i=0;i<Vn_ID_next-100;i++){
		switch(Vn[i].ifgetnull){
			case YES:ch='Y';break;
			case NO: ch='N';break;
			default:ch='?';
		}
		printf(" %c",ch);
	}