ll1.cpp

本程序作为计算机学院编译原理课程试验的一部分

		if (first_set[first_vn_num].vn==gra_list[i].head)//如果左部是当前要求first集的非终结符
		{
		    int l=0;
		    while(l<gra_list[i].body_len)   //对句子的右部每个字符(编码)
		    {
				if (gra_list[i].body[l]>0)  //如果是终结符
				{
					first_set[first_vn_num].vt[first_set[first_vn_num].vt_len]=gra_list[i].body[l];  //加入当前要求的非终结符的first集
					first_set[first_vn_num].vt_len++;
					if(gra_list[i].body[l]==vtset[empty_position].code)  //如果为空,当前要求的first集的空标志置1
						first_set[first_vn_num].flag_empty=1;

					gra_list[i].first[gra_list[i].first_len]=gra_list[i].body[l]; //附加把每个句子的first集求得,以便于构建分析表时使用
					gra_list[i].first_len++;
					break;
				}
				else   //不是终结符
				{
					int j;
					for (j=0; j<first_set_num; j++)  //找到此非终结符在first集数组中的位置
						if (first_set[j].vn==gra_list[i].body[l])
							break;
					if (first_set[j].flag_cla==1)  //如果该非终结符的first集已经计算过,则加到当前要求的非终结符的first中
					{
						for (int k=0; k<first_set[j].vt_len; k++)
						{
							first_set[first_vn_num].vt[first_set[first_vn_num].vt_len]=first_set[j].vt[k];
							first_set[first_vn_num].vt_len++;
							if(first_set[j].vt[k]==vtset[empty_position].code)  //如果该非终结符的first集中有空,则置当前要求的非终结符的first集的空标志为1
							{
								first_set[first_vn_num].flag_empty=1;
							}
							gra_list[i].first[gra_list[i].first_len]=first_set[j].vt[k]; //附加把每个句子的first集求得
							gra_list[i].first_len++;
						}
						break;
					}
					else if(first_set[j].flag_empty==1) //如果该终结符的first集中有空
						l++;  //看右部的下一个符号
					else //否则,递归计算该非终结符的first集
						cal_first(j);  
				}
			}
		}
	}
	first_set[first_vn_num].flag_cla=1; //当前非终结符的first集合求完后,置已经求过标志为1
}

//函数:输出first集
void output_first_set()
{
	printf("first set:\n------------------------------\n");
	for (int i=0; i<first_set_num; i++)
	{
		printf("%s-> ",vset[-first_set[i].vn-1].sym);
		for (int j=0; j<first_set[i].vt_len;j++)
			printf("%s ", vtset[first_set[i].vt[j]-1].sym);
		printf("\n");
	}
	printf("==============================\n");
}

//函数:求文法的follow集
void cal_follow_set()
{
	vtset[vtset_num].sym[0]='#';      //把#符加到终结符集合中
	vtset[vtset_num].sym[1]='\0';
	vtset[vtset_num].code= vtset_num+1;
	vtset_num = vtset_num+1;
	
	for (int i=0; i<vset_num; i++)  //初始化存储follow集的数据结构
	{
		follow_set[i].vn=vset[i].code;
		follow_set[i].flag_cla=0;
		follow_set[i].flag_empty=first_set[i].flag_empty;
		follow_set[i].vt_len=0;
	}
	follow_set_num=vset_num;
	
	for (int j=0; j<follow_set_num; j++) //如果follow集没计算完
		if (follow_set[j].flag_cla==0)   //如果该非终结符的follow集没计算过
			cal_follow(j);   //递归计算该非终结符的follow集
}

