operation.h

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

								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";					
						}
					}
					break;
				}//else
			}//for j
		}//for i
	}//while ud
    
	for(i=0;i<n;i++)
	{
		if(G[i][0].nultag==1)
		{
			count_first[i]++;
		    first[i][count_first[i]]='@';
	
		}
	}

	str+="把@加入到可以得到\r\n可推导至空的规则的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";
	return str;

}

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


void CGram::add_follow(char vn,int k)
{
	int i,j,t,sign;

    i=num[vn]-1;
	if(i==k)return;

	for(j=1;j<=count_follow[i];j++)
	{
		sign=0;
        for(t=1;t<=count_follow[k];t++)
	        if(follow[k][t]==follow[i][j])
		        sign=1;
	    if(sign==0)
		{
			count_follow[k]++;
		    follow[k][count_follow[k]]=follow[i][j];
			ud=1;
		}
	}
}


CString CGram::get_follow()
{
    int i,j,t,k,s,sign,tk,tj,tud;
    
	CString str;
	follow[0][1]='#';
	count_follow[0]=1;

	str="把#加入到开始符";
	str+=begin_ch;
	str+="中\r\n得到:\r\n";

	for(tk=0;tk<fw;tk++)
	{
	    str+="follow(";
			str+=follow[tk][0];
			str+=") = { ";

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


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

								if(s!=j+1)
								{
									str+="由于";
									for(tj=j+1;tj<s;tj++)
										str+=G[i][tj].letter;
									str+="可推导至@,所以\r\n";
								}
								str+="把";
								
								str+=G[i][0].letter;
								str+="->";
								for(tj=1;tj<=G[i][0].tag;tj++)
									str+=G[i][tj].letter;
								str+="中";
								str+=follow[k][0];
								str+="后的";
								str+=G[i][s].letter;
								str+="\r\n加入到";

								str+=follow[k][0];
								str+="的follow集中\r\n得到:\r\n";
								
								for(tk=0;tk<fw;tk++)
								{
									str+="follow(";
									str+=follow[tk][0];
									str+=") = { ";

									for(tj=1;tj<=count_follow[tk];tj++)
									{
										str+=follow[tk][tj];
										if(tj!=count_follow[tk])
											str+=',';
									}
									str+=" }\r\n";
								}
								str+="\r\n";
							}//if sign
				            break;
						}//is tag

						else if(G[i][s].nultag==0)
						{
							tud=ud;
						    ud=0;
							first_addto_follow(G[i][s].letter,k);

							if(ud==1)
							{


								if(s!=j+1)
								{
									str+="由于";
									for(tj=j+1;tj<s;tj++)
										str+=G[i][tj].letter;
									str+="可推导至@,所以\r\n";
								}
								str+="把";
						    	str+=G[i][0].letter;
								str+="->";
								for(tj=1;tj<=G[i][0].tag;tj++)
									str+=G[i][tj].letter;
								str+="中处于";
								str+=follow[k][0];
								str+="后的";
								str+=G[i][s].letter;
								str+="的first集\r\n加入到";

								str+=follow[k][0];
								str+="的follow集中\r\n得到:\r\n";
								
								for(tk=0;tk<fw;tk++)
								{
									str+="follow(";
									str+=follow[tk][0];
									str+=") = { ";

									for(tj=1;tj<=count_follow[tk];tj++)
									{
										str+=follow[tk][tj];
										if(tj!=count_follow[tk])
											str+=',';
									}
									str+=" }\r\n";
								}
								str+="\r\n";
							}//if ud

							ud=(ud||tud);
							break;
						}//else if
						
						else
						{
							tud=ud;
							ud=0;
							first_addto_follow(G[i][s].letter,k);
							if(ud==1)
							{
								if(s!=j+1)
								{
									str+="由于";
									for(tj=j+1;tj<s;tj++)
										str+=G[i][tj].letter;
									str+="可推导至@,所以\r\n";
								}
								str+="把";
								str+=G[i][0].letter;
								str+="->";
								for(tj=1;tj<=G[i][0].tag;tj++)
									str+=G[i][tj].letter;
								str+="中处于";
								str+=follow[k][0];
								str+="后的";
								str+=G[i][s].letter;
								str+="的first集\r\n加入到";

								str+=follow[k][0];
								str+="的follow集中\r\n得到:\r\n";
								
								for(tk=0;tk<fw;tk++)
								{
									str+="follow(";
									str+=follow[tk][0];
									str+=") = { ";

									for(tj=1;tj<=count_follow[tk];tj++)
									{
										str+=follow[tk][tj];
										if(tj!=count_follow[tk])
											str+=',';
									}
									str+=" }\r\n";
								}
								str+="\r\n";
							}//if ud
							ud=(ud||tud);
						}//else
					}//for s
	}//for k
						
	ud=1;
    while(ud)
	{
		ud=0;
	    for(k=1;k<fw;k++)
		{
            for(i=0;i<n;i++)
		        for(j=1;j<=G[i][0].tag;j++)
				    if(follow[k][0]==G[i][j].letter)
					{
					    if(j==G[i][0].tag)
						{
							tud=ud;
							ud=0;
						    add_follow(G[i][0].letter,k);
							if(ud==1)
							{
								str+="由于";
								str+=follow[k][0];
								str+="是";
								for(tj=1;tj<=G[i][0].tag;tj++)
									str+=G[i][tj].letter;
								str+="的最后一个字符,所以\r\n";
								str+="把";
								str+=G[i][0].letter;
								str+="->";
								for(tj=1;tj<=G[i][0].tag;tj++)
									str+=G[i][tj].letter;
								str+="中左部";
								str+=G[i][0].letter;
								str+="的follow集\r\n加入到";
								str+=follow[k][0];
								str+="的follow集中\r\n得到:\r\n";

								for(tk=0;tk<fw;tk++)
								{
									str+="follow(";
									str+=follow[tk][0];
									str+=") = { ";

									for(tj=1;tj<=count_follow[tk];tj++)
									{
										str+=follow[tk][tj];
										if(tj!=count_follow[tk])
											str+=',';
									}
									str+=" }\r\n";
								}
								str+="\r\n";
							}//if ud
							ud=(ud||tud);
						}//if tag
					    
						else
						{
						    for(s=j+1;s<=G[i][0].tag;s++)
							    if(G[i][s].nultag==0)
								    break;
						    if(s>G[i][0].tag)
							{
								tud=ud;
								ud=0;
							    add_follow(G[i][0].letter,k);
								if(ud==1)
								{

									str+="由于";
									for(tj=j+1;tj<=G[i][0].tag;tj++)
										str+=G[i][tj].letter;
									str+="可推导至@,所以\r\n";

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

									for(tk=0;tk<fw;tk++)
									{
										str+="follow(";
										str+=follow[tk][0];
										str+=") = { ";

										for(tj=1;tj<=count_follow[tk];tj++)
										{
											str+=follow[tk][tj];
											if(tj!=count_follow[tk])
												str+=',';
										}
										str+=" }\r\n";
									}
									str+="\r\n";
								}// if ud
								ud=(ud||tud);
							}//if s
						}//else
					}//if follow
		}//for k
	}//while ud

	return str;
}



