ll1文法dlg.cpp

LL(1)文法

			if(N[pos]==0)
			{
				buffer=Ptt.pleft[i];
				Ptt.RecordDel(Ptt.pleft[i],Ptt.pright[i]);			
			}
		}
		if(Ptt.RecordFind(buffer)==false)
		{
			pos=Vn.Find(buffer);
			N[pos]=0;
		}
	}

}

}

void CLL1Dlg::InsertFirstVts(CString left,CString right)
{
	int posx,posy;
	posx=Vt.Find(right);
	posy=Vn.Find(left);
	if(First[posx][posy]==false)
		First[posx][posy]=true;
		
}
void CLL1Dlg::InsertFirstVt(int i,CString right)
{
	int posx;
	posx=Vt.Find(right);

	{	if(Fs[posx][i]==false)
			Fs[posx][i]=true;
	}
}

void CLL1Dlg::IncludeFirstVts(CString str1,CString str2)
{
	int pos1,pos2,length;
	int i;
	pos1=Vn.Find(str1);
	pos2=Vn.Find(str2);
	length=Vt.GetLength()-2;
	for(i=0;i<length;i++)
	{
		First[i][pos1]=First[i][pos1]||First[i][pos2];
	}
}

void CLL1Dlg::IncludeFirstVt(int i,CString str2)
{
	int pos2,length;
	int j;
	pos2=Vn.Find(str2);
	length=Vt.GetLength()-2;
	for(j=0;j<length;j++)
	{
		Fs[j][i]=Fs[j][i]||First[j][pos2];
	}
}

void CLL1Dlg::InsertFollows(CString left,CString right)
{
	int posx,posy;
	posx=Vt.Find(right);
	posy=Vn.Find(left);
	if(Follow[posx][posy]==false)
		Follow[posx][posy]=true;
}

bool CLL1Dlg::IsLast(int i,int j0)
{
	int j,pos;
	if(j0==Pt.pright[i].GetLength()-1)
		return(true);
	for(j=j0+1;j<Pt.pright[i].GetLength();j++)
	{
		pos=Vn.Find(Pt.pright[i][j]);
		if(pos==-1)
			return(false);
		if(N[pos]==0)
			return(false);		
	}
	
	return(true);
}

void CLL1Dlg::IncludeFollows(CString str1,CString str2)
{
	int pos1,pos2,length;
	int i;
	pos1=Vn.Find(str1);
	pos2=Vn.Find(str2);
	length=Vt.GetLength()-3;
	for(i=0;i<length;i++)
	{
		Follow[i][pos1]=Follow[i][pos1]||First[i][pos2];
	}
	i=Vt.GetLength()-1;
	Follow[i][pos1]=Follow[i][pos1]||First[i][pos2];

}

void CLL1Dlg::IncludeFollow(int i,int j)
{
	int pos1,pos2,length;
	pos1=Vn.Find(Pt.pright[i][j]);
	pos2=Vn.Find(Pt.pleft[i]);
	length=Vt.GetLength()-3;
	for(i=0;i<length;i++)
	{
		Follow[i][pos1]=Follow[i][pos1]||Follow[i][pos2];
	}
	i=Vt.GetLength()-1;
	Follow[i][pos1]=Follow[i][pos1]||Follow[i][pos2];

}

void CLL1Dlg::IncludeSelect(int i,CString left)
{
	int j;
	int pos,length;
	pos=Vn.Find(left);
	length=Vt.GetLength()-3;
	for(j=0;j<length;j++)
		Select[j][i]=Select[j][i]||Follow[j][pos];
	Select[length][i]=true;
}

void CLL1Dlg::ArrayCopy(CString str)
{
	int i,j;
	if(str=="First")
	{
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
				Compare[i][j]=First[i][j];
	}
	if(str=="Follow")
	{
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
				Compare[i][j]=Follow[i][j];
	}


}

bool CLL1Dlg::ArrayCompare(CString str)
{
	int i,j;
	if(str=="First")
	{
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
				if(Compare[i][j]!=First[i][j])
					return(true);
		return(false);
	}
	if(str=="Follow")
	{
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
				if(Compare[i][j]!=Follow[i][j])
					return(true);
		return(false);
	}
	
	return(false);
}

