lexdemoview.cpp

包括一个LR(1)的语法分析程序和一个LL(1)的语法分析程序的例子

// lexDemoView.cpp : implementation of the CLexDemoView class
//

#include "stdafx.h"
#include "lexDemo.h"

#include "lexDemoDoc.h"
#include "lexDemoView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView

IMPLEMENT_DYNCREATE(CLexDemoView, CView)

BEGIN_MESSAGE_MAP(CLexDemoView, CView)
	//{{AFX_MSG_MAP(CLexDemoView)
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	ON_COMMAND(IDM_LL_ONE, OnLlOne)
	ON_COMMAND(IDM_REVERSE_POLAND, OnReversePoland)
	ON_COMMAND(IDM_LR_ZERO, OnLrZero)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView construction/destruction

CLexDemoView::CLexDemoView()
{
	// TODO: add construction code here
  m_analTable = NULL;
}

CLexDemoView::~CLexDemoView()
{
	if (m_analTable != NULL)
		delete []m_analTable;
}

BOOL CLexDemoView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView drawing

void CLexDemoView::OnDraw(CDC* pDC)
{
	CLexDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView printing

BOOL CLexDemoView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CLexDemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CLexDemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView diagnostics

#ifdef _DEBUG
void CLexDemoView::AssertValid() const
{
	CView::AssertValid();
}

void CLexDemoView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CLexDemoDoc* CLexDemoView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CLexDemoDoc)));
	return (CLexDemoDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView message handlers
//功能描述: 打开指定文件，对文件内容进行分析
void CLexDemoView::OnFileOpen() 
{
	
	
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::LexAnal
//功能描述: 打开指定文件，对文件内容进行分析
Status CLexDemoView::LexAnal()
{
	char chInput;
	char * szTop = NULL;
	char * szOut = NULL;
	CString strTop;
	CString strOut;
  CString strVal;
	LElem nextElem = NULL;
	int i = 0;
	Status sRet = OK;
	InitAnalTable();
	InitAnalStack();
	do
	{
		sRet = GetNextInput(chInput);
		if (END_OF_INPUT == sRet)  //输入字符已经读取完毕, 但分析栈仍不为空，出错
		{
			LexUtil::ErrMsg("error: end of Input while analStack is not empty");	
			break;
		}
		sRet = m_analStack.Top(strTop);
		if (IsTerminals(strTop))  //判断分析栈栈顶元素是否为终结符
		{
			if (strTop[0] == chInput)   //如果栈顶的终结符与输入的字符相同的话，则出栈否则报错
			{
				m_analStack.Pop(strOut);
			}
			else
			{
				LexUtil::ErrMsg("Parse error");
				break;
			}
		}
		else										//分析栈栈顶元素不是终结符的话
		{
			nextElem = FindNextState((LPTSTR)(LPCTSTR)strTop, chInput);
			if (nextElem != NULL)
			{
				strVal.Format("%d:%s---", i++, nextElem->replace);
				if (P == nextElem->nextStep)
				{
					strVal.Insert(strVal.GetLength(), "P");
				}
				else if (N == nextElem->nextStep)
				{
					strVal.Insert(strVal.GetLength(), "N");
				}
				else if (ACC == nextElem->nextStep)
				{
					strVal.Insert(strVal.GetLength(), "ACC");
				}
				m_analStack.Pop(strOut);
				SplitPush(nextElem->replace);
				if (P ==nextElem->nextStep)   //如果下一动作是P的话
				{
					UnGetInput();
				}	
			}
			else
			{
				CString strMsg;
				strMsg.Format("%s: %c", strTop, chInput);
				LexUtil::ErrMsg(strMsg);
				LexUtil::ErrMsg("在分析表中没有匹配动作序列");
				break;
			}
		}
		m_lstToken.AddString(strVal);
		AddToListForLL(m_analStack);
	} while (!m_analStack.IsEmpty());
	return OK;
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::InitAnalTable
//功能描述: 构造LL(1)语法分析表
//分析表的来源:教材159页的练习题6.6中的文法所对应的分析表
//这个表与教材134页的表6-6中的分析表比很相象，只不过增加了
//  对 *, /的支持
Status CLexDemoView::InitAnalTable()
{
	if (NULL != m_analTable)
    return OK;
  
  m_analTable = new Elem[TABLE_LENGTH];
  if (NULL == m_analTable)
		return FAIL;
  
  strcpy(m_analTable[0].notTerminals, "E");
	m_analTable[0].terminal = '(';
	strcpy(m_analTable[0].replace, "E1T");
	m_analTable[0].nextStep = P;

	strcpy(m_analTable[1].notTerminals, "E");
	m_analTable[1].terminal = 'i';
	strcpy(m_analTable[1].replace, "E1T");
	m_analTable[1].nextStep = P;

	strcpy(m_analTable[2].notTerminals, "E1");
	m_analTable[2].terminal = '+';
	strcpy(m_analTable[2].replace, "E1T");
	m_analTable[2].nextStep = N;

	strcpy(m_analTable[3].notTerminals, "E1");
	m_analTable[3].terminal = '-';
	strcpy(m_analTable[3].replace, "E1T");
	m_analTable[3].nextStep = N;
	
	strcpy(m_analTable[4].notTerminals, "E1");
	m_analTable[4].terminal = ')';
	strcpy(m_analTable[4].replace, "e");   //e means empty
	m_analTable[4].nextStep = P;

	strcpy(m_analTable[5].notTerminals, "E1");
	m_analTable[5].terminal = '#';
	strcpy(m_analTable[5].replace, "e");   //e means empty
	m_analTable[5].nextStep = P;

	strcpy(m_analTable[6].notTerminals, "T");
	m_analTable[6].terminal = '(';
	strcpy(m_analTable[6].replace, "T1F"); 
	m_analTable[6].nextStep = P;

	strcpy(m_analTable[7].notTerminals, "T");
	m_analTable[7].terminal = 'i';
	strcpy(m_analTable[7].replace, "T1F"); 
	m_analTable[7].nextStep = P;

	strcpy(m_analTable[8].notTerminals, "T1");
	m_analTable[8].terminal = '+';
	strcpy(m_analTable[8].replace, "e"); 
	m_analTable[8].nextStep = P;

	strcpy(m_analTable[9].notTerminals, "T1");
	m_analTable[9].terminal = '-';
	strcpy(m_analTable[9].replace, "e"); 
	m_analTable[9].nextStep = P;

	strcpy(m_analTable[10].notTerminals, "T1");
	m_analTable[10].terminal = '*';
	strcpy(m_analTable[10].replace, "T1F"); 
	m_analTable[10].nextStep = N;  

	strcpy(m_analTable[11].notTerminals, "T1");
	m_analTable[11].terminal = '/';
	strcpy(m_analTable[11].replace, "T1F"); 
	m_analTable[11].nextStep = N;  

	strcpy(m_analTable[12].notTerminals, "T1");
	m_analTable[12].terminal = ')';
	strcpy(m_analTable[12].replace, "e"); 
	m_analTable[12].nextStep = P;  

	strcpy(m_analTable[13].notTerminals, "T1");
	m_analTable[13].terminal = '#';
	strcpy(m_analTable[13].replace, "e"); 
	m_analTable[13].nextStep = P;  

	strcpy(m_analTable[14].notTerminals, "F");
	m_analTable[14].terminal = '(';
	strcpy(m_analTable[14].replace, "F1P"); 
	m_analTable[14].nextStep = P;  

	strcpy(m_analTable[15].notTerminals, "F");
	m_analTable[15].terminal = 'i';
	strcpy(m_analTable[15].replace, "F1P"); 
	m_analTable[15].nextStep = P;  

	strcpy(m_analTable[16].notTerminals, "F1");
	m_analTable[16].terminal = '+';
	strcpy(m_analTable[16].replace, "e"); 
	m_analTable[16].nextStep = P;  

	strcpy(m_analTable[17].notTerminals, "F1");
	m_analTable[17].terminal = '-';
	strcpy(m_analTable[17].replace, "e"); 
	m_analTable[17].nextStep = P;  

	strcpy(m_analTable[18].notTerminals, "F1");
	m_analTable[18].terminal = '*';
	strcpy(m_analTable[18].replace, "e"); 
	m_analTable[18].nextStep = P;  

	strcpy(m_analTable[19].notTerminals, "F1");
	m_analTable[19].terminal = '/';
	strcpy(m_analTable[19].replace, "e"); 
	m_analTable[19].nextStep = P;  

	strcpy(m_analTable[20].notTerminals, "F1");
	m_analTable[20].terminal = ')';
	strcpy(m_analTable[20].replace, "e"); 
	m_analTable[20].nextStep = P;  

	strcpy(m_analTable[21].notTerminals, "F1");
	m_analTable[21].terminal = '#';
	strcpy(m_analTable[21].replace, "e"); 
	m_analTable[21].nextStep = P;  

	strcpy(m_analTable[22].notTerminals, "P");
	m_analTable[22].terminal = '(';
	strcpy(m_analTable[22].replace, ")E"); 
	m_analTable[22].nextStep = N;  	

	strcpy(m_analTable[23].notTerminals, "P");
	m_analTable[23].terminal = 'i';
	strcpy(m_analTable[23].replace, "e"); 
	m_analTable[23].nextStep = N;  	

	strcpy(m_analTable[24].notTerminals, ")");
	m_analTable[24].terminal = ')';
	strcpy(m_analTable[24].replace, "e"); 
	m_analTable[24].nextStep = N;  	

	strcpy(m_analTable[25].notTerminals, "+");
	m_analTable[25].terminal = '+';
	strcpy(m_analTable[25].replace, "e"); 
	m_analTable[25].nextStep = ACC;  	

	strcpy(m_analTable[25].notTerminals, "#");
	m_analTable[25].terminal = '#';
	strcpy(m_analTable[25].replace, "e"); 
	m_analTable[25].nextStep = ACC;  	

	return OK;
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::InitAnalStack
//功能描述: 构造语法分析栈  
Status CLexDemoView::InitAnalStack()
{
  //m_analStack.InitStack(40);
	m_analStack.Push("#");
	m_analStack.Push("E");
	return OK;
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::GetNextInput()
//功能描述: 获得下一个输入流中的字符
Status CLexDemoView::GetNextInput(char& valOut)
{
	if (m_szInput[m_lInputPos] != '\0')
	{
		valOut = m_szInput[m_lInputPos++];
		return OK;
	}
	else
	{
		return END_OF_INPUT;
	}
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::UnGetInput
//功能描述: 回退输入流指针到前一个字符
Status CLexDemoView::UnGetInput()
{
	if (m_lInputPos <= 0)
	{
		return BEGINNING_OF_INPUT;
	}
	else
	{
		m_lInputPos--;
		return OK;
	}
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::IsTerminals
//功能描述:判断参数字符串是否为终结符元素  
bool CLexDemoView::IsTerminals(CString strVal)
{
	if (!strcmp(strVal, "i"))
	{
		return true;
	} 
	if (!strcmp(strVal, "("))
	{
		return true;
	}
	if (!strcmp(strVal, "+"))
	{
		return true;
	}
	if (!strcmp(strVal, "-"))
	{
		return true;
	}
	if (!strcmp(strVal, "*"))
	{
		return true;
	}
	if (!strcmp(strVal, "/"))
	{
		return true;
	}
	if (!strcmp(strVal, ")"))
	{
		return true;
	}
	return false;
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::FindNextState
//功能描述:根据当前栈顶元素和输入元素查分析表取得下一个状态动作
LElem CLexDemoView::FindNextState(char * szTop, char chInput)
{
	for (int i = 0; i < TABLE_LENGTH; i++)
	{
		if(!strcmp(m_analTable[i].notTerminals, szTop) && m_analTable[i].terminal == chInput)  //换到匹配的状态动作的话
		{
			return &m_analTable[i];
		}
	}
	return NULL;
}

/////////////////////////////////////////////////////////////////////////////
// CLexDemoView::Splitpush
//功能描述:
Status CLexDemoView::SplitPush(char * szVal)
{
	char szIn[3];
	if (strlen(szVal) > 2)
	{
		szIn[0] = szVal[0];
		szIn[1] = szVal[1];
		szIn[2] = '\0';
		m_analStack.Push(szIn);
		szIn[0] = szVal[2];
		szIn[1] = '\0';
		m_analStack.Push(szIn);
	}
	else
	{
		if (strcmp(szVal, "e"))
		{
			strcpy(szIn, szVal);
			m_analStack.Push(szIn);
		}
	}
	return OK;
}

//功能描述:模拟LL(1)语法分析方法  
//分析的字符串：i*i-i/i
void CLexDemoView::OnLlOne() 
{
	InitListBox();
	m_lstResult.AddString("分析栈");
	m_lstToken.AddString("分析动作");
	strcpy(m_szInput, "i*i-i/i#");
	m_lInputPos = 0;
	LexAnal();
}

//功能描述:模拟逆波兰转换过程
void CLexDemoView::OnReversePoland() 
{
	CString strSrc, strDst, strAsmOut;
	Status sRet = OK;
	strSrc = "(a+b)*c-d/2";
	//进行逆波兰转换
	sRet = PolandRConvert(strSrc, strDst);
  //根据逆波兰式生成asm Code	
	MakeAsmCode(strDst, strAsmOut);   
	AfxMessageBox(strAsmOut);
}


//功能描述:逆波兰转换
//@arg: CString strSrc
//@arg: CString& strDst
//@return:Status
Status CLexDemoView::PolandRConvert(CString strSrc, CString& strDst)
{
	Status sRet = OK;
	int i = 0;
	int nPRI = 0;  //运算符优先级
	int length = strSrc.GetLength();
	char chInput;
	char chTop;
	char chOut;
  Stack<char> stack;
  while(i < length)
	{
		chInput = strSrc.GetAt(i);
		//如果是操作数的话.直接输出
		if (IsOperand(chInput) && chInput != '(' && chInput != ')' )  
		{
			strDst.Insert(strDst.GetLength(), chInput);
		}
		else
		{
			//当前字符是运算符的话
			if (IsOperator(chInput))
			{
				//如果运算符栈为空的话,直接将运算符入栈
				if (stack.IsEmpty())
				{
					stack.Push(chInput);
				}
				//如果运算符栈不为空的话，就需要比较栈顶运算符与当前输入运算符的优先级
				else 
				{
					nPRI = GetPRI(chInput);
					do
					{
						sRet = stack.Top(chTop);
						//如果当前运算符优先级>栈顶运算符优先级的话.入栈,退出循环
						if (nPRI > GetPRI(chTop) || STACK_EMPTY == sRet )
						{
							stack.Push(chInput);
							break;
						}
						//如果当前运算符优先级<=栈顶运算符优先级的话.栈顶运算符出栈，进输出流,继续循环
						else
						{
							stack.Pop(chOut);
							strDst.Insert(strDst.GetLength(), chOut);
						}
					}	while (1);
				}
			} //end of if (IsOperator(chInput))
			//当前字符是左括号的话
			else if ('(' == chInput) 
			{
				stack.Push(chInput);
			}
			//当前字符是右括号的话