lr.cpp.svn-base

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

#include <fstream>
#include <stdio.h>
#include "whale.h"
#include "lr.h"
#include "precedence.h"
#include "utilities.h"
using namespace std;

#include <automata_builder/lr0.h>
#include <automata_builder/lr1.h>
#include <automata_builder/lr1_tables.h>
#include <automata_builder/conflicts.h>
#include <automata_builder/minimal_expansion.h>
#include <automata_builder/stack_context.h>

#include "precedence.h"

void print_conflicts(const Automata_builder::LR1_conflicts& conflicts,
	const Automata_builder::Minimal_expansion& min_exp,
	const Automata_builder::Stack_context& context, int num_states);

class Whale_conflict_resolver : public Automata_builder::LR1_conflict_resolver
{
public:
	std::pair<bool, int> resolve(Automata_builder::Symbol lookahead,
		int next_state, const std::vector<int>& reduces) const
	{
		int terminal_number=((next_state==-1) ? -1 : lookahead.terminal_number()+1);
		vector<int> adjusted_reduces(reduces);
		for(int i=0; i<adjusted_reduces.size(); i++)
			adjusted_reduces[i]++;

		return resolve_lr_conflict(terminal_number, next_state, adjusted_reduces);
	}
};

Automata_builder::Symbol map_symbol(const SymbolNumber& n)
{
	if(n.is_terminal())
	{
		// Pretend there's no such thing as eof

		return Automata_builder::Terminal(n.terminal_number()-1);
	}
	else
	{
		// Likewise, ignore S' existence

		return Automata_builder::Nonterminal(n.nonterminal_number()-1);
	}
}

Automata_builder::Grammar convert_grammar(const WhaleData& w)
{
	assert(w.eof_terminal_number == 0);

	using namespace Automata_builder;

	Automata_builder::Grammar result;

	// Ignore S' -> S rule.
	result.rules.resize(w.rules.size()-1);
	for(int i=1; i<w.rules.size(); i++)
	{
		result.rules[i-1].left=Nonterminal(w.rules[i].nn-1);

		for(int j=0; j<w.rules[i].body.size(); j++)
			result.rules[i-1].right.push_back(map_symbol(w.rules[i].body[j]));
	}

	for(int i=1; i<w.terminals.size(); i++)
		result.terminals.push_back(w.terminals[i].name);

	for(int i=1; i<w.nonterminals.size(); i++)
		result.nonterminals.push_back(w.nonterminals[i].name);

	result.grammar_start=Nonterminal(w.start_nonterminal_number-1);

	return result;
}

void store_tables(const Automata_builder::LR1_tables& tables)
{
#ifdef WHALE_DEBUG
	cout << "Tables constructed. Handing them back.\n";
#endif

	using namespace Automata_builder;

	data.lr_automaton.states.resize(tables.states_count());
	for(int i=0; i<tables.states_count(); i++)
	{
		vector<int> &actions=data.lr_automaton.states[i].action_table;
		vector<int> &gotos=data.lr_automaton.states[i].goto_table;

		actions.resize(tables.terminals_count());
		for(int j=0; j<tables.terminals_count(); j++)
		{
			LRAction ta;
			LR1_tables::LR_action sa=tables.actions(i, Symbol::from_int(j));

			if(sa.is_error())
				ta=LRAction::error();
			else if (sa.is_shift())
				ta=LRAction::shift(sa.shift_state());
			else if (sa.is_reduce())
				ta=LRAction::reduce(sa.reduce_rule()+1);
			else if (sa.is_accept())
				ta=LRAction::accept();

			actions[j]=ta.get_n();
		}

		gotos.resize(data.nonterminals.size());
		gotos[0]=-1;
		for(int j=1; j<data.nonterminals.size(); j++)
		{
			int g=tables.gotos(i, Nonterminal(j-1));
			gotos[j]=((g==LR1_tables::no_goto) ? -1 : g);
		}
	}
}

void build_automaton()
{
	using namespace Automata_builder;

	Automata_builder::Grammar g = convert_grammar(data);

#ifdef WHALE_DEBUG
	cout << "LR library comes into play! Say your prayers!\n";
	cout << "Grammar is\n";
	cout << g << "\n";
#endif

	if (data.variables.method == Variables::LR1)
	{
		LR1_data lr1_data(g);

	#ifdef WHALE_DEBUG
		dump_lr1_automaton(cout, lr1_data);
	#endif

		construct_tables(lr1_data, Whale_conflict_resolver());
		store_tables(lr1_data.tables());

		if(data.variables.dump_lr_automaton_to_file)
		{
			ofstream os((data.file_name + string(".lr1")).c_str());
			dump_lr1_automaton(os, lr1_data);
		}

        print_conflicts(lr1_data.conflicts(), lr1_data.minimal_expansion(),
                        lr1_data.stack_context(), lr1_data.tables().states_count());
	}
	else if (data.variables.method == Variables::SLR1 ||
		data.variables.method == Variables::LALR1)
	{
		LR0_data lr0_data(g);

	#ifdef WHALE_DEBUG
		dump_lr0_automaton(cout, lr0_data);
	#endif

		if(data.variables.method==Variables::SLR1)
			compute_lookaheads_SLR1(lr0_data);
		else if(data.variables.method==Variables::LALR1)
			compute_lookaheads_LALR1(lr0_data);
		else
			assert(false);

		construct_tables(lr0_data, Whale_conflict_resolver());
		store_tables(lr0_data.tables());
		print_conflicts(lr0_data.conflicts(), lr0_data.minimal_expansion(),
			lr0_data.stack_context(), lr0_data.tables().states_count());

		if(data.variables.dump_canonical_conflicts)
		{
			ofstream ofs((data.file_name + string(".canonical_conflicts")).c_str());
			print_conflict_situations(ofs, lr0_data);
		}
		if(data.variables.dump_lr_automaton_to_file)
		{
			ofstream os((data.file_name + string(".lr0")).c_str());
			dump_automaton(os, lr0_data);
		}
		if (data.variables.dump_verbose_conflicts)
		{
			ofstream ofs((data.file_name + string(".verbose_conflicts")).c_str());
			print_verbose_conflicts(ofs, lr0_data);
		}
	}
	else
		assert(false);
}

