ll1.h

ll1的词法分析实现,没有短语分析,只是确定是不是LL1文法.

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>

void print();
char * search_None(char** grammar);//查找非终结符
void search(char ** goal);
char search2(char * goal,int pos);
int findNone(char x,char grammar[]);//查找空字符
void find_first(char g,char f[],char *goal[],char state[],char NoneChar[]);//求出g的first的集
int find_state(char x,char s[],char grammar[]);//查找非终结符在能否推出~(ε)
int find_None(char None,char str[]);//查找str中是否含有空（~）
void trim_same(char ts[],char result[]);//去掉一个字符串里相同的字符
int find_same(char a[],char b[]);//查找两个字符串中是否包含相同的字符
void find_follow(char x,char fl[],char *goal[],char state[],char NoneChar[]);//
void find_select(char g[],char fs[],char *goal[],char state[],char NoneChar[]);
#define MAXSIZE 10
char *input_G[10];
//char first[10][10];//存放每个非终结符的first集
//char follow[10][10];//存放每个非终结符的follow集
//char *select[10];//存放每个非终结符的select集
int grammar_line;

void read_file()
{
	FILE *fp;

	if((fp=fopen("ll(1).txt","r"))==NULL)
	{
		printf("The file doesn't exist!");
		getchar();
		exit(1);
	}
	int i=0;
    while(!feof(fp))
	{
		input_G[i]=(char *)malloc(10*sizeof(char));
		//得到文本的数据
		fscanf(fp,"%s",input_G[i]);
		i++;
	}
	grammar_line=i;
	/*for(int iii=0;iii<10;iii++)
	{
		printf("%s\n",input_G[iii]);
	}*/
}

char * search_None(char** grammar)
{
	int j,k=0;
	char  *NoneChar=(char*)malloc(20*sizeof(char));
	    
	for(int i=0;i<grammar_line;i++)
    {
         for(j=0;j<k;j++)
             if(grammar[i][0]==NoneChar[j])
                break;
         if(j>=k)
         {
                 NoneChar[j++]=grammar[i][0];
                 k=j;
         }
    }
	NoneChar[j+1]='\0';
	return NoneChar;
}
void print()
{
	//printf("the length of input_G %d\n",strlen(*input_G));
	search(input_G);
}

