makefollow1.cpp

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

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

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

void makeFollowSet()
{
	nonterminals[0].follow.push_back( "$" );
   
	bool changed = true;

	while( changed )
	{
		vecNter nonterminals_bef = nonterminals;

		for( int i = 0;i < (int)productions.size();i++ )
		{
			int n = (int)productions[i].size();
            
			for( int j = 1;j < n;j++ )
			{
				if( findIndex( productions[i][j] ) == -1  ) continue;
				int indexJ = findIndex( productions[i][j] );
				int k;
				for( k = j + 1;k < n;k++ )
				{
					int indexK = findIndex( productions[i][k] );         
					if( findIndex(productions[i][k]) == -1 ) // Xj is a terminal and not ε ,put Xj into first(A)
				   {
					   string str = productions[i][k];
					   if( !hasexisted(nonterminals[ indexJ ].follow,str) )
						   nonterminals[ indexJ ].follow.push_back( str );
					   break;
					}
					else
					{
						addFir_toFol( nonterminals[indexJ] , nonterminals[indexK] );
						if( !hasexisted( nonterminals[ indexK ].first,  "ε" ) ) break;   
					}
				}//for--->k
                   if(k == n)addFol_toFol(nonterminals[indexJ],nonterminals[findIndex(productions[i][0])] );
			      // if( hasexisted(first,"ε") ) addFol_toFol(nonterminals[indexJ],nonterminals[findIndex(productions[i][0])] );
			}//for--->j
		}//for--->i

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

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

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

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