operation.h

LL(1)文法分析过程的可视化及教学应用研究

	//-----------------------------------------------------------------

	for(k=0;k<fw;k++)
	{
		for(i=0;i<n;i++)
			if(G[i][0].letter==follow[k][0])
			{
				for(s=k+1;s<fw;s++)
					if(G[i][1].letter==follow[s][0])
					{
						sign=0;
						for(t=0;t<n;t++)
						{

							if(G[t][0].letter==follow[s][0])
							{
								ud=1;
								sign=1;

								insert_G(i+1);
								if(t>i)t++;
								if(G[t][1].letter!='@')
								{
								    for(j=1;j<=G[t][0].tag;j++)
									    G[i+1][j]=G[t][j];

									for(j=2;j<=G[i][0].tag;j++)
										G[i+1][j+G[t][0].tag-1]=G[i][j];

   								    G[i+1][0].tag=G[t][0].tag+G[i][0].tag-1;
								}
							   else
							   {
									for(j=2;j<=G[i][0].tag;j++)
									G[i+1][j-1]=G[i][j];
								    G[i+1][0].tag=G[i][0].tag-1;
									
									if(G[i+1][0].tag==0)
									{
										G[i+1][0].tag=1;
										G[i+1][1].letter='@';
									}
							   }
							   
							   G[i+1][0].letter=follow[k][0];
							}
						}
						if(sign==1)
						{
							del_G(i);
						    i--;

						}

						
						

	tt="";
    tttt="";
	
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						tt+="    ";
						tt+=follow[tk][0];
						tt+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						tt+=G[ti][tj].letter;
					tt+='|';

				}
			}
			tt=tt.Left(tt.GetLength()-1);
			tt+="\r\n";
		}

	tttt="用左部为";
	tttt+=follow[s][0];
	tttt+="的产生式的右部\r\n代换左部为";
	tttt+=follow[k][0];
	tttt+="的产生式右部中的";
	tttt+=follow[s][0];
	tttt+="\r\n文法变为:\r\n";

	str+=tttt+tt;
	str+="\r\n";


					}
			}

		for(i=0;i<LEN;i++)
		{
			for(j=0;j<LEN;j++)
			       arr[i][j]=0;
			a[i]=0;
		}

		l=0;
		tc=follow[k][0];
		for(i=0;i<n;i++)
			if(G[i][0].letter==follow[k][0])
			{
				arr[l][0]=i;
				for(j=1;j<=G[i][0].tag;j++)
					arr[l][j]=G[i][j].letter;
				l++;
			}
		s=0;
		for(i=0;i<l-1;i++)
		{
			for(j=i+1;j<l;j++)
			{
				if(arr[i][1]==arr[j][1])
				{
					if(s==0)
					{
						a[0]=arr[i][0];
						a[1]=arr[j][0];
						s=2;
					}
					else
					{
						a[s]=arr[j][0];
						s++;
					}
				}
			}
			if(s!=0)
			{
				c=1;
				break;
			}
		}

		if(s!=0)
		{
			ud=1;

			for(c=1;;c++)
			{
				for(l=0;l<s;l++)
				{
					if(G[a[l]][0].tag<c||G[a[0]][c].letter!=G[a[l]][c].letter)
					{
					    e=1;
						c--;
						break;
					}
				}
				
				if(e==1)break;

			}

			for(t=0;t<256;t++)
				if(vn[t]==1)
				{
					vn[t]=2;
					G[n][0].letter=G[arr[i][0]][0].letter;
					G[n][0].tag=c+1;
					

					for(j=1;j<=c;j++)
					{
						G[n][j].letter=arr[i][j];
					}
					G[n][j].letter=t;
					n++;
				    
				    for(i=0;i<s;i++)
					{
						for(j=1;j<=G[a[i]][0].tag;j++)
							G[a[i]][j]=G[a[i]][j+c];
						G[a[i]][0].tag=G[a[i]][0].tag-c;
						G[a[i]][0].letter=t;

						if(G[a[i]][0].tag==0)
						{
							G[a[i]][0].tag=1;
							G[a[i]][1].letter='@';
						}
					}
                    
					if(G[n-1][0].letter==begin_ch)
					{
                        swap_G(a[0],n-1);
					}

					tag_mark();

				
	tt="";
    tttt="";
	
		for(tk=0;tk<fw;tk++)
		{
			tsign=0;
			for(ti=0;ti<n;ti++)
			{
				if(G[ti][0].letter==follow[tk][0])
				{
					if(tsign==0)
					{
						tsign=1;
						tt+="    ";
						tt+=follow[tk][0];
						tt+="->";
					}

					for(tj=1;tj<=G[ti][0].tag;tj++)
						tt+=G[ti][tj].letter;
					tt+='|';

				}
			}
			tt=tt.Left(tt.GetLength()-1);
			tt+="\r\n";
		}

	tttt="引入新非终结符";
	tttt+=t;
	tttt+="\r\n对";
	tttt+=tc;
	tttt+="的产生式提取左公共因子\r\n";
	tttt+="文法变为:\r\n";

	str+=tttt+tt;
	str+="\r\n";


					break;				
				
				}

				if(t>=256)
				{
					tag[4]=1;
					return str;
				}

		}

	}
	tag_mark();
	opt_G();

    get_first();
	get_follow();
	get_select();

	}

	tag_mark();
	opt_G();
	return str;
}


