ll1文法dlg.cpp

确定的自顶向下方法

			}
		}
		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]);//VN非终结符
			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];                  //a获得句子的第一个符号

	Vtt=Vt;                         //Vtt获得终结符
	Vt.Delete(Vt.Find("ε"),2);     //终结符集中删除ε和它后面的一个字符
	Vtt.Delete(Vtt.Find("ε"),3);   //从ε开始，删除3个字符

	Output[i][1]=stack.GetData();   //获得栈内容
	Output[i][2]=sentence;          //当前句子
	i++;
	if(Vt.Find(a)==-1)              //如果句子开始不是终结符，出错
	{

		Flag=false;
	}
	for(;Flag;)
	{
		stack.Pop(X);                       //弹出栈顶到X
		if(Vtt.Find(X)!=-1)                 //如果X是终结符
		{
			if(X==a)               
			{
				if(sentence[0]!='#')        //还没有结束或者说结束还早
					sentence.Delete(0,1);   //句子从位置0开始，删除1个字符。
				a=sentence[0];              //a获得句子当前的开始符号
				if(Vt.Find(a)==-1)          //如果句子不全是终结符
				{
			
					break;
				}
				Output[i][1]=stack.GetData();   //获得栈全部内容
				Output[i][2]=sentence;          //获得当前句子
				i++;
				continue;
			}
			else
			{
			
				break;
			}
		}
		else              //X不是终结符
		{
			if(X=='#')    //X是结束符号
			{
				if(X==a)  //结束符号是栈顶，且与a匹配
				{
				
					break;
				}
				else
				{
			
					break;
				}
			}              
			else                 //X是#以外的终结符号
			{
				posx=Vt.Find(a); //终结符集里确定a的位置
				posy=Vn.Find(X);  //非终结符里确定X的位置
				if(Analyze[posx][posy].IsEmpty()) //如果预测分析表中非终结符推不出终结符，出错
				{
			
					break;
				}
				else
				{
					str=Analyze[posx][posy];  //从预测分析表中获得推导产生式
					Output[i][3]=str;         //设置Output数组
					str.Delete(0,3);          //删除前三个字符，即非终结符，-，>
					if(str!="ε")             //产生式右侧不是ε,倒序入栈
						stack.Push(str);
					Output[i][1]=stack.GetData();
					Output[i][2]=sentence;
					i++;
					continue;
				}
			}

		}

	}

}

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=1;i<num+1;i++)
	{
		str.Format("%d",i);
		m_list6.InsertItem(i,str);
		for(j=1;j<4;j++)
		{
			m_list6.SetItemText(i-1,j,Output[i-1][j]);
		}
	}
	
}

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

    UpdateData(true);
	InitAndConvertPt();      //读入文法
	InitArray();                  //初始化N[][]数组
	InitListControl();
	Create_N_Table();         //判断哪些非终结符可以推出空,存入N[]
	FirstVt();
	FollowVt();
	SelectVt();
	Create_Analyze_Table();
	Analyse();
	ShowList6();
	
	
}

void CLL1Dlg::OnOpen() 
{
	// TODO: Add your control notification handler code here
			CFileDialog fd(true);
	fd.m_ofn.lpstrTitle="请选择你要打开的文件";  //标题
	fd.m_ofn.lpstrInitialDir="e:\\";            //初始目录
	if(fd.DoModal())
	{
		m_strFileName=fd.GetPathName();
		
		CStdioFile sf;
		CString str;
		if(sf.Open(m_strFileName.GetBuffer(0),CFile::modeRead))
		{
			CString  strTemp;
			while(sf.ReadString(strTemp))
			{
				str+=strTemp;
				str+="\r\n";
			}	
			SetDlgItemText(IDC_EDIT1,str);
			
			sf.Close();
		}
	}
}