precedence.cpp.svn-base

Complete support for EBNF notation; Object-oriented parser design; C++ output; Deterministic bottom-

		precedence_symbol.was_implicitly_declared=true;
	}
	else
		precedence_symbol.declared_at=t_name;

	int new_psn=data.precedence_symbols.size();
	data.precedence_symbols.push_back(precedence_symbol);

	return new_psn;
}

bool acquire_relations_between_precedence_symbols(vector<triad<int, Terminal *, int> > &relation_statements)
{
	bool flag=true;

	for(int i=0; i<data.S->statements.size(); i++)
		if(typeid(*data.S->statements[i])==typeid(NonterminalPrecedenceStatement))
		{
			NonterminalPrecedenceStatement &precedence_statement=*dynamic_cast<NonterminalPrecedenceStatement *>(data.S->statements[i]);

			for(int j=0; j<precedence_statement.expr.size(); j++)
			{
				int m=precedence_statement.expr[j]->operands.size();

				if(m>1)
				{
					vector<int> these_psn;
					bool local_flag=true;
					for(int k=0; k<m; k++)
					{
						Terminal *t=precedence_statement.expr[j]->operands[k];
						Terminal *t_assoc=precedence_statement.expr[j]->associativity[k];
						if(!strcmp(t->text, "*"))
							these_psn.push_back(-1);
						else
						{
							int psn=acquire_single_precedence_symbol(t, t_assoc, false, true);
							if(psn!=-1)
								these_psn.push_back(psn);
							else
								local_flag=false;
						}
					}
					if(local_flag==false)
					{
						flag=false;
						continue;
					}

					for(int k=0; k<m-1; k++)
						relation_statements.push_back(make_triad(these_psn[k], precedence_statement.expr[j]->comparison_operators[k], these_psn[k+1]));
				}
			}
		}

	for(int i=0; i<data.rules.size(); i++)
	{
		RuleData &rule=data.rules[i];

		if(rule.precedence_symbol_number==-1)
		{
			int tn=-1;
			for(int j=rule.body.size()-1; j>=0; j--)
				if(rule.body[j].is_terminal())
				{
					tn=rule.body[j].terminal_number();
					break;
				}

			if(tn!=-1)
				rule.precedence_symbol_number=data.find_precedence_symbol(data.terminals[tn].name);
		}

		for(int j=0; j<rule.precedence_expressions.size(); j++)
			for(int k=0; k<rule.precedence_expressions[j]->operands.size(); k++)
				if(rule.precedence_expressions[j]->comparison_operators[k])
				{
					assert(rule.precedence_symbol_number>=0);

					Terminal *t_x=rule.precedence_expressions[j]->operands[k];
					Terminal *t_sign=rule.precedence_expressions[j]->comparison_operators[k];

					int psn=data.find_precedence_symbol(t_x->text);
					if(psn==-1)
					{
						// if I'm not mistaken, the
						// error message have already
						// been printed out.
						flag=false;
						continue;
					}

					relation_statements.push_back(make_triad(rule.precedence_symbol_number, t_sign, psn));
				}
	}

	return flag;
}

void set_default_associativity()
{
	for(int i=0; i<data.precedence_symbols.size(); i++)
	{
		PrecedenceSymbolData &ps=data.precedence_symbols[i];

		if(ps.associativity==PrecedenceSymbolData::ASSOC_UNDEFINED)
			ps.associativity=PrecedenceSymbolData::ASSOC_LEFT;
	}
}

