ll1.cpp

输入一个表达式子 然后输出 这个式子 的LL1文法形式

// LL1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "LL1.h"
#include "instruct.h"
#include "endflag.h"
#include "mstack.h"

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

/////////////////////////////////////////////////////////////////////////////
// The one and only application object

CWinApp theApp;

using namespace std;

////////////my thread funaction to deal the problem
UINT deal(LPVOID param){
	Cinstruct *headofinstruct=(Cinstruct *)param;
	Cinstruct *itemp;
	int i,j;
	bool change=FALSE;
	TCHAR c,c1;
	TCHAR flag;
	Cuendflag * uendflag;
	//////////get endflag
	Sleep(100);
	itemp=headofinstruct;
	while(itemp!=NULL){
		if(!Cendflag::isaflag(itemp->i_s.GetAt(0))){
			new Cendflag(itemp->i_s.GetAt(0));
		}
		itemp=itemp->next;
	}
	Sleep(100);
	/////////check null
	itemp=headofinstruct;
	while(itemp!=NULL){
		if(Cendflag::getflag(itemp->i_s.GetAt(0))->isNull==TRUE){
			itemp=itemp->next;
			if(itemp==NULL&&change==TRUE){
				itemp=headofinstruct;
				change=FALSE;
				continue;
			}
		}
		if(itemp->i_s.GetLength()==3){
			(Cendflag::getflag(itemp->i_s.GetAt(0)))->isNull=TRUE;
			change=TRUE;
		}
		if(itemp->i_s.GetLength()>3){
			for(i=3;i<itemp->i_s.GetLength();i++){
				c=itemp->i_s.GetAt(i);
				if(Cendflag::isaflag(c)){
					if(!(Cendflag::getflag(c)->isNull)){
						break;
					}
				}else{
					break;
				}
			}
			if(i==itemp->i_s.GetLength()){
				Cendflag::getflag(itemp->i_s.GetAt(0))->isNull=TRUE;
				change=TRUE;
			}
		}
		itemp=itemp->next;
		if(itemp==NULL&&change==TRUE){
			itemp=headofinstruct;
			change=FALSE;
		}
	}
	//////check null end
	Sleep(100);
	//////get the first stack
	change=FALSE;
	itemp=headofinstruct;
	while(itemp!=NULL){
		flag=itemp->i_s.GetAt(0);
		if(itemp->i_s.GetLength()==3){
			if(Cendflag::getflag(flag)->addfirst('\0')){
				change=TRUE;
			}
			itemp=itemp->next;
			if(itemp==NULL&&change==TRUE){
				itemp=headofinstruct;
				change=FALSE;
			}
			continue;
		}
		for(i=3;i<itemp->i_s.GetLength();i++){
			c=itemp->i_s.GetAt(i);
			flag=itemp->i_s.GetAt(0);
			if(!(Cendflag::isaflag(c))){
				if(Cendflag::getflag(flag)->addfirst(c)){
					change=TRUE;
				}
				break;
			}else{
				uendflag=Cendflag::getflag(c)->first;
				while(uendflag!=NULL){
					if(uendflag->flag!='\0'){
						if((Cendflag::getflag(flag))->addfirst(uendflag->flag)){
							change=TRUE;
						}
					}
					uendflag=uendflag->next;
				}
				if(Cendflag::getflag(c)->isNull==FALSE){
					break;
				}

			}
		}
		if(Cendflag::getflag(flag)->isNull==TRUE){
			if((Cendflag::getflag(flag))->addfirst('\0')){
				change=TRUE;
			}
		}
		itemp=itemp->next;
		if(itemp==NULL&&change==TRUE){
			itemp=headofinstruct;
			change=FALSE;
		}

	}
    /////////////end of first
	Sleep(100);
	////////////deal follow
	change=FALSE;
	itemp=headofinstruct;
	while(itemp!=NULL){
		flag=itemp->i_s.GetAt(0);
		if(flag=='S'){
			if((Cendflag::getflag(flag))->addfollow('#')){
				change=TRUE;
			}
		}
		for(i=3;i<itemp->i_s.GetLength();i++){
			c=itemp->i_s.GetAt(i);
			if(Cendflag::isaflag(c)){
				for(j=i+1;j<itemp->i_s.GetLength();j++){
					c1=itemp->i_s.GetAt(j);
					if(Cendflag::isaflag(c1)){
						uendflag=Cendflag::getflag(c1)->first;
						while(uendflag!=NULL){
							if((Cendflag::getflag(c))->addfollow(uendflag->flag)){
								change=TRUE;
							}
							uendflag=uendflag->next;
						}
						if(Cendflag::getflag(c1)->isNull==FALSE){
							break;
						}
					}else{
						if((Cendflag::getflag(c))->addfollow(c1)){
							change=TRUE;
						}
						break;
					}

				}
				if(j==itemp->i_s.GetLength()){
					uendflag=Cendflag::getflag(flag)->follow;
					while(uendflag!=NULL){
						if((Cendflag::getflag(c))->addfollow(uendflag->flag)){
							change=TRUE;
						}
						uendflag=uendflag->next;
					}
				}
			}
		}
		itemp=itemp->next;
		if(itemp==NULL&&change==TRUE){
			itemp=headofinstruct;
			change=FALSE;
		}
	}
    ////////////end of follow
	Sleep(100);
	////////////select code
	itemp=headofinstruct;
	while(itemp!=NULL){
		flag=itemp->i_s.GetAt(0);
		if(itemp->i_s.GetLength()==3){
			uendflag=Cendflag::getflag(flag)->follow;
			while(uendflag!=NULL){
				itemp->adduendflag(uendflag->flag);
				uendflag=uendflag->next;
			}
		}else{
			for(i=3;i<itemp->i_s.GetLength();i++){
				c=itemp->i_s.GetAt(i);
				if(Cendflag::isaflag(c)==FALSE){
					itemp->adduendflag(c);
					break;
				}else{
					uendflag=Cendflag::getflag(flag)->first;
					while(uendflag!=NULL){
						itemp->adduendflag(uendflag->flag);
						uendflag=uendflag->next;
					}
					if(Cendflag::getflag(c)->isNull==FALSE){
						break;
					}
				}
			}
			if(i==itemp->i_s.GetLength()){
				uendflag=Cendflag::getflag(flag)->follow;
				while(uendflag!=NULL){
					itemp->adduendflag(uendflag->flag);
				    uendflag=uendflag->next;
				}
			}
		}
		itemp=itemp->next;
	}

	///////////end of select
	Sleep(100);
	//////////check ll1


	/////////end check ll1

	return 0;
}

