status.cpp

（1） 给定一段符合Pascal子集语法的语言

#include "StdAfx.h"
#include ".\status.h"

mystack::mystack(void)
{
	content = NULL;
}

int mystack::IsEmpty()
{
	if(content == NULL)
		return 1;
	return 0;
}

void mystack::PopIn(LRPrefix *src)
{
	LRPrefix *temp = new LRPrefix();
	temp->setPrefix(src);
	temp->next = content;
	content = temp;
}

void mystack::PushOut(LRPrefix *dst)
{
	dst->setPrefix(content);
	LRPrefix *temp = content;
	content = content->next;
	delete temp;
}

LRPrefix* mystack::GetStackTop()
{
	return content;
}

/* ---------------------------------------------------- */
/* ---------------------------------------------------- */
/* ---------------------------------------------------- */

status::status(void)
{
	prefix_num = 0;
	number = 0;
	_prefix.clear();
}

LRPrefix * status::addPrefix(LRPrefix *src)
{
	for( int i = 0 ; i < prefix_num ; i++)
	{
		if( _prefix[i]._prefix.testEqual(&src->_prefix) )//已经存在这样的活前缀，只需要添加预测符号
		{
			//添加所有src中的预测符到temp中
			for( int j = 0 ; j < src->symbol_num ; j++)
				_prefix[i].addForwardSymbol( src->_symbol[j] );
			return &_prefix[i];
		}
	}
	LRPrefix *temp = new LRPrefix();
	temp->setPrefix( src );
	temp->status_in = number;
	_prefix.push_back(*temp);
	prefix_num++;
	return &_prefix[prefix_num-1];
}

int status::PrefixExist(LRPrefix *src)
{
	for( int i = 0 ; i < prefix_num ; i++)
		if( _prefix[i].testEqual(src) )
			return 1;
	return 0;
}

void status::AddPossiblePrefix(status *father, int symbol)
{
	for( int i = 0 ; i < father->prefix_num ; i++)
	{
		if( symbol == father->_prefix[i]._prefix.getFirstSymbol() )
		{
			addPrefix( &father->_prefix[i] );
			_prefix[prefix_num-1].checked = 0;
			_prefix[prefix_num-1].used = 0;
			_prefix[prefix_num-1]._prefix.prefix_pos++;
		}
	}
}

//输出状态的具体信息
void status::output()
{
	record<<"当前的状态号为"<<number<<":"<<endl;
	for( int i = 0 ; i < prefix_num ; i++)
	{
		_prefix[i].output();
	}
	record<<endl;;
}

//寻找closure集合
void status::FindClosure()
{
	class convert_queue _queue;
	int _forward;//_next是活前缀的下一个符号，_now是当前的左式, _forward为预测的
	LRPrefix _now;
	//已存在的非终结符进栈
	for( int i = 0 ; i < prefix_num ; i++)
	{
		if( _prefix[i]._prefix.getFirstSymbol() != -1 )
		{
			_prefix[i].checked = 1;
			_queue.PopIn(&_prefix[i]);
		}
	}
	//逐一检查符号
	while( _queue.IsEmpty() != 1 )
	{
		_queue.PushOut(&_now);								//退栈的活前缀
		int firstSymbol = _now._prefix.getFirstSymbol();	//活前缀的后继符号
		if( firstSymbol == -1 )
			continue;

		for(int i = 0 ;i < creation_num; i ++)
		{
			if(_creation[i].getLeft() == firstSymbol)		//所有关于firstSymbol的产生式
			{
				class LRPrefix temp;
				temp._prefix.creation_name = i;
				temp._prefix.prefix_pos = 0;
				_forward = _now._prefix.getSecondSymbol();	//添加后继内容的预测
				if(_forward == -2)							//添加预测符号的first集合
				{
					for(int k = 0 ; k < _now.symbol_num ; k ++)
						temp.addForwardSymbol(_now._symbol[k]);
				}
				else if(_forward == -1)						//规约态
					continue;
				else
				{
					if(_forward > 50 )						//添加直接后继的first集合
					{
						temp.addForwardSymbol(_forward);
					}
					else
					{
						for(int i = 0 ; i < ps.nes[_forward].first_num ; i ++)
						{
							temp.addForwardSymbol(ps.nes[_forward]._first[i]);
						}
					}
				}
				LRPrefix * nextPrefix = addPrefix(&temp);
				_queue.update(nextPrefix);
				if( nextPrefix->checked == 0)
				{
					nextPrefix->checked = 1;
					_queue.PopIn(nextPrefix);
				}		
			}
		}
	}
}

/* ---------------------------------------------------- */
/* ---------------------------------------------------- */
/* ---------------------------------------------------- */

convert_queue::convert_queue(void)
{
	first = last = NULL;
}

void convert_queue::AddStatus(status *temp)
{
	for( int i = 0 ; i < temp->prefix_num ; i++)
	{
		if( temp->_prefix[i].used != 1 )
		{
			PopIn( &temp->_prefix[i] );
			temp->_prefix[i].used = 1;
		}
	}
}

int convert_queue::IsEmpty()
{
	if(first == NULL && last == NULL)
		return 1;
	return 0;
}

void convert_queue::update(LRPrefix *src)
{
	LRPrefix *temp = first;
	while( temp != NULL )
	{
		if( src->_prefix.testEqual(&temp->_prefix) == 1 )
			temp->setPrefix(src);
		temp = temp->next;
	}
}
void convert_queue::PopIn(LRPrefix * src)//从队尾加入
{

	LRPrefix *temp = new LRPrefix();
	temp->setPrefix(src);
	if(last == NULL)
		last = first = temp;
	else
	{
		last->next = temp;
		last = temp;
	}
}

void convert_queue::PushOut(LRPrefix *dst)//从队首加入
{
	if( IsEmpty() == 0 )
	{
		dst->setPrefix(first);
		LRPrefix *temp = first;
		first = first->next;
		if(first == NULL)
			last = NULL;
		delete temp;
	}
}