void CGram::swap_G(int a,int b)
{
	int j;
    for(j=0;j<=G[a][0].tag||j<=G[b][0].tag;j++)
	{
		G[n][j]=G[b][j];
		G[b][j]=G[a][j];
		G[a][j]=G[n][j];
		G[n][j].letter=0;
		G[n][j].tag=0;
		G[n][j].nultag=0;
	}

}

void CGram::opt_G()
{
    int sign,i,j,k;
	re_initial();

	r_vn[begin_ch]=1;

	sign=1;

	while(sign)
	{
		sign=0;
	    for(i=0;i<n;i++)
			if(r_vn[G[i][0].letter]==1)
				for(j=1;j<=G[i][0].tag;j++)
					if(G[i][j].tag==1&&r_vn[G[i][j].letter]!=1)
					{
						r_vn[G[i][j].letter]=1;
						sign=1;
					}
	}

	for(i=0;i<n;i++)
	{
		if(r_vn[G[i][0].letter]==0)
		{
			vn[G[i][0].letter]=1;
			add_vn[G[i][0].letter]=0;
			del_G(i);
			i--;
		}

		if(G[i][0].tag==1&&G[i][0].letter==G[i][1].letter)
		{
			del_G(i);
			i--;
		}

		for(k=i+1;k<n;k++)
			if(G[i][0].tag==G[k][0].tag&&G[i][0].letter==G[k][0].letter)
			{
				sign=0;
				for(j=1;j<=G[i][0].tag;j++)
					if(G[i][j].letter!=G[k][j].letter)
					{
						sign=1;
						break;
					}

				if(sign==0)
					del_G(k);
			}
	}

	tag_mark();

}


void CGram::del_G(int i)
{
	int k,j;
	for(k=i;k<n;k++)
		for(j=0;j<LEN;j++)
			G[k][j]=G[k+1][j];
	n--;
}

void CGram::insert_G(int i)
{
	int k,j;
	for(k=n;k>i;k--)
		for(j=0;j<LEN;j++)
			G[k][j]=G[k-1][j];
	for(j=0;j<LEN;j++)
	{
		G[i][j].letter=0;
		G[i][j].tag=0;
		G[i][j].nultag=0;
	}

	n++;
}

void CGram::tag_mark()
{
	int i,j,sign;

	re_initial();

	for(i=0;i<n;i++)
	{
		if(G[i][1].letter=='@')
		{
			G[i][1].nultag=1;
			G[i][0].nultag=1;
			nulchar[G[i][0].letter]=1;
			G[i][0].tag=1;
		}
		else
			G[i][1].nultag=0;


		for(j=1;j<=G[i][0].tag;j++)
		{
            if(vn[G[i][j].letter]!=0)
				G[i][j].tag=1;
			else
				G[i][j].tag=0;
		}	
	}

    sign=1;

	while(sign)
	{
		sign=0;
	    for(i=0;i<n;i++)
		    for(j=1;j<=G[i][0].tag;j++)
			    if(nulchar[G[i][j].letter]==1)
				    G[i][j].nultag=1;


	    for(i=0;i<n;i++)
		{
			for (j=1;j<=G[i][0].tag;j++)
				if(G[i][j].nultag==0)break;
			if(j>G[i][0].tag && nulchar[G[i][0].letter]!=1)
			{
				G[i][0].nultag=1;
				nulchar[G[i][0].letter]=1;
				sign=1;
			}
		}
	}

	for(i=0;i<n;i++)
	{
		if(num[G[i][0].letter]==0)
		{
			follow[fw][0]=G[i][0].letter;
			num[G[i][0].letter]=++fw;
		}

	    vn[G[i][0].letter]=2;

		for(j=1;j<=G[i][0].tag;j++)
		{
			if(G[i][j].tag==0)
                vt[G[i][j].letter]=2;
			else
				vn[G[i][j].letter]=2;
		}
	}
	
	vt['#']=2;
	vt['@']=3;
}


