precedence.cpp.svn-base

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

#include "whale.h"
#include "precedence.h"
#include "parser.h"
#include "process.h"
//#include "stl.h"
#include "utilities.h"

#include <fstream>

using namespace std;
using namespace Whale;

// NB: comparisons with asterisk are not transitive.

//#define DEBUG_CONFLICT_RESOLUTION

bool acquire_new_precedence_symbols();
int acquire_single_precedence_symbol(Terminal *t_name, Terminal *t_assoc, bool can_create_new_symbols, bool can_use_existing_symbols);
bool acquire_relations_between_precedence_symbols(vector<triad<int, Terminal *, int> > &relation_statements);
void set_default_associativity();

bool process_precedence()
{
	bool flag=true;

	bool keep_log=data.variables.dump_precedence_to_file;
	ofstream log;
	if(keep_log)
	{
		string log_file_name=data.file_name+string(".prec");
		log.open(log_file_name.c_str());
		log << "Precedence.\n\n";
	}

	vector<triad<int, Terminal *, int> > relation_statements;

	if(!acquire_new_precedence_symbols())
		return false;

	if(!acquire_relations_between_precedence_symbols(relation_statements))
		return false;

	set_default_associativity();

	if(data.precedence_symbols.size() || relation_statements.size()>0)
		cout << data.precedence_symbols.size() << " precedence symbols, "
			<< relation_statements.size() << " relations.\n";
	if(keep_log)
	{
		log << data.precedence_symbols.size() << " precedence symbols, "
			<< relation_statements.size() << " relations.\n\n";

		for(int i=0; i<data.precedence_symbols.size(); i++)
			log << data.precedence_symbols[i].name << "\n";
		log << "\n";
	}

	data.precedence_database.initialize(data.precedence_symbols.size());

	for(int i=0; i<relation_statements.size(); i++)
	{
		triad<int, Terminal *, int> t=relation_statements[i];

		// should deal with asteriskness in some other way!
		if(t.first==-1 || t.third==-1) continue;

		if(typeid(*t.second)==typeid(TerminalEqual) ||
			typeid(*t.second)==typeid(TerminalAssign))
		{
			data.precedence_database.access_equivalence_relation(t.first, t.third)=true;
		}
		else if(typeid(*t.second)==typeid(TerminalLessThan))
			data.precedence_database.access_partial_order_relation(t.first, t.third)=true;
		else if(typeid(*t.second)==typeid(TerminalGreaterThan))
			data.precedence_database.access_partial_order_relation(t.third, t.first)=true;
		else
			assert(false);
	}

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

			if(rule.precedence_symbol_number>=0)
				log << "Rule " << rule.in_printable_form()
					<< " has precedence "
					<< data.precedence_symbols[rule.precedence_symbol_number].name
					<< ".\n";
		}

		log << "\n\tBefore closure.\n";
		data.precedence_database.print_tables(log);
	}

	data.precedence_database.closure();

	if(keep_log)
	{
		log << "\n\tAfter closure.\n";
		data.precedence_database.print_tables(log);
		log << "\n";

		for(int i=0; i<data.precedence_database.n; i++)
			for(int j=0; j<data.precedence_database.n; j++)
				if(data.precedence_database.partial_order_relation[i][j])
					log << data.precedence_symbols[i].name << " < " << data.precedence_symbols[j].name << "\n";
	}

	set<int> precedence_symbols_we_have_problems_with;
	for(int i=0; i<data.precedence_symbols.size(); i++)
	{
		bool less_than_self=data.precedence_database.access_partial_order_relation(i, i);
		if(less_than_self)
			precedence_symbols_we_have_problems_with.insert(i);
	}
	if(precedence_symbols_we_have_problems_with.size())
	{
		cout << "Inconsistent precedence information: something is "
			"wrong somewhere around symbol"
			<< (precedence_symbols_we_have_problems_with.size()==1 ? " " : "s ");
		custom_print(cout, precedence_symbols_we_have_problems_with.begin(), precedence_symbols_we_have_problems_with.end(), PrecedenceNamePrinter(), ", ", " and ");
		cout << ".\n";
		flag=false;
	}

	return flag;
}

