operator1stdlg.cpp

一个具有图形表示界面的算符优先的语法分析算法,根据<编译原理>的知识,加上自己的理解来实现的

// operator1stDlg.cpp : 实现文件
//

#include "stdafx.h"
#include "operator1st.h"
#include "operator1stDlg.h"
#include ".\operator1stdlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif


#define M 6
struct lang
{
	char left; //产生式的左部
	char right[M]; //产生式的
};


#define N 9  //产生式的项数
//产生式的结构体数组,@为null e
struct lang langP[N]={
	{'Z',"#E#"},
	{'E',"E+T"},
	{'E',"T"},
	{'T',"T*F"},
	{'T',"F"},
	{'F',"P^F"},
	{'F',"P"},
	{'P',"(E)"},
	{'P',"i"}
};

#define VnMAX 20
char VnSet[VnMAX]={0};
int VnCount;

#define VtMAX 50
char VtSet[VtMAX]={0};
int VtCount;

//建立Vn字符集
void CreateVnSet()
{
	int k=0;
	int i=0;
	
	VnSet[k]=langP[i].left;
	while(i<N)
	{
		if(VnSet[k]!=langP[i].left)
		{
			k++;
			VnSet[k]=langP[i].left;
		}
		i++;
	}
	VnCount=k;
}

//查找ch是否已经在Vt字符集中
bool FindinVtSet(char ch)
{
	int i=0;
	while(VtSet[i]!=0)
	{
		if(ch==VtSet[i])
		{
			return true;
		}
		i++;
	}

	return false;
}

//插入当前的Vt字符至Vt字符集
void Insert2VtSet(char ch)
{
	int i=0;
	while(VtSet[i]!=0)
	{
		i++;
	}
	VtSet[i]=ch;
	VtCount=i;
}

//创建Vt字符集
void CreateVtSet()
{
	int i=0;
	int j;
	char temp;
	while(langP[i].left!=0)
	{
		j=0;
		while(langP[i].right[j]!=0)
		{
			temp=langP[i].right[j];
			if(temp<'A' || temp>'Z')
				if(!FindinVtSet(temp))
				{
					Insert2VtSet(temp);
				}
			j++;
		}
		i++;
	}
}

bool F[VnMAX][VtMAX]={0};

//查找一Vn字符在VnSet里对应的index
int FindVnIndex(char ch)
{
	int i;
	for(i=0;i<=VnCount;i++)
	{
		if(ch==VnSet[i])
		{
			return i;
		}
	}

	return -1;
}

//查找一Vt字符在VtSet里对应的index
int FindVtIndex(char ch)
{
	int i;
	for(i=0;i<=VtCount;i++)
	{
		if(ch==VtSet[i])
		{
			return i;
		}
	}

	return -1;
}

//FirstVt首终结符集
struct First
{
	char VtArr[VtMAX];
}FirstVt[VnMAX]={0};

int flag;

//单个Vt和FirstVtSet并
void VtUFisrtVt(int VnIndex,char Vt)
{
	
	int Count=0;

	while( FirstVt[VnIndex].VtArr[Count]!=0 )  //找出DestFirst的Vt集合大小
	{
		Count++;
	}
	
	int i;
	for(i=0;i<Count;i++)  //如果follow中已经有此Vt了,则返回
	{
		if( Vt==FirstVt[VnIndex].VtArr[i] )
		{
			return;
		}
	}

	FirstVt[VnIndex].VtArr[Count]=Vt;
	flag=1;
}

//两个FirstVtSet并
void FirstVtUFirstVt(int leftindex,int rightindex)
{
	int LCnt=0;
	int RCnt=0;

	while( FirstVt[leftindex].VtArr[LCnt]!=0)  //找出目的地的Vt集合大小
	{
		LCnt++;
	}

	while( FirstVt[rightindex].VtArr[RCnt]!=0 )  //找出源的Vt集合大小
	{
		RCnt++;
	}

	if(RCnt==0)  //如果为零,则不处理,退出
	{
		return;
	}

    int i,j;
	for(i=0;i<RCnt;i++)  //两个集合的并运算
	{
		if( FirstVt[rightindex].VtArr[i]=='@' )
		{
			goto nextfirstUfirstloop;
		}
		for(j=0;j<LCnt;j++)
		{
			if( FirstVt[rightindex].VtArr[i]==FirstVt[leftindex].VtArr[j] )
			{
				goto nextfirstUfirstloop;
			}
		}
		FirstVt[leftindex].VtArr[LCnt]=FirstVt[rightindex].VtArr[i];
		LCnt++;
		flag=1;
nextfirstUfirstloop: ;
	}

}

