grammar.cpp.svn-base

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

}

template<class T> inline set<vector<T> > set_consisting_of_a_single_one_element_vector(const T &x)
{
	set<vector<T> > result;
	vector<T> v;
	v.push_back(x);
	result.insert(v);
	return result;
}

template<class T> inline set<vector<T> > set_consisting_of_a_single_empty_vector()
{
	set<vector<T> > result;
	result.insert(vector<T>());
	return result;
}

set<vector<NonterminalExpression *> > make_rules_proc(NonterminalExpression *expr)
{
	if(typeid(*expr)==typeid(NonterminalExpressionDisjunction))
	{
		NonterminalExpressionDisjunction &expr_d=*dynamic_cast<NonterminalExpressionDisjunction *>(expr);
		set<vector<NonterminalExpression *> > result=make_rules_proc(expr_d.expr1);
		union_assign(result, make_rules_proc(expr_d.expr2));
		return result;
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionConjunction))
	{
		NonterminalExpressionConjunction &expr_c=*dynamic_cast<NonterminalExpressionConjunction *>(expr);
		assert(false);
		return set<vector<NonterminalExpression *> >();
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionConcatenation))
	{
		NonterminalExpressionConcatenation &expr_cat=*dynamic_cast<NonterminalExpressionConcatenation *>(expr);
		return concatenate_sets_of_vectors(make_rules_proc(expr_cat.expr1), make_rules_proc(expr_cat.expr2));
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionComplement))
	{
		NonterminalExpressionComplement &expr_com=*dynamic_cast<NonterminalExpressionComplement *>(expr);
		assert(false);
		return set<vector<NonterminalExpression *> >();
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionOmittable))
	{
		NonterminalExpressionOmittable &expr_om=*dynamic_cast<NonterminalExpressionOmittable *>(expr);
		set<vector<NonterminalExpression *> > result=make_rules_proc(expr_om.expr);
		result.insert(vector<NonterminalExpression *>()); // {epsilon}
		return result;
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionInParentheses))
	{
		NonterminalExpressionInParentheses &expr_p=*dynamic_cast<NonterminalExpressionInParentheses *>(expr);
		return make_rules_proc(expr_p.expr);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionIteration))
	{
		NonterminalExpressionIteration &expr_it=*dynamic_cast<NonterminalExpressionIteration *>(expr);
		set<vector<NonterminalExpression *> > result;

		vector<NonterminalExpression *> v;
		v.push_back(&expr_it);
		result.insert(v);

		if(expr_it.reflexive)
			result.insert(vector<NonterminalExpression *>()); // {epsilon}

		return result;
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionIterationPair))
	{
		NonterminalExpressionIterationPair &expr_it2=*dynamic_cast<NonterminalExpressionIterationPair *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_it2);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionEpsilon))
	{
		return set_consisting_of_a_single_empty_vector<NonterminalExpression *>();
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionSymbol))
	{
		NonterminalExpressionSymbol &expr_s=*dynamic_cast<NonterminalExpressionSymbol *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_s);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionMemberName))
	{
		NonterminalExpressionMemberName &expr_mn=*dynamic_cast<NonterminalExpressionMemberName *>(expr);
		return make_rules_proc(expr_mn.expr);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionCreate))
	{
		NonterminalExpressionCreate &expr_create=*dynamic_cast<NonterminalExpressionCreate *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_create);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionUpdate))
	{
		NonterminalExpressionUpdate &expr_update=*dynamic_cast<NonterminalExpressionUpdate *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_update);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionConnectUp))
	{
		NonterminalExpressionConnectUp &expr_up=*dynamic_cast<NonterminalExpressionConnectUp *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_up);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionCode))
	{
		NonterminalExpressionCode &expr_code=*dynamic_cast<NonterminalExpressionCode *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_code);
	}
	else if(typeid(*expr)==typeid(NonterminalExpressionPrecedence))
	{
		NonterminalExpressionPrecedence &expr_pr=*dynamic_cast<NonterminalExpressionPrecedence *>(expr);
		return set_consisting_of_a_single_one_element_vector<NonterminalExpression *>(&expr_pr);
	}
	else
	{
		assert(false);
		return set<vector<NonterminalExpression *> >();
	}
}

int find_creator_or_updater_in_rule(const RuleData &rule, int pos)
{
	assert(rule.body.size()>pos);
	for(int i=pos; i>=0; i--)
		if(rule.body[i].is_nonterminal())
		{
			NonterminalData &nonterminal=data.nonterminals[rule.body[i].nonterminal_number()];
			if(nonterminal.category==NonterminalData::CREATOR || nonterminal.category==NonterminalData::UPDATER)
				return i;
		}
	return -1;
}