//函数:计算每个非终结符A的follow集的递归函数
void cal_follow(int follow_vn_num)
{
	if (follow_vn_num==0)    //如果是文法开始符合,把#符加到其follow集中
	{
		follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=END_SYM;//#
		follow_set[follow_vn_num].vt_len++;
	}
	for (int i=0; i<gra_lis_num; i++)  //对文法的每条句子
	{
		int q;
		for (q=0; q<gra_list[i].body_len; q++)  //对该句子右部的每个符号(编码)
		{
			if (gra_list[i].body[q]!=follow_set[follow_vn_num].vn)  //找到要求的非终结符A
				continue;
			else  //找到了
			{
				for(; q<gra_list[i].body_len-1;q++)  //不到该句子右部的尾部
				{
					if (gra_list[i].body[q+1]>0)//如果非终结符A的后一个符号为终结符
					{
						int flag_exist=0;
						for(int p=0; p<follow_set[follow_vn_num].vt_len; p++)  //判断该终结符是否已经在非终结符A的follow集中
						{
							if (follow_set[follow_vn_num].vt[p]==gra_list[i].body[q+1])
							{
								flag_exist=1;
								break;
							}
						}
						if(flag_exist==0)    //不在,加到非终结符A的follow集中
						{
							follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=gra_list[i].body[q+1];
							follow_set[follow_vn_num].vt_len++;
						}
						break;
					}
					else  //为非终结符B
					{
						int n;
						for (n=0; n<first_set_num; n++)  //找到其在first集中的位置
							if(first_set[n].vn==gra_list[i].body[q+1])
								break;
						for (int m=0; m<first_set[n].vt_len; m++) //把所有非终结符B的first集中的元素(出去空)加到非终结符A的follow集中
						{
							int flag_exist=0;
							for(int p=0; p<follow_set[follow_vn_num].vt_len; p++)   //判断该终结符是否已经在非终结符A的follow集中
							{
								if (follow_set[follow_vn_num].vt[p]==first_set[n].vt[m])
								{
									flag_exist=1;
									break;
								}
							}
							if ((first_set[n].vt[m]!=vtset[empty_position].code)&&(flag_exist==0))  //不在且该该终结符不为空,加到非终结符A的follow集中
							{
								follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=first_set[n].vt[m];
								follow_set[follow_vn_num].vt_len++;
							}
						}
						if (first_set[n].flag_empty==1)  //如果终结符B的first集中含有空,则继续看该文法句子右部的下一个符号
							continue;
						else    //如果终结符B的first集中无空,找下一个该句子中下一个非终结符A
							break;
					}
				}
				if (q>=gra_list[i].body_len-1)  //如果到了句子右部的尾部,说明非终结符A在该句子的尾部或A后的符号都可空
				{
					int r;
					for (r=0; r<follow_set_num; r++)   //找到该句子左部的非终结符D在follow集中的位置
						if (follow_set[r].vn == gra_list[i].head)
							break;
					if((follow_set[r].vn!=follow_set[follow_vn_num].vn)&&(follow_set[r].flag_cla==0)) //如果D与A不等,且D的follow集合未计算过,递归计算D的follow集
						cal_follow(r);
					if (follow_set[r].flag_cla==1) //如果D的follow集计算过,把D的follow集中的元素付给A的follow集
					{
						int s;
						for (s=0; s<follow_set[r].vt_len;s++)
						{
							int p;
							int flag_exist=0;
							for(p=0; p<follow_set[follow_vn_num].vt_len; p++)   //判断A的follow集中是否已经存在D的follow集中的元素
							{
								if (follow_set[follow_vn_num].vt[p]==follow_set[r].vt[s])
								{
									flag_exist=1;
									break;
								}
							}
							if (flag_exist==0)   //不存在,复制
							{
								follow_set[follow_vn_num].vt[follow_set[follow_vn_num].vt_len]=follow_set[r].vt[s];
								follow_set[follow_vn_num].vt_len++;
							}
						}
					}	
				}
			}
		}
	}
	follow_set[follow_vn_num].flag_cla=1;     //当前非终结符A的follow集合求完后,置已经求过标志为1
}

//函数:输出follow集
void output_follow_set()
{
	printf("follow set:\n------------------------------\n");
	for (int i=0; i<follow_set_num; i++)
	{
		printf("% s->", vset[-follow_set[i].vn-1].sym);
		for (int j=0; j<follow_set[i].vt_len; j++)
		{
			if(follow_set[i].vt[j]==END_SYM)//#
				printf("# ");
			else
				printf("%s ",vtset[follow_set[i].vt[j]-1].sym);
		}
		printf("\n");
	}
	printf("==============================\n");
}

