lr(0).c

构造LR(0)分析表。对给定的文法

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LEN 40

typedef struct {
		int expressionNum;
		int pointNum;
}statusType;
typedef struct {
		int status1;
		char character;
		int status2;
}gotoType;

statusType tempStatus[LEN];
statusType status[LEN][LEN];
gotoType gotoStatus[LEN];

char wenfa[LEN][LEN];
char expressions[LEN][LEN];
int temp[LEN];
char characters[LEN];
char ends[LEN];
char notEnds[LEN];
int table[LEN][LEN];

void readFromFile(void);
void fillExpression(void);
void fillTemStatuspNull(void);
void fillStatusNull(void);
int closure(void);
char isEnd(char);
char afterChar(int ,int);
void expand(char);
int hasStatus(void);
void allCharacters(void);
void fillTempStatus(int ,char);
void DNF(void);
void fillGoto(int,char,int);
void allEndsAndNotEnds(void);
int getGotoStatus(int,char);
void initTable(void);
int getTable(int ,char);
void printWenFa(void);
void printTable(void);
void control(char *);

void readFromFile()
{
	FILE *fp;
	char temp;
    char fileName[10];
	printf("please input your fileName:");
	scanf("%s",fileName);
	if((fp=fopen(fileName,"r"))==NULL)
	{
		printf("no such file");
		exit(0);
	}
	temp=fgetc(fp);
	int i=0;
	int j=0;
	while(temp!=EOF)
	{
		for(j=0;temp!='\n';j++)
		{
			while(temp==' ')
				temp=fgetc(fp);
			wenfa[i][j]=temp;
			temp=fgetc(fp);
		}
		temp=fgetc(fp);
		i++;
	}
}


void fillExpression(void)
{
		int i=0, j=0, n=3, m=1;
		expressions[0][0]='@';
		expressions[0][1]='-';
		expressions[0][2]='>';
		expressions[0][3]=wenfa[0][0];
		for(;i<LEN;i++)
			for(j=3;j<strlen(wenfa[i]);j++)
			{
				if(wenfa[i][j]!='|')
				{
					expressions[m][0]=wenfa[i][0];
					expressions[m][1]='-';
					expressions[m][2]='>';
					expressions[m][n]=wenfa[i][j];
					n++;
				}
				else
				{
					m++;
					n=3;
				}
			}
}
void fillStatusNull(void)
{
		int i=0;
		int j=0;
		for(i=0;i<LEN;i++)
				for(j=0;j<LEN;j++)
				{
						status[i][j].expressionNum=-1;
						status[i][j].pointNum=-1;
				}
}

void fillTempStatusNull(void)
{
		int i=0;
		for(i=0;i<LEN;i++)
		{
				tempStatus[i].expressionNum=-1;
				tempStatus[i].pointNum=-1;
		}
}


int closure(void)
{
		int i=0,p=0,p2=0,j=0,k=0,m;
		char ch;
		for(;status[p][0].expressionNum!=-1;p++)
		{}
		for(i=0;tempStatus[i].expressionNum!=-1;i++)
		{
				ch=afterChar(tempStatus[i].expressionNum,tempStatus[i].pointNum);
				if(ch=='\0'|| isEnd(ch)=='y')
						continue;
				else
				{
						for(k=0;k<LEN;k++)
								temp[k]=-1;
						
						expand(ch);
							for(p2=0;tempStatus[p2].expressionNum!=-1;p2++)
							{}
						for(j=0;temp[j]!=-1;j++)
						{
								tempStatus[p2].expressionNum=temp[j];
								tempStatus[p2].pointNum=0;
								p2++;
						}
				}
		}
		m=hasStatus();
		if(m!=-1)
			return m;
		else
			for(i=0;tempStatus[i].expressionNum!=-1;i++)
			{
				status[p][i].expressionNum=tempStatus[i].expressionNum;
				status[p][i].pointNum=tempStatus[i].pointNum;
			}			
		return p;
}




char afterChar(int m,int n)
{
		char string[LEN]={'\0'};
		int length=0;
		strcpy(string,expressions[m]);
		length=strlen(string);
		if(n>=length-3)
				return '\0';
		else
				return string[n+3];
}