// 'requested_rules' is a set of all rules already made for this alternative of
// this nonterminal. 'rule' is the current rule; its body is incomplete. The
// symbol returned by this function shall be appended to the end or rule body
// by the caller.
// TO DO: if there are no symbols for this creator or updater to process, then
// remove it.
SymbolNumber make_creator_or_updater_or_use_existing_one(const set<RuleData> &requested_rules, RuleData &rule, int last1)
{
	NonterminalExpressionCreate *expr_create=dynamic_cast<NonterminalExpressionCreate *>(rule.expr_body[last1]);
	NonterminalExpressionUpdate *expr_update=dynamic_cast<NonterminalExpressionUpdate *>(rule.expr_body[last1]);
	assert((expr_create!=NULL) ^ (expr_update!=NULL));

#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
	cout << "make_creator_or_updater_or_use_existing_one(): " << rule.in_printable_form() << "\n";
#endif

	// Looking for an existing creator or updater that could be used here.

	int first1;
	if(expr_create)
		first1=0;
	else if(expr_update)
	{
		first1=find_creator_or_updater_in_rule(rule, last1-1);
		assert(first1!=-1);
	}
	else
		assert(false);

#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
	cout << "\tfirst1=" << first1 << ", last1=" << last1 << "\n";
#endif

	for(set<RuleData>::const_iterator p=requested_rules.begin(); p!=requested_rules.end(); p++)
	{
		if(rule.an!=p->an)
			continue;

		int last2=-1;
		for(int i=0; i<p->expr_body.size(); i++)
			if(p->expr_body[i]==rule.expr_body[last1])
			{
				last2=i;
				break;
			}
		if(last2==-1)
			continue;

	#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
		cout << "\tConsidering " << data.full_symbol_name(p->body[last2], false)
			<< " in rule " << p->in_printable_form() << "\n";
	#endif

		int first2;
		if(expr_create)
			first2=0;
		else if(expr_update)
		{
			first2=find_creator_or_updater_in_rule(*p, last2-1);
			assert(first2!=-1);
		}
		else
			assert(false);
	#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
		cout << "\t\tfirst2=" << first2 << ", last2=" << last2 << "\n";
	#endif

		if(last1-first1 != last2-first2)
		{
		#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
			cout << "\t\tLength mismatch.\n";
		#endif
			continue;
		}

		bool ok_flag=true;
		for(int i=last1-1, j=last2-1; i>=first1; i--, j--)
			if(rule.expr_body[i]!=p->expr_body[j])
			{
			#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
				cout << "\t\tMismatch in position (" << i << ", " << j << ")\n";
			#endif
				ok_flag=false;
				break;
			}

		if(ok_flag)
		{
			#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
				cout << "\t\tReusing " << data.full_symbol_name(p->body[last2], false) << "\n";
			#endif
			return p->body[last2];
		}
	}

	// Creating a new creator or updater.

	int symbol_nn;
	if(expr_create)
	{
		if(expr_create->creator_nn.size()==0)
			expr_create->local_creator_number=++data.nonterminals[rule.nn].number_of_creators;
		symbol_nn=make_invoker_or_creator_or_updater(rule.nn, rule.an, expr_create->local_creator_number, expr_create->creator_nn.size()+1, NonterminalData::CREATOR, expr_create->kw);
		expr_create->creator_nn.push_back(symbol_nn);
	}
	else if(expr_update)
	{
		if(expr_update->updater_nn.size()==0)
			expr_update->local_updater_number=++data.nonterminals[rule.nn].number_of_updaters;
		symbol_nn=make_invoker_or_creator_or_updater(rule.nn, rule.an, expr_update->local_updater_number, expr_update->updater_nn.size()+1, NonterminalData::UPDATER, expr_update->kw);
		expr_update->updater_nn.push_back(symbol_nn);
	}
	else
		assert(false);

#ifdef DEBUG_MAKE_CREATOR_OR_UPDATER_OR_USE_EXISTING_ONE
	cout << "\t\tCreating nonterminal " << data.nonterminals[symbol_nn].name << "\n";
#endif

	return SymbolNumber::for_nonterminal(symbol_nn);
}

bool operator <(const RuleData &r1, const RuleData &r2)
{
	// the order of comparison is really important.
	if(r1.nn<r2.nn) return true;
	if(r1.nn>r2.nn) return false;
	if(r1.body<r2.body) return true;
	if(r1.body>r2.body) return false;
	if(r1.an<r2.an) return true;
	if(r1.an>r2.an) return false;
	if(r1.expr_body<r2.expr_body) return true;
	if(r1.expr_body>r2.expr_body) return false;
	return r1.precedence_expressions<r2.precedence_expressions;
}

void build_create_and_update_operator_locations_and_source_rules_database()
{
//	cout << "build_creator_and_updater_source_rules_database()\n";
	for(int i=0; i<data.rules.size(); i++)
	{
		RuleData &rule=data.rules[i];

		for(int j=0; j<rule.body.size(); j++)
		{
			SymbolNumber sn=rule.body[j];

			if(sn.is_nonterminal())
			{
				NonterminalData::Category category=data.nonterminals[sn.nonterminal_number()].category;

				if(category==NonterminalData::CREATOR || category==NonterminalData::UPDATER)
				{
				//	cout << data.symbol_name(sn) << " in " << rule.in_printable_form() << "\n";
					rule.create_and_update_operator_locations.push_back(j);
				}
				if(category==NonterminalData::CREATOR)
				{
					int nn=sn.nonterminal_number();

					AlternativeData &alternative=data.access_alternative(rule.nn, rule.an);
					if(find(alternative.creator_nn.begin(), alternative.creator_nn.end(), nn)==alternative.creator_nn.end())
						alternative.creator_nn.push_back(nn);

					if(rule.creator_nn==-1)
						rule.creator_nn=nn;
					else if(rule.creator_nn!=nn)
					{
						cout << "\n\n\t\tUnexpected internal error:\n\n";
						cout << "Found " << data.nonterminals[nn].name
							<< " in rule " << rule.in_printable_form()
							<< ", " << data.nonterminals[rule.creator_nn].name
							<< " expected.\n";
						assert(false);
					}
				}
				if(data.nonterminals[sn.nonterminal_number()].is_ancillary)
				{
					data.nonterminals[sn.nonterminal_number()].rules_where_ancillary_symbol_is_used.push_back(i);
				}
			}
		}
	}
}