ll1文法dlg.cpp

确定的自顶向下方法

// LL1文法Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "LL1文法.h"
#include "LL1文法Dlg.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

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

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

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

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

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLL1Dlg dialog

CLL1Dlg::CLL1Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(CLL1Dlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CLL1Dlg)
	m_Grammar = _T("");
	m_sentence = _T("");
	m_sign = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CLL1Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CLL1Dlg)
	DDX_Control(pDX, IDC_EDIT3, m_Con_sentence);
	DDX_Control(pDX, IDC_LIST6, m_list6);
	DDX_Control(pDX, IDC_EDIT1, m_Con_Grammar);
	DDX_Text(pDX, IDC_EDIT1, m_Grammar);
	DDX_Text(pDX, IDC_EDIT3, m_sentence);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CLL1Dlg, CDialog)
	//{{AFX_MSG_MAP(CLL1Dlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDOK, OnBianyi)
	ON_BN_CLICKED(IDC_BUTTON1, OnOpen)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLL1Dlg message handlers

BOOL CLL1Dlg::OnInitDialog()
{
	CDialog::OnInitDialog();
	CString str;
	str="S->aH\r\nH->aMd|d\r\nM->Ab|ε\r\nA->aM|e\n";
	m_Con_Grammar.SetWindowText(str);
	str="aaabd";
	m_Con_sentence.SetWindowText(str);
	// Add "About..." menu item to system menu.
	m_list6.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list6.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list6.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list6.SetTextBkColor(RGB(240,247,233));           //背景颜色
	m_list6.InsertColumn(0,"步骤");
	m_list6.InsertColumn(1,"符号栈");
	m_list6.InsertColumn(2,"输入串",LVCFMT_RIGHT);
	m_list6.InsertColumn(3,"所用产生式");
	m_list6.SetColumnWidth(0,40);
	m_list6.SetColumnWidth(1,100);
	m_list6.SetColumnWidth(2,100);
	m_list6.SetColumnWidth(3,80);
	// IDM_ABOUTBOX must be in the system command range.
	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);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

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

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CLL1Dlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		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;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CLL1Dlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}
int CLL1Dlg::InitPt()
{
	int i;
	int spacepos=0;
	int retpos=0;
	int retflag;
	int pos;
	i=0;
	CString s;
	CString temp1;
	CString temp2;
	CString ret;
	s.Empty();
	temp1.Empty();
	temp2.Empty();
	ret.Empty();
	s=m_Grammar+"\r\n";
	while(1)                   //删除文法之前的字符
	{
		if(s!="")
		{
			if(!isupper(s[0]))
				s.Delete(0,1);
			else break;
		}
		else
		{
			return(-1);
		}
			
	}

	while(1)                   //删除文法前中后的空格符
	{
		spacepos=s.Find(" ");
		if(spacepos==-1)
			break;
		s.Delete(spacepos,1);
	}

	spacepos=0;
	retflag=0;
	while(1)                   //删除文法前中后多余回车符
	{
		ret.Empty();
		retpos=s.Find("\r\n",retflag);
		if(retpos==-1)
			break;
		if(retpos<=s.GetLength()-3)
		{
			ret+=s[retpos+2];
			ret+=s[retpos+3];
		}
		if(ret=="\r\n")
		{
			s.Delete(retpos,2);
			retflag=retpos;
		}
		else retflag=retpos+1;
	}
////////////////
	m_Grammar=s;
	UpdateData(false);

	while(s.Find("\r\n")!=-1)          //利用文法生成Pt
	{								   //每条将文法的左部存在Pt.pleft(char)	
		pos=s.Find("->");              //右部存入Pt.pright(CString)
        temp1=s.Left(pos);
		s.Delete(0,pos+2);
		while(s.Find("\r\n") > s.Find("|") && s.Find("|") != -1)
		{
			pos=s.Find("|");
			temp2=s.Left(pos);
			s.Delete(0,pos+1);

			Pt0.RecordApp(temp1[0],temp2);
			i++;
		}
		if(s.Find("\r\n")!=-1)
		{
			pos=s.Find("\r\n");
			temp2=s.Left(pos);
			s.Delete(0,pos+2);
			Pt0.RecordApp(temp1[0],temp2);
			i++;
		}
	}
	return(0);
}

void CLL1Dlg::VnRefresh(ClassPt Ptt)      //得到文法Ptt的非终结符集
{
	Vn.Empty();
	int i;
	int length=Ptt.GetLength();
	for(i=0;i<length;i++)
	{
		if(Vn.Find(Ptt.pleft[i])==-1)
			Vn+=Ptt.pleft[i];
	}
	GetVnReverse();
	

}

void CLL1Dlg::GetVnReverse()            //得到Vn的倒排序
{
	int i;
	int len=Vn.GetLength();
	VnReverse.Empty();
	for(i=len-1;i>=0;i--)
		VnReverse+=Vn[i];
}

