parser.cpp

C编译器

#include "globals.h"
#include "util.h"
#include "parser.h"

extern DVec_str productions;
extern vecStr terminals;
extern vecNter nonterminals;
extern DVec_int table;
extern vecStr vec ;

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//( findIndex( str ) >= 0 )//&& hasexisted( nonterminals[ indexRight ].first,  "ε" ) ) //Xj is a nonterminal and its first set contains ε 
				{
					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

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
}

void makeTable()
{
	
	for(int i = 0, j = 0;j < (int)terminals.size();j++ )
	{
		if( terminals[j] != "ε" )
		{
			vec.push_back(terminals[j]);
			i++;
		}
	}
	vec.push_back("$");

	table.resize( nonterminals.size() );
	vector<int> v(vec.size() ,-1 );
	for( int i = 0;i < (int)table.size() ;i++ )
		table[i] = v;

	for(int i = 0;i < (int)productions.size();i++ )
	{
		bool flag = false;                         //测试ε 是否在First(A)中
		int nterIndex = findIndex( productions[i][0] );
		string token;

		vecStr pro(productions[i].begin() + 1,productions[i].end() );
		vecStr first = makeFirst(pro);
		for( int j = 0;j < (int)first.size();j++ )
		{
			token = first[j];//cout<<token;
			int terIndex = findTerIndex( vec,token );//cout<<terIndex;
			if( terIndex != -1)	table[nterIndex][terIndex] = i;

			else flag = true;
		}
		if( flag )
		{
			for(size_t j = 0;j <nonterminals[nterIndex].follow.size();j++)
			{
				token = nonterminals[nterIndex].follow[j];
				int terIndex = findTerIndex( vec,token );
				if( table[nterIndex][terIndex] == -1 )    
			        table[nterIndex][terIndex] = i;							
			}
		}//if
	}//for--->i
}//makeTable