/*
* 2016 Maciej Wiecierzewski
*/
/**
* @constructor
* @param {Grammar} grammar
* @returns {Expression}
*/
function Expression(grammar)
{
this.grammar = grammar;
this.iterations = 10;
}
/** Generates expression */
Expression.prototype.generateExpression = function()
{
do
{
this.string = this.grammar.symbols[this.grammar.startSymbol].str;
this.syntaxTree = new Node(this.string, 0);
this.applyRules(this.iterations);
} while(this.string.length <= this.minExpLength);
this.opOrder = this.figureOpOrder();
}
/**
* Creates syntax tree basing on given string
* @param {string} str
*/
Expression.prototype.createFromString = function(str)
{
console.log(str);
var lastNode = null;
var pos = 0;
for(var i = 0; i < str.length; i++)
{
var char = str.charAt(i);
if(char === "(")
{
var node = new Node("", 0);
if(lastNode !== null)
lastNode.insertChild(node);
lastNode = node;
}
else if(char === ")")
{
lastNode = lastNode.parent;
}
else
{
var operator = this.findOperator(char);
if(operator.arity === 0)
{
var node = new Node(char, pos);
node.rule = this.findRule(char);
lastNode.insertChild(node);
}
else
{
lastNode.rule = this.findRule(char);
lastNode.pos = pos;
}
pos++;
}
}
this.syntaxTree = lastNode.root;
this.string = this.syntaxTree.toString({left: "", right: ""})
console.log(this.string);
console.log(this.syntaxTree.toString());
this.opOrder = this.figureOpOrder(true);
}
/**
* Returns an 'Operator' object with given symbol
* @param {type} symbol
* @returns {Expression.grammar.operators}
*/
Expression.prototype.findOperator = function(symbol)
{
for(var i = 0; i < this.grammar.operators.length; i++)
{
if(this.grammar.operators[i].symbol === symbol)
return this.grammar.operators[i];
}
}
/**
* Returns an 'Rule' object with given operator sybol
* @param {type} operatorSymbol Character representing operator in the string
* @returns {Expression.grammar.rules}
*/
Expression.prototype.findRule = function(operatorSymbol)
{
for(var i = 0; i < this.grammar.rules.length; i++)
{
if(this.grammar.rules[i].operator !== null &&
this.grammar.rules[i].operator === operatorSymbol)
{
return this.grammar.rules[i];
}
}
}
/** Computes and prints out the probablility of apperance for symbols and operators */
Expression.prototype.expressionProbability = function()
{
var grammar = this.grammar;
var symbolsApperanceProb = new Array(grammar.symbols.length);
var symbolsPickedProb = new Array(grammar.symbols.length);
var rulesProb = new Array(grammar.rules.length);
var maxIter = this.iterations;
var operatorsProb = [];
symbolsApperanceProb.fill(0);
symbolsApperanceProb[grammar.startSymbol] = 1;
while(maxIter --> 0)
{
var probSum = symbolsApperanceProb.reduce(
function(total, currentValue) {
return total+currentValue;
} );
for(var i = 0; i < symbolsPickedProb.length; i++)
{
symbolsPickedProb[i] = symbolsApperanceProb[i] / probSum;
}
for(var i = 0; i < symbolsPickedProb.length; i++)
{
var symbol = grammar.symbols[i].str;
var rules = grammar.getRulesN(symbol);
var probSum = 0;
for(var j = 0; j < rules.length; j++)
probSum += grammar.rules[rules[j]].probability;
for(var j = 0; j < rules.length; j++)
{
var n = rules[j];
rulesProb[n] = symbolsPickedProb[i] * (grammar.rules[n].probability / probSum);
if(grammar.rules[n].operator !== null)
{
if(operatorsProb[grammar.rules[n].operator])
operatorsProb[grammar.rules[n].operator] += rulesProb[n];
else
operatorsProb[grammar.rules[n].operator] = rulesProb[n];
}
}
}
var newSymbolsProb = new Array(grammar.symbols.length);
newSymbolsProb.fill(0);
for(var i = 0; i < newSymbolsProb.length; i++)
{
var symbol = grammar.symbols[i].str;
for(var j = 0; j < grammar.rules.length; j++)
{
if(grammar.rules[j].string.includes(symbol))
{
newSymbolsProb[i] += rulesProb[j];
}
}
}
var str = "";
var sum = 0;
for(var i = 0; i < symbolsApperanceProb.length; i++)
{
if(str != "")
str += ", ";
str += symbolsApperanceProb[i];
sum += symbolsApperanceProb[i];
}
console.log("symbol apperance: "+str+" sum: "+sum);
str = "";
sum = 0;
for(var i = 0; i < symbolsPickedProb.length; i++)
{
if(str != "")
str += ", ";
str += symbolsPickedProb[i];
sum += symbolsPickedProb[i];
}
console.log("symbol pict: "+str+" sum: "+sum);
str = "";
sum = 0;
for(var i = 0; i < rulesProb.length; i++)
{
if(str != "")
str += ", ";
str += rulesProb[i];
sum += rulesProb[i];
}
console.log("rules: "+str+" sum: "+sum);
str = "";
sum = 0;
for(i in operatorsProb)
{
if(str != "")
str += ", ";
str += "["+i+"]="+operatorsProb[i];
sum += operatorsProb[i];
}
console.log("operators: "+str+" sum: "+sum);
var total = sum;
str = "";
sum = 0;
for(i in operatorsProb)
{
if(str != "")
str += ", ";
str += "["+i+"]="+operatorsProb[i]/total*100+"%";
sum += operatorsProb[i]/total*100;
}
console.log("operators%: "+str+" sum: "+sum+"%");
symbolsApperanceProb = newSymbolsProb;
}
}
/**
* Picks randomly a rule from the set
* @param {Array} rules
* @returns {String|Expression.prototype.pickRule.rules}
*/
Expression.prototype.pickRule = function(rules)
{
var probSum = 0;
for(var i = 0; i < rules.length; i++)
probSum += rules[i].probability;
if(probSum == 0)
return "";
var segments = [];
var s = 0;
for(i in rules)
{
s += rules[i].probability/probSum;
segments.push(s);
}
var r = Math.random();
var i = 0;
for(i; i < segments.length; i++)
{
if(r < segments[i]) break;
}
return rules[i];
}
/**
* Returns symbols in the expression's string
* @param {string} string Expression's string
* @param {type} symbols
* @param {boolean} terminal
* @returns {Array|Expression.prototype.findSymbols.result}
*/
Expression.prototype.findSymbols = function(string, symbols, terminal)
{
var result = [];
for(var i in symbols)
{
if(symbols[i].terminal == terminal)
{
for(var j = 0; j < string.length; j++)
{
if(string[j] == symbols[i].str)
result.push(j);
}
}
}
return result;
}
/**
* Returns nonterminal symbols in the expression's string
* @param {type} string
* @param {type} symbols
* @returns {Array|Expression.prototype.findSymbols.result}
*/
Expression.prototype.nonTerminalSymbols = function(string, symbols)
{
return this.findSymbols(string, symbols, false);
}
/**
* Returns terminal symbols in the expression's string
* @param {type} string
* @param {type} symbols
* @returns {Array|Expression.prototype.findSymbols.result}
*/
Expression.prototype.terminalSymbols = function(string, symbols)
{
return this.findSymbols(string, symbols, true);
}
/**
* Replaces symbol in string according to given rule and adds new node in the syntax tree
* @param {number} symbolPos
* @param {Rule} rule
*/
Expression.prototype.applyRule = function(symbolPos, rule)
{
var node = this.syntaxTree.findNode(symbolPos);
if(node.children.length > 0) console.log("@err");
node.setRule(rule); // adds new node
var replacement = rule.string;
this.string = this.string.substr(0, symbolPos)+replacement+this.string.substr(symbolPos+1, this.string.length-symbolPos-1);
}
/**
* Builds expression by picking a random symbol and chosing a matching rule
* @param {numbers} iter How many times a symbol will be substited
*/
Expression.prototype.applyRules = function(iter)
{
var grammar = this.grammar;
var rules = grammar.rules;
var endRules = grammar.endRules;
var symbols = grammar.symbols;
var symbolsPos = this.nonTerminalSymbols(this.string, symbols);
while(symbolsPos.length > 0 && iter --> 0)
{
var i = Math.round(Math.random()*(symbolsPos.length-1));
var symbolPos = symbolsPos[i];
var symbol = this.string.substr(symbolPos, 1);
var _rules = grammar.getRules(symbol);
var rule = this.pickRule(_rules);
this.applyRule(symbolPos, rule);
symbolsPos = this.nonTerminalSymbols(this.string, symbols);
}
this.ridNonterminals();
this.finish();
}
/** Replaces all nonterminal symbols with matching rules */
Expression.prototype.ridNonterminals = function()
{
var grammar = this.grammar;
var rules = grammar.rules;
var endRules = grammar.endRules;
for(var i = 0; i < endRules.length; i++)
{
var endRule = endRules[i];
var symbol = rules[endRule].symbol;
var replacement = rules[endRule].string;
var regExp = new RegExp(symbol, 'g');
this.string = this.string.replace(regExp, replacement);
}
}
/** Replaces terminal symbols with operators so there is no symbols left */
Expression.prototype.finish = function()
{
var grammar = this.grammar;
var rules = grammar.rules;
var symbols = grammar.symbols;
var symbolsPos = this.terminalSymbols(this.string, symbols);
while(symbolsPos.length > 0)
{
var symbolPos = symbolsPos[0];
var symbol = this.string.substr(symbolPos, 1);
var _rules = grammar.getRules(symbol);
var rule = this.pickRule(_rules);
this.applyRule(symbolPos, rule);
symbolsPos = this.terminalSymbols(this.string, symbols);
}
}
/**
* Figures out the order of operators
* @param {type} noPosShift
* @returns {Array|Expression.prototype.figureOpOrder.nArr}
* @todo rewrite it
*/
Expression.prototype.figureOpOrder = function(noPosShift)
{
function Order(pos, no)
{
this.pos = pos;
this.no = no;
}
this.getOrder = function(pos)
{
return this.opOrder[pos];
}
function compare(a, b)
{
var aInt = parseInt(a.pos);
var bInt = parseInt(b.pos);
if(aInt > bInt) return 1;
else if(aInt == bInt) return 0;
else if(aInt < bInt) return -1;
}
function Entry(pos, order)
{
this.pos = pos;
this.order = order;
}
function getLength(node)
{
if(node.rule == null)
return 0;
var z = node.rule.string.length - 1;
for(var i = 0; i < node.children.length; i++)
{
z += getLength(node.children[i]);
}
return z;
}
function getSymbolPos(node)
{
var pos = 0;
var childNo = 0;
var z = 0;
for(var i = 0; i < node.rule.string.length; i++)
{
if(node.rule.string.charAt(i) === node.rule.operator)
{
pos = (node.pos + z + i);
}
else
{
z += getLength(node.children[childNo]);
childNo++;
}
}
return pos;
}
function getEntries(node)
{
if(noPosShift)
arr.push(new Entry(node.pos, node.order));
else
arr.push(new Entry(getSymbolPos(node), node.order));
for(var i = 0; i < node.children.length; i++)
{
getEntries(node.children[i]);
}
}
this.syntaxTree.figureOrder();
var arr = [];
getEntries(this.syntaxTree);
arr.sort(compare);
var nArr = [];
var str = "";
for(var i = 0; i < arr.length; i++)
{
if(str != "")
str += " ";
var order = arr.length - arr[i].order + 1;
//str += "["+arr[i].pos+"] = "+order;
str += order;
nArr.push(order);
}
console.log(str);
return nArr;
}