void CLL1Dlg::FirstVt()
{
	int i,j;
	int pos;
	bool Flag=true;
	while(Flag)
	{
		Flag=false;
		ArrayCopy("First");
		for(i=0;i<Pt.GetLength();i++)
		{
			pos=Vn.Find(Pt.pleft[i]);
			if(N[pos]==1)
			{
				InsertFirstVts(Pt.pleft[i],"ε");
				if(Pt.pright[i]=="ε")
					InsertFirstVt(i,"ε");
			}
			for(j=0;j<Pt.pright[i].GetLength();j++)
			{
				if(Vt.Find(Pt.pright[i][j])!=-1)
				{
					InsertFirstVts(Pt.pleft[i],Pt.pright[i][j]);
					InsertFirstVt(i,Pt.pright[i][j]);
					break;
				}
				if(Vn.Find(Pt.pright[i][j])!=-1)
				{
					IncludeFirstVts(Pt.pleft[i],Pt.pright[i][j]);
					IncludeFirstVt(i,Pt.pright[i][j]);
					pos=Vn.Find(Pt.pright[i][j]);
					if(N[pos]==0)
						break;
					if(j==Pt.pright[i].GetLength()-1 && N[pos]==1)
					{
						InsertFirstVts(Pt.pleft[i],"ε");
						InsertFirstVt(i,"ε");
					}

				}

			}

		}
		Flag=ArrayCompare("First");
	}

}

void CLL1Dlg::FollowVt()
{
	Vt+="#";
	int pos1,pos2;
	pos1=Vn.Find(Pt.Starter);
	pos2=Vt.Find("#");
	Follow[pos2][pos1]=true;
	int i,j;
	bool Flag=true;
	while(Flag)
	{
		Flag=false;
		ArrayCopy("Follow");
		for(i=0;i<Pt.GetLength();i++)
		{
			for(j=0;j<Pt.pright[i].GetLength();j++)
			{
				if(Vt.Find(Pt.pright[i][j])!=-1)
					continue;
				if(j<Pt.pright[i].GetLength()-1)
				{
					if(Vn.Find(Pt.pright[i][j])!=-1 && Vt.Find(Pt.pright[i][j+1])!=-1)
					{
						InsertFollows(Pt.pright[i][j],Pt.pright[i][j+1]);
					}
					if(Vn.Find(Pt.pright[i][j])!=-1 && Vn.Find(Pt.pright[i][j+1])!=-1)
					{
						IncludeFollows(Pt.pright[i][j],Pt.pright[i][j+1]);
					}
				}
				if(IsLast(i,j))
				{
					IncludeFollow(i,j);
				}
			}
		}
		Flag=ArrayCompare("Follow");
	}

}

void CLL1Dlg::SelectVt()
{
	int i,j;
	int length;
	int nullpos;
	///////////////////////////////////////////
	//初始化Select[][],使Select[][]=First[][]
	///////////////////////////////////////////
	length=Vt.GetLength()-3;
	for(i=0;i<length;i++)
		for(j=0;j<20;j++)
			Select[i][j]=Fs[i][j];
	for(i=0;i<Pt.GetLength();i++)
	{
		nullpos=Vt.Find("ε");
		if(Fs[nullpos][i]==1)
			IncludeSelect(i,Pt.pleft[i]);

	}
}

void CLL1Dlg::Create_Analyze_Table()
{
	int i,j;
	int pos;
	CString Vtt=Vt;
	CString str;
	Vtt.Delete(Vtt.Find("ε"),2);
	for(i=0;i<Pt.GetLength();i++)
	{
		for(j=0;j<Vt.GetLength();j++)
		{
			pos=Vn.Find(Pt.pleft[i]);
			if(Select[j][i]==1)
			{
				str.Empty();
				str+=Pt.pleft[i];
				str+="->";
				str+=Pt.pright[i];
				Analyze[j][pos]=str;
			}
		}
	}

}

void CLL1Dlg::Analyse()
{
	CStack stack;
	CString str,sentence,Vtt;
	bool Flag=true;
	char X,a;
	int posx,posy;
	int i=0;
	str.Empty();
	sentence.Empty();
	str+=Pt.Starter;
	str+="#";
	stack.Push(str);
	sentence=m_sentence;
	sentence+="#";
	a=sentence[0];

	Vtt=Vt;
	Vt.Delete(Vt.Find("ε"),2);
	Vtt.Delete(Vtt.Find("ε"),3);

	Output[i][1]=stack.GetData();
	Output[i][2]=sentence;
	i++;
	if(Vt.Find(a)==-1)
	{
		Error();
		Flag=false;
	}
	for(;Flag;)
	{
		stack.Pop(X);
		if(Vtt.Find(X)!=-1)
		{
			if(X==a)
			{
				if(sentence[0]!='#')
					sentence.Delete(0,1);
				a=sentence[0];
				if(Vt.Find(a)==-1)
				{
					Error();
					break;
				}
				Output[i][1]=stack.GetData();
				Output[i][2]=sentence;
				i++;
				continue;
			}
			else
			{
				Error();
				break;
			}
		}
		else
		{
			if(X=='#')
			{
				if(X==a)
				{
					Success();
					break;
				}
				else
				{
					Error();
					break;
				}
			}
			else
			{
				posx=Vt.Find(a);
				posy=Vn.Find(X);
				if(Analyze[posx][posy].IsEmpty())
				{
					Error();
					break;
				}
				else
				{
					str=Analyze[posx][posy];
					Output[i][3]=str;
					str.Delete(0,3);
					if(str!="ε")
						stack.Push(str);
					Output[i][1]=stack.GetData();
					Output[i][2]=sentence;
					i++;
					continue;
				}
			}

		}

	}

}