// rv.first: are we sure, rv.second: -1 for shift, 0+ for reduce.
pair<bool, int> resolve_lr_conflict(int shift_terminal, int shift_state, const vector<int> &reduce_rules)
{
	// ought to rewrite the whole function: it was a bad idea to
	// unload all input values to those vectors.

	assert(reduce_rules.size()>0 || shift_terminal!=-1);

#ifdef DEBUG_CONFLICT_RESOLUTION
	cout << "Processing LR conflict: shift " << shift_terminal
		<< ", reduce " << reduce_rules << "\n";
#endif

	vector<int> priorities;
	vector<LRAction> actions;
	if(shift_terminal!=-1)
	{
		TerminalData &terminal=data.terminals[shift_terminal];
		int psn=data.find_precedence_symbol(terminal.name);
	#ifdef DEBUG_CONFLICT_RESOLUTION
		cout << "For Shift: " << psn << "\n";
	#endif
		priorities.push_back(psn); // possibly -1.
		actions.push_back(LRAction::shift(shift_state));
	}
	for(int i=0; i<reduce_rules.size(); i++)
	{
		priorities.push_back(data.rules[reduce_rules[i]].precedence_symbol_number);
	#ifdef DEBUG_CONFLICT_RESOLUTION
		cout << "For Reduce: " << priorities.back() << "\n";
	#endif
		actions.push_back(LRAction::reduce(reduce_rules[i]));
	}

	// How does 'associativity' influence conflict resolution:
	// If a is left-associative, it means that for each b: a~b
	//		Shift a   <   Reduce R (precedence b)
	// If a is right-associative, it means that for each b: a~b
	//		Shift a   >   Reduce R (precedence b)
	// Only shift-reduce conflicts may be resolved using associativity.

	// Note: if a~b, then a and b should have the same associativity.

	// Trying to find an action with highest precedence.
	for(int i=0; i<priorities.size(); i++)
	{
		// Suppose action[i] has the highest precedence.
	#ifdef DEBUG_CONFLICT_RESOLUTION
		cout << "Suppose " << priorities[i] << "\n";
	#endif

		bool success_flag=true;
		for(int j=0; j<priorities.size(); j++)
		{
			if(i==j) continue;
		#ifdef DEBUG_CONFLICT_RESOLUTION
			cout << "\tConsider " << priorities[j] << "\n";
		#endif

			if(priorities[i]==-1 || priorities[j]==-1)
			{
			//	cout << "conflict resolution: the bad thing.\n";
				success_flag=false;
				break;
			}
			else if(data.precedence_database.access_partial_order_relation(priorities[j], priorities[i]))
			{
				// action[i] > action[j] - quite coherent with
				// our hypothesis.
			}
			else if(data.precedence_database.access_equivalence_relation(priorities[i], priorities[j]))
			{
				// action[i] ~ action[j]. Depends upon
				// associativity.

				if(actions[i].is_shift() && actions[j].is_reduce() &&
					data.precedence_symbols[priorities[i]].associativity==PrecedenceSymbolData::ASSOC_RIGHT)
				{
					// right associativity ==> shift
					// has greater precedence ==> satisfies
					// the hypothesis.
				}
				else if(actions[i].is_reduce() && actions[j].is_shift() &&
					data.precedence_symbols[priorities[j]].associativity==PrecedenceSymbolData::ASSOC_LEFT)
				{
					// left associativity ==> shift has
					// less precedence ==> satisfies the
					// hypothesis.
				}
				else
				{
					success_flag=false;
					break;
				}
			}
			else
			{
				// This example disproves our hypothesis.
				success_flag=false;
				break;
			}
		}

		if(success_flag)
		{
			if(actions[i].is_shift())
				return make_pair(true, -1);
			else if(shift_state==-1)
				return make_pair(true, i);
			else
				return make_pair(true, i-1);
		}
	}

	return make_pair(false, (shift_state>=0 ? -1 : 0));
}

void PrecedenceDatabase::initialize(int supplied_n)
{
	n=supplied_n;
	equivalence_relation.destructive_resize(n, n);
	partial_order_relation.destructive_resize(n, n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
		{
			equivalence_relation[i][j]=false;
			partial_order_relation[i][j]=false;
		}
}

void PrecedenceDatabase::closure()
{
	for(int i=0; i<n; i++)
		equivalence_relation[i][i]=true;

	bool flag=true;

	while(flag)
	{
		flag=false;

		for(int i=0; i<n; i++)
			for(int j=0; j<n; j++)
			{
				if(equivalence_relation[i][j] &&
					!equivalence_relation[j][i])
				{
					equivalence_relation[j][i]=true;
					flag=true;
				}

				for(int k=0; k<n; k++)
				{
					if(!equivalence_relation[i][k] &&
						equivalence_relation[i][j] &&
						equivalence_relation[j][k])
					{
						equivalence_relation[i][k]=true;
						flag=true;
					}
					if(!partial_order_relation[i][k] &&
						partial_order_relation[i][j] &&
						partial_order_relation[j][k])
					{
						partial_order_relation[i][k]=true;
						flag=true;
					}
					if(!partial_order_relation[i][k] &&
						partial_order_relation[i][j] &&
						equivalence_relation[j][k])
					{
						partial_order_relation[i][k]=true;
						flag=true;
					}
					if(!partial_order_relation[i][k] &&
						equivalence_relation[i][j] &&
						partial_order_relation[j][k])
					{
						partial_order_relation[i][k]=true;
						flag=true;
					}
				}
			}
	}
}

void PrecedenceDatabase::print_tables(ostream &os)
{
	os << "Equivalence relation:\n";
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
			os << equivalence_relation[i][j] << " ";
		os << "\n";
	}
	os << "Partial order relation:\n";
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
			os << partial_order_relation[i][j] << " ";
		os << "\n";
	}
}