lexdemoview.cpp

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

			else if (')' == chInput)
			{
				do
				{
					//运算符栈中无匹配的'('的话，报错返回
					if (stack.IsEmpty())
					{
						sRet = FAIL;
						return sRet;
					}
					stack.Pop(chOut);
					//运算符栈顶是'('的话，退出循环
					if ('(' == chOut)
					{
						break;
					}
					else
					{
						strDst.Insert(strDst.GetLength(), chOut);
					}
				}	while (1);
			}
		}
		i++;
	} //end of while(i < length)
	while (!stack.IsEmpty())
	{
		stack.Pop(chOut);
		//如果栈顶是')'的话，报错退出
		if (')' == chOut)
		{
			sRet = FAIL;
			break;
		}
		else
		{
			strDst.Insert(strDst.GetLength(), chOut);
		}
	}
	return sRet;
}

//功能描述:判断字符是否是操作数
//@arg:char chVal
//@return:bool
bool CLexDemoView::IsOperand(char chVal)
{
	return !IsOperator(chVal);
}

//功能描述:判断字符是否是操作符
//@arg:char chVal
//@return: bool
bool CLexDemoView::IsOperator(char chVal)
{
	if ('+' == chVal || '-' == chVal || '*' == chVal
		|| '/' == chVal)
		return true;
	else 
		return false;
}

//功能描述:获得运算符的优先级(PRI==Privilege)
//@arg:char chVal
//@return:int 
int  CLexDemoView::GetPRI(char chVal)
{
	int nPRI = 0;
	switch(chVal)
	{
	case '+':
	case '-':
		nPRI = 3;
		break;
	case '*':
	case '/':
		nPRI = 4;
		break;
	case '(':
	case ')':
		nPRI = 0;
		break;
	}
	return nPRI;
}

//功能描述:根据逆逆波兰式生成汇编码
//@arg:CString strDst
//@arg:CString& strOut
//@return Status
Status CLexDemoView::MakeAsmCode(CString strDst, CString& strOut)
{
	Status  sRet = OK;     //返回值
	Stack<char> stack; //工作栈  
	CString strOpCode;    //asm  code
	CString strErrMsg;    //出错信息
	int i = 0;
	char chNow;						//当前操作字符
  char chOperand1, chOperand2;  //操作数1,操作数2,用于协助构成汇编指令
	char tmp[2];
	int length = strDst.GetLength();  //逆波兰式长度
	LPTSTR  lpszAsmCode = strOut.GetBuffer(ASM_CODE_LENGTH);
	*lpszAsmCode = '\0';
	if (NULL == lpszAsmCode)
	{
		strErrMsg.Format("File:%d,Line:%d:getBuffer from CString Failed\n", __FILE__, __LINE__);
		LexUtil::ErrMsg(strErrMsg);
		return FAIL;
	}
	while (i < length)
	{
		chNow = strDst.GetAt(i);
		//如果当前字符是操作数的话
		if (IsOperator(chNow))
		{
			//注意出栈的顺序与栈的结构有关
			stack.Pop(chOperand2);
			stack.Pop(chOperand1);
			//获得相应操作符对应的汇编指令
			sRet = GetOpCode(chNow, strOpCode);
			//该操作符无对应的汇编码支持的话,报错，返回
			if (sRet != OK)
			{
				strErrMsg.Format("操作符%c无对应的汇编码\n", chNow);
				LexUtil::ErrMsg(strErrMsg);
				return sRet;
			}
			tmp[0] = chOperand1;
			tmp[1] = '\0';
			
			//如果Operand1不是Ax(T)的话,构成Mov Ax, Operand1指令
			if (chOperand1  != 'T')
			{
				strcat(lpszAsmCode, "Mov AX,");
				strcat(lpszAsmCode, tmp);
				strcat(lpszAsmCode, "\n");
			}
			//构成OP AX, Operand2指令
			strcat(lpszAsmCode, strOpCode);
			strcat(lpszAsmCode, " AX,");
			tmp[0] = chOperand2;
			strcat(lpszAsmCode, tmp);
			strcat(lpszAsmCode, "\n");
			//将AX以T的名称入栈  			
			stack.Push('T');
		}
		//如果当前字符是操作符的话
		else
		{
			stack.Push(chNow);
		}
		i++;
	}
	strOut.ReleaseBuffer(-1);
	return sRet;
}


//功能描述:根据相应的操作符获得对应的asm code
//@arg:char chOp
//@arg:CString& strCode
//@return:Status
Status CLexDemoView::GetOpCode(char chOp, CString& strCode)
{
	Status sRet = OK;
	switch (chOp)
	{
	case '+':
		strCode = "Add";
		break;
	case '-':
		strCode = "Sub";
		break;
	case '*':
		strCode = "Mul";
		break;
	case '/':
		strCode = "Div";
		break;
	default:
		sRet = FAIL;
	}
	return sRet;
}