//找出能够直接推出ε(用~表示)的非终结副符,0代表否,1代表可以,2代表未定
void search(char **goal)
{
	char fei;//能推出ε(用~表示)的非终结符
	char *NoneChar=search_None(input_G);
	int lenNone=strlen(NoneChar);
	char AllNone[10];//记录全部是非终结符的产生式
	
	//定义一个以非终结符个数为上界的一维数组
	char *state1=(char *)malloc(20*sizeof(char));
	for(int j=0;j<lenNone;j++)
	{
		state1[j]='2';//未定
	}
	state1[j]='\0';
	//第一次扫描
	for(int gr=0;gr<grammar_line;gr++)
	{
	for(int i=0;goal[gr][i]!='\0';i++)
	{
		if(goal[gr][i]=='~')
		{
			fei=goal[gr][0];
			for(int n=0;n<lenNone;n++)
			{
				if(NoneChar[n]==fei)
					state1[n]='1';
			}
		}
		else
		{
			fei=NULL;
		}
	}
	}
	
	//第二次扫描
	bool None=false;
	for(int g2=0;g2<grammar_line;g2++)
	{
		for(int i5=0,jj=3;i5<lenNone;i5++)
		{
			if(goal[g2][jj]==NoneChar[i5]&&state1[i5]=='1')
			{
				jj++;
				i5=0;
				None=true;
			}
			else if((goal[g2][jj]>'Z'||goal[g2][jj]<'A')&&(goal[g2][jj]!='\0'))
			{
				None=false;
				break;
			}
			else if(goal[g2][jj]==NoneChar[i5]&&state1[i5]!='1')
			{
				jj++;
				i5=0;
				None=false;
			}
		}
		if(None==true)
		{
			for(int i6=0;i6<lenNone;i6++)
			{
				if(goal[g2][0]==NoneChar[i6])
				{
					state1[i6]='1';
				}
			}
		}
	}
    
	printf("各个字符是否能够推出空见下(1表是可以)\n");
	for(int m=0;m<lenNone;m++)
		printf("  %c---%c\t",NoneChar[m],state1[m]);
	printf("\n\n");
    char f[10],fl[10],fs[10];
	/*find_follow('D',fl,goal,state1,NoneChar);
	printf("%s***\n",fl);*/
	printf("非终结符的first、follow集分别如下:\n");
	for(int b=0;b<lenNone;b++)
	{
		find_first(NoneChar[b],f,goal,state1,NoneChar);
		find_follow(NoneChar[b],fl,goal,state1,NoneChar);
		printf("  %c的first集为：%s\tfollow集为：%s\n",NoneChar[b],f,fl);
		//printf("  %c的follow集为：%s\n",NoneChar[b],fl);
		printf("\n");
	}
	printf("各个产生式的select集如下:\n");
	for(int gg=0;gg<grammar_line;gg++)
	{
		find_select(goal[gg],fs,goal,state1,NoneChar);
		printf("  %s的select集为：%s\n",goal[gg],fs);
	}
	char fs1[10],fs2[10],fs3[10];//用于存储两个select集
	int result=1,j3=0;//0表示非LL(1)文法,1表示LL(1)文法
	for(int j1=0;j1<grammar_line;j1++)
	{
		for(int j2=j1+1;j2<grammar_line;j2++)
		{
			if(goal[j1][0]==goal[j2][0])
			{
				find_select(goal[j1],fs1,goal,state1,NoneChar);
				find_select(goal[j2],fs2,goal,state1,NoneChar);
				if(find_same(fs1,fs2)==0)
				{
					printf("\n\tSORRY!此文法为非LL(1)文法\n");
					result=0;
					break;
				}
			}
		}
		if(result==0)
			break;
	}
	
	printf("\n");
	if(result==1)
	{
		//ll(1)文法预测分析表
		printf("LL(1)文法预测分析表如下：\n");
		printf("终结符       非终结符\n");
		for(;j3<grammar_line;j3++)
		{
			find_select(goal[j3],fs3,goal,state1,NoneChar);
			printf("   %c    ->     %s\n",goal[j3][0],fs3);
		}
		printf("\n\t恭喜您!此文法为LL(1)文法\n");
	}

}
//g表示非终结符，f[]存放first集，*goal[]表示文法，state[]代表能否推出空
void find_first(char g,char f[],char *goal[],char state[],char NoneChar[])
{
	int f1=0,i,j=3;
	char ff[10],ff1[10];//存放递归时的first集

	if(g>'Z'||g<'A')////g不是非终结符，则g的first集是其本身 
	{
		ff1[f1++]=g;
	}
	else
	{
		for(int gr=0;gr<grammar_line;gr++)
		{
			if(goal[gr][0]==g)
			{
				if(goal[gr][j]>'Z'||goal[gr][j]<'A'&&goal[gr][j])
				{
					ff1[f1++]=goal[gr][j];
				}
				else
				{
					for(;goal[gr][j]!='\0';j++)
					{
						find_first(goal[gr][j],ff,goal,state,NoneChar);
						for(i=0;i<strlen(ff);)
						{
							if(ff[i]=='~')
							{
								i++;
							}
							else
							{
								ff1[f1]=ff[i++];
								f1++;
							}
						}
						if(find_None('~',ff)!=1)
							break;
					}
				}
				if(find_state(g,state,NoneChar)==1)
				{
					ff1[f1]='~';
					f1++;
				}

				ff1[f1]='\0';				
			}
		}
	}
	trim_same(ff1,f);

}
void find_follow(char x,char fl[],char *goal[],char state[],char NoneChar[])
{
	int i=0,j,r=0;
	char f[10],fl1[10];

	for(int g=0;g<grammar_line;g++)
	{
		for(j=3;goal[g][j]!='\0';j++)
		{
			if(goal[g][j]==x)
			{
				j++;
				if(goal[g][j]!='\0')
				{
					find_first(goal[g][j],f,goal,state,NoneChar);
					//判断fl中是否有f中的字符
					//for(r=0;r<strlen(fl);r++)
					//{
						for(r=0;r<strlen(f);)
						{
							if(f[r]=='~')
								r++;
							else
							{
								fl1[i]=f[r++];
								i++;
							}
						}
					//}
				}
			}
			else
			{
				fl1[i]='#';
				//i++;
			}
			fl1[i+1]='\0';
		}
	}
	trim_same(fl1,fl);
}
void find_select(char g[],char fs[],char *goal[],char state[],char NoneChar[])
{
	int i=0,k;
	char f[10],fs1[10];

	for(int j=3;g[j]!='\0';)
		{
			if((g[j]>'Z'||g[j]<'A')&&g[j]!='~')
			{
				fs1[i++]=g[j];
				break;
			}//if
			else if(g[j]=='~')
			{
				find_follow(g[0],f,goal,state,NoneChar);
				for(k=0;k<strlen(f);)
				{
					fs1[i++]=f[k++];					
				}//for
				break;
			}
			else
			{
				find_first(g[j],f,goal,state,NoneChar);
				if(find_None('~',f)==1)//如果右边的非终结符的first集包含空
				{
					for(k=0;k<strlen(f);)
					{
						if(f[k]=='~')
							k++;
						else
							fs1[i++]=f[k++];
					}//for
					j++;//有空串的话取下一个字符
				}//if
				else
				{
					for(k=0;k<strlen(f);)
					{
						fs1[i++]=f[k++];
					}//for
					j++;
				}//else
			}//else
		}//for
	fs1[i]='\0';//表示结束
	trim_same(fs1,fs);
}
int findNone(char x,char grammar[])
{
	int i,c=-1;
    for(i=0;i<strlen(grammar);i++)
	if(grammar[i]==x)
        c=1;

     return c;
}
//查找非终结符在能否推出~(ε)
int find_state(char x,char s[],char grammar[])
{
	for(int i=0;i<strlen(s);i++)
	{
		if(x==grammar[i]&&s[i]=='1')
			return 1;
		else 
			return 0;
	}
}
int find_None(char None,char str[])
{
	for(int i=0;i<strlen(str);i++)
	{
		if(str[i]==None)
			return 1;
		else 
			return 0;
	}	 
}
//去掉一个ts字符串里相同的字符
void trim_same(char ts[],char result[])
{
	int i,j,k=0;
  for(i=0;i<(int)strlen(ts);i++)
  {
	  for(j=i+1;j<(int)strlen(ts);j++)
	  {
         if(ts[i]==ts[j])
			 break;
	  }
	 
     if(j==(int)strlen(ts))
	 {
	   result[k]=ts[i];
	   k++;
	 }

      
  }
  result[k]='\0';
}
//判断两个字符串中是否有相同的字符
int find_same(char a[],char b[])
{
	int result=0;
	for(int i=0;i<strlen(a);i++)
	{
		for(int j=0;j<strlen(b);j++)
		{
			if(a[i]==b[j])
				result=0;
			else
				result=1;
		}
		if(result==0)
			break;
	}
	return result;
}