LRAction process_lr_conflict(int this_state, int shift_terminal, int shift_state, const std::vector<int> &reduce_rules)
{
	if(shift_terminal<0 || shift_state<0)
		shift_terminal=-1, shift_state=-1;
	LRConflictResolutionPrecedent lr_crp(shift_terminal, reduce_rules);
	set<LRConflictResolutionPrecedent>::iterator p=data.lr_conflict_resolution_precedents.find(lr_crp);
	int action_number;
	if(p!=data.lr_conflict_resolution_precedents.end())
	{
		p->states_where_this_conflict_is_present.insert(this_state);
		action_number=p->action_we_took;
	}
	else
	{
		pair<bool, int> result=resolve_lr_conflict(shift_terminal, shift_state, reduce_rules);

		lr_crp.action_we_took=result.second;
		lr_crp.are_we_sure=result.first;
		lr_crp.states_where_this_conflict_is_present.insert(this_state);

		data.lr_conflict_resolution_precedents.insert(lr_crp);
		action_number=result.second;
	}

	if(action_number==-1)
		return LRAction::shift(shift_state);
	else if(action_number>=0)
		return LRAction::reduce(reduce_rules[action_number]);
	else
	{
		assert(false);
		return LRAction::error();
	}
}

void print_symbol(ostream& os, Automata_builder::Symbol s)
{
	if (s.is_terminal())
		os << data.terminals[s.terminal_number()+1].name;
	else if (s.is_nonterminal())
		os << data.nonterminals[s.nonterminal_number()+1].name;
	else if (s.is_eof())
		os << "eof";
	else
		os << "??";
}

void print_accessing_sentence(ostream& os, int state,
	const Automata_builder::Minimal_expansion& min_exp,
	const Automata_builder::Stack_context& context)
{
	using namespace Automata_builder;

	vector<Symbol> seq = context.symbols(state);

	os << "\tsymbols  : ";
	for(int i=0; i<seq.size(); i++)
	{
		print_symbol(os, seq[i]);
		os << " ";
	}
	os << "\n";

	os << "\tsentence : ";
	for(int i=0; i<seq.size(); i++)
		if(seq[i].is_terminal())
		{
			print_symbol(os, seq[i]);
			os << " ";
		}
		else
		{
			const vector<Symbol> &exp=min_exp.for_nonterminal(seq[i].nonterminal_number());
			for(int j=0; j<exp.size(); j++)
			{
				print_symbol(os, exp[j]);
				os << " ";
			}
		}
}

void print_conflicts(const Automata_builder::LR1_conflicts& conflicts,
	const Automata_builder::Minimal_expansion& min_exp,
	const Automata_builder::Stack_context& context, int num_states)
{
	using namespace Automata_builder;

	string log_file_name=data.file_name+string(".conflicts");

	if(conflicts.num_conflicts()==0)
	{
		remove(log_file_name.c_str());
        cout << "No conflicts.\n";
		return;
	}

	ofstream log;
	if(data.variables.dump_conflicts_to_file)
	{
		log.open(log_file_name.c_str());
		log << "LR conflicts.\n\n";

        for(int pass=1; pass<=2; pass++)
        {
            log << (pass==1 ? "Unresolved conflicts:\n" : "Resolved conflicts:\n");

            for(int s=0; s<num_states; s++)
            {
                if(conflicts.conflicts(s).empty())
                    continue;

                bool state_no_printed(false);

                vector<LR1_conflict>::const_iterator i
                    =conflicts.conflicts(s).begin();
                for(; i!=conflicts.conflicts(s).end(); i++)
                {
                    if(pass==1 && !i->def_resolution
                       || pass==2 && i->def_resolution)
                        continue;

                    if(!state_no_printed)
                    {
                        state_no_printed = true;
                        log << "State " << s << ":\n";
                        log << "Accessed via: \n";
                        print_accessing_sentence(log, s, min_exp, context);
                        log << "\n";
                    }

                    log << "Conflict on ";
                    print_symbol(log, i->lookahead);
                    log << " between ";

                    bool flag=false;
                    for(int j=(i->next_state==-1 ? 1 : 0);
                        j<=i->reduces.size();
                        j++) // stay calm
                    {
                        if(flag)
                        {
                            const char *s=(j<i->reduces.size() ? ", " : " and ");
                            log << s;
                        }
                        else
                            flag=true;

                        if(j==0)
                        {
                            log << "Shift " << i->next_state;
                        }
                        else
                        {
                            RuleData &rule=data.rules[i->reduces[j-1]+1];
                            log << "Reduce " << rule.in_printable_form();
                        }
                    }

                    if(!i->def_resolution)
                    {
                        log << ", resolved in favour of ";

                        if(i->resolution==-1)
                        {
                            const char *s=data.terminals[i->lookahead.terminal_number()+1].name;
                            log << "Shift " << s;
                        }
                        else
                        {
                            RuleData &rule=data.rules[i->reduces[i->resolution]+1];
                            log << "Reduce " << rule.in_printable_form();
                        }
                        log << ".\n";
                    }
                    else
                    {
                        log << ".\n";
                    }
                }
            }
        }
    }
    cout << conflicts.num_conflicts() << " conflicts (";
    cout << conflicts.num_unresolved_conflicts() << " unresolved).\n";
}