first.cpp

算符优先算法的部分

// First.cpp: implementation of the CFirst class.
//
//////////////////////////////////////////////////////////////////////
#include <windows.h>
#include "stdafx.h"
#include "SymBolDlg.h"
#include "First.h"
#include "SysGraph.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
#include <vector>
#include <iterator>
using   namespace   std;
CFirst::CFirst()
{
     ncount=0;
	 ncountUnTeminalChar=0;
	 retuStr="";
	 MoreMatricxStr="";
	 EqualMatricxStr="";
	 LessMatricxStr="";
}

CFirst::~CFirst()
{

}
BOOL CFirst::ReadFileFromFun(CString filename)
{
    	file.Open(filename,CFile::modeNoTruncate|CFile::modeReadWrite);
		int i=0;
		file.SeekToBegin();	
        while ((file.ReadString(strError))!=FALSE)
		{
              ncount++;
        }	
		pstrFileData=new CString[ncount];//TODO:此函数是将文件中的字符串读出来并将每个产生式
		pUnTerminalChar=new char[ncount];
		memset(pUnTerminalChar,'0',ncount*sizeof(char));
		file.SeekToBegin();//指针重新指到文件开始	
		while (((file.ReadString(strError))!=FALSE)&&(i<ncount))
		{
			strError=strError+"\0";
			StoreUnTerminal(strError);
            pstrFileData[i]=strError;//pstrFileData字符串数组
			i++;
		}
		pFirstVT=new CString[ncountUnTeminalChar];
		pLastVT=new CString[ncountUnTeminalChar];
	    for (int j=0;j<ncountUnTeminalChar;j++)
		{
		  pFirstVT[j]=pUnTerminalChar[j];//给非终结符添加到指针中
		  pLastVT[j]=pUnTerminalChar[j];
		}
		file.Close();
	return TRUE;
}
void CFirst::StoreUnTerminal(CString str)
{
  //TODO:将非终结符存在一个字符数组中供以后使用此函数是用上面的函数来控制流程的所以不用担心跳不出循环
	int i=0;
	while(i<ncount)
	{
	   if(pUnTerminalChar[i]==str[0])// pUnTerminalChar应该先开辟空间??????
	   {
		   break;
	   }
	   if (pUnTerminalChar[i]=='0')
	   {
		   ncountUnTeminalChar++;
		   pUnTerminalChar[i]=str[0];
		   break;
	   }
	   i++;
	}
}
BOOL CFirst::CaculateFirstVT()
{ 
   FirstVTChar *A=new FirstVTChar[ncount];
	int i=0;
	while (i<ncount)
	{
         CString tempStr;
	     tempStr=pstrFileData[i];
	     //char c='→';此字符不能输出
	     if (!(tempStr[3]>64&&tempStr[3]<91))
		 {//当右部产生式第一个字符是终结符时
	    	  A[i].TerminalChar=tempStr[3];
	    	  A[i].UnTerminalChar=tempStr[0];
	    	  A[i].state=TRUE;
              storeFirstVT.push(A[i]);//将形如A—>a...产生式直接求出这样的FirstVT集
	     	  i++;
		      continue;
		 }
	     else if ((tempStr[3]>64&&tempStr[3]<91))//计算当第一个字符是大写字符时
		 {
			 
	    	  if (tempStr.GetLength()<6)
			  {//判断产生式有多少个字符
		    	  int a=tempStr.GetLength();
		    	  i++;
			      continue;
			  }
			  if (tempStr[4]<65||tempStr[4]>90)
			  {
			      A[i].TerminalChar=tempStr[4];
		          A[i].UnTerminalChar=tempStr[0];
		          A[i].state=TRUE;//将形如A—>Ba...这类文法推入栈中
                  storeFirstVT.push(A[i]);
	              i++;
		          continue;
			  }
		 }
    	  else
		  {//此算法也能判断是否是算符优先文法
    		  AfxMessageBox("此文法不是算符优先文法!");
    	      return FALSE;
		  }
	}
	  FirstVTORLastVT=TRUE;//判断是FirstVT还是LastVT集合的标志此处计算FirstVT集合
    	ParseStack();//分析栈中的字符计算FirstVT集合
    	return TRUE;
}
void CFirst::ParseStack()
{ 
	CString str;//保存返回来的终结符
   while (!storeFirstVT.empty()) 
   {
	   FirstVTChar B;
	   B=storeFirstVT.top();
	   storeFirstVT.pop();
	   if (FirstVTORLastVT==TRUE)
	   {//解析FirstVT集
		   str=ParseChar(B,0);
	   }
	   else
	   {//解析LastVT集
		   str=ParseLastVTChar(B,0);
	   }
	   Readfile(staticFileName);//读取文件
	   retuStr="";
       int len=str.GetLength();
	   if (len==0)
	   {
		   continue;
	   }
	   FirstVTChar*C=new FirstVTChar[len];
	   for (int i=0;i<len;i++)
	   {//判断从栈中弹出的元素是否是满足算法的要求
		  C[i].UnTerminalChar=str[i];
		  C[i].TerminalChar=B.TerminalChar;
		  C[i].state=TRUE;
		  storeFirstVT.push(C[i]);
	   }
   }
}
/*根据算法搜索产生式是否有满足若(B,a)是从栈中弹出的元素，
则搜索产生式若产生式有形如A—>B...则将(A,a)推入栈中*/
CString CFirst::ParseChar(FirstVTChar B,int i)
{/*返回所有的形如A—>B...这样的非终结符A全部推入栈中返回
	所有的非终结符字符串*/
  char    tempChar=B.UnTerminalChar;//从栈中弹出的非终结符
  CString tempStr;//第一个字符串 
  tempStr=pstrFileData[i];
  for (char c=B.UnTerminalChar;i<ncount;c=tempChar)
  {
	   if (pstrFileData[i]=="1111111") 
	   {//将产生式全部置为"1111111"以此判断是否是搜索过的产生式
           i++;
		    if (i==ncount) 
			   {//文件末尾
				StorefirstVT(B,tempChar,pFirstVT);
				   break;
			   }
		   tempStr=pstrFileData[i];
		   continue;
	   }
	   else
	   {
		   if (tempStr[3]==c) 
		   {
			   if (tempStr[0]==c) 
			   {
				   i++;
				    if (i==ncount) 
					{
                       StorefirstVT(B,tempChar,pFirstVT);
			    	   break;
					}
				   tempStr=pstrFileData[i];
				   continue;
			   }
			   else
			   {
				   int m;
				   tempChar=tempStr[0];	
				   m=retuStr.Find(tempChar,0);
					if (m!=-1)
					{
						pstrFileData[i]="1111111";
						i++;
						tempStr=pstrFileData[i];
						continue;
					}
					//将每一个字符分别存入某个非终结符的FirstVT集中
				   StorefirstVT(B,tempChar,pFirstVT);
				   retuStr+=tempChar;//循环判断是否有相同的字母
				   pstrFileData[i]="1111111";//当所有的产生式全部为"1111111"时则搜索产生式完毕
				  FirstVTChar M;
				  M.TerminalChar=B.TerminalChar;
				  M.UnTerminalChar=c;
				  M.state=FALSE;
				  ParseChar(M,i);//运用递归求出所有形如A—>Ba...的产生式
				  i=0;
				  continue;
			   }
		   }
		   else
		   {
			   i++;
			   if (i==ncount) 
			   {
				   StorefirstVT(B,tempChar,pFirstVT);
				   break;
			   }
			   tempStr=pstrFileData[i];
		   }
	   }
	 
  }
  return retuStr;//返回非终结符的字符串
}
void CFirst::StorefirstVT(FirstVTChar B,char CH,CString *p)
{  
	CString strtemp;
	for (int i=0;i<ncountUnTeminalChar;i++)
	{
		strtemp=p[i];
		if (strtemp[0]==B.UnTerminalChar)
		{
		   int m;
		   m=strtemp.Find(B.TerminalChar,0);
		   if (m==-1)
		   {
			   p[i]+=B.TerminalChar;
		   }
		}
	 if (strtemp[0]==CH)
		{
	      if(CH!=B.UnTerminalChar)
		  {
			  int n;
			n=strtemp.Find(B.TerminalChar,0);
			if (n==-1)
			{
				p[i]+=B.TerminalChar;
			}
		  }
		}
	}
}
//	  int a= (*(+i)).Replace((LPCTSTR)(*(pstrFileData+i)),"1111");
//	  *(pstrFileData+i) = "111111111";字符串转化
BOOL CFirst::CaculateLastVT()
{//同FirstVT集基本相似只是产生式搜索字符的方向不同
    FirstVTChar *A=new FirstVTChar[ncount];//用FirstVT结构体计算LastVT
	int i=0,len=0;
	while (i<ncount)
	{
         CString tempStr;
	     tempStr=pstrFileData[i];
		 len=tempStr.GetLength();
	     //char c='→';此字符不能输出
	     if (!(tempStr[len-1]>64&&tempStr[len-1]<91))
		 {
	    	  A[i].TerminalChar=tempStr[len-1];
	    	  A[i].UnTerminalChar=tempStr[0];
              storeFirstVT.push(A[i]);
	     	  i++;
		      continue;
		 }
	     else if ((tempStr[len-1]>64&&tempStr[len-1]<91))
		 {
			 
	    	  if (len<6)
			  {
		    	 // int a=tempStr.GetLength();
		    	  i++;
			      continue;
			  }
			  if (tempStr[len-2]<65||tempStr[len-2]>90)
			  {
			      A[i].TerminalChar=tempStr[len-2];
		          A[i].UnTerminalChar=tempStr[0];
                  storeFirstVT.push(A[i]);
	              i++;
		          continue;
			  }
		 }
    	  else
		  {
    		  AfxMessageBox("此文法不是算符优先文法!");
    	      return FALSE;
		  }
	}
	    FirstVTORLastVT=FALSE;//计算LastVT集标志位
    	ParseStack();//分析栈中的字符计算FirstVT集合
    	return TRUE;
}
CString CFirst::ParseLastVTChar(FirstVTChar B,int i)
{
  char    tempChar=B.UnTerminalChar;//从栈中弹出的非终结符
  CString tempStr;//第一个字符串 
  tempStr=pstrFileData[i];
  int len=0;
  len=tempStr.GetLength();
  for (char c=B.UnTerminalChar;i<ncount;c=tempChar)
  {
	   if (pstrFileData[i]=="1111111") 
	   {
           i++;
		    if (i==ncount) 
			   {
				StorefirstVT(B,tempChar,pLastVT);
				   break;
			   }
		   tempStr=pstrFileData[i];
		   len=tempStr.GetLength();
		   continue;
	   }
	   else
	   {
		   if (tempStr[len-1]==c) 
		   {
			   if (tempStr[0]==c) 
			   {
				   i++;
				    if (i==ncount) 
					{
                       StorefirstVT(B,tempChar,pLastVT);
			    	   break;
					}
				   tempStr=pstrFileData[i];
				   len=tempStr.GetLength();
				   continue;
			   }
			   else
			   {
				   int m;
				   tempChar=tempStr[0];	
				   m=retuStr.Find(tempChar,0);
					if (m!=-1)
					{
						pstrFileData[i]="1111111";
						i++;
						tempStr=pstrFileData[i];
						len=tempStr.GetLength();
						continue;
					}
				   StorefirstVT(B,tempChar,pLastVT);
				   retuStr+=tempChar;//循环判断是否有相同的字母FFF
				   pstrFileData[i]="1111111";
				  FirstVTChar M;
				  M.TerminalChar=B.TerminalChar;
				  M.UnTerminalChar=c;
				  M.state=FALSE;
				  ParseLastVTChar(M,i);
				  i=0;
				  continue;
			   }
		   }
		   else
		   {
			   i++;
			   if (i==ncount) 
			   {
				   StorefirstVT(B,tempChar,pLastVT);
				   break;
			   }
			   tempStr=pstrFileData[i];
			   len=tempStr.GetLength();
		   }
	   }
	 
  }
  return retuStr;
}
//读取文件重新将变量pstrFileData赋值更新变量
void CFirst::Readfile(CString filename)
{
	file.Open(filename,CFile::modeNoTruncate|CFile::modeReadWrite);
	file.SeekToBegin();//指针重新指到文件开始	
	int j=0;
	while (((file.ReadString(strError))!=FALSE)&&(j<ncount))
	{
			strError=strError+"\0";
            pstrFileData[j]=strError;//pstrFileData字符串数组
			j++;
	}
	file.Close();
}
void CFirst::PriorityMatricx()
{//计算优先矩阵
	BOOL flag;
	CString tempStr="";
	Readfile(staticFileName);//更新变量
	for (int i=0;i<ncount;i++) 
	{
		tempStr=pstrFileData[i];//获取第i个产生式
		if(tempStr.GetLength()<5)
		{//搜索产生式类型A—>a
			continue;
		}
		else if (tempStr.GetLength()==5)
		{//搜索产生式类型A—>ab
			flag=FirstTwoChar(tempStr[3],tempStr[4]);//判断是否是算符优先文法
			if (flag==FALSE)
			{
				AfxMessageBox("此文法不是算符优先文法!");
			}
			continue;
		}
		else
		{
            for (int j=3;(j+1)<tempStr.GetLength();j++)
	          {     //TODO:将任意两个字符传入字符比较函数中
                 
				flag=FirstTwoChar(tempStr[j],tempStr[j+1]);
				if (flag==FALSE)
				{
						AfxMessageBox("此文法不是算符优先文法!");					
				}
				if ((j+2)<tempStr.GetLength()) 
				{
				     FirstTwoChar(tempStr[j],tempStr[j+2]);//保存优先级
				}
	          }
		}
	}
}
BOOL CFirst::FirstTwoChar(char a,char b)//第几个产生式字符是两个的时候
{
		if (!(a>64&&a<91))
			{
				if (!(b>64&&b<91))//最后一个字符是终结符的情况
				{
					EqualMatricxStr+=a+(CString)'='+b+(CString)'@';
				    return TRUE;
				}
				else//最后一个字符是非终结符的情况计算<关系
				{
					for (int k=0;k<ncountUnTeminalChar;k++)
					{
						CString str=pFirstVT[k];
						if (b==str[0])
						{
							str=str.Right(str.GetLength()-1);
							for (int m=0;m<str.GetLength();m++)
							{
								LessMatricxStr+=a+(CString)'<'+str[m]+(CString)'@';
							}
							return TRUE;
						}
					}
				}
			}
		else if ((a>64&&a<91)&&!(b>64&&b<91)) 
			{
				for (int p=0;p<ncountUnTeminalChar;p++)
				{
					CString str1=pLastVT[p];
					if (a==str1[0])
					{
						str1=str1.Right(str1.GetLength()-1);
						for (int L=0;L<str1.GetLength();L++)
						{
                           MoreMatricxStr+=str1[L]+(CString)'>'+b+(CString)'@';
						}					
						return TRUE;
					}
				}
			}//第三个字符是非终结符的情况下判断LastVT
		else
		{
			return FALSE;
		}
		return TRUE;
}