// grammar.js - Manipulação da estrutura da gramática.
// Run with: jsdb -load grammar.js

load("dump.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"] ];

function Grammar(code) {
	this.vars = [];
	this.terms = [];
	this.init = null;
	this.rules = [];

	this.addRule = function(lhs, rhs, prob) {
		if (!this.rules[lhs]) {
			this.rules[lhs] = [];
			this.vars[lhs] = true;
		}
		this.rules[lhs].push([prob].concat(rhs));
	}

	this.load = function(code) {
		var i=0;
		var t;
		var lhs, rhs, prob;
		var lines = code.split("\n");

		if (!lines[i].match(/Terminais/))
			throw Error("Invalid format at line " + i + "!");
		while (t = lines[++i].match(/^\[ *([^ ]*) *]/))
			this.terms[t[1]] = true;

		if (!lines[i].match(/Variaveis/))
			throw Error("Invalid format at line " + i + "!");
		while (t = lines[++i].match(/^\[ *([^ ]*) *]/))
			this.vars[t[1]] = true;

		if (!lines[i].match(/Inicial/))
			throw Error("Invalid format at line " + i + "!");
		t = lines[++i].match(/^\[ *([^ ]*) *]/);
		this.init = t[1];

		if (!lines[++i].match(/Regras/))
			throw Error("Invalid format at line " + i + "!");
		while ((t=lines[++i]) && (t = t.match(/^(.*)>(.*);([^#]*)/))) {
			lhs = t[1].match(/^\[ *([^ ]*) *]/)[1];
			rhs = t[2].match(/\[ *[^ ]* *]/g).map(function(x) { return x.match(/\[ *([^ ]*) *]/)[1] });
			prob = parseFloat(t[3]);
			this.addRule(lhs, rhs, prob);
		}

		if (lines[i] && lines[i] != "")
			throw Error("Invalid format at line " + i + "!");
	}


	// Remove substituições de variáveis.
	this.removeSubsts = function() {
		for (var lhs in this.rules)
			for (var i in this.rules[lhs]) {
				while ((rule = this.rules[lhs][i]),
				       rule.length==2 && this.vars[rule[1]]) {
					var prod = rule[1];
					for (var j in this.rules[prod]) {
						var newrule = this.rules[prod][j];
						var newrhs = newrule.slice(1);
						newrhs.unshift(newrule[0] * rule[0]);
						this.rules[lhs].push(newrhs);
					}
					this.rules[lhs].splice(i, 1);
				}
			}
	}

	// Converte a gramática para forma normal de Chomsky.
	// Assume que substituições de variáveis já foram removidas.
	this.chomskify = function() {
		// 1. Analisa todas as regras >=2 que geram terminais.

		for (var lhs in this.rules)
			for (var i in this.rules[lhs])
				if (this.rules[lhs][i].length >= 3)
					for (j=1; this.rules[lhs][i][j]; j++) {
						var sym = this.rules[lhs][i][j];
						var symalt = sym + "'";
						if (this.terms[sym]) {
							if (!this.vars[symalt])
								this.addRule(symalt, [sym], 1);
							this.rules[lhs][i][j] = symalt;
						}
					}

		// 2. Quebra regras com 3 ou mais símbolos.

		for (var lhs in this.rules)
			for (var i in this.rules[lhs])
				if (this.rules[lhs][i].length >= 4) {
					var num = 1;
					var sym = lhs;
					if (this.vars[sym + num]) {
						for (var n=1; this.vars[sym + n + "." + num]; n++) ;
						sym = sym + n + ".";
					}

					var rhs = this.rules[lhs][i].splice(2);
					this.rules[lhs][i].push(sym + num);
					while (rhs.length > 2) {
						this.addRule(sym + num, [rhs.shift(), sym + (++num)], 1);
					}
					this.addRule(sym + num, rhs, 1);
				}
	}

	// Ordena as produções em ordem decrescente de probabilidade.
	this.sortByProb = function() {
		for (var lhs in this.rules)
			for (var i in this.rules[lhs])
				this.rules[lhs].sort(function(a,b) { return b[0]-a[0] });
	}

	this.dump = function() {
		var out = "";
		var i, j, k;

		out+="Terminais\n"
		for (i in this.terms)
			out += "[ " + i + " ]\n";
		out+="Variaveis\n"
		for (i in this.vars)
			out += "[ " + i + " ]\n";
		out+="Inicial\n"
		out += "[ " + this.init + " ]\n";

		out+="Regras\n"
		for (i in this.rules) {
			for (j in this.rules[i]) {
				out += "[ " + i + " ] > ";
				for (k=1; this.rules[i][j][k]; k++)
					out += "[ " + this.rules[i][j][k] + " ] ";
				out += ";" + this.rules[i][j][0] + "\n";
			}
		}

		return out;
	}

	if (code) {
		this.load(code);
		this.removeSubsts();
		this.chomskify();
		this.sortByProb();
	}
}