//函数:构造分析表
void construct_analyse_table()
{
	int count=0;
	for(int s=0; s<vtset_num; s++)   //构建用于分析表的终结符集合,去除空,加入#,其中#符的编码为0
	{
		int flag=0;
		if(s!=empty_position)
		{
			if(s!=vtset_num-1)
			{
				strcpy(vtset_for_ana[count].sym,vtset[s].sym);
				vtset_for_ana[count].code=vtset[s].code;
			}
			else
			{
				vtset_for_ana[count].sym[0]='#';
				vtset_for_ana[count].sym[1]='\0';
				vtset_for_ana[count].code=END_SYM;
			}
			flag=1;
		}
		if(flag==1)
			count++;
	}
	vtset_for_ana_num=count; 
	     
	row_num = vset_num;              //确定分析表的行列
	col_num = vtset_for_ana_num;

	for(int r=0; r<row_num; r++)      //初始化分析表
	{
		for(int j=0; j<col_num; j++)
		{
			analyse_table[r][j].flag=0;       
			analyse_table[r][j].body_len=0;   
		}
	}
	
	int tmp_row;      //临时行列变量,表示分析表行列
	int tmp_col;
	
	for(int i=0; i<gra_lis_num; i++)   //对文法的每条句子S
	{
		int k;
		for(k=0; k<vset_num; k++)     //找到其左部非终结符在非终结符集合中的位置
			if(gra_list[i].head==vset[k].code)
				break;

		tmp_row=k;   //把其位置付给临时行变量
		int flag=0;
		for(int j=0; j<gra_list[i].first_len; j++)  //对应每条句子的first集中的每个元素
		{
			if(gra_list[i].first[j]==vtset[empty_position].code)  //如果为空,标志置1
				flag=1;
			else //不为空
			{
				int l;
				for(l=0; l<vtset_for_ana_num; l++)  //找到其在分析表终结符集合中的位置
				{
					if(gra_list[i].first[j]==vtset_for_ana[l].code)
						break;
				}
				tmp_col=l;  //把其在分析表终结符集合中的位置付给临时列变量
				
				analyse_table[tmp_row][tmp_col].head=gra_list[i].head;  //把该句子S存储到分析表的对应行列中,并置表项存在标志为1
				analyse_table[tmp_row][tmp_col].flag=1;
				for(int m=0; m<gra_list[i].body_len; m++)
				{
					analyse_table[tmp_row][tmp_col].body[analyse_table[tmp_row][tmp_col].body_len]=gra_list[i].body[m];
					analyse_table[tmp_row][tmp_col].body_len++;
				}
			}
		}
		if(flag==1)  //如果该句子的first集中有空
		{
			int j;
			for(j=0; j<follow_set_num; j++)  //找到该句子左部非终结符A在follow集中的位置
				if(gra_list[i].head==follow_set[j].vn)
					break;
			
			int m;  //把该句子左部非终结符在follow集中的位置付给行临时变量
			for(m=0; m<follow_set[j].vt_len; m++)   //对非终结符A的follow集中的每个元素a
			{
				int l;
				for(l=0; l<vtset_for_ana_num; l++)  //找到a在分析表非终结符集合中的位置
					if(follow_set[j].vt[m]==vtset_for_ana[l].code)
						break;
				
				tmp_col=l;	//把a在分析表非终结符集合中的位置付给临时列变量
				analyse_table[tmp_row][tmp_col].head=gra_list[i].head;   //把该句子S存储到分析表的对应行列中,并置表项存在标志为1
				analyse_table[tmp_row][tmp_col].flag=1;
				for(int n=0; n<gra_list[i].body_len; n++)
				{
					analyse_table[tmp_row][tmp_col].body[analyse_table[tmp_row][tmp_col].body_len]=gra_list[i].body[n];
					analyse_table[tmp_row][tmp_col].body_len++;
				}				
			}
		}
	}
}

//函数:输出分析表到文件
void output_analyse_table()
{
	if ((afp = fopen("Ana_table.txt","w"))==NULL)  //打开要输出到的文件
	{
		printf("open file:vsetFile error.\n");
		exit(0);
	}
	for(int r=0; r<col_num; r++)   //输出分析表终结符
	{
		if(vtset_for_ana[r].code==0)
			fprintf(afp,"                #                  ");
		else
			fprintf(afp,"          %4s                      ",vtset_for_ana[vtset_for_ana[r].code-1].sym);
	}
	fprintf(afp,"\n");
	for(int i=0; i<row_num; i++)  //每一行
	{
		fprintf(afp,"%5s ",vset[-vset[i].code-1].sym);  //输出分析表非终结符
		for(int j=0; j<col_num; j++)   //该行的每一列
		{
			if(analyse_table[i][j].flag==1) //如果表项存在
			{
				fprintf(afp,"%4s->",vset[-analyse_table[i][j].head-1].sym);  //输出句子的左部
				int k;
				for(k=0; k<analyse_table[i][j].body_len; k++)  //输出句子的右部
				{
					if(analyse_table[i][j].body[k]<0)   //如果是非终结符
						fprintf(afp,"%4s ",vset[-analyse_table[i][j].body[k]-1].sym);
					else  //终结符
						fprintf(afp,"%4s ",vtset[analyse_table[i][j].body[k]-1].sym);
				}
				for(; k<MAX_GRA_BODY_LEN; k++)   //填补空白
					fprintf(afp,"     ");
			}
			else
				fprintf(afp,"                               "); //填补空白
		}
		fprintf(afp,"\n");
	}
	fclose(afp);
}

