ll1文法dlg.cpp

c++词法分析器。可以分析简单的输入字符串。希望对大家有帮助。

// 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_LastGrammar = _T("");
	m_sentence = _T("");
	m_text2 = _T("");
	m_text1 = _T("");
	m_check1 = FALSE;
	m_check2 = FALSE;
	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_EDIT6, m_con_sign);
	DDX_Control(pDX, IDC_EDIT3, m_Con_sentence);
	DDX_Control(pDX, IDC_LIST6, m_list6);
	DDX_Control(pDX, IDC_LIST5, m_list5);
	DDX_Control(pDX, IDC_LIST4, m_list4);
	DDX_Control(pDX, IDC_LIST3, m_list3);
	DDX_Control(pDX, IDC_LIST2, m_list2);
	DDX_Control(pDX, IDC_LIST1, m_list1);
	DDX_Control(pDX, IDC_EDIT2, m_Con_LastGrammar);
	DDX_Control(pDX, IDC_EDIT1, m_Con_Grammar);
	DDX_Text(pDX, IDC_EDIT1, m_Grammar);
	DDX_Text(pDX, IDC_EDIT2, m_LastGrammar);
	DDX_Text(pDX, IDC_EDIT3, m_sentence);
	DDX_Text(pDX, IDC_EDIT5, m_text2);
	DDX_Text(pDX, IDC_EDIT4, m_text1);
	DDX_Check(pDX, IDC_CHECK1, m_check1);
	DDX_Check(pDX, IDC_CHECK2, m_check2);
	DDX_Text(pDX, IDC_EDIT6, m_sign);
	//}}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)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

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