void CLL1Dlg::ShowList1()
{
	int i;
	int Vnnum;
	CString str;
	Vnnum=Vn.GetLength();
	for(i=0;i<Vnnum;i++)
	{
		m_list1.InsertColumn(i,"0");
		m_list1.SetColumnWidth(i,25);
	}
	m_list1.InsertItem(0,"0");
	m_list1.InsertItem(1,"0");
	for(i=0;i<Vnnum;i++)
	{
		str=Vn[i];
		m_list1.SetItemText(0,i,str);
	}
	for(i=0;i<Vnnum;i++)
	{
		str.Empty();
		if(N[i]==1)
			str="√";
		m_list1.SetItemText(1,i,str);

	}
	
}

void CLL1Dlg::ShowList2()
{
	int i,j;
	int Vnnum,Vtnum;
	CString str;
	Vnnum=Vn.GetLength();
	if(Vt.Find("ε")!=-1)
		Vtnum=Vt.GetLength()-2;
	else
		Vtnum=Vt.GetLength();
	for(i=0;i<Vtnum+1;i++)
	{
		m_list2.InsertColumn(i,"0");
		m_list2.SetColumnWidth(i,25);
	}
	m_list2.SetColumnWidth(0,30);
	m_list2.InsertItem(0,"★");
	for(i=0;i<Vnnum;i++)
	{
		str=Vn[i];
		m_list2.InsertItem(i+1,str);
	}
	for(i=Vnnum;i<Vnnum+Pt.GetLength();i++)
		m_list2.InsertItem(i+1,Pt.pright[i-Vnnum]);
	for(i=0;i<Vtnum;i++)
	{
		str=Vt[i];
		m_list2.SetItemText(0,i+1,str);
	}
	m_list2.SetItemText(0,Vtnum,"ε");
	for(i=0;i<Vnnum;i++)
		for(j=0;j<Vtnum;j++)
		{
			str.Empty();
			if(First[j][i]==1)
				str="√";
			m_list2.SetItemText(i+1,j+1,str);
		}
	for(i=Vnnum;i<Vnnum+Pt.GetLength();i++)
		for(j=0;j<Vtnum;j++)
		{
			str.Empty();
			if(Fs[j][i-Vnnum]==1)
				str="√";
			m_list2.SetItemText(i+1,j+1,str);
		}
		

}

void CLL1Dlg::ShowList3()
{
	int i,j;
	int Vnnum,Vtnum;
	CString str;
	Vnnum=Vn.GetLength();
	if(Vt.Find("ε")!=-1)
		Vtnum=Vt.GetLength()-2;
	else
		Vtnum=Vt.GetLength();
	for(i=0;i<Vtnum+1;i++)
	{
		m_list3.InsertColumn(i,"0");
		m_list3.SetColumnWidth(i,25);
	}
	m_list3.InsertItem(0,"★");
	for(i=0;i<Vtnum;i++)
	{
		str=Vt[i];
		m_list3.SetItemText(0,i+1,str);
	}
	m_list3.SetItemText(0,Vtnum,"#");
	for(i=0;i<Vnnum;i++)
	{
		str=Vn[i];
		m_list3.InsertItem(i+1,str);
	}
	for(i=0;i<Vnnum;i++)
		for(j=0;j<Vtnum;j++)
		{
			str.Empty();
			if(Follow[j][i]==1)
				str="√";
			m_list3.SetItemText(i+1,j+1,str);
		}
	for(i=0;i<Vnnum;i++)
		m_list3.SetItemText(i+1,Vtnum,"√");
	

}

