sfyx.cpp

编译原理

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#define N 10
using namespace std;

bool IsVt(char ch)
{
	if( ch >= 'A' && ch <= 'Z' )
		return false;
	return true;
}

void FirstVt( vector<string> grammar,vector<char> &firstp,vector<char> &firsta)
{
	for( int i = 0; i < grammar.size(); i++ )
	{
		if( IsVt( grammar[i][1] ) )
		{
			firstp.push_back( grammar[i][0] );
			firsta.push_back( grammar[i][1] );
		}
		else if( grammar[i].length() > 2 && IsVt( grammar[i][2] ) )
		{
			firstp.push_back( grammar[i][0] );
			firsta.push_back( grammar[i][2] );
		}
	}
	int n = firstp.size();
	char p;
	for( int j = 0; j < n; j++)
	{
		p = firstp[j];
		for( int k = 0; k < grammar.size(); k++ )
		{
			if( grammar[k][1] == p && grammar[k][0] != grammar[k][1] )
			{
				firstp.push_back( grammar[k][0] );
				firsta.push_back( firsta[j] );
				p = grammar[k][0];
				k = 0;
			}
		}
	}
}

void LastVt(vector<string> grammar,vector<char> &lastp,vector<char> &lasta)
{
	for( int i = 0; i < grammar.size(); i++ )
	{
		int last = grammar[i].length()-1;
		if( IsVt( grammar[i][last] ) )
		{
			lastp.push_back( grammar[i][0] );
			lasta.push_back( grammar[i][last]);
		}
		else if( IsVt( grammar[i][last-1]) )
		{
			lastp.push_back( grammar[i][0] );
			lasta.push_back( grammar[i][last-1]);
		}
	}
	int n = lastp.size();
	char p;
	for( int j = 0; j < n; j++)
	{
		p = lastp[j];
		for( int k = 0; k < grammar.size(); k++ )
		{
			if( grammar[k][1] == p && grammar[k][0] != grammar[k][1] )
			{
				lastp.push_back( grammar[k][0] );
				lasta.push_back( lasta[j] );
				p = grammar[k][0];
				k = 0;
			}
		}
	}
}

void SimpleGrammar( vector<string> &grammar)
{
	ifstream in("a.txt");
	string strTemp;
	for( string str; getline(in,str); )
	{
		strTemp = "";
		strTemp += str[0];
		for(int i=3; i<str.length(); i++)
		{
			if( str[i] != '|' )
				strTemp += str[i];
			else
			{
				grammar.push_back(strTemp);
				strTemp = "";
				strTemp += str[0];
			}
		}
		grammar.push_back(strTemp);
	}
}

void FindVt(vector<string> grammar, vector<char> &vt)
{
	for( int i = 0; i < grammar.size(); i++ )
	{
		int flag = 0;
		for( int j = 0; j < grammar[i].length(); j++)
		{
			if( IsVt( grammar[i][j] ) )
			{
				flag = 0;
				for( int k = 0; k < vt.size(); k++ )
				{
					if( vt[k] == grammar[i][j] )
					{
						flag = 1;
						break;
					}
				}
				if( flag == 0 )
					vt.push_back( grammar[i][j] );
			}
		}
	}
}

int getNum( vector<char> vt, char ch)
{
	for( int i = 0; i < vt.size(); i++)
		if( vt[i] == ch )
			return i;
}

void CreatTable( vector<string> grammar, vector<char> firstp, vector<char> firsta, vector<char>lastp, vector<char>lasta, vector<char> vt, char table[N][N])
{
	for( int i = 0; i < grammar.size(); i++ )
	{
		int n = grammar[i].length();
		if( n > 2 )
		{
			for( int j = 1; j < n-1; j++)
			{
				if( IsVt(grammar[i][j]) && IsVt(grammar[i][j+1]) )
				{
					table[getNum(vt,grammar[i][j])][getNum(vt,grammar[i][j+1])] = '=';
					table[getNum(vt,grammar[i][j])][vt.size()] = '$';
					table[vt.size()][getNum(vt,grammar[i][j+1])] = '$';
				}
				if( j < n-2 && IsVt(grammar[i][j]) && !IsVt(grammar[i][j+1]) && IsVt(grammar[i][j+2]) )
				{
					table[getNum(vt,grammar[i][j])][getNum(vt,grammar[i][j+2])] = '=';
					table[getNum(vt,grammar[i][j])][vt.size()] = '$';
		 			table[vt.size()][getNum(vt,grammar[i][j+2])] = '$';
				}
				if( IsVt(grammar[i][j]) && !IsVt(grammar[i][j+1]) )
				{
					for( int k = 0; k < firstp.size(); k++)
					{
						if( firstp[k] == grammar[i][j+1] )
							table[getNum(vt,grammar[i][j])][getNum(vt,firsta[k])] = '<';
					}
				}
				if( !IsVt(grammar[i][j]) && IsVt(grammar[i][j+1]) )
				{
					for( int l = 0; l < lastp.size(); l++)
					{
						if( lastp[l] == grammar[i][j] )
							table[getNum(vt,lasta[l])][getNum(vt,grammar[i][j+1])] = '>';
					}
				}
			}
		}
	}

	for( int i1 = 0; i1 <= vt.size(); i1++ )
	{
		if( table[i1][vt.size()] != '$' )
			table[i1][vt.size()] = '>';
		if( table[vt.size()][i1] != '$' )
			table[vt.size()][i1] = '<';
	}
	table[vt.size()][vt.size()] = '=';
	cout<<"          优先表        "<<endl;
	cout<<"   ";
	for( int m1 = 0; m1 < vt.size(); m1++)
		cout<<vt[m1]<<"   ";
	cout<<'#';
	cout<<endl;
	for( int m = 0; m <= vt.size(); m++)
	{
		if( m == vt.size())
			cout<<'#'<<"  ";
		else
			cout<<vt[m]<<"  ";
		for( int n = 0; n <= vt.size(); n++)
		{
			if( table[m][n] == '$')
				cout<<"    ";
			else
				cout<<table[m][n]<<"   ";
		}
		cout<<endl;
	}
	cout<<endl;
}

void main()
{
	vector<string> grammar;//存文法
	vector<char> firstp;
	vector<char> firsta;
	vector<char> lastp;
	vector<char> lasta;
	vector<char> vt;
	char table[N][N];
	for( int i = 0; i < N; i++ )
		for( int j = 0; j < N; j++ )
			table[i][j] = ' ';
	
	SimpleGrammar(grammar);//化简文法
	FindVt(grammar,vt);//求终结符集合
	FirstVt(grammar,firstp,firsta);
	LastVt(grammar,lastp,lasta);
	CreatTable( grammar,firstp,firsta,lastp,lasta,vt,table);
}