BOOL CLL1Dlg::OnInitDialog()
{
	CDialog::OnInitDialog();
	CString str;
	str="E->E+T|T\r\nT->T*F|F\r\nF->(E)|i\r\n";
//	str="S->Qc|c\r\nQ->Rb|b\r\nR->Sa|a\r\n";
//	str="S->AB|bC\r\nA->b|ε\r\nB->aD|ε\r\nC->AD|b\r\nD->aS|c\r\n";
//	str="A->ad|Bc\r\nB->aA|bB\r\n";

	m_Con_Grammar.SetWindowText(str);

	str="i*i+i";

	m_Con_sentence.SetWindowText(str);

	// Add "About..." menu item to system menu.
	m_list1.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list1.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list1.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list1.SetTextBkColor(RGB(240,247,233));           //背景颜色

	m_list2.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list2.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list2.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list2.SetTextBkColor(RGB(240,247,233));           //背景颜色

	m_list3.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list3.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list3.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list3.SetTextBkColor(RGB(240,247,233));           //背景颜色

	m_list4.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list4.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list4.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list4.SetTextBkColor(RGB(240,247,233));           //背景颜色

	m_list5.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES|LVS_EX_HEADERDRAGDROP);
    m_list5.SetTextColor(RGB(0,0,255));                  //显示字体的颜色
    m_list5.SetBkColor(RGB(240,247,233));             //选中此列的颜色
    m_list5.SetTextBkColor(RGB(240,247,233));           //背景颜色

	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
		{
			AfxMessageBox("非LL(1)文法~!");
			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);
			if(temp1=="")
			{
				AfxMessageBox("非LL(1)文法~!");
				return(-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);
			if(temp1=="")
			{
				AfxMessageBox("非LL(1)文法~!");
				return(-1);
			}
			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++)
	{
		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()
{
	int i,j;

	m_list1.DeleteAllItems();
	m_list2.DeleteAllItems();
	m_list3.DeleteAllItems();
	m_list4.DeleteAllItems();
	m_list5.DeleteAllItems();
	m_list6.DeleteAllItems();
	for(i=0;i<6;i++)
		for(j=0;j<=20;j++)
		{
			m_list1.DeleteColumn(j);
			m_list2.DeleteColumn(j);
			m_list3.DeleteColumn(j);
			m_list4.DeleteColumn(j);
			m_list5.DeleteColumn(j);			
		}
	
}

void CLL1Dlg::RemoveDirectLeftRecursion()            //消除直接左递归
{
	int i;
	CString str;
	for(i=0;i<Pt.GetLength();i++)
	{
		if(Pt.pleft[i]==Pt.pright[i][0])
		{
			str=Pt.pleft[i];
			Pt.RemoveDirectLeftRecursion(str);
		}
	}
}

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

void CLL1Dlg::RemoveAllLeftRecursion()        //消除文法的一切左递归
{
	int i,j,k;
	int len=VnReverse.GetLength();
	CString ToInstead,BeInstead;
	for(i=0;i<len;i++)
	{
		for(j=0;j<i;j++)
		{
			ToInstead=VnReverse[j];
			BeInstead=VnReverse[i];
			//InsteadOf内参数前项为去取代的非终结符
			//后项为被取代的非终结符
			Pt.InsteadOf(ToInstead,BeInstead);    
		}
		for(k=0;k<Pt.GetLength();k++)
		{
			if(Pt.pleft[k]==VnReverse[i] && Pt.pright[k][0]==VnReverse[i])
			{
				Pt.RemoveDirectLeftRecursion(VnReverse[i]);
				HiddenLeftRecursionExist=true;
			}
		}
	}	

}

bool CLL1Dlg::PickupCommonFactor()
{
	
	int i;
	int length;
	bool Flag,Flagflag,Finish;
	int Count=0;             //设置计数器,避免提取公因子时死循环
	Flagflag=true;
//	Pt.GetInVn(Vn);
	Pt.SetPriority();
	Pt.Sort();
	while(Flagflag)
	{
		Count++;
		if(Count>14 || Pt.NewNonTerminator>='N')
		{
			AfxMessageBox("提取公因子陷入无限循环,提取失败~!");
			CommonFactorExist=-1;
			return(false);
		}
		Flag=false;
		Flagflag=false;
		Finish=true;
		Vn=Pt.GetNewVn();
		while(Finish)
		{
			Finish=false;
			for(i=0;i<Pt.GetLength();i++)                //处理右部以终结符开始的产生式
			{
				if(isupper(Pt.pright[i][0]))
				{
					Pt.InsteadOf(Pt.pright[i][0],Pt.pleft[i]);
					Finish=true;
				}
			}
		}
		for(i=0;i<Vn.GetLength();i++)
		{
			length=Pt.GetNum(Vn[i]);
			Pt.SetPriority();
			Pt.Sort();
			Flag=Pt.PickupCommonFactor(Vn[i],length);
			if(Flag)
			{
				CommonFactorExist=1;
				Flagflag=Flag;
			}
		}	
	}
	return(true);
}

void CLL1Dlg::InitAndConvertPt()     //初始化文法,以及进行消除左递归、提取公因子操作
{

	m_Con_Grammar.GetWindowText(m_Grammar);
	m_Con_sentence.GetWindowText(m_sentence);
	Pt0.Empty();
	HiddenLeftRecursionExist=false;               //假定不存在隐藏左递归
	CommonFactorExist=0;                      //假定没有公因子提取
	m_text1.Empty();
	m_text2.Empty();

	InitPt();                         //录入文法
	Pt=Pt0;                           //ClassPt类拷贝

	VnRefresh(Pt);                    //更新Vn值
	VtRefresh(Pt);                    //更新Vt值
    Pt.GetInVnPrimal(Vn);

	Pt.GetInVn(Vn);                   //拷贝 Vn 进 ClassPt类
	Pt.SetStarter();                  //设置文法开始符号,及其优先级 

	RemoveDirectLeftRecursion();      //消除直接左递归

	PtBuffer=Pt;                      //拷贝Pt到PtBuffer,如果不存在隐藏左递归,则
                                      //还原文法为PtBuffer。避免经过处理后文法太乱
    if(m_check1)
	{
		RemoveAllLeftRecursion();         //消除一切左递归
		Pt.ClearUselessSentence();
		if(HiddenLeftRecursionExist)
		{
			m_text1="存在隐藏左递归,已消除";
			UpdateData(false);
		}
		else
		{
			m_text1="不存在隐藏左递归";
			UpdateData(false);
		}

	}

	if(m_check2)
	{
		PickupCommonFactor();
		Pt.ClearUselessSentence();
		if(CommonFactorExist==1)
			m_text2="存在左公因子,已提取";
		else if(CommonFactorExist==-1)
			m_text2="无法提取公因子";
		else
			m_text2="不存在左公因子";
		UpdateData(false);

	}

 	if(HiddenLeftRecursionExist || CommonFactorExist)      //显示处理后的文法
	{
		SetLastGrammarText(Pt);       //如果存在隐藏左递归则输出Pt文法           
	}
	else
	{
		SetLastGrammarText(PtBuffer); //否则输出PtBuffer文法
		Pt=PtBuffer;
	}
    Pt.SetPriority();
	Pt.Sort();

}

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]);