void CLL1Dlg::VtRefresh(ClassPt Ptt)      //得到文法Ptt的终结符集
{
	Vt.Empty();
	bool Flag;
	int i,j;
	int length=Ptt.GetLength();
	CString str;
	for(i=0;i<length;i++)
		for(j=0;j<Ptt.pright[i].GetLength();j++)
			if(Vt.Find(Ptt.pright[i][j])==-1 && Vn.Find(Ptt.pright[i][j])==-1)
				Vt+=Ptt.pright[i][j];
	Flag=false;
	for(i=0;i<Vt.GetLength()-1;i++)//删除终结符集中ε及其以后的空,如果有删除过，Flag置true
	{
		str.Empty();
		str+=Vt[i];
		str+=Vt[i+1];
		if(str=="ε")
		{
			Vt.Delete(i,2);
			i-=2;
			Flag=true;
		}
	}
	if(Flag)
		Vt+="ε";		
}

void CLL1Dlg::InitArray()             //初始化数组
{
	int i,j;
	for(i=0;i<20;i++)
		N[i]=9;                         // 9 代表未处理
	for(i=0;i<20;i++)
		for(j=0;j<20;j++)
		{
			First[i][j]=false;
			Follow[i][j]=false;
			Fs[i][j]=false;
			Select[i][j]=false;
			Analyze[i][j].Empty();
		}
	for(i=0;i<50;i++)
		for(j=0;j<50;j++)
			Output[i][j].Empty();
	
}

void CLL1Dlg::InitListControl()
{

	m_list6.DeleteAllItems();	
}

void CLL1Dlg::SetLastGrammarText(ClassPt Ptt)          //显示处理后的文法
{
	int i;
	CString str;
	str.Empty();
	Ptt.SetPriority();
	Ptt.Sort();
	for(i=0;i<Ptt.GetLength();i++)
	{
		str+=Ptt.pleft[i]+"->"+Ptt.pright[i]+"\r\n";		
	}
}


void CLL1Dlg::InitAndConvertPt()     //初始化文法
{
	m_Con_Grammar.GetWindowText(m_Grammar);
	m_Con_sentence.GetWindowText(m_sentence);
	Pt0.Empty();
	InitPt();                         //录入文法
	Pt=Pt0;                           //ClassPt类拷贝
	VnRefresh(Pt);                    //更新Vn值
	VtRefresh(Pt);                    //更新Vt值
    Pt.GetInVnPrimal(Vn);
	Pt.GetInVn(Vn);                   //拷贝 Vn 进 ClassPt类
	Pt.SetStarter();                  //设置文法开始符号,及其优先级 

}

void CLL1Dlg::Create_N_Table()
{
	ClassPt Ptt=Pt;
	int i,j;
	int pos;
	int num;
	CString buffer;
//////////////////////////////////////////////////////////////////////////////////////
//删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则
//将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出ε。
//////////////////////////////////////////////////////////////////////////////////////
	for(i=0;i<Ptt.GetLength();i++)
	{
		for(j=0;j<Ptt.pright[i].GetLength();j++)
		{
			if(Vt.Find(Ptt.pright[i][j])!=-1)				
			{
				buffer=Ptt.pleft[i];
				Ptt.RecordDel(Ptt.pleft[i],Ptt.pright[i]);
				if(Ptt.RecordFind(buffer)==false)
				{
					pos=Vn.Find(buffer);
					N[pos]=0;
				}
				i--;
			}
			break;
		}
	}
/////////////////////////////////////////////////////////////////////////////////////
//若某一非终结符的某一产生式右部为ε，则将数组中对应该非终结符的标志置为"是"，并从文法
//中删除该非终结符的所有产生式。
/////////////////////////////////////////////////////////////////////////////////////
	for(i=0;i<Ptt.GetLength();i++)
	{
		if(Ptt.pright[i]=="ε")
		{
			buffer=Ptt.pleft[i];
			num=Ptt.RecordDel(Ptt.pleft[i]);
			i-=num;
			pos=Vn.Find(buffer);
			N[pos]=1;
		}
	}
//////////////////////////////////////////////////////////////////////////////////////
//扫描产生式右部的每一符号。
////若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为
////空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产
////生式。
////若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终
/////结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。
//重复，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。
//////////////////////////////////////////////////////////////////////////////////////
while(Ptt.GetLength()!=0)
{
	for(i=0;i<Ptt.GetLength();i++)
	{
		for(j=0;j<Ptt.pright[i].GetLength();j++)
		{
			pos=Vn.Find(Ptt.pright[i][j]);
			if(N[pos]==1)
			{
				Ptt.pright[i].Delete(j,1);
				j--;
			}
		}
		if(Ptt.pright[i].IsEmpty())
		{
			pos=Vn.Find(Ptt.pleft[i]);
			N[pos]=1;
			Ptt.RecordDel(Ptt.pleft[i]);
		}
	}
	buffer.Empty();
	buffer="SWB";
	for(i=0;i<Ptt.GetLength();i++)
	{
		for(j=0;j<Ptt.pright[i].GetLength();j++)
		{
			pos=Vn.Find(Ptt.pright[i][j]);
			if(N[pos]==0)
			{
				buffer=Ptt.pleft[i];
				Ptt.RecordDel(Ptt.pleft[i],Ptt.pright[i]);