//函数:分析给定的句型
void analyse()
{
	top=0;
	analyse_stack[top++]=END_SYM;//把#压入栈中
	analyse_stack[top++]=-1;     //把开始符号压入栈中
	int senindex=0;
	int tmp_vn,tmp_vt;   //临时终结符,非终结符
	int tmp_row,tmp_col; //临时行,列变量
	printf("analyse sequence:\n------------------------------\n");
	while(analyse_stack[top-1]!=END_SYM)  //如果栈不为空
	{
		if(analyse_stack[top-1]>=0)  //如果栈顶元素为终结符
		{
			for(int r=0; r<top; r++) //输出当前栈中符号
			{
				if(analyse_stack[r]==END_SYM)
					printf("# ");
				else if(analyse_stack[r]<0)
					printf("%s ",vset[-analyse_stack[r]-1].sym);
				else
					printf("%s ",vtset[analyse_stack[r]-1].sym);
			}
			printf("\n");
			if(analyse_stack[top-1]==vtset[empty_position].code)  //如果其为空,弹出
				top--;
			else if(analyse_stack[top-1]==sentence[senindex].code)//如果其和输入指针指向的输入符号相同
			{
				top--;      //弹出
				senindex++; //输入指针指向下一个输入符号
			}
			else  //否则,错误退出
			{
				printf("error  !!\n");
				exit(0);
			}
		}
		else  //栈顶元素为非终结符
		{
			for(int r=0; r<top; r++)  //输出当前栈中符号
			{
				if(analyse_stack[r]==END_SYM)
					printf("# ");
				else if(analyse_stack[r]<0)
					printf("%s ",vset[-analyse_stack[r]-1].sym);
				else
					printf("%s ",vtset[analyse_stack[r]-1].sym);
			}
			tmp_vn=analyse_stack[top-1];
			tmp_vt=sentence[senindex].code;
			int i;
			for(i=0; i<vset_num; i++)   //找到其在非终结符集合中的位置
				if(tmp_vn==vset[i].code)
					break;
			
			tmp_row=i;   //把其在非终结符集合中的位置付给临时行变量
			int j;
			for(j=0; j<vtset_for_ana_num; j++) //找到输入指针指向的终结符在终结符集合中的位置
			{
				if(tmp_vt==vtset_for_ana[j].code)
					break;
			}
			tmp_col=j;  //把输入指针指向的终结符在终结符集合中的位置付给临时列变量
			if(analyse_table[tmp_row][tmp_col].flag==1) //如果临时行变量和临时列变量对应的表项存在
			{
				top--;  //弹出栈顶元素
				int m=analyse_table[tmp_row][tmp_col].body_len;
				for(; m>0; m--) //把分析表中对应项的句子的右部从右到左压入栈中
				{
					analyse_stack[top++]=analyse_table[tmp_row][tmp_col].body[m-1];
				}
				printf("%15s->",vset[-analyse_table[tmp_row][tmp_col].head-1].sym); //输出分析表中对应项的句子
				for(int k=0; k<analyse_table[tmp_row][tmp_col].body_len; k++)
				{
					if(analyse_table[tmp_row][tmp_col].body[k]<0) //非终结符
						printf("%s ",vset[-analyse_table[tmp_row][tmp_col].body[k]-1].sym);
					else  //终结符
						printf("%s ",vtset[analyse_table[tmp_row][tmp_col].body[k]-1].sym);
					
				}	
				printf("\n");
			}
			else       //否则,出错退出
			{
				printf("error:analyse table is empty\n");
				exit(0);
			}
		}
	}
	printf("==============================\n");
}