makefirst.cpp

这是编译原理编译器中的一部分

#include "parse.h"
#include "read.h"
#include "make.h"

extern DVec_str productions;
extern vecStr terminals;
extern vecNter nonterminals;

void makeFirstSet()
{
	bool changed = true;
	while( changed )
	{
		vecNter nonterminals_bef = nonterminals;
		for( size_t i = 0;i < productions.size();i++ )
		{
			int indexLeft = findIndex( productions[i][0] );
            size_t j;
			for( j = 1;j < productions[i].size();j++ )       //for the production A-->X1X2..Xj....Xn
			{
				string str = productions[i][j]; 
				int indexRight = findIndex(str);
				if( hasexisted(terminals,str ) && productions[i][j] != "ε" ) // Xj is a terminal and not ε ,put Xj into first(A)
				{
					if(!hasexisted(nonterminals[ indexLeft ].first,str ) )
						nonterminals[ indexLeft ].first.push_back( str );
					break;
				}
				else if( str == "ε" )continue;                                                         //Xj is ε   
				else
				{
					addFir_toFir( nonterminals[indexLeft] , nonterminals[indexRight] );
					if( !hasexisted( nonterminals[ indexRight ].first,  "ε" ) ) break;     //Xj is a nonterminal and its first set doesnot contain ε
				}
				                      
			}// for --->j

			if(  ( ( findIndex( productions[i][j-1] ) >= 0 && j == productions[i].size() )
				 || productions[i][j-1] == "ε"  ) && !hasexisted(nonterminals[indexLeft].first,"ε") ) 
				 nonterminals[indexLeft].first.push_back( "ε" );
		} // for ---> i

		if( !firHasched( nonterminals_bef, nonterminals ) )
			changed = false;
	}  // while
}      // makeFirstSet

int  findIndex( string str )
{
	int i;
	for(  i = 0;i <(int) nonterminals.size() ;i++)	
		if( nonterminals[i].token== str )
			return i;
	return -1;
}

void addFir_toFir(Nonterminal &set1,Nonterminal &set2)
{
	for(size_t i = 0;i < set2.first.size() && set2.first[i] != "ε";i++)
		if( !hasexisted( set1.first,set2.first[i] ) )
			set1.first.push_back( set2.first[i] );
}

bool firHasched(vecNter vecb,vecNter veca)
{
	for( size_t i = 0;i < vecb.size();i++)
		if( veca[i].first != vecb[i].first )return true;
	return false;
}

int getProIndex( string str)
{
	for( int i = 0;i < (int)productions.size();i++)
		if( productions[i][0] == str )
			return i;
	return -1;
}