grammar.cpp.svn-base

来自「Complete support for EBNF notation; Obje」· SVN-BASE 代码 · 共 639 行 · 第 1/2 页

#include <fstream>
#include "whale.h"
#include "grammar.h"
#include "parser.h"
//#include "nstl/stl.h"
#include "ancillary.h"
#include "utilities.h"
#include "process.h"
using namespace std;
using namespace Whale;

//#define DEBUG_RULE_NUMBERS
//#define DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE

template<class T> set<vector<T> > concatenate_sets_of_vectors(const set<vector<T> > &s1, const set<vector<T> > &s2);
template<class T> inline set<vector<T> > set_consisting_of_a_single_one_element_vector(const T &x);
template<class T> inline set<vector<T> > set_consisting_of_a_single_empty_vector();
set<vector<NonterminalExpression *> > make_rules_proc(NonterminalExpression *expr);
int find_creator_or_updater_in_rule(const RuleData &rule, int pos);
SymbolNumber make_creator_or_updater_or_use_existing_one(const set<RuleData> &requested_rules, RuleData &rule, int last1);
void build_create_and_update_operator_locations_and_source_rules_database();

bool make_rules()
{
	bool flag=true;

	set<NonterminalExpressionConnectUp *> bad_connect_up_operators;

	for(int i=0; i<data.nonterminals.size(); i++)
	{
		data.nonterminals[i].first_rule=data.rules.size();
		NonterminalData::Category category=data.nonterminals[i].category;

		if(category==NonterminalData::NORMAL ||
			category==NonterminalData::EXTERNAL ||
			category==NonterminalData::BODY)
		{
			set<RuleData> requested_rules;

			for(int j=0; j<data.nonterminals[i].alternatives.size(); j++)
			{
				AlternativeData &alternative=data.nonterminals[i].alternatives[j];

				set<vector<NonterminalExpression *> > rule_bodies=make_rules_proc(alternative.expr);

				for(set<vector<NonterminalExpression *> >::iterator p=rule_bodies.begin(); p!=rule_bodies.end(); p++)
				{
					RuleData rule(i, j);

					rule.expr_body=*p;

					for(int k=rule.expr_body.size()-1; k>=0; k--)
					{
						NonterminalExpression *expr=(*p)[k];

						if(typeid(*expr)==typeid(NonterminalExpressionCode))
						{
							NonterminalExpressionCode *expr_code=dynamic_cast<NonterminalExpressionCode *>(expr);

							// to be activated upon reduce.
							if(rule.code_to_execute_upon_reduce==NULL)
							{
								rule.code_to_execute_upon_reduce=expr_code;
								rule.expr_body.pop_back();
							}
							else
								break;
						}
						else if(typeid(*expr)==typeid(NonterminalExpressionConnectUp))
						{
							NonterminalExpressionConnectUp *expr_up=dynamic_cast<NonterminalExpressionConnectUp *>(expr);

							alternative.connect_up=true;
						//	data.variables.connect_up_operators_are_used=true;
							rule.expr_body.pop_back();
						}
						else
							break;
					}

					for(int k=0; k<rule.expr_body.size(); k++)
					{
						NonterminalExpression *expr=rule.expr_body[k];

						if(typeid(*expr)==typeid(NonterminalExpressionSymbol))
							rule.body.push_back(dynamic_cast<NonterminalExpressionSymbol *>(expr)->sn);
						else if(typeid(*expr)==typeid(NonterminalExpressionIteration))
							rule.body.push_back(SymbolNumber::for_nonterminal(dynamic_cast<NonterminalExpressionIteration *>(expr)->iterator_nn));
						else if(typeid(*expr)==typeid(NonterminalExpressionIterationPair))
							rule.body.push_back(SymbolNumber::for_nonterminal(dynamic_cast<NonterminalExpressionIterationPair *>(expr)->iterator_nn));
						else if(typeid(*expr)==typeid(NonterminalExpressionCreate) ||
							typeid(*expr)==typeid(NonterminalExpressionUpdate))
						{
							rule.body.push_back(make_creator_or_updater_or_use_existing_one(requested_rules, rule, k));
						}
						else if(typeid(*expr)==typeid(NonterminalExpressionCode))
						{
							NonterminalExpressionCode *expr_code=dynamic_cast<NonterminalExpressionCode *>(expr);

							if(expr_code->invoker_nn==-1)
							{
								int local_invoker_number=++data.nonterminals[i].number_of_invokers;
								expr_code->invoker_nn=make_invoker_or_creator_or_updater(i, j, local_invoker_number, 0, NonterminalData::INVOKER, expr_code->code);
								data.nonterminals[expr_code->invoker_nn].code_invoker_declaration=expr_code;
							}

							rule.body.push_back(SymbolNumber::for_nonterminal(expr_code->invoker_nn));
						}
						else if(typeid(*expr)==typeid(NonterminalExpressionConnectUp))
						{
							NonterminalExpressionConnectUp *expr_up=dynamic_cast<NonterminalExpressionConnectUp *>(expr);

							// in this version, all
							// of them are considered bad.
							bad_connect_up_operators.insert(expr_up);
							rule.expr_body.erase(rule.expr_body.begin()+k, rule.expr_body.begin()+k+1);
							k--;
						}
						else if(typeid(*expr)==typeid(NonterminalExpressionPrecedence))
						{
							NonterminalExpressionPrecedence *expr_pr=dynamic_cast<NonterminalExpressionPrecedence *>(expr);
							rule.precedence_expressions.push_back(expr_pr);
							rule.expr_body.erase(rule.expr_body.begin()+k, rule.expr_body.begin()+k+1);
							k--;
						}
						else
							assert(false);
					}

					assert(rule.body.size()==rule.expr_body.size());
					requested_rules.insert(rule);
				}
			}

			// note: no autoincrement in this for statement.
			for(set<RuleData>::const_iterator p=requested_rules.begin(); p!=requested_rules.end(); )
			{
				// looking for rules with the same body, they
				// should reside in the close vicinity.
				set<RuleData>::const_iterator p2;
				int count=0;
				map<int, int> how_many_rules_from_alternative;
				for(p2=p; p2!=requested_rules.end(); p2++, count++)
				{
					if(p2->body!=p->body)
						break;
					how_many_rules_from_alternative[p2->an]++;
				}
				assert(count>0);

				if(count>1)
				{
					bool more_than_one_from_single_alternative=(count>how_many_rules_from_alternative.size());
					bool different_alternatives=(how_many_rules_from_alternative.size()>1);

					cout << "Rule " << p->in_printable_form()
						<< " can be generated in " << english1_itoa(count, false)
						<< " different ways";
					if(different_alternatives || data.nonterminals[i].multiple_alternatives_mode)
					{
						if(different_alternatives)
							cout << ": ";

						for(map<int, int>::const_iterator p4=how_many_rules_from_alternative.begin(); p4!=how_many_rules_from_alternative.end(); p4++)
						{
							if(p4!=how_many_rules_from_alternative.begin())
							{
								map<int, int>::const_iterator p5=p4;
								p5++;
								if(p5!=how_many_rules_from_alternative.end())
									cout << "; ";
								else
									cout << " and ";
							}

							if(different_alternatives && more_than_one_from_single_alternative)
								cout << "in " << english1_itoa(p4->second, false)
									<< " way" << (p4->second==1 ? "" : "s")
									<< " from the " << english2_itoa(p4->first+1, false)
									<< " alternative";
							else
								cout << "from the " << english2_itoa(p4->first+1, false) << " alternative";
						}

						cout << ".\n";
					}
					else
						cout << ".\n";
				}

				data.rules.push_back(*p);
				p=p2;
			}
		}
		else if(category==NonterminalData::START)
		{
			assert(!i);

			RuleData rule(i, 0);
			rule.body.push_back(SymbolNumber::for_nonterminal(data.start_nonterminal_number));
			data.rules.push_back(rule);
		}
		else if(category==NonterminalData::ITERATOR)
		{
			ClassHierarchy::Class *type=data.nonterminals[i].type;
			assert(type);

			if(type->template_parameters.size()==1)
			{
				RuleData rule1(i, 0);
				rule1.body.push_back(type->template_parameters[0]->assigned_to);
				data.rules.push_back(rule1);

				RuleData rule2(i, 0);
				rule2.body.push_back(SymbolNumber::for_nonterminal(i));
				rule2.body.push_back(type->template_parameters[0]->assigned_to);
				data.rules.push_back(rule2);
			}
			else if(type->template_parameters.size()==2)
			{
				RuleData rule1(i, 0);
				rule1.body.push_back(type->template_parameters[0]->assigned_to);
				data.rules.push_back(rule1);

				RuleData rule2(i, 0);
				rule2.body.push_back(SymbolNumber::for_nonterminal(i));
				rule2.body.push_back(type->template_parameters[1]->assigned_to);
				rule2.body.push_back(type->template_parameters[0]->assigned_to);
				data.rules.push_back(rule2);
			}
			else
				assert(false);
		}
		else if(category==NonterminalData::CREATOR || category==NonterminalData::UPDATER)
		{
			RuleData rule(i, 0);

			// rule.body=epsilon

			data.rules.push_back(rule);
		}
		else if(category==NonterminalData::INVOKER)
		{
			RuleData rule(i, 0);

			// rule.body=epsilon
		//	cout << data.nonterminals[i].name << "\n";
			assert(data.nonterminals[i].code_invoker_declaration);
			rule.code_to_execute_upon_reduce=data.nonterminals[i].code_invoker_declaration;

			data.rules.push_back(rule);
		}
		else
			assert(false);

		data.nonterminals[i].last_rule=data.rules.size();
	#ifdef DEBUG_RULE_NUMBERS
		cout << data.nonterminals[i].name << ": " << data.nonterminals[i].first_rule << " " << data.nonterminals[i].last_rule << "\n";
	#endif
		assert((data.nonterminals[i].last_rule>data.nonterminals[i].first_rule) ||
			(category==NonterminalData::NORMAL && data.nonterminals[i].alternatives.size()==0));
	}

	if(bad_connect_up_operators.size()>0)
	{
		vector<Terminal *> v;
		for(set<NonterminalExpressionConnectUp *>::const_iterator p=bad_connect_up_operators.begin(); p!=bad_connect_up_operators.end(); p++)
			v.push_back((*p)->kw);

		cout << "The current version of Whale doesn't support "
			<< "connect_up operators other than in the rightmost "
			<< "position in rule; thus, declaration"
			<< (bad_connect_up_operators.size()==1 ? " " : "s ");
		print_a_number_of_terminal_locations(cout, v, "at");
		cout << (bad_connect_up_operators.size()==1 ? " is " : " are ")
			<< "invalid.\n";
		flag=false;
	}

	cout << data.terminals.size() << " terminals, ";
	cout << data.nonterminals.size() << " nonterminals, ";
	cout << classes.total_classes << " classes, ";
	cout << classes.total_data_members << " data members";
	cout << ".\n";

	cout << data.rules.size() << " context-free rules created.\n";

	if(data.variables.dump_grammar_to_file)
	{
		string grammar_file_name=data.file_name+string(".grammar");
		ofstream grammar_file(grammar_file_name.c_str());
		print_grammar(grammar_file);
	}

	build_create_and_update_operator_locations_and_source_rules_database();

	return flag;
}

void print_grammar(ostream &os)
{
	os << "\tContext-free grammar:\n";
	for(int i=0; i<data.rules.size(); i++)
		os << data.rules[i].in_printable_form() << "\n";
}

template<class T> set<vector<T> > concatenate_sets_of_vectors(const set<vector<T> > &s1, const set<vector<T> > &s2)
{
	set<vector<T> > result;

	for(set<vector<T> >::const_iterator p1=s1.begin(); p1!=s1.end(); p1++)
		for(set<vector<T> >::const_iterator p2=s2.begin(); p2!=s2.end(); p2++)
		{
			vector<T> v(*p1);
			copy((*p2).begin(), (*p2).end(), back_inserter(v));
			result.insert(v);
		}

	return result;