compiler.cpp

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

// compiler.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"



//在left为左室的产生式加入first_symbol的符号first集合 
void addFirstSymbol(int left, int first_symbol)
{	
	if(left == first_symbol)
		return;
	if(first_symbol > NES_ES || first_symbol == -1 )//加入终结符
	{
		ps.getNes(left)->AddFirstSymbol(first_symbol);
	}
	else
	{
		if( ps.getNes(first_symbol)->first_finish == 0 ) //先算出完整的first集合
		{
			for(int i= 0 ; i < creation_num ; i ++)
			{
				if(_creation[i].getLeft() == first_symbol)
				{
					addFirstSymbol(_creation[i].getLeft(), _creation[i].getPosition(0));
				}
			}
			ps.getNes(first_symbol)->first_finish = 1;
		}
		for(int i = 0 ; i < ps.getNes(first_symbol)->first_num ; i ++)
		{
			ps.getNes(left)->AddFirstSymbol(ps.getNes(first_symbol)->_first[i]);
		}
	}
}

int testExist(class LRPrefix *temp, int move_symbol)
{
	int src_status = temp->status_in;
	for(int i = 0 ;i < status_num ;i ++)
	{
		if( _status[i].PrefixExist(temp) == 1 )//S[i]状态中包含temp这个前缀
		{
			int check_flag = 1;
			for( int j = 0 ; j < _status[src_status].prefix_num ; j++)//检查是否包含所有这个状态的移进符号
			{
				if( _status[src_status]._prefix[j]._prefix.getFirstSymbol() == move_symbol )
				{
					LRPrefix check;
					check.setPrefix( &_status[src_status]._prefix[j] );
					check._prefix.prefix_pos++;
					check_flag = check_flag * _status[i].PrefixExist(&check);
				}
			}
			if( check_flag == 1 )
				return i;
		}
	}
	return -1;
}

LRPrintTable_Item *	getAction(int status, int forward_symbol)//寻找相应的处理
{
	LRPrintTable_Line * temp = _table.findLRStatus(status);
	if( temp != NULL)
	{
		for(int i = 0 ;i < symbol_num ; i ++)
			if( temp->_item[i].Symbol_num == forward_symbol)
				return &temp->_item[i];
	}
	return NULL;
}