void CGram::add_first(char vn,int i)
{
	int k,j,t,sign;
	for(k=0;k<n;k++)
	{
		if(first[k][0]==vn)
		{
			for(j=1;j<=count_first[k];j++)
				if(first[k][j]!='@')
				{
					sign=0;
			        for(t=1;t<=count_first[i];t++)
				        if(first[i][t]==first[k][j])
					        sign=1;
				    if(sign==0)
					{
						count_first[i]++;
					    first[i][count_first[i]]=first[k][j];
						ud=1;
					}
				}
		}
	}
}



CString CGram::get_first()
{
    int i,j,t,sign,tk,tj,tud;


	CString str;

    for(i=0;i<n;i++)
	{
		first[i][0]=G[i][0].letter;
		count_first[i]=0;
		if(G[i][1].tag==0&&G[i][1].letter!='@')
		{
			count_first[i]++;
			first[i][count_first[i]]=G[i][1].letter;
			ud=1;
		    
		}
	}

	str="计算右部以终结符开始的非空规则\r\n得到:\r\n";

	for(tk=0;tk<n;tk++)
	{
	    str+="first(";
		str+=first[tk][0];
		str+="->";

		for(tj=1;tj<=G[tk][0].tag;tj++)
			str+=G[tk][tj].letter;

		str+=") = { ";
		
		for(tj=1;tj<=count_first[tk];tj++)
		{
			str+=first[tk][tj];
            if(tj!=count_first[tk])
			str+=',';
		}
	    str+=" }\r\n";
	}
	str+="\r\n";

	ud=1;
	while(ud)
	{
		ud=0;
	    for(i=0;i<n;i++)
		{
	    	for(j=1;j<=G[i][0].tag;j++)
			{
			    if(G[i][j].tag==1)
				{
					tud=ud;
					ud=0;
					add_first(G[i][j].letter,i);


					if(ud==1)
					{
						if(j!=1)
						{
							str+="由于";
							for(tk=1;tk<j;tk++)
								str+=G[i][tk].letter;
							str+="可以推导至空,所以\r\n";
						}

						str+="把";
						str+=G[i][j].letter;
						str+="的first集\r\n加入到";
						str+=G[i][0].letter;
						str+="->";
						for(tk=1;tk<=G[i][0].tag;tk++)
							str+=G[i][tk].letter;
						str+="的first集中\r\n得到:\r\n";

						for(tk=0;tk<n;tk++)
						{
							str+="first(";
							str+=first[tk][0];
							str+="->";

							for(tj=1;tj<=G[tk][0].tag;tj++)
								str+=G[tk][tj].letter;
							str+=") = { ";
		
							for(tj=1;tj<=count_first[tk];tj++)
							{
								str+=first[tk][tj];
								if(tj!=count_first[tk])
									str+=',';
							}
							str+=" }\r\n";
						}
						str+="\r\n";
					
					}//ud
					ud=(ud||tud);

				    if(G[i][j].nultag==0)break;
				}//if
				
				else
				{
					if(j!=1)
					{
						sign=0;
						for(t=1;t<=count_first[i];t++)
							if(first[i][t]==G[i][j].letter)
								sign=1;
						if(sign==0)
						{
							count_first[i]++;
							first[i][count_first[i]]=G[i][j].letter;
							ud=1;
						
							str+="由于";

							for(tk=1;tk<j;tk++)
								str+=G[i][tk].letter;
							str+="可以推导至空,所以\r\n把";
							str+=G[i][j].letter;
							str+="加入到";
							str+=G[i][0].letter;
							str+="->";
							for(tk=1;tk<=G[i][0].tag;tk++)
								str+=G[i][tk].letter;
							str+="的first集中\r\n得到:\r\n";
	
							for(tk=0;tk<n;tk++)
							{
								str+="first(";
								str+=first[tk][0];
								str+="->";

								for(tj=1;tj<=G[tk][0].tag;tj++)
									str+=G[tk][tj].letter;