predictive parsing.cpp

预测分析算法 《编译原理 技术与工具》123页算法

// Predictive Parsing .cpp : 定义控制台应用程序的入口点。
//
//预测分析算法 <<编译原理 技术与工具>>(英文) P187 算法 
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
typedef	struct  {
		string nter;
		string ter;
		vector<string> rpart;
} PARSINGTABLENODE;
typedef vector<PARSINGTABLENODE> PARSINGTABLE;
void CreateParsingTable( PARSINGTABLE &table);
void InitInput(vector<string> &nonter, vector<string> &ter, vector<string> &input, PARSINGTABLE &table);
const string NULLSTRING = "NULL";

class Preparser
{
public:
	Preparser(vector<string> nterm, vector<string> ter, vector<string> in, PARSINGTABLE table);
	~Preparser();
	vector<string> M(string nter, string ter);
	bool IsTerminal(string str);
	bool preparsing();
private:
	vector<string> input;
	unsigned int ip;
	vector<string> nonterm;
	vector<string> term;
	stack<string> staStack;//状态栈
	vector<string> output;
	PARSINGTABLE ParsingTable;
};

Preparser::Preparser(vector<string> nterm, vector<string> ter, vector<string> in, PARSINGTABLE table)
{
	nonterm = nterm;
	term = ter;
	input = in;
	input.push_back("$");
	ip = 0;
	staStack.push("$");
	staStack.push(nonterm[0]);
	ParsingTable = table;

}
Preparser::~Preparser()
{
	input.clear();
	nonterm.clear();
	term.clear();
	output.clear();

}
bool Preparser::IsTerminal(string str)
{
	for(unsigned int i = 0; i < term.size(); i ++)
	{
		if(str == term[i])
			return true;
	}
	return false;
}

vector<string> Preparser::M(const std::string nter,const std::string ter)
{
	for( unsigned int i = 0; i < ParsingTable.size(); i ++)
	{
		if( nter == ParsingTable[i].nter && ter == ParsingTable[i].ter)
		{
			return ParsingTable[i].rpart;
		}
	}
	vector<string> tmp;
	tmp.push_back(NULLSTRING);
	return tmp;
}

bool Preparser::preparsing()
{
	//预测分析算法 <<编译原理 技术与工具>>(英文) P187 算法 
	ip = 0;
	string X;
	string a;
	vector<string> tmp;
	vector<string> tmp1;
	do
	{
		X = staStack.top();
		a = input[ip];
		if( IsTerminal(X) || "S" == X )
		{
			if(a == X)
			{
				X == staStack.top();
				staStack.pop();
				ip ++;
			}
			else return false;
		}
		else
		{
			tmp1 = tmp = M(X, a);
			if( NULLSTRING != tmp[0])
			{
				X = staStack.top();
				staStack.pop();
				while(!tmp.empty())
				{
					if("ε" != tmp.back())
					{
						staStack.push(tmp.back());
					}
					tmp.pop_back();
				}
				cout<<X<<"->";
				for(unsigned int i = 0; i < tmp1.size(); i ++)
				{
					cout<<tmp1[i];
				}
				cout << endl;
			}
			else 
			{
				return false;
			}
		}		
	}while( "$" != X);
	return true;
}


int main()
{
	vector<string> nonterm;//{"E", "E'", "T", "T'", "F"};
	vector<string> term;// {"id", "+", "*", "(", ")", "$"};
	vector<string> input;//({"id", "+", "id", "*", "id"});
	PARSINGTABLE table;
	InitInput(nonterm, term, input, table);//初始化输入

	Preparser preparser(nonterm, term, input, table);
	if(!preparser.preparsing())
	{
		cout << "出错\n";
	}
	else
	{
		cout << "正常\n";
	}

	return 0;
}
//初始化输入
void InitInput(vector<string> &nonterm, vector<string> &term, vector<string> &input, PARSINGTABLE &table)
{
	
	nonterm.push_back("E");
	nonterm.push_back("E'");
	nonterm.push_back("T");
	nonterm.push_back("T'");
	nonterm.push_back("F");
	term.push_back("id");
	term.push_back("+");
	term.push_back("*");
	term.push_back("(");
	term.push_back(")");
	term.push_back("$");
	input.push_back("id");
	input.push_back("+");
	input.push_back("id");
	input.push_back("*");
	input.push_back("id");
	CreateParsingTable(table);

}

//构造分析表
void CreateParsingTable( PARSINGTABLE & table)
{
	PARSINGTABLENODE node;

	//E→TE'
	node.nter = "E";
	node.ter = "id";
	node.rpart.push_back("T");
	node.rpart.push_back("E'");
	table.push_back(node);
	node.rpart.clear();

	//E→TE'
	node.nter = "E";
	node.ter = "(";
	node.rpart.push_back("T");
	node.rpart.push_back("E'");
	table.push_back(node);
	node.rpart.clear();

	//E'→+TE'
	node.nter = "E'";
	node.ter = "+";
	node.rpart.push_back("+");
	node.rpart.push_back("T");
	node.rpart.push_back("E'");
	table.push_back(node);
	node.rpart.clear();

	//E'→$
	node.nter = "E'";
	node.ter = ")";
	node.rpart.push_back("ε");
	table.push_back(node);
	node.rpart.clear();

	//E'→$
	node.nter = "E'";
	node.ter = "$";
	node.rpart.push_back("ε");
	table.push_back(node);
	node.rpart.clear();

	//T→FT'
	node.nter = "T";
	node.ter = "id";
	node.rpart.push_back("F");
	node.rpart.push_back("T'");
	table.push_back(node);
	node.rpart.clear();

	//T→FT'
	node.nter = "T";
	node.ter = "(";
	node.rpart.push_back("F");
	node.rpart.push_back("T'");
	table.push_back(node);
	node.rpart.clear();


	//T'→$
	node.nter = "T'";
	node.ter = "+";
	node.rpart.push_back("ε");
	table.push_back(node);
	node.rpart.clear();

	//T'→*FT'
	node.nter = "T'";
	node.ter = "*";
	node.rpart.push_back("*");
	node.rpart.push_back("F");
	node.rpart.push_back("T'");
	table.push_back(node);
	node.rpart.clear();

	//T'→$
	node.nter = "T'";
	node.ter = ")";
	node.rpart.push_back("ε");
	table.push_back(node);
	node.rpart.clear();

	//T'→$
	node.nter = "T'";
	node.ter = "$";
	node.rpart.push_back("ε");
	table.push_back(node);
	node.rpart.clear();

	//F→id
	node.nter = "F";
	node.ter = "id";
	node.rpart.push_back("id");
	table.push_back(node);
	node.rpart.clear();

	//F→(E)
	node.nter = "F";
	node.ter = "(";
	node.rpart.push_back("(");
	node.rpart.push_back("E");
	node.rpart.push_back(")");
	table.push_back(node);
	node.rpart.clear();

}