CString CGram::get_select()
{
	int i,j,t,s,sign,tj,tk;

	CString str;
	tag[0]=0;
    
	for(i=0;i<n;i++)
	{
		select[i][0]=first[i][0];

		for(j=1;j<=count_first[i];j++)
			if(first[i][j]!='@')
			{
				sign=0;
		        for(t=1;t<=count_select[i];t++)
			        if(select[i][t]==first[i][j])
				        sign=1;
			    if(sign==0)
				{
					count_select[i]++;
				    select[i][count_select[i]]=first[i][j];

					if(judge[num[select[i][0]]][first[i][j]]==1)
						tag[0]=1;
					else

						judge[num[select[i][0]]][first[i][j]]=1;
				}
			}
	}
    
	str+="把各规则的first集中除@外的元素\r\n加入到对应的select集中\r\n得到:\r\n";

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

		for(tj=1;tj<=G[tk][0].tag;tj++)
			str+=G[tk][tj].letter;
		str+=") = { ";
		
		for(tj=1;tj<=count_select[tk];tj++)
		{
			str+=select[tk][tj];
            if(tj!=count_select[tk])
			str+=',';
		}
	    str+=" }\r\n";
	}
	str+="\r\n";


	for(i=0;i<n;i++)
	{
		if(G[i][0].nultag==1)
		{
			s=num[G[i][0].letter]-1;
			for(j=1;j<=count_follow[s];j++)
			{
				sign=0;
		        for(t=1;t<=count_select[i];t++)
			        if(select[i][t]==follow[s][j])
				        sign=1;
			    if(sign==0)
				{
					count_select[i]++;
				    select[i][count_select[i]]=follow[s][j];

					if(judge[num[select[i][0]]][follow[s][j]]==1)
						tag[0]=1;
					else

						judge[num[select[i][0]]][follow[s][j]]=1;
				}
			}
		}
	}

	str+="把能够推导至@的规则\r\n左部非终结符的follow集\r\n加入到该规则的select集中\r\n得到:\r\n";

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

		for(tj=1;tj<=G[tk][0].tag;tj++)
			str+=G[tk][tj].letter;
		str+=") = { ";
		
		for(tj=1;tj<=count_select[tk];tj++)
		{
			str+=select[tk][tj];
            if(tj!=count_select[tk])
			str+=',';
		}
	    str+=" }\r\n";
	}

	for(i=0;i<n;i++)
	{
		if(count_select[i]==0)break;
	}
	if(i<n)tag[5]=1;

	return str;
}



CString CGram::creat_s()
{
	char str[LEN]={0};
	int i,j,k,t,l;
	char arr[LEN][LEN]={0};

	int sign=1;
	CString s;


	str[0]=1;
	str[1]=begin_ch;


	while(sign)

	{
		if(str[0]>LEN)
		{
			s="";
			return s;
		}

		sign=0;
		for(k=1;k<=str[0];k++)
		{
			if(vn[str[k]]!=0)
				break;
		}


		if(k<=str[0])
		{
			sign=1;

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

			l=0;
			for(i=0;i<n;i++)
			    if(G[i][0].letter==str[k])
				{
				    arr[l][0]=G[i][0].tag;
				    for(j=1;j<=G[i][0].tag;j++)
					    arr[l][j]=G[i][j].letter;
				    l++;
				}

			if(l!=0)
				t=rand()%l;
			else 
			{
				s="";
				return s;
			}

			add_str(str,arr[t],k);
		}
	}

	s=str;
	s=s.Right(s.GetLength()-1);
	return s;

}

void CGram::add_str(char str1[],char str2[],int p)
{

	int i;

	if(str2[1]=='@')
	{
		for(i=p;i<LEN;i++)
			str1[i]=str1[i+1];

		str1[LEN-1]=0;
		str1[0]=str1[0]-1;

	    return;
	}

	for(i=LEN-1;i>p+str2[0]-1;i--)
		str1[i]=str1[i-str2[0]+1];

	for(i=1;i<=str2[0];i++)
		str1[p+i-1]=str2[i];

	str1[0]=str1[0]+str2[0]-1;


}