///////////end of my thread


int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
	int nRetCode = 0;

	// initialize MFC and print and error on failure
	if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
	{
		// TODO: change error code to suit your needs
		cerr << _T("Fatal Error: MFC initialization failed") << endl;
		nRetCode = 1;
	}
	else
	{
		// TODO: code your application's behavior here.
		///////////parame
		Cinstruct * headofinstruct=NULL;
		CString instruct;
		CString in;
		Cinstruct * itemp;
		TCHAR ctemp[50];
		CWinThread * thread;
		Cmstack * input=NULL;
		Cmstack * stat=NULL;
		Cuendflag * uendflag;
		int i;
		bool ok=FALSE;
		//////////end of param

		/////////my code 
		cout<<"请输入文法(输入第一个字符为0结束,S为开始符,空字符不输)\n格式：A->abh"<<endl;
		while(TRUE){
			cout<<"推导式  :";
			cin>>ctemp;
			instruct.Format("%s",ctemp);
			if(instruct.GetAt(0)=='0'){
				break;
			}
			////////check the instruct
			if(instruct.GetLength()<3){
				cout<<"input error"<<endl;
				continue;
			}
			if(instruct.GetAt(0)<_T('A')||instruct.GetAt(0)>_T('Z')){
				cout<<"input error"<<endl;
				continue;
			}
			if(instruct.GetAt(1)!=_T('-')||instruct.GetAt(2)!=_T('>')){
				cout<<"input error"<<endl;
				continue;
			}
			//////instruct the instruct
			itemp=new Cinstruct();
			if(headofinstruct==NULL){
				headofinstruct=itemp;
				itemp->next=NULL;
			}else{
				itemp->next=headofinstruct;
				headofinstruct=itemp;
			}
			itemp->i_s=instruct;
		}
		///////////end of while

		///////////new thread
		DWORD c=0;
		thread=AfxBeginThread(deal,headofinstruct);
		cout<<"分析中..";
		GetExitCodeThread(thread->m_hThread,&c);
		while(c==STILL_ACTIVE){
			Sleep(100);
			cout<<'.';
			c=0;
			GetExitCodeThread(thread->m_hThread,&c);
		}

		Cendflag *a;
		//////////check input 
		while(TRUE){
			cout<<endl<<"输入待检测的输入串(形式:aabbcc#):";
		    cin>>ctemp;
			if(ctemp[0]=='#'){
				break;
			}
			in.Format("%s",ctemp);
			for(i=in.GetLength()-1;i>=0;i--){
				if(input==NULL){
					input=new Cmstack(in.GetAt(i));
				}else{
					Cmstack::push(input,in.GetAt(i));
				}
			}
			stat=new Cmstack(_T('#'));
			Cmstack::push(stat,_T('S'));
			while(Cmstack::get(input)!=_T('#')&&Cmstack::get(stat)!=_T('#')){
				ok=FALSE;
				if(Cmstack::get(input)==Cmstack::get(stat)){
					cout<<Cmstack::get(input)<<"匹配成功"<<endl;
					Cmstack::pop(input);
					Cmstack::pop(stat);
					continue;
				}
				if((!Cendflag::isaflag(Cmstack::get(input)))&&(!Cendflag::isaflag(Cmstack::get(stat)))){
					cout<<"无法匹配,不是句型"<<endl;
					break;
				}
				itemp=headofinstruct;
				while(itemp!=NULL){
					if(itemp->i_s.GetAt(0)==Cmstack::get(stat)){
						uendflag=itemp->uendflag;
						while(uendflag!=NULL){
							if(uendflag->flag==Cmstack::get(input)){
								cout<<"用 "<<itemp->i_s.GetBuffer(itemp->i_s.GetLength())<<"  推导"<<endl;
								Cmstack::pop(stat);
								if(itemp->i_s.GetLength()!=3){
									for(i=itemp->i_s.GetLength()-1;i>=3;i--){
										Cmstack::push(stat,itemp->i_s.GetAt(i));
									}
								}
								ok=TRUE;
								break;
							}
							if(ok==TRUE) break;
							uendflag=uendflag->next;
						}
					}
					if(ok==TRUE) break;
					itemp=itemp->next;
				}
				if(itemp==NULL&&ok==FALSE){
					cout<<"无法匹配,不是句型"<<endl;
					break;
				}
			}
			delete input;
			delete stat;
			input=NULL;
			stat=NULL;
		}
        ////////////end of check input
 	}

	return nRetCode;
}