//功能描述:进行LR(0)语法分析
//被分析的字符串:a,b,a#
void CLexDemoView::OnLrZero() 
{
	Stack<CString> statusStack; //状态栈
	Stack<CString> symbolStack; //文法符号栈
	LRElem  actionTable[12];		//action分析表
  Regulation regTable[5];			//规则表
	ElemGoto gotoTable[4];			//Goto分析表
	Status sRet;								//操作状态返回值
	CString statusTop;					//栈顶的状态字符串
	CString statusPush;					//用于在移进分析栈时入栈的状态
	CString strErrMsg;					//错误消息信息
	CString strVal;							//用于向ListBox中Insert元素
	LRElem  lrElem;							//用来返回action分析表中的元素
  long lLen = 0;
	int  nStep = 0;							//用于指示分析动作是第几步
	char input[] = "a,b,a#";			//输入串
	char chInput;
	//初始化ListBox
	InitListBox(); 
	m_lstResult.AddString("状态栈");
	m_lstToken.AddString("符号栈");
	//初始化LR(0)的状态栈
	InitStatusStack(statusStack);
	//初始化符号栈
	InitSymbolStack(symbolStack);
	//初始化LR(0)的分析表
	InitLRTable(actionTable, gotoTable);
	//初始化LR(0)的规则表
	InitRegTable(regTable);
	//初始化输入流位置为0
  m_lInputPos = 0; 
	lLen = strlen(input);
	//如果输入未处理完的话
	while (m_lInputPos < lLen) 
	{
		chInput = input[m_lInputPos];	
		sRet = statusStack.Top(statusTop);
		//在Action表中查找对应元素
		lrElem = LookInActionTable(actionTable, statusTop, chInput);
		//如果在Action表中没有找到对应元素的话
		if (NOT_SUPPORT == lrElem.type)
		{
			strErrMsg.Format("在action表中未找到相应动作---%s:%c", statusTop, chInput);
			LexUtil::ErrMsg(strErrMsg);
			return;
		}
		//如果是移进动作的话,新状态入栈,输入符号入符号栈并移动输入流指针到下一个字符处
		else if (MOVE_IN == lrElem.type)
		{
			statusPush.Format("S%d", lrElem.nNum);
			statusStack.Push(statusPush);
			statusPush.Format("%c", chInput);
			symbolStack.Push(statusPush);
			m_lInputPos++;
		}
		//如果是归约动作的话,则查归约规则表，将该规则左部的符号入符号栈，将查goto表，将查得的状态入分析栈
		else if (DEDUCE == lrElem.type)
		{
			int nRGLen = 0;  //规则右部的长度
			int i = 0;
			CString strOut;
			CString symbolTop;
			ElemGoto elemGoto;
			//获得需要采用的规则右部的长度
			nRGLen = regTable[lrElem.nNum].right.GetLength();
			//分析栈退出相应个数的元素
			while (i < nRGLen)
			{
				statusStack.Pop(strOut);
				i++;
			}
		  i = 0;
			//符号栈退出相应个数的元素
			while (i < nRGLen)
			{
				symbolStack.Pop(strOut);
				i++;
			}
			//将规则左部的文法符号入符号栈
			symbolStack.Push(regTable[lrElem.nNum].left);
			statusStack.Top(statusTop);
			symbolStack.Top(symbolTop);
			//根据新的分析栈顶状态和符号栈栈顶称号查goto表找到下一状态入栈
			elemGoto = LookInGotoTable(gotoTable, statusTop, symbolTop);
			//如果在goto表中未找到对应项的话，就报错退出
			if (elemGoto.statusNext.GetLength() <= 0)
			{
				strErrMsg.Format("在goto表中找不到对应元素--%s:%s", statusTop, symbolTop);
				LexUtil::ErrMsg(strErrMsg);
				return;
			}
			statusStack.Push(elemGoto.statusNext);
		}
		//如果分析已经结束的话
		else if (ACC == lrElem.type)
		{
			break;
		}
    //将本步的分析结果加入ListBox中
		strVal.Format("%d:", nStep);
		statusStack.Top(statusTop);
		strVal.Insert(strVal.GetLength(), statusTop);
		symbolStack.Top(statusTop);
		strVal.Insert(strVal.GetLength(), statusTop);
		//m_lstResult.AddString(strVal);
		AddToListForLR(statusStack, symbolStack);  //为LR(0)方法向m_lstResult和m_lstToken中添加分析过程的中间结果
		
		nStep++;
	} //end of while (m_lInputPos < lLen) 
}