void FindFirstVt()
{
	int i,j;
	char ch1,ch2;
	int VnIndex;

	for(i=0;i<=N;i++)
	{
		ch1=langP[i].right[0];
		ch2=langP[i].right[1];
		VnIndex=FindVnIndex(langP[i].left);

		if( ch1!=0 )
		{
			if( ch1<'A' || ch1>'Z')
			{
				VtUFisrtVt(VnIndex,ch1);
			}
		}

		if( ch1>='A' && ch1<='Z')
		{
			if( FindVnIndex(ch1)!=-1)
			{
				if( ch2!=0 )
				{
					if( ch2<'A' || ch2>'Z' )
					{
						VtUFisrtVt(VnIndex,ch2);
					}
				}
			}
		}
	}
	
	flag=1;
	int Lindex,Rindex;
	while(flag)
	{
		flag=0;
		for(i=0;i<=N;i++)
		{
			ch1=langP[i].right[0];
			if(ch1>='A' && ch1<='Z')
			{
				Lindex=FindVnIndex(langP[i].left);
				Rindex=FindVnIndex(ch1);
				if(Rindex!=-1)
				{
					FirstVtUFirstVt(Lindex,Rindex);
				}
			}
		}
	}
}

struct Last
{
	char VtArr[VtMAX];
}LastVt[VnMAX]={0};

//单个Vt和LastVtSet并
void VtULastVt(int VnIndex,char Vt)
{
	
	int Count=0;

	while( LastVt[VnIndex].VtArr[Count]!=0 )  //找出DestFirst的Vt集合大小
	{
		Count++;
	}
	
	int i;
	for(i=0;i<Count;i++)  //如果follow中已经有此Vt了,则返回
	{
		if( Vt==LastVt[VnIndex].VtArr[i] )
		{
			return;
		}
	}

	LastVt[VnIndex].VtArr[Count]=Vt;
	flag=1;
}

//两个LastVtSet并
void LastVtULastVt(int leftindex,int rightindex)
{
	int LCnt=0;
	int RCnt=0;

	while( LastVt[leftindex].VtArr[LCnt]!=0)  //找出目的地的Vt集合大小
	{
		LCnt++;
	}

	while( LastVt[rightindex].VtArr[RCnt]!=0 )  //找出源的Vt集合大小
	{
		RCnt++;
	}

	if(RCnt==0)  //如果为零,则不处理,退出
	{
		return;
	}

    int i,j;
	for(i=0;i<RCnt;i++)  //两个集合的并运算
	{
		if( LastVt[rightindex].VtArr[i]=='@' )
		{
			goto nextlastUlastloop;
		}
		for(j=0;j<LCnt;j++)
		{
			if( LastVt[rightindex].VtArr[i]==LastVt[leftindex].VtArr[j] )
			{
				goto nextlastUlastloop;
			}
		}
		LastVt[leftindex].VtArr[LCnt]=LastVt[rightindex].VtArr[i];
		LCnt++;
		flag=1;
nextlastUlastloop: ;
	}
}

void FindLastVt()
{
	int i,j;
	char ch1,ch2;
	int VnIndex;
	int cnt;

	for(i=0;i<=N;i++)
	{
		cnt=0;
		while(langP[i].right[cnt]!=0)
		{
			cnt++;
		}
		ch1=langP[i].right[cnt-1];
		ch2=langP[i].right[cnt-2];
		VnIndex=FindVnIndex(langP[i].left);

		if( ch1!=0 )
		{
			if( ch1<'A' || ch1>'Z')
			{
				VtULastVt(VnIndex,ch1);
			}
		}

		if( ch1>='A' && ch1<='Z')
		{
			if( FindVnIndex(ch1)!=-1)
			{
				if( ch2!=0 )
				{
					if( ch2<'A' || ch2>'Z' )
					{
						VtULastVt(VnIndex,ch2);
					}
				}
			}
		}
	}

	flag=1;
	int Lindex,Rindex;
	while(flag)
	{
		flag=0;
		for(i=0;i<=N;i++)
		{
			cnt=0;
			while(langP[i].right[cnt]!=0)
			{
				cnt++;
			}
			ch1=langP[i].right[cnt-1];
			if(ch1>='A' && ch1<='Z')
			{
				Lindex=FindVnIndex(langP[i].left);
				Rindex=FindVnIndex(ch1);
				if(Rindex!=-1)
				{
					LastVtULastVt(Lindex,Rindex);
				}
			}
		}
	}
}