bool acquire_new_precedence_symbols()
{
	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)
				{
					Terminal *t=precedence_statement.expr[j]->operands[0];
					Terminal *t_assoc=precedence_statement.expr[j]->associativity[0];
					int psn=acquire_single_precedence_symbol(t, t_assoc, true, false);
					if(psn==-1) flag=false;
				}
			}
		}

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

		bool there_are_comparisons=false;
		set<int> lone_precedence_symbols;

		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]==NULL)
				{
					Terminal *t=rule.precedence_expressions[j]->operands[k];
					int psn=acquire_single_precedence_symbol(t, NULL, true, true);
					if(psn==-1)
						flag=false;
					else
						lone_precedence_symbols.insert(psn);
				//	cout << "\t" << t->text << "\n";
				}
				else
				{
					Terminal *t=rule.precedence_expressions[j]->operands[k];
					int psn=acquire_single_precedence_symbol(t, NULL, true, true);
					if(psn==-1) flag=false;
					there_are_comparisons=true;
				}

		if(lone_precedence_symbols.size()==0)
		{
			if(there_are_comparisons)
			{
				// Create a new precedence symbol for this rule
				string s=string("Rule")+roman_itoa(i+1, true);

				PrecedenceSymbolData precedence_symbol;
				precedence_symbol.name=strdup(s.c_str());
				// *** change ***
				precedence_symbol.declared_at=NULL;
				precedence_symbol.was_implicitly_declared=true;

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

				rule.precedence_symbol_number=new_psn;
			}
		}
		else if(lone_precedence_symbols.size()==1)
		{
			// everything's clear: just assign this precedence symbol
			// to the rule

			rule.precedence_symbol_number=*lone_precedence_symbols.begin();
		}
		else if(lone_precedence_symbols.size()>1)
		{
			cout << "Warning (*** change me ***): unexpected artistry "
				"with precedence symbols somewhere around ";
			rule.precedence_expressions[0]->operands[0]->print_location(cout);
			cout << ".\n";
			rule.precedence_symbol_number=*lone_precedence_symbols.begin();
		}
	}

	return flag;
}

// returns precedence symbol number upon success, -1 upon failure
int acquire_single_precedence_symbol(Terminal *t_name, Terminal *t_assoc, bool can_create_new_symbols, bool can_use_existing_symbols)
{
	assert(can_create_new_symbols || can_use_existing_symbols);

	if(!strcmp(t_name->text, "*")) // by now, all uses of the asterisk are invalid
	{
		cout << "Invalid use of asterisk at ";
		t_name->print_location(cout);
		cout << ".\n";
		return -1;
	}

	PrecedenceSymbolData::Associativity associativity_given;
	if(t_assoc)
	{
		if(!strcmp(t_assoc->text, "left"))
			associativity_given=PrecedenceSymbolData::ASSOC_LEFT;
		else if(!strcmp(t_assoc->text, "none"))
			associativity_given=PrecedenceSymbolData::ASSOC_NONE;
		else if(!strcmp(t_assoc->text, "right"))
			associativity_given=PrecedenceSymbolData::ASSOC_RIGHT;
		else
		{
			cout << "Invalid associativity at ";
			t_assoc->print_location(cout);
			cout << ": expecting 'left', 'right' or 'none'.\n";
			return -1;
		}
	}
	else
		associativity_given=PrecedenceSymbolData::ASSOC_UNDEFINED;

	int psn=data.find_precedence_symbol(t_name->text);
	if(psn!=-1)
	{
		if(can_use_existing_symbols)
		{
			if(t_assoc && data.precedence_symbols[psn].associativity!=PrecedenceSymbolData::ASSOC_UNDEFINED &&
				associativity_given!=PrecedenceSymbolData::ASSOC_UNDEFINED &&
				data.precedence_symbols[psn].associativity!=associativity_given)
			{
				cout << "Associativity declaration for ";
				cout << "precedence symbol " << t_name->text << " at ";
				t_assoc->print_location(cout);
				cout << " doesn't match previous declaration at ";
				data.precedence_symbols[psn].declared_at->print_location(cout);
				cout << ".\n";
				return -1;
			}
			return psn;
		}
		else
		{
			PrecedenceSymbolData &precedence_symbol=data.precedence_symbols[psn];
			cout << "Precedence symbol " << precedence_symbol.name << ", ";
			precedence_symbol.print_where_it_was_declared(cout);
			cout << ", cannot be redeclared at ";
			t_name->print_location(cout);
			cout << ".\n";
			return -1;
		}
	}

	int nn=data.find_nonterminal(t_name->text);
	if(nn!=-1)
	{
		cout << "Symbol already in use (WRITE ME!) at ";
		t_name->print_location(cout);
		cout << ".\n";
		return -1;
	}

	int tn=data.find_terminal(t_name->text);

	if(tn==-1 && !can_create_new_symbols)
	{
		cout << "Reference to undefined precedence symbol "
			<< t_name->text << " at ";
		t_name->print_location(cout);
		cout << ".\n";
		return -1;
	}

	PrecedenceSymbolData precedence_symbol;
	precedence_symbol.name=t_name->text;
	precedence_symbol.associativity=associativity_given;

	if(tn!=-1 && !can_create_new_symbols)
	{
		TerminalData &terminal=data.terminals[tn];

		precedence_symbol.declared_at=terminal.declaration;