char isEnd(char ch)
{
		if(ch>='A' && ch<='Z')
				return 'n';
		return 'y';
}

void expand(char ch)
{
		int i=0,j=0;
		for(;expressions[i][0]!='\0';i++)
		{
				if(expressions[i][0]==ch)
				{
						temp[j]=i;
						j++;
				}
		}
}

int hasStatus(void)
{
		int i=0,j=0,length=0,length2=0;
		for(length=0;tempStatus[length].expressionNum!=-1;length++)
		{}
		for(i=0;status[i][0].expressionNum!=-1;i++)
		{
				for(length2=0;status[i][length2].expressionNum!=-1;length2++)
				{}
				if(length!=length2)
						continue;
				else
				{
					for(j=0;j<length;j++)
					{
						if(status[i][j].expressionNum!=tempStatus[j].expressionNum || status[i][j].pointNum!=tempStatus[j].pointNum)
								break;
						
					}
				}
				if(j==length)
					return i;
		}
		return -1;
}


void allCharacters(void)
{
		int i=0,j=0;
		char ch[2]={'\0'},temp;
		for(i=0;wenfa[i][0]!='\0';i++)
		
				for(j=0;wenfa[i][j]!='\0';j++)
				{
						temp=wenfa[i][j];
						if(strchr(characters,temp)==NULL && temp!='-' &&temp!='>' && temp!='|' )
						{
								ch[0]=wenfa[i][j];
								strcat(characters,ch);
								ch[0]='\0';
						}
				}
}
void allEndsAndNotEnds(void)
{
		int i=0;
		char ch[2]={'\0'};
		for(;(ch[0]=characters[i])!='\0';i++)
		{
				if(isEnd(ch[0])=='y')
						strcat(ends,ch);
				else
						strcat(notEnds,ch);
		}
		strcat(ends,"$");
		//printf("%s\n",ends);
		//printf("%s\n",notEnds);
}


void DNF(void)
{
		int i=0,j=0,k;
		for(j=0;status[j][0].expressionNum!=-1;j++)
		{
				for(i=0;characters[i]!='\0';i++)
				{
					fillTempStatusNull();
					fillTempStatus(j,characters[i]);
					if(tempStatus[0].expressionNum==-1)
							continue;
					else
					{
							fillGoto(j,characters[i],closure());
					}
				}
		}

}


void fillTempStatus(int p,char ch)
{
		int i=0,j=0;
		for(;status[p][i].expressionNum!=-1;i++)
		{
				if(afterChar(status[p][i].expressionNum,status[p][i].pointNum)==ch)
				{
						tempStatus[j].expressionNum=status[p][i].expressionNum;
						tempStatus[j].pointNum=status[p][i].pointNum+1;
						j++;
				}
		}
}
				
void fillGoto(int a,char ch,int b)
{
		int i=0;
		for(i=0;gotoStatus[i].character!='\0';i++)
		{}
		gotoStatus[i].status1=a;
		gotoStatus[i].character=ch;
		gotoStatus[i].status2=b;
}


int getGotoStatus(int status,char ch)
{
		int i=0;
		for(;gotoStatus[i].character!='\0';i++)
		{
				if(gotoStatus[i].status1==status && gotoStatus[i].character==ch)
				{
						return gotoStatus[i].status2;
				}
		}
		return -1;
}

int hasGuiYue(int s)
{
		int i=0,a,b;
		for(;status[s][i].expressionNum!=-1;i++)
		{
				a=status[s][i].expressionNum;
				b=status[s][i].pointNum;
				if(a==0 && b==1)
						return 88;
				else
				{
					if(afterChar(status[s][i].expressionNum,status[s][i].pointNum)=='\0')
						return status[s][i].expressionNum;
				}
		}
		return -1;
}