void creation_init()
{
}
/*-----------------------------*/
/*主函数：
/*-----------------------------*/
int _tmain(int argc, _TCHAR* argv[])
{	
	int i, j;//用于循环
	symbol_num = _sm.sm.size();

	/*-----------------------------*/
	/*获得所有creation并输出
	/*-----------------------------*/
	FileReader fr;
	fr.OpenFile();
	while( fr.IsEnd() != 1 )
	{
		creation *tempCreation = new creation();
		fr.ReadLine();
		//A[creation_num].analyze( &fr );
		tempCreation->analyze( &fr);
		tempCreation->setName( creation_num + 1 );
		_creation.push_back( *tempCreation );
		//A[creation_num].setName(creation_num + 1);
		creation_num++;
	}
	fr.CloseFile();
/*
	for(i = 0 ; i < creation_num ;i ++)
	{
		A[i].output();
	}
*/
	FileReader fr_table;
	fr_table.setFileName("table.txt");
	int exist = fr_table.OpenFile();
	if( exist == 1 )
	{
		cout<<"LR1 表已存在，正在读取。。。。。"<<endl;
		_table.readTable(&fr_table);
		_table.print();
	}
	else
	{
		cout<<"LR1表不存在，正在建立。。。。。"<<endl;
	/*-----------------------------*/
	/*获得所有的符号并输出
	/*-----------------------------*/
	for( i = 0 ; i < creation_num ; i++)
	{
		int sss = _creation[i].getLeft();
		ps.addSymbol( _creation[i].getLeft() );
		for( int j = 0 ; j < _creation[i].getLength() ;j++)
			ps.addSymbol( _creation[i].getPosition(j) );
	}
	creation_init();
	//ps.output();

	/*-----------------------------*/
	/*求first集合并输出
	/*-----------------------------*/
	for(i = 0 ;i < ps.nes_num ;i ++)
	{
		for(j = 0 ; j < creation_num ; j ++)
		{
			if( _creation[j].getLeft() == ps.nes[i].symbol_name )
			{
				addFirstSymbol(_creation[j].getLeft(), _creation[j].getPosition(0));
			}
		}
		ps.nes[i].first_finish = 1;
	}
	//ps.outputFirst();

	/*-----------------------------*/
	/*产生LR1表
	/*-----------------------------*/
	LRTable lr;
	lr.addItem(status_num);
	//设置起始状态S[0]
	status *tempNewStatus = new status();
	tempNewStatus->number = status_num;
	LRPrefix newPrefix;
	newPrefix._prefix.creation_name = 0;
	newPrefix._prefix.prefix_pos = 0;
	newPrefix.status_in = 0;
	newPrefix.addForwardSymbol(2000);
	tempNewStatus->addPrefix(&newPrefix);
	tempNewStatus->FindClosure();//扩展属于这个状态的活前缀
	tempNewStatus->output();
	_status.push_back(*tempNewStatus);
	
	status_num++;//状态数增加
	lr.addItem(status_num);
	
	//开始求转移
	class convert_queue _convertStack;//转移队列
	_convertStack.AddStatus(&_status[0]);
	class LRPrefix _ondeal;
	int symbol, end;

	while(_convertStack.IsEmpty() != 1)
	{
		_convertStack.PushOut(&_ondeal);//退出队列
		end = _ondeal.testEffective();//测试是规约还是移进
		if(end == 0)//规约
		{
			if(_ondeal._prefix.creation_name != 0)
				for(int k = 0 ; k < _ondeal.symbol_num ; k++)
				{
					LRTable_Item *tempItem = lr.findItem(_ondeal.status_in);
					if( tempItem != NULL)
						tempItem->AddItem(_ondeal._symbol[k], _ondeal._prefix.creation_name , 1);//规约
				}
			else
			{
				LRTable_Item *tempItem = lr.findItem(_ondeal.status_in);
				if( tempItem != NULL)
					tempItem->AddItem(2000, status_num, 4);//接收
			}
			continue;
		}
		symbol = _ondeal._prefix.getFirstSymbol();
		_ondeal._prefix.prefix_pos++;
		int pos = testExist(&_ondeal, symbol);//已存在
		if(pos != -1 )//testExist负责检查在以前的状态中是否已经出现这个前缀,
		{
			LRTable_Item *tempItem = lr.findItem(_ondeal.status_in);
			if( tempItem != NULL)
			{
				if(symbol < NES_ES )
					tempItem->AddItem(symbol, pos, 3);//非终结符状态转移
				else
					tempItem->AddItem(symbol, pos, 2);//增加移进
			}
			continue;
		}
		//建立新的状态集
		tempNewStatus = new status();
		tempNewStatus->number = status_num;
		LRTable_Item *tempItem = lr.findItem(_ondeal.status_in);
		if( tempItem != NULL) 
		{
			if(symbol < NES_ES )
				tempItem->AddItem(symbol, status_num, 3);//非终结符状态转移
			else
				tempItem->AddItem(symbol, status_num, 2);//增加移进
		}
		tempNewStatus->AddPossiblePrefix(&_status[_ondeal.status_in], symbol);
		if( status_num == 22)
		{
			int ss = 0 ;
			 ss ++;
		}
		tempNewStatus->FindClosure();
		tempNewStatus->output();
		_status.push_back(*tempNewStatus);
		_convertStack.AddStatus(&_status[status_num]);
		status_num++;//状态数增加
		lr.addItem(status_num);
	}
	//打印lr表
	lr.output();
	_table.SetTable(&lr);
	_table.print();
	}

	//词法分析器初始化
//	for(i = 0 ; i < 100 ;i ++)
//		cout<<_analyze.getNextWord()<<",";
	anaStack _as;
	//初始化状态栈
	anaStatus * newAnaStatus = new anaStatus();
	_as.PopIn(newAnaStatus);
	//初始化符号栈
	anaSymbol * newAnaSymbol = new anaSymbol();
	newAnaSymbol->symbol = 2000;//#
	
	//开始解析
	action _act;
	string useless;
	int forward_symbol;
	LRPrintTable_Item *tempItem;
	anaStatus * tempStatus;
	anaSymbol *tempSymbol;
	forward_symbol = _analyze.getNextWord();
	cout<<forward_symbol<<endl;
	while(1)
	{	
		if( _global.global_type == error )
			return 0;
		tempItem = getAction(_as.content->status_num, forward_symbol);//寻找相应的处理
		if( tempItem->type == 0 )
			tempItem = getAction(_as.content->status_num, -1);
		if(tempItem->type == 1)//规约
		{
			int temp_creation = tempItem->status;//规约的产生式
			int creation_length = _creation[temp_creation].getLength();//规约的长度
			int finish_symbol = _creation[temp_creation].getLeft();//规约后的非终结符

			_as.PushOut(NULL, creation_length);//状态栈规约
			if( _creation[temp_creation].getPosition(0) != -1 )
				_as.PushSymbolOut(NULL, creation_length);//符号栈规约

			_act.take_action(temp_creation);
			//cin>>useless;
			cout<<"按产生式"<<temp_creation<<"规约到了"<<finish_symbol<<endl;
			//移入左式
			tempItem = getAction(_as.content->status_num, finish_symbol);//寻找相应的处理
			//状态栈处理
			tempStatus = new anaStatus();
			tempStatus->status_num = tempItem->status;
			_as.PopIn(tempStatus);
			//处理符号栈
			tempSymbol = new anaSymbol();
			tempSymbol->symbol = finish_symbol;
			_as.PopSymbolIn(tempSymbol);

			cout<<"察看规约后符号";
			_as.outputSymbol();
			cout<<endl;
			cout<<"察看移进后状态";
			_as.outputStatus();
			cout<<endl;
		}
		else if(tempItem->type == 2)//移进
		{
			cout<<"移进了"<<forward_symbol<<endl;
			//添加状态栈内容
			tempStatus = new anaStatus();
			tempStatus->status_num = tempItem->status;
			_as.PopIn(tempStatus);
			//添加符号栈内容
			tempSymbol = new anaSymbol();
			tempSymbol->symbol = forward_symbol;
			_as.PopSymbolIn(tempSymbol);
			
			cout<<"察看移进后符号";
			_as.outputSymbol();
			cout<<endl;
			cout<<"察看移进后状态";
			_as.outputStatus();
			cout<<endl;

			//继续获取符号
			forward_symbol = _analyze.getNextWord();
			if(forward_symbol == -1)
				forward_symbol = 2000;
		}
		else if(tempItem->type == 3)//非终结符移进,没有用
		{
			tempStatus = new anaStatus();
			tempStatus->status_num = tempItem->status;
			_as.PopIn(tempStatus);

			cout<<"察看移进后符号";
			_as.outputSymbol();
			cout<<endl;
			cout<<"察看移进后状态";
			_as.outputStatus();
			cout<<endl;
		}
		else if(tempItem->type == 4)//结束
		{
			cout<<"finish"<<endl;
			break;
		//	return 1;
		}
		else
		{
			cout<<"error!!"<<endl;
			break;
		//	return 1;
		}
	}
	//_act._code.output();
	_act._code.output_C();
	//_global.printVTable();
	return 0;
}