/*
Adriane Boyd

Parser class.

*/

#include <iostream.h>
#include "grammar.h"
#include "parser.h"

// Constructor
Parser::Parser()
{
	numderiv = 0;
	init();
}

// Destructor
Parser::~Parser()
{
	cleanup();
}

// delete unneeded TLists generated in the latest parse
void Parser::cleanup()
{
	int i;

	for(i = 0; i < numderiv; i++)
	{
		delete derivarray[i];
		delete derivrules[i];
	}
}

// initialize derivarray and derivrules so that all old lists are deleted and
// so that all rules are empty
void Parser::init()
{
	int i;

	cleanup();

	for(i = 0; i < MAX_DERIV; i++)
	{
		derivrules[i] = NULL;
	}
}


// Return 1 if a good sentence, 0 if not
int Parser::parse(TList *sent, Grammar *gram, Lexicon *lex)
{
	TList *lexsent;

	lexsent = wordsToLex(sent, lex);

	if(lexsent == NULL)
	{
		return 0;
	}

	init();

	return process(lexsent, gram);
}

// Create a list corresponding to the lexical entry for each word in the 
// sentence
TList *Parser::wordsToLex(TList *sent, Lexicon *lex)
{
	int i;
	TList *lexsent = new TList;
	char word[MAX_NAME_LEN];
	char *type;

	for(i = 0; i < sent->count(); i++)
	{
		strncpy(word, sent->getName(i), MAX_NAME_LEN);
		type = lex->getType(word);
		if(type != NULL)
		{
			lexsent->insertLast(type, 0);
		}
		else
		{
			return NULL;
		}
	}

	return lexsent;
}

// Parse the sentence for real
// Return 1 if the sentence was successfully parsed, 0 if not
int Parser::process(TList *lexsent, Grammar *gram)
{
	int pos = 0, i, correct = 0;

	char *start = gram->getStartSymbol();

	// set up the initial state in the derivation table

	derivarray[0] = new TList;
	derivarray[0]->insertFirst(start, 0);

	numderiv = 1;

	// for each word, expand all the entries as much as possible and then
	// select (reduce) only the ones which match the given lexical entry
	while(pos < lexsent->count())
	{
		expand(lexsent, gram);

		// print out derivation table (comment out the next block
		// to have only the final results shown)
		cout << "\nExpansionen an der " << pos << ". Position " << endl;
		for(i = 0; i < numderiv; i++)
		{
			cout << i << " Symbole: ";
			derivarray[i]->print();
			cout << i << " Regeln:  ";
			derivrules[i]->printTerms();
		}
		cout << endl;

		reduce(lexsent, pos);
		pos++;
	}

	// for the derivation entries remaining in the table, print out the
	// rule sequences corresponding the empty entries, if there are any
	// if there aren't any empty entries, the sentence wasn't accepted
	for(i = 0; i < numderiv; i++)
	{
		if(derivarray[i]->count() == 0)
		{
			if(correct == 0)
			{
				cout << "\nGuter Satz!\n" << endl;
				cout << "Folge(n) von Regeln" << endl;
				cout << "-------------------" << endl;
			}
			derivrules[i]->printTerms();
			correct = 1;
		}
	}

	return correct;
}

// Expand all the rules as much as possible in the derivation table
void Parser::expand(TList *lexsent, Grammar *gram)
{
	int i, j, rulematches, rulenum;
	TList *derivline, *templine, *ruleline;

	// for each entry in the derivation table, expand
	// (numderiv increases as entries are expanded, so all new entries will
	//  further expanded if possible)
	for(i = 0; i < numderiv; i++)
	{
		if(derivarray[i]->count() > 0 && !derivarray[i]->termStart())
		{
			// find out how many rules' LHS matches the first
			// symbol
			rulematches = gram->getNumMatches(derivarray[i]->getName(0));

			// for each of the rules, get the RHS and substitute
			// according in the derivation table and record which
			// rule was used in the rule table
			for(j = 0; j < rulematches; j++)
			{
				derivline = gram->getRHS(derivarray[i]->getName(0), j);
				rulenum = derivline->termStart();
				derivline->deleteFirst();

				templine = derivarray[i]->duplicate();
				templine->deleteFirst();
				derivline->append(templine);
				derivarray[numderiv] = derivline;

				if(derivrules[i] == NULL)
				{
					derivrules[i] = new TList;
				}
				ruleline = derivrules[i]->duplicate();
				derivrules[numderiv] = ruleline;
				derivrules[numderiv]->insertLast("", rulenum);

				numderiv++;
			}
		}
	}
}

// Keep only the entries in the derivation table whose first symbol corresponds
// to the lexical symbol at the given position in the sentence, removing the
// accepted symbol from the lists and deleting old lists
void Parser::reduce(TList *lexsent, int pos)
{
	int i;
	char *lex = lexsent->getName(pos);
	int newderivcount = 0;
	TList *templist;

	for(i = 0; i < numderiv; i++)
	{
		if(derivarray[i]->count() > 0 && strncmp(lex, derivarray[i]->getName(0), MAX_NAME_LEN) == 0)
		{
			derivarray[i]->deleteFirst();

			templist = derivarray[newderivcount];
			derivarray[newderivcount] = derivarray[i];
			if(i > newderivcount)
			{
				delete templist;
				derivarray[i] = NULL;
			}

			templist = derivrules[newderivcount];
			derivrules[newderivcount] = derivrules[i];
			if(i > newderivcount)
			{
				delete templist;
				derivrules[i] = NULL;
			}
			newderivcount++;
		}
	}

	numderiv = newderivcount;
}