void initTable(void)
{
		int i=0,j=0,length=0,temp=0;
		allEndsAndNotEnds();
		for(i=0;i<LEN;i++)
				characters[i]='\0';
		printf("%s\n",characters);
		strcat(characters,ends);
		strcat(characters,notEnds);
		//printf("%s\n",characters);
		for(length=0;status[length][0].expressionNum!=-1;length++)
		{}
		for(i=0;i<length;i++)
		{
				for(j=0;characters[j]!='\0';j++)
				{
						table[i][j]=getGotoStatus(i,characters[j]);
				}

		}
		for(i=0;i<length;i++)
		{
				temp=hasGuiYue(i);
				if(temp!=-1 && temp!=88)
						for(j=0;characters[j]!='\0';j++)
								table[i][j]=-temp*10;
				if(temp==88)
				{
					for(j=0;characters[j]!='$';j++)
					{}
					table[i][j]=temp;
				}

		}

}


int getTable(int s,char a)
{
		int i=0,j=0;
		for(;table[i][0]!=0;i++)
				for(j=0;table[i][j]!=0;j++)
						if(i==s && characters[j]==a)
								return table[i][j];
		return -1;
}
void printWenFa(void)
{
		printf("TEN WENFA IS:\n");
		int i=0,j=0;
		for(;wenfa[i][0]!='\0';i++)
		{
				for(j=0;wenfa[i][j]!='\0';j++)
						printf("%c",wenfa[i][j]);
				printf("\n");
		}
		for(i=0;wenfa[i][0]!='\0';i++)
				strcat(wenfa[i],"|");
}


void printTable(void)
{
	printf("THE TABLE IS:\n");
	int i=0,j=0,m=0,k=0;
	for(i=0;characters[i]!='\0';i++)
	{
			if(i==0)
					printf("     ");
			printf("%-5c",characters[i]);
	}
	printf("\n");

	for(i=0;table[i][0]!=0;i++)
	{
			k=0;
			printf("%-5d",i);
			for(j=0;(m=table[i][j])!=0;j++)
			{
					if(k<strlen(ends))
					{

						if(m==-1)
							printf("     ");
						if(m>0 && m!=88)
							printf("S%d   ",m);
						if(m<-1)
							printf("R%d   ",-m/10);
						if(m==88)
							printf("acc  ");
						k++;
						continue;
					}
					if(m==-1)
						printf("     ");
					if(m>0)
						printf("%-5d",m);

			}
			printf("\n");
	}
}

void control(char *string)
{
		int p=0,p2=0,length=0,i=0,j=0,temp=0,statusStack[LEN]={-1};
		char a,b,charStack[LEN]={'\0'};
		statusStack[0]=0;
		charStack[0]='$';
		a=string[p];
		while((temp=getTable(statusStack[p2],a))!=88)
		{
				if(temp>0)
				{
						p2++;
						p++;
						statusStack[p2]=temp;
						charStack[p2]=a;
						a=string[p];
						for(i=0;i<=p2;i++)
								printf("%d",statusStack[i]);
						printf("%15s",charStack);
						printf("%15s\n",&string[p]);
				}
				else if(temp<-1)
				{
						temp=-temp/10;
						b=expressions[temp][0];
						length=strlen(expressions[temp])-3;
						for(i=p2;p2>i-length;p2--)
						{
								statusStack[p2]=-1;
								charStack[p2]='\0';
						}
						p2++;
						charStack[p2]=b;
						statusStack[p2]=getTable(statusStack[p2-1],b);
						for(i=0;i<=p2;i++)
								printf("%d",statusStack[i]);
						printf("%15s",charStack);
						printf("%15s\n",&string[p]);
				}
				else if(temp==-1)
				{
						printf("ERROR!!!\n");
						return;
				}
		}
		printf("SUCSESS!!\n");
}


int main()
{
	int i=0;
	char string[LEN];
	readFromFile();
	printWenFa();
	fillExpression();
	fillTempStatusNull();
	fillStatusNull();
	tempStatus[0].expressionNum=0;
	tempStatus[0].pointNum=0;
	for(i=0;expressions[i][0]!='\0';i++)
        printf("%s\n",expressions[i]);
	closure();
	allCharacters();
	DNF();
	initTable();
	printTable();
	printf("please input:");
	scanf("%s",string);
	strcat(string,"$");
	control(string);
	getchar();
	getchar();
	getchar();
}