load("grammar.js")

// Grammar:
//  - vars: dicionário de booleanos (pesquisam-se as chaves; isto é, para
//    testar se uma variável existe, basta testar se g.vars["Var"] é true)
//  - terms: dicionário de booleanos (same as above)
//  - init: string
//  - rules: dicionário de vetores de vetores. cada posição contém um vetor
//    de todas as regras cujo LHS é a chave. Cada elemento desse vetor é um
//    vetor contendo a probabilidade da regra seguida dos símbolos do RHS da
//    regra.
//    Exemplo:
//     Gramática: [ VP ] > [ VT ] [ NP ] ;0.9
//                [ VP ] > [ Copula ] [ NP ] ;0.1
//     Estrutura: g.rules["VP"] = [ [0.9, "VT", "NP"],
//                                  [0.1, "Copula", "NP"] ];


// Retorna lista de variáveis que geram o terminal.
function prod_term(grammar, symbol){
	var ls = [];
	for (var p in grammar.vars)
		for (var q in grammar.rules[p])
			if (grammar.rules[p][q][1] == symbol)
				ls.push([p,grammar.rules[p][q]]);
	return ls;
}	

// Retorna lista de variáveis que geram as duas variáveis de parâmetro
// nessa ordem.
function prod_vars(grammar, symbol1, symbol2, pos) {
	var ls=[];
	for (var p in grammar.vars)
		for (var q in grammar.rules[p])
			if (grammar.rules[p][q][1] == symbol1)
				if (grammar.rules[p][q][2] == symbol2)
					ls.push([p,grammar.rules[p][q],pos])
	return ls;
}

// Algoritmo de Cocke-Younger-Kasami para reconhecimento.
function CYK(gram, words) {
	var V=[];

	for (var i=1; i<=words.length; i++) {
		V[i] = [];
		for (var j=1; j<=words.length-i+1; j++){
			V[i][j] = [];
		}	
	}
	
	for (var r=0; r<words.length; r++)
		V[r+1][1] = V[r+1][1].concat(prod_term(gram, words[r]));
		
	
	for (var s=2; s<=words.length; s++)
		for (var r=1; r<=words.length-s+1; r++)
			for (var k=1; k<=s-1; k++)
				for (var l in V[r][k]) // toda váriavel que gera qualquer combinação de duas váriaveis
					for (var m in V[r+k][s-k])
						V[r][s] = V[r][s].concat(prod_vars(gram, V[r][k][l][0], V[r+k][s-k][m][0], [r,s,k,l,m]));

	return V;
}


// Gera as árvores sintáticas a partir da matriz CYK.
function gentrees(V, init) {
	var trees = [];
	var r=1, s=V.length-1;
	for (i in V[r][s]) {
		if (V[r][s][i][0] == init)
			trees.push(gentree(V, init, r, s, i));
	}

	trees.sort(function(a,b) { return b[0]-a[0] });

	return trees;
}

// Gera uma árvore sintática individual.
function gentree(V, init, r, s, i) {
	var pos = V[r][s][i][2];
	var rule = V[r][s][i][1];

	if (s==1)
		return [rule[0], init, rule[1]];
	else {
		var left = gentree(V, rule[1], pos[0], pos[2], pos[3]);
		var right = gentree(V, rule[2], pos[0]+pos[2], pos[1]-pos[2], pos[4]);
		var prob = rule[0] * left[0] * right[0];
		return [prob, init, left, right];
	}
}

// Converte a lista de árvores em uma string bem-apresentável.
function formattrees(trees) {
	var out = "";
	var first = true;

	if (trees.length == 0)
		return "No parse.";

	for (var i in trees) {
		if (first)
			first = false;
		else
			out+="\n";

		out += formattree(trees[i]);
	}
	return out;
}

function formattree(tree, indent, prefix) {
	var out = "";
	if (indent === undefined)
		indent = 0;
	if (prefix === undefined)
		prefix = "*";

	out += pad(indent) + prefix + " " + tree[1] + " (" + tree[0] + ")\n";
	if (tree[3]) {
		out += formattree(tree[2], indent+4, "-");
		out += formattree(tree[3], indent+4, "+");
	}
	else {
		out += pad(indent+4) + "= " + tree[2] + "\n";
	}

	return out;
}

// Retorna as árvores correspondentes à frase.
function parse(g, s) {
	var words = s.toLowerCase().replace(/[,.:;!]/g, "").
	              replace(/  */, " ").split(" ");
	var mx = CYK(g, words);
	var trees = gentrees(mx, g.init);
	return trees;
}