void CLL1Dlg::ShowList4()
{
	int i,j;
	int Vtnum,Vnnum;
	CString str;
	Vnnum=Vn.GetLength();
	if(Vt.Find("ε")!=-1)
		Vtnum=Vt.GetLength()-2;
	else
		Vtnum=Vt.GetLength();
	for(i=0;i<Vtnum+1;i++)
	{
		m_list4.InsertColumn(i,"0");
		m_list4.SetColumnWidth(i,25);
	}
	m_list4.SetColumnWidth(0,55);
	m_list4.InsertItem(0,"★");
	for(i=0;i<Vtnum;i++)
	{
		str=Vt[i];
		m_list4.SetItemText(0,i+1,str);
	}

	m_list4.SetItemText(0,Vtnum,"#");
	for(i=0;i<Pt.GetLength();i++)
	{
		str.Empty();
		str+=Pt.pleft[i];
		str+="->";
		str+=Pt.pright[i];
		m_list4.InsertItem(i+1,str);
	}
	for(i=0;i<Vtnum;i++)
		for(j=0;j<Pt.GetLength();j++)
		{
			str.Empty();
			if(Select[i][j]==1)
				str="√";
			m_list4.SetItemText(j+1,i+1,str);
		}

}

void CLL1Dlg::ShowList5()
{
	int i,j;
	int Vtnum,Vnnum;
	CString Vtt,str;
	Vtt=Vt;
	if(Vt.Find("ε")!=-1)
		Vtt.Delete(Vt.Find("ε"),2);

	Vtnum=Vtt.GetLength();
	Vnnum=Vn.GetLength();
	for(i=0;i<Vtnum+1;i++)
	{
		m_list5.InsertColumn(i,"0");
		m_list5.SetColumnWidth(i,55);
	}
	m_list5.SetColumnWidth(0,20);
	m_list5.InsertItem(0,"★");
	for(i=0;i<Vtnum;i++)
	{
		str=Vtt[i];
		m_list5.SetItemText(0,i+1,str);
	}
	for(i=0;i<Vnnum;i++)
	{
		str=Vn[i];
		m_list5.InsertItem(i+1,str);
	}
	for(i=0;i<Vtnum;i++)
		for(j=0;j<Vnnum;j++)
			m_list5.SetItemText(j+1,i+1,Analyze[i][j]);
}

void CLL1Dlg::ShowList6()
{
	int i,j;
	int num=0;
	CString str;
	while(Output[num][1]!="")
	{
		num++;
	}
	if(Output[num-1][1]=="#" && Output[num-1][2]=="#")
		Output[num-1][3]+="(成功)";
	else
		Output[num-1][3]="出 错";
	for(i=0;i<num;i++)
	{
		str.Format("%d",i);
		m_list6.InsertItem(i,str);
		for(j=1;j<4;j++)
		{
			m_list6.SetItemText(i,j,Output[i][j]);
		}
	}
	
}

void CLL1Dlg::ShowAllList()
{
	ShowList1();
	ShowList2();
	ShowList3();
	ShowList4();
	if(Flag_IsLL1)
	{
		ShowList5();
		ShowList6();
	}
}

bool CLL1Dlg::IsLL1()
{
	int i,j,z;
	int num,pos;
	bool Flag;
	pos=0;
	for(int k=0;k<Vn.GetLength();k++)
	{
		num=Pt.GetNum(Vn[k]);
		for(i=pos;i<num+pos-1;i++)
			for(j=i+1;j<num+pos;j++)
			{
				for(z=0;z<Vt.GetLength()-2;z++)
				{
					Flag=Select[z][i] && Select[z][j];
					if(Flag)
						return(false);
				}
			}
		pos+=num;
	}
	return(true);

}

void CLL1Dlg::Error()
{
	m_sign="预-测-分-析-失-败";
	m_con_sign.SetWindowText(m_sign);
	
}

void CLL1Dlg::Success()
{
	m_sign="预-测-分-析-成-功";
	m_con_sign.SetWindowText(m_sign);
}

void CLL1Dlg::OnBianyi()                     //***总控程序***
{

    UpdateData(true);
	InitAndConvertPt();      //读入文法、消除左递归、提取公因子
	InitArray();                  //初始化N[][]数组
	InitListControl();
	VnRefresh(Pt);
	VtRefresh(Pt);
	Create_N_Table();         //判断哪些非终结符可以推出空,存入N[]
	FirstVt();
	FollowVt();
	SelectVt();
	Flag_IsLL1=IsLL1();
	if(!Flag_IsLL1)
		AfxMessageBox("不是LL(1)文法~!");
	else
	{
		Create_Analyze_Table();
		Analyse();
	}
	ShowAllList();
	
}