int PriorityTable[VtMAX][VtMAX]={0};

//构造优先表
//1---A=B
//2---A<B
//3---A>B
void CreatePriorityTable()
{
	int i,j;
	int cnt;
	char ch0,ch1,ch2;
	int index0,index1,index2;
	for(i=0;i<N;i++)
	{
		cnt=0;
		while(langP[i].right[cnt]!=0)
		{
			cnt++;
		}
		
		for(j=0;j<cnt-1;j++)
		{
			ch0=langP[i].right[j];
			ch1=langP[i].right[j+1];
			index0=FindVtIndex(ch0);
			index1=FindVtIndex(ch1);
			if( index0!=-1 && index1!=-1)
			{
				PriorityTable[index0][index1]=1;
			}

			if(j<cnt-2)
			{
				ch2=langP[i].right[j+2];
				index0=FindVtIndex(ch0);
				index1=FindVnIndex(ch1);
				index2=FindVtIndex(ch2);
				if( index0!=-1 && index1!=-1 && index2!=-1)
				{
					PriorityTable[index0][index2]=1;
				}
			}

			index0=FindVtIndex(ch0);
			index1=FindVnIndex(ch1);
			if( index0!=-1 && index1!=-1 )
			{
				int k=0;
				int Vtindex;
				while(FirstVt[index1].VtArr[k]!=0)
				{
					Vtindex=FindVtIndex(FirstVt[index1].VtArr[k]);
					PriorityTable[index0][Vtindex]=2;
					k++;
				}
			}

			index0=FindVnIndex(ch0);
			index1=FindVtIndex(ch1);
			if( index0!=-1 && index1!=-1 )
			{
				int k=0;
				int Vtindex;
				while(LastVt[index0].VtArr[k]!=0)
				{
					Vtindex=FindVtIndex(LastVt[index0].VtArr[k]);
					PriorityTable[Vtindex][index1]=3;
					k++;
				}
			}
		}
	}
}

char stack[256]={0};
char InputStr[50]="i+i*i#";

//把s[j+1]...s[k]归约为某个N
//char Reduce(int head,int tail)


int OpFirstCalc()
{
	int k=0;
	int i=0;
	int j;
	stack[k]='#';
	char a,Q;
	int indexJ,indexA,indexQ;
	
	do
	{
		a=InputStr[i];
		if(stack[k]<'A' || stack[k]>'Z')
		{
			j=k;
		}
		else
		{
			j=k-1;
		}

		indexA=FindVtIndex(a);
		indexJ=FindVtIndex(stack[j]);
		while( PriorityTable[indexJ][indexA]==3 )
		{
			do
			{
				Q=stack[j];
				indexQ=FindVtIndex(Q);
				if( stack[j-1]<'A' || stack[j-1]>'Z' )
				{
					j=j-1;
				}
				else
				{
					j=j-2;
				}
				indexJ=FindVtIndex(stack[j]);
			}while( PriorityTable[indexJ][indexQ]!=2 );
			k=j+1;
			stack[k]='N';
		}

		if( PriorityTable[indexJ][indexA]==2 || PriorityTable[indexJ][indexA]==1)
		{
			k++;
			stack[k]=a;
		}
		else
		{
			return 0;
		}

		i++;
	}while(a!='#');
	
	return 1;
}
// 用于应用程序“关于”菜单项的 CAboutDlg 对话框

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// 对话框数据
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV 支持

// 实现
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// Coperator1stDlg 对话框



Coperator1stDlg::Coperator1stDlg(CWnd* pParent /*=NULL*/)
	: CDialog(Coperator1stDlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void Coperator1stDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(Coperator1stDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP


	ON_BN_CLICKED(IDC_OperFirst, OnBnClickedOperfirst)
END_MESSAGE_MAP()


// Coperator1stDlg 消息处理程序

BOOL Coperator1stDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// 将\“关于...\”菜单项添加到系统菜单中。

	// IDM_ABOUTBOX 必须在系统命令范围内。
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
	//  执行此操作
	SetIcon(m_hIcon, TRUE);			// 设置大图标
	SetIcon(m_hIcon, FALSE);		// 设置小图标

	// TODO: 在此添加额外的初始化代码
	
	return TRUE;  // 除非设置了控件的焦点，否则返回 TRUE
}

void Coperator1stDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 如果向对话框添加最小化按钮，则需要下面的代码
//  来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
//  这将由框架自动完成。

void Coperator1stDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // 用于绘制的设备上下文

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// 使图标在工作矩形中居中
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// 绘制图标
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

//当用户拖动最小化窗口时系统调用此函数取得光标显示。
HCURSOR Coperator1stDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}