//功能描述:初始化(LR0)分析栈
//@arg:Stack<CString> &statusStack
//@return:Status
Status CLexDemoView::InitStatusStack(Stack<CString> &statusStack)
{
	Status sRet = OK;
	//初始化stack,设置栈的尺寸
	//statusStack.InitStack(STACK_SIZE);
	statusStack.Push("S0");
	return sRet;
}

//功能描述:初始化(LRO)符号栈
//@arg:Stack<CString> &symbolStack
//@return:Status
Status CLexDemoView::InitSymbolStack(Stack<CString> &symbolStack)
{
	Status sRet = OK;
	//初始化stack,设置栈的尺寸
	//symbolStack.InitStack(STACK_SIZE);
	symbolStack.Push("#");
	return sRet;
}

//功能描述:初始化LR(0)的分析表
//@arg:LRElem actionTable[]
//@arg:ElemGoto gotoTable[])
//@return:Status
Status CLexDemoView::InitLRTable(LRElem actionTable[], ElemGoto gotoTable[])
{
	Status sRet = OK;
  //初始化action表
	//分析表的来源:教材199页的表8-3的分析表
	actionTable[0].statusPrev = "S0";
	actionTable[0].chInput = 'a';
	actionTable[0].type = MOVE_IN;
	actionTable[0].nNum = 3;
	actionTable[1].statusPrev = "S0";
	actionTable[1].chInput = 'b';
	actionTable[1].type = MOVE_IN;
	actionTable[1].nNum = 4;
	actionTable[2].statusPrev = "S1";
	actionTable[2].chInput = '#';
	actionTable[2].type = ACC;
	actionTable[2].nNum = 0;
	actionTable[3].statusPrev = "S2";
	actionTable[3].chInput = ',';
	actionTable[3].type = MOVE_IN;
	actionTable[3].nNum = 5;
	actionTable[4].statusPrev = "S2";
	actionTable[4].chInput = '#';
	actionTable[4].type = DEDUCE;
	actionTable[4].nNum = 2;
	actionTable[5].statusPrev = "S3";
	actionTable[5].chInput = ',';
	actionTable[5].type = DEDUCE;
	actionTable[5].nNum = 3;
	actionTable[6].statusPrev = "S3";
	actionTable[6].chInput = '#';
	actionTable[6].type = DEDUCE;
	actionTable[6].nNum = 3;
	actionTable[7].statusPrev = "S4";
	actionTable[7].chInput = ',';
	actionTable[7].type = DEDUCE;
	actionTable[7].nNum = 4;
	actionTable[8].statusPrev = "S4";
	actionTable[8].chInput = '#';
	actionTable[8].type = DEDUCE;
	actionTable[8].nNum = 4;
	actionTable[9].statusPrev = "S5";
	actionTable[9].chInput = 'a';
	actionTable[9].type = MOVE_IN;
	actionTable[9].nNum = 3;
	actionTable[10].statusPrev = "S5";
	actionTable[10].chInput = 'b';
	actionTable[10].type = MOVE_IN;
	actionTable[10].nNum = 4;
	actionTable[11].statusPrev = "S6";
	actionTable[11].chInput = '#';
	actionTable[11].type = DEDUCE;
	actionTable[11].nNum = 1;
	//初始化Goto表
	gotoTable[0].statusPrev = "S0";
	gotoTable[0].statusNext = "S1";
	gotoTable[0].symbol = "L";
	gotoTable[1].statusPrev = "S0";
	gotoTable[1].statusNext = "S2";
	gotoTable[1].symbol = "E";
	gotoTable[2].statusPrev = "S5";
	gotoTable[2].statusNext = "S6";
	gotoTable[2].symbol = "L";
	gotoTable[3].statusPrev = "S5";
	gotoTable[3].statusNext = "S2";
	gotoTable[3].symbol = "E";
	return sRet;
}

//功能描述:初始化LR(0)的规则表
//@arg:Regulation regTable[]
//@return:Status
Status CLexDemoView::InitRegTable(Regulation regTable[])
{
	Status sRet = OK;
	//初始化LR(0)文法规则表
	//注意，为了与分析表统一，规则是从1开始计数的，所以第一个元素为空
	regTable[0].left = "";
	regTable[0].right = "";
  regTable[1].left = "L";
	regTable[1].right = "E,L";
  regTable[2].left = "L";
	regTable[2].right = "E";
  regTable[3].left = "E";
	regTable[3].right = "a";
  regTable[4].left = "E";
	regTable[4].right = "b";
	return sRet;
}

//功能描述:根据给定的分析表查询LR(0)的action表获得下一步的动作
//@arg: LRElem actionTable[]
//@arg: CString statusTop
//@arg: char chInput
//@return:LRElem
LRElem CLexDemoView::LookInActionTable(LRElem actionTable[], CString statusTop, char chInput)
{
	//long lTableSize = sizeof(actionTable)/sizeof(LRElem);
  long lTableSize = 12;
	for (int i = 0; i < lTableSize; i++)
	{
		//找到匹配元素的话
		if (!actionTable[i].statusPrev.Compare(statusTop) && chInput == actionTable[i].chInput)
		{
			return actionTable[i];
		}
	}
	//如果在actinTable中未找到相应元素的话就返回一个NOT_SUPPORT的信息
  LRElem elemRet;  
	elemRet.type = NOT_SUPPORT;
	return elemRet;
}

//功能描述:根据给定的goto表查询LR(0)的action表获得下一步的动作
//@arg: LRElem actionTable[]
//@arg: CString statusTop
//@arg: char chInput
//@return:LRElem
ElemGoto CLexDemoView::LookInGotoTable(ElemGoto gotoTable[], CString statusTop, CString symbolTop)
{
	//long lTableSize = sizeof(gotoTable)/sizeof(ElemGoto);
	long lTableSize = 4;
	for (int i = 0; i < lTableSize; i++)
	{
		//在goto表中找到匹配项的话直接返回
		if (statusTop == gotoTable[i].statusPrev && symbolTop == gotoTable[i].symbol)
		{
			return gotoTable[i];
		}
	}
	//如果没有找到匹配项，返回空状态
  ElemGoto elemRet;
	elemRet.statusNext = "";
	elemRet.statusNext = "";
	elemRet.symbol = "";
	return elemRet;
}

//功能描述:对显示语法分析结果的ListBox进行初始化
//@return:Status 
Status CLexDemoView::InitListBox() 
{
	Status sRet = OK;
  int nWidth = 0;  //ListBox的Width
  //如果ListBox尚未被Created的话  
  if (m_lstResult.m_hWnd == NULL)
	{
		CRect rctCtl;
		GetWindowRect(rctCtl);
		ScreenToClient(rctCtl);
		nWidth = rctCtl.Width();
		rctCtl.DeflateRect(10, 20 , nWidth / 3 * 2, 20);

		m_lstResult.Create(WS_BORDER | WS_VISIBLE | WS_CHILD | WS_VSCROLL |WS_HSCROLL,
			 rctCtl , this,  0xffff);
	}
	//如果ListBox已经生成的话，就将其清空
	else
	{
		m_lstResult.ResetContent(); 
	}
	//进行m_lstToken  ListBox的初始化
	if (NULL == m_lstToken.m_hWnd)
	{
		CRect rctCtl;
		m_lstResult.GetWindowRect(&rctCtl);
		rctCtl.OffsetRect(rctCtl.Width() + 10, 0);
		ScreenToClient(rctCtl);
		m_lstToken.Create(WS_BORDER | WS_VISIBLE | WS_CHILD | WS_VSCROLL | WS_HSCROLL,
			 rctCtl , this,  0xffff);
	}
	else
	{
		m_lstToken.ResetContent();
	}
	return sRet;
}

//功能描述:为LR分析过程在ListBox中添加分析的中间结果//功能描述:
//@arg:Stack<CString> statusStack; //状态栈
//@arg:Stack<CString> symbolStack; //文法符
//@return:Status
Status CLexDemoView::AddToListForLR(Stack<CString> statusStack, Stack<CString> symbolStack)  
{
	CString strVal;
	CString strOut;   //用于存放出栈的String 
	//向m_lstResult中添加状态栈中的内容
	//如果符号栈不为空的话
	while (!statusStack.IsEmpty())
	{
    statusStack.Pop(strOut);
		strVal.Insert(0, " ");
		strVal.Insert(0, strOut);
	}
	m_lstResult.AddString(strVal);
	//向m_lstToken中添加符号栈的内容
	strVal.Empty(); 
	while (!symbolStack.IsEmpty())
	{
		symbolStack.Pop(strOut);
		strVal.Insert(0, " ");
		strVal.Insert(0, strOut);
	}
  m_lstToken.AddString(strVal);
	return OK;
}

//功能描述:为LL(1)分析过程在ListBox中添加分析的中间过程
//@arg:Stack<CString> statusStack
//@return:Status
Status CLexDemoView::AddToListForLL(Stack<CString> statusStack)
{
	CString strVal;
	CString strOut;   //用于存放出栈的String 
	//向m_lstResult中添加状态栈中的内容
	//如果符号栈不为空的话
	while (!statusStack.IsEmpty())
	{
    statusStack.Pop(strOut);
		strVal.Insert(0, " ");
		strVal.Insert(0, strOut);
	}
	m_lstResult.AddString(strVal);
	return OK;
}