grammar.cpp

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

// grammar.cpp: implementation of the Cgrammar class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "OperandAnalyzer.h"
#include "grammar.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
/****************************************************************/
//    构造函数,参数是一个字符串符,在去空格后,调其它的子函数求产生式,终结符,非终结符
/****************************************************************/
Cgrammar::Cgrammar(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++];
	}
	this->getproduce(m_temp);  //求产生式集
	this->getVn();  //求非终结符号集
	this->getVt();  //求终结符号集
}
/******************************************************************/
//   求产生式,参数是一个字符串符, 默认有->符号的字符串左右两可构成产生式//
/******************************************************************/
void Cgrammar::getproduce(CString m_edit)
{
	int m_count = 0;
	produce prnew;//存放产生式的临时变量
    for(; m_count < m_edit.GetLength(); m_count++)//扫描每一个字符
	{
		if(m_count + 2 < m_edit.GetLength() && m_edit[m_count + 1] == '-' 
			&& m_edit[m_count + 2] == '>')  //对在一行中出现->符号就默认有产生式
		{
			 ////////////////
			 prnew.v_left = m_edit[m_count]; //开始记录新的产生式
			 m_grammar.push_back(prnew);
             char m_temp = m_edit[m_count]; //存放新的产生式的左边的字符
			 m_count += 3;    
			 while(m_count < m_edit.GetLength() && m_edit[m_count] != '\r') //扫描符号->后的字符
			 {
				 if(m_count < m_edit.GetLength() && m_edit[m_count] == '|')
				 {   //识别字符|后,存入产生式,开始记录新的产生式
					 m_grammar[m_grammar.size() - 1].v_right += "\0";
					 prnew.v_left = m_temp;
			         m_grammar.push_back(prnew);
				 }
				 else //m_grammar.size() - 1是一个动态的量,它保证存入的字符是存入最后一个产生式中
					 m_grammar[m_grammar.size() - 1].v_right += m_edit[m_count];
				 m_count++;
			}
		}
	}
}
/*********************************************************************************/
//  得到非终结符集, 由扫描产生式得出//
/**********************************************************************************/
void Cgrammar::getVn()   
{
    int m_count;
	for(m_count = 0; m_count < m_grammar.size(); m_count++) //扫描每一个产生式的左部
	{
        int m_temp = 0;
		while(m_temp < m_Vn.size()) //查看扫描出的新的非终结符是否已经存在
		{	
			if(m_Vn[m_temp] == m_grammar[m_count].v_left)
				break;
		    m_temp++;
		}
		if(m_temp >= m_Vn.size()) //如果是新的非终结符则存入非终结符集
			m_Vn.push_back(m_grammar[m_count].v_left);
	}
}
/*******************************************************************************/
// 得到终结符集, 由扫描产生式得出//
/*******************************************************************************/
void Cgrammar::getVt()  
{
    int m_count;
	for(m_count = 0; m_count < m_grammar.size(); m_count++)//扫描每一个产生式右部
	{
		int m_temp = 0, m_len = strlen(m_grammar[m_count].v_right);
		while(m_temp < m_len)//扫描每一个产生式右部的每一个字符
		{
			 int m_temp2 = 0;
		     while(m_temp2 < m_Vt.size() && !isupper(m_grammar[m_count].v_right[m_temp]))
			 {   //查看扫描出的新的终结符是否已经存在
				 if(m_Vt[m_temp2] == m_grammar[m_count].v_right[m_temp])
				   break;
				 m_temp2++;
			 }
			 //如果是新的终结符则存入终结符集 isupper()可以识别字符是否是大写字母,如果是则返回true
			 if(m_temp2 >= m_Vt.size()&& !isupper(m_grammar[m_count].v_right[m_temp]))
		         m_Vt.push_back(m_grammar[m_count].v_right[m_temp]);
			 m_temp++;
		}
	}
}
/*************************************************************************************/
// 输出产生式,将产生式以一条一行的格式写入一个字符串参数中 //
/**************************************************************************************/
void Cgrammar::display(CString &m_edit)
{
    for(int m_count = 0; m_count < m_grammar.size(); m_count++)
	{
		CString m_temp;
		m_temp.Format("%d:", m_count+1);//将整形转换成字符串型
		m_edit += m_temp + m_grammar[m_count].v_left + "->" +
			m_grammar[m_count].v_right + "\r\n";  //写入产生式
	}
}
/*******************************************************************/
//  返回非终结符的个数
/******************************************************************/
int Cgrammar::getVnsize()
{
	return m_Vn.size();
}
/*******************************************************************/
//  返回终结符的个数
/******************************************************************/
int Cgrammar::getVtsize()
{
	return m_Vt.size();
}
/*******************************************************************/
//  返回非终结符的下标--如果参数是非终结符的一员,则返回其对应的下标,否则返回-1 //
/******************************************************************/
int Cgrammar::getVnsuffix(char m_temp)
{
    for(int m_suffix = 0; m_suffix < m_Vn.size(); m_suffix++)
		if(m_Vn[m_suffix] == m_temp) 
			return m_suffix;
	return -1;
}
/*******************************************************************/
//  返回终结符的下标--如果参数是终结符的一员,则返回其对应的下标,否则返回-1 //
/******************************************************************/
int Cgrammar::getVtsuffix(char m_temp)
{
    for(int m_suffix = 0; m_suffix < m_Vt.size(); m_suffix++)
		if(m_Vt[m_suffix] == m_temp)
			return m_suffix;
	return -1;
}
/*******************************************************************/
//  将终结符写入传入的参数--列表的第一行,非终结符写入第一列
/******************************************************************/
void Cgrammar::getlist(CListCtrl &m_list)
{
	int m_count;
	char ch[2] = {'\0','\0'};
	m_list.SetExtendedStyle(LVS_EX_GRIDLINES|LVS_EX_FULLROWSELECT);
	m_list.InsertColumn(0, ch, LVCFMT_LEFT, 30); //第一列空起,用来写非终结符
	for( m_count = 0; m_count < m_Vt.size(); m_count++)
	{   
		*ch= m_Vt[m_count];   	//将终结符放在表每一列的头一行
		m_list.InsertColumn(m_count + 1, ch, LVCFMT_LEFT, 30);
	}
    for( m_count = 0; m_count < m_Vn.size(); m_count++)
	{	
		*ch= m_Vn[m_count];    //将非终结符放在表的头一行列
		m_list.InsertItem(m_list.GetItemCount(), ch);
	}

}
/*******************************************************************/
//  求firstVT集,将结果写入参数列表中,之前列表应该写入了非终结符和终结符
/******************************************************************/
void Cgrammar::getFirstVT(CListCtrl &m_list)
{
	int m_count;
    vector <produce>  m_push; //栈
	produce  m_temp;

	this->getlist(m_list);

	int m_Inem, m_column;//行,列 
	for(m_count = 0; m_count < m_grammar.size(); m_count++)
	{  //对每一个形如P->a.. 和 P->Qa..的产生式进行操作
        m_column = this->getVtsuffix(m_grammar[m_count].v_right[0]);
		m_temp.v_right = m_grammar[m_count].v_right[0];  //确认产生式是否是形如 P->a..  
		if(m_column == -1 && strlen(m_grammar[m_count].v_right) >= 2)
        {     //如果产生式不是形如 P->a..,则看其是否形如P->Qa..
			m_column = this->getVtsuffix(m_grammar[m_count].v_right[1]);
			m_temp.v_right = m_grammar[m_count].v_right[1];
		}
		if(m_column != -1)
		{   //如果产生式满足 P->a..或者P->Qa.. 
			m_Inem = this->getVnsuffix(m_grammar[m_count].v_left); //得到 P的下标
			m_list.SetItemText(m_Inem , m_column + 1, "1"); //F[P,a] = 1
			m_temp.v_left = m_grammar[m_count].v_left ;
			m_temp.v_right += "\0";
			m_push.push_back(m_temp); //将产生式P->a存入栈
		}
	}

    
	while(!m_push.empty()) //出栈
	{
		m_temp = m_push[m_push.size() - 1];//保存将要出栈的产生式    
		m_push.pop_back(); //出栈
		for(m_count = 0; m_count < m_grammar.size(); m_count++)//扫描每一个产生式
			if(m_grammar[m_count].v_right[0] == m_temp.v_left)
			{ //对每一条形如 P->Q..的产生式操作
			    m_column = this->getVtsuffix(m_temp.v_right[0]); 
				m_Inem = this->getVnsuffix(m_grammar[m_count].v_left);
			    m_list.SetItemText(m_Inem, m_column + 1, "1");//F[P,a]=1
			    if(m_temp.v_left != m_grammar[m_count].v_left)
				{  //如果是新的产生式,则存入栈中
					m_temp.v_left = m_grammar[m_count].v_left;
					m_push.push_back(m_temp);
				}
			}

	}
  
}
/*******************************************************************/
//  求LastVT集,将结果写入参数列表中,之前列表应该写入了非终结符和终结符
/******************************************************************/
void Cgrammar::LastVT(CListCtrl &m_list)
{
    int m_count;
    vector <produce>  m_push;
	produce  m_temp;

	this->getlist(m_list);

	int m_Inem, m_column, m_len;
	for(m_count = 0; m_count < m_grammar.size(); m_count++)
	{  //对每一个形如P->...a 和 P->..aQ的产生式进行操作
        m_len = strlen(m_grammar[m_count].v_right);
		m_column = this->getVtsuffix(m_grammar[m_count].v_right[m_len-1]);
		m_temp.v_right = m_grammar[m_count].v_right[m_len - 1]; //确认产生式是否是形如 P->...a
		if(m_column == -1 && m_len-2 >= 0)
        {     //如果产生式不是形如 P->...a,则看其是否形如P->...aQ
			m_column = this->getVtsuffix(m_grammar[m_count].v_right[m_len - 2]);
			m_temp.v_right = m_grammar[m_count].v_right[m_len - 2];
		}
		if(m_column != -1)
		{   //如果产生式满足 P->a..或者P->Qa.. 
			m_Inem = this->getVnsuffix(m_grammar[m_count].v_left);
			m_list.SetItemText(m_Inem , m_column + 1, "1");//F[P,a] = 1
			m_temp.v_left = m_grammar[m_count].v_left ;
			m_temp.v_right += "\0";
			m_push.push_back(m_temp);//将新产生式P->a存入栈
		}
	}

    
	while(!m_push.empty())
	{
		m_temp = m_push[m_push.size() - 1]; //保存将要出栈的产生式 
		m_push.pop_back();  //出栈
		for(m_count = 0; m_count < m_grammar.size(); m_count++)
		{	//对每一条形如 P->..Q的产生式操作
			m_len = strlen(m_grammar[m_count].v_right);
			if(m_grammar[m_count].v_right[m_len - 1] == m_temp.v_left)
			{
			    m_column = this->getVtsuffix(m_temp.v_right[0]);
				m_Inem = this->getVnsuffix(m_grammar[m_count].v_left);
				if(1 != atoi(m_list.GetItemText(m_Inem, m_column + 1)))
				{  //如果是新的产生式,则存入栈中
					m_list.SetItemText(m_Inem, m_column + 1, "1");//F[P,a]=1
					m_temp.v_left = m_grammar[m_count].v_left;
					m_push.push_back(m_temp);
				}
			}
		}

	}

}

/*******************************************************************/