grammar.cpp

一个用VC++写的算符优先分析程序

//  将终结符入在列表的头一行和头一列
/******************************************************************/
void Cgrammar::first_table_head(CListCtrl &m_list)
{
	int m_count;
	char m_ch[2] = {'\0', '\0'};
	m_list.SetExtendedStyle(LVS_EX_GRIDLINES|LVS_EX_FULLROWSELECT);
    m_list.InsertColumn(0, m_ch, LVCFMT_LEFT, 30);
	for(m_count = 0; m_count < m_Vt.size(); m_count++)//终结符
	{
		*m_ch= m_Vt[m_count];
		m_list.InsertColumn(m_count + 1, m_ch, LVCFMT_LEFT, 60);
		m_list.InsertItem(m_list.GetItemCount(), m_ch);
	}

}


/*******************************************************************/
//  清空表格
/******************************************************************/
void Cgrammar::delete_list(CListCtrl &m_list)
{
    m_list.DeleteAllItems(); 
    int m_count = m_list.GetHeaderCtrl()->GetItemCount();
    for(int i=0; i< m_count; i++)
                m_list.DeleteColumn(0);
}
/*******************************************************************/
//  根据firstVT,LastVT求得优先表,第四个参数有默认值,默认值是false,
//  当第四个参数是false时求整个优先表,为true时仅是在列表原有的基础上再执行一步 //   
/******************************************************************/
void Cgrammar::first_table(CListCtrl &m_list, CListCtrl &m_FirstVT, CListCtrl &m_LastVT, bool symbol)
{// symbol = true 时单步执行
     int m_count, m_i, m_len;
	 bool m_symbol = false;  
	 for(m_count =0; m_count < m_grammar.size(); m_count++)  //扫描每一条产生式
	 {	 
		 m_len = strlen(m_grammar[m_count].v_right);
		 for(m_i = 0; m_i < m_len ; m_i++)  //扫描每一条产生式的右部的每一个字符
		 {
			 int m_Item, m_column, i;

			 if(m_i +1 < m_len)  //应对产生式形如:p->..ab..进行操作
			 {
			      m_Item = this->getVtsuffix(m_grammar[m_count].v_right[m_i]); //得到两个字符的下标
			      m_column = this->getVtsuffix(m_grammar[m_count].v_right[m_i + 1]);
			      if(-1 != m_Item && -1 != m_column  // 如果满足p->..ab.. 并且没有字符被填入
					  && TRUE == m_list.GetItemText(m_Item, m_column +1).IsEmpty())
				  {   
					  m_list.SetItemText(m_Item, m_column +1, "=");  //让F[a,b]='='
					  m_symbol = true;  //标志已经执行了一步
				  }
			 }

			 if(m_i +2 <m_len) //应对产生式形如:p->..aAb..进行操作
			 {
			       m_Item = this->getVtsuffix(m_grammar[m_count].v_right[m_i]); 
			       m_column = this->getVtsuffix(m_grammar[m_count].v_right[m_i + 2]);
			       if(-1 != m_Item  && -1 != m_column && -1 != this->getVnsuffix(m_grammar[m_count].v_right[m_i + 1])
					   && TRUE == m_list.GetItemText(m_Item, m_column +1).IsEmpty())
				   {     // 如果满足p->..aAb.. 并且没有字符被填入
					   m_list.SetItemText(m_Item, m_column +1, "=");  //让F[a,b]='='
				       m_symbol = true;   //标志已经执行了一步  
				   } 
			 }

			 if(m_i +1 < m_len) //应对产生式形如:p->..aA..进行操作
			 {
			       m_Item = this->getVtsuffix(m_grammar[m_count].v_right[m_i]); //p->..aA..
			       m_column = this->getVnsuffix(m_grammar[m_count].v_right[m_i + 1]);
			       if( -1 != m_Item && -1 != m_column)	 
				       for(i = 0; i < m_Vt.size(); i++) //找firstVT(A)的非终结符如b, 让F[a,b]='<'
					        if(1 == atoi(m_FirstVT.GetItemText(m_column, i + 1)) 
								&& TRUE == m_list.GetItemText(m_Item, i +1).IsEmpty())
							{    // 如果满足p->..aA.. 并且没有字符被填入
								m_list.SetItemText(m_Item, i +1, "<"); 
							    m_symbol = true; //标志已经执行了一步 
							}
			 }

		     if(m_i +1 < m_len)////应对产生式形如:p->..Aa..进行操作
			 {
			       m_Item = this->getVnsuffix(m_grammar[m_count].v_right[m_i]); //p->..Aa..
			       m_column = this->getVtsuffix(m_grammar[m_count].v_right[m_i + 1]);
			       if( -1 != m_Item && -1 != m_column)
				       for(i = 0; i < m_Vt.size(); i++) //找LastVT(A)的非终结符如b, 让F[b,a]='> 
					      if(1 == atoi(m_LastVT.GetItemText(m_Item, i + 1))
							  && TRUE == m_list.GetItemText(i, m_column +1).IsEmpty())
						  {  // 如果满足p->..aA.. 并且没有字符被填入 
							  m_list.SetItemText(i, m_column + 1, ">");  
							  m_symbol = true; //标志已经执行了一步
						  }
			 }
			 if(m_symbol && symbol) //如果是单步执行而且是已经执行了一步,则跳出
			 break;
		 }
		 if(m_symbol && symbol) //如果是单步执行而且是已经执行了一步,则返回
			 break;
	 }
	 if(symbol && !m_symbol) //提示
		 ::AfxMessageBox("优先表已经完成!!!!", MB_OK);

}
/*******************************************************************************/
//   拓展文法
/********************************************************************************/
void Cgrammar::add_produce()
{
	if(!m_grammar.empty())//有产生式则可以拓展
	{
        produce m_temp;
	    char ch = 'A' ;
	    while(-1 != this->getVnsuffix(ch))//找一个新的非终结符
		    ch++;
	    CString str;
	    str.Format("#%c#", m_grammar[0].v_left);
	    m_temp.v_right = "#" + str + "#";//确认新的产生式
	    m_temp.v_left = ch;
	    m_grammar.push_back(m_temp);//更新产生式,终结符集,非终结符集
	    this->getVn();
	    this->getVt();
		
	}
	
		
}
/*******************************************************************************/
//   构建算符优先分析过程列表
/********************************************************************************/
void Cgrammar::first_analyse_head(CListCtrl &m_list, CString &m_edit)
{  
	if(m_edit.IsEmpty())
		::AfxMessageBox("请输入句子!!!!", MB_OK);
	else
	{
		m_list.SetExtendedStyle(LVS_EX_GRIDLINES|LVS_EX_FULLROWSELECT);  //定义列表的风格
    
	    m_list.InsertColumn(0, "步骤", LVCFMT_LEFT, 40);  //初始化分析列表头
        m_list.InsertColumn(1, "栈", LVCFMT_LEFT, 100);
	    m_list.InsertColumn(2, "输入缓冲区", LVCFMT_LEFT, 100);
	    m_list.InsertColumn(3, "动作", LVCFMT_LEFT, 150);
  
	    m_list.InsertItem(m_list.GetItemCount(), "1");   //初始化第一行的内容
	    m_list.SetItemText(0, 1, "#");
        m_list.SetItemText(0, 2, m_edit + "#");
	    m_list.SetItemText(0, 3, "初始状态");

	}
}
/*******************************************************************************/
//  根据first_table(优先表)求得分析表,第四个参数有默认值,默认值是false,
//  当第四个参数是false时求整个分析表,为true时仅是在列表原有的基础上再执行一步 // 
//  单步还未实现  
/********************************************************************************/
void Cgrammar::first_analyse(CListCtrl &m_analyse, CString &m_edit, CListCtrl &m_list, bool symbol)
{
	  int m_count, m_j ,m_symbol = false;
	  CString m_t, m_behavior, m_sentence;
      if(m_edit.IsEmpty())  //如果句子是空的则不进行分析
		  return;
	 //从列表中取得初始值
      m_t = m_analyse.GetItemText(m_analyse.GetItemCount() - 1, 1); // 栈 
	  m_behavior = m_analyse.GetItemText(m_analyse.GetItemCount() - 1, 3); //记录动作的变量
	  m_sentence = m_analyse.GetItemText(m_analyse.GetItemCount() - 1, 2); //记录还末分析的句子
	 //定义一些中间变量
	  char m_p = m_sentence[0];  //指向要分析的句子的头对象   
	  CString d ; 
	  d.Format("#%c", m_grammar[0].v_left);
	  m_count = m_t.GetLength() - 1;  //指向栈的栈顶值
      while(0 != m_t.Compare(d) || m_p != '#') 
	  {
		  m_p = m_sentence[0]; //
		  if(-1 != this->getVtsuffix(m_t[m_count]))  //让m_j指向终结符
			  m_j = m_count;
		  else
			  m_j = m_count - 1;

		  int m_Item, m_column, i;
		  CString m_swap;

		  m_Item = this->getVtsuffix(m_t[m_j]); //读栈的栈顶值
		  m_column = this->getVtsuffix(m_p);   // 读输入缓冲区的第0个无素
		  if ( 0 == m_list.GetItemText(m_Item, m_column + 1).Compare("<")
			  ||  0 == m_list.GetItemText(m_Item, m_column + 1).Compare("="))
		  {   //如果满足m_t[m_j]</=m_p (s[j]<a or s[j]=a)
			  m_behavior.Format("%c%s%c,%c入栈", m_t[m_j] , m_list.GetItemText(m_Item, 
				  m_column + 1), m_p, m_p);  //记录动作
			  m_t += m_p;  //入栈
			  m_sentence = m_sentence.Right(m_sentence.GetLength() - 1); //值已经入栈,消支
			  m_count++;  //更新栈顶指针
		  }
		  else if(0 == m_list.GetItemText(m_Item, m_column + 1).Compare(">"))
		  {
			  char q ;//, p ;
			  int j ; //记录值的变量
			  do{
				  q = m_t[m_j]; //记录终结符
				  j = m_j; //记录值
				  if( -1 != this->getVtsuffix(m_t[m_j - 1]))
					  m_j--;    //使m_j指向下一个终结符
				  else
					  m_j -= 2;
				  m_Item = this->getVtsuffix(m_t[m_j]); //确定两个终结符的下标 
				  m_column = this->getVtsuffix(q);  //确认两个终结符的关系
				  if(-1 == m_Item || -1 == m_column)
				  {	  
					  ::AfxMessageBox("句子无法用算符优先处法来分析!!!\n");
					  return;
				  }
			  }while(0 != m_list.GetItemText(m_Item, m_column + 1).Compare("<")); //
			  m_swap = ""; //将栈的从第m_j到m_count上的值入进m_swap
			  m_swap = m_t.Right(m_count - m_j );
			  for(i = 0; i< m_grammar.size(); i++)
			  {	  //在产生式中寻找右部与m_swap相匹配的产生式
				  if(0 == m_grammar[i].v_right.Compare(m_swap))
					  break;
				  else if(m_grammar[i].v_right.GetLength() == m_count - m_j)
					  if(m_grammar[i].v_right[j- (m_j + 1)] == m_t[j])
						  break;
			  }
			  if(i < m_grammar.size())
			  {   //找到产生式以后,利用找到的产生式进行归约
				  m_behavior.Format("%c<%c>%c,用%c->%s归约", m_t[m_j], q, m_p, 
					  m_grammar[i].v_left,m_grammar[i].v_right); //记录动作
				  m_t = m_t.Left(m_t.GetLength() - m_count + m_j); //出栈
				  m_t += m_grammar[i].v_left; //产生式的左部入栈
				  m_count = m_j +1; //更新栈顶指针
			  }
			  else
			  {   //找不到的话,退出
				  m_behavior.Format("找不到与%s相匹配的产生式\n", m_swap);
				  ::AfxMessageBox(m_behavior, MB_OK);
				  return;
			  }
		  }
		 else   
		 {	  //如果读栈的栈顶值与输入缓冲区的第0个无素无关系则退出
			 m_swap.Format("%s不是正确的句型!!\n在优先表里的第%c行第%c列中找不到他们的优先关系!!!",
				 m_edit, m_t[m_j], m_p);
			 ::AfxMessageBox(m_swap, MB_OK);
			 return;
		 }
		 //将最新的操作放入列表中
		 m_swap.Format("%d", m_analyse.GetItemCount() + 1);  //构建一个新行
		 m_analyse.InsertItem(m_analyse.GetItemCount(), m_swap);

		 m_Item = m_analyse.GetItemCount() - 1; //在新行中放入最新的操作
		 m_analyse.SetItemText(m_Item, 1, m_t);
		 m_analyse.SetItemText(m_Item, 2, m_sentence);
	     m_analyse.SetItemText(m_Item, 3, m_behavior);
         if(symbol)
		 { 	m_symbol = true;  break; }
	  }
	  if(!m_symbol && symbol)
		  ::AfxMessageBox("分析已经结束!!!!", MB_OK);
}

/*******************************************************************************/
//   消除字符串的空格
/********************************************************************************/
void Cgrammar::delete_blank(CString &m_edit)
{
	CString m_temp;
	int m_count = 0, m_number = 0;   
	while(m_count < m_edit.GetLength())  //去空格
	{
		while(m_edit[m_count] == ' ' || m_edit[m_count] == '\t')
			m_count++;
		m_temp  += m_edit[m_count++];
	}
	m_edit = m_edit;
}

/*******************************************************************************/
//   析构函数
/********************************************************************************/
Cgrammar::~Cgrammar()
{
	m_Vn.~vector();
	m_Vt.~vector();
	m_grammar.~vector();
}

/*******************************************************************************
//code by phay
//2007 12 29
/********************************************************************************