void Coperator1stDlg::DrawExp()
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=30;
	int y=50;
	CString str;

	int i;
	for(i=0;i<N;i++)
	{
		str.Format("%c",langP[i].left);
		pDC->TextOut(x,y,str);
		str.Format("%s","-->");
		pDC->TextOut(x+20,y,str);
		str.Format("%s",langP[i].right);
		pDC->TextOut(x+50,y,str);
		y+=20;
	}

	ReleaseDC(pDC);
}

void Coperator1stDlg::DrawVnSet()
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=150;
	int y=50;
	CString str;

	int i;
	for(i=0;i<=VnCount;i++)
	{
		str.Format("%c",VnSet[i]);
		pDC->TextOut(x,y,str);
		y+=20;
	}

	ReleaseDC(pDC);
}

void Coperator1stDlg::DrawFirstVtSet()
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=180;
	int y=50;
	CString str;

	str.Format("%s","FirstVtSet");
	pDC->TextOut(180,30,str);
	
	int i,j;
	for(i=0;i<=VnCount;i++)
	{
		for(j=0;j<VtMAX;j++)
		{
			if(FirstVt[i].VtArr[j]!=0)
			{
				str.Format("%c",FirstVt[i].VtArr[j]);
				pDC->TextOut(x,y,str);
				x+=15;
			}
		}
		x=180;
		y+=20;
	}

	ReleaseDC(pDC);
}

void Coperator1stDlg::DrawLastVtSet()
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=260;
	int y=50;
	CString str;
	
	str.Format("%s","LastVtSet");
	pDC->TextOut(260,30,str);
	
	int i,j;
	for(i=0;i<=VnCount;i++)
	{
		for(j=0;j<VtMAX;j++)
		{
			if(LastVt[i].VtArr[j]!=0)
			{
				str.Format("%c",LastVt[i].VtArr[j]);
				pDC->TextOut(x,y,str);
				x+=15;
			}
		}
		x=260;
		y+=20;
	}

	ReleaseDC(pDC);
}

//绘制优先表
void Coperator1stDlg::DrawPriorityTable()
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=340;
	int y=50;
	CString str;
	
	int i,j;
	//画出框架
	for(i=0;i<=VtCount;i++)
	{
		str.Format("%c",VtSet[i]);
-		pDC->TextOut(x,y,str);
	
		y+=30;
	}


	y=30;
	x+=30;
	for(j=0;j<=VtCount;j++)
	{
		str.Format("%c",VtSet[j]);
		pDC->TextOut(x,y,str);
		x+=30;
	}


	x=370;
	y=50;
	//画出关系二维表
	for(i=0;i<=VtCount;i++)
	{
		for(j=0;j<=VtCount;j++)
		{
			if(PriorityTable[i][j]==1)
			{
				str.Format("%s","=");
			}
			else if(PriorityTable[i][j]==2)
			{
				str.Format("%s","<");
			}
			else if(PriorityTable[i][j]==3)
			{
				str.Format("%s",">");
			}

			pDC->TextOut(x,y,str);
			x+=30;
		}

		x=370;
		y+=30;
	}

	ReleaseDC(pDC);
}

//分析结果的输出
void Coperator1stDlg::DrawExpResult(int m)
{
	CDC* pDC=GetDC();  //获取设备上下文
	int x=180;
	int y=290;
	CString str;

	str.Format("%s",InputStr);
	pDC->TextOut(x,y,str);

	if(m==1)
	{
		str.Format("%s","is a correct expression");
		pDC->TextOut(x+50,y,str);
	}
	else if(m==0)
	{
		str.Format("%s","is NOT a correct expression");
		pDC->TextOut(x+50,y,str);
	}

	ReleaseDC(pDC);
}

void Coperator1stDlg::OnBnClickedOperfirst()
{
	// TODO: 在此添加控件通知处理程序代码
	DrawExp();
	
	CreateVnSet();
	CreateVtSet();
	FindFirstVt();
	FindLastVt();

	DrawVnSet();
	DrawFirstVtSet();
	DrawLastVtSet();

	CreatePriorityTable();
	DrawPriorityTable();

	int m=OpFirstCalc();
	DrawExpResult(m);
}