"use strict";
/** @fileOverview Implements `class page.SLR1.State`.
* @author Axel T. Schreiner <ats@cs.rit.edu>
* @version 1.5.0
*/
/** Creates a representation for a new state of the SLR(1) automaton.
* @class Represents a state of the SLR(1) automaton.
* @private
*
* @param {page.SLR1.Config[]} _configs core and closure defining this state.
* @param {number} _core number of marked rules in the core.
* @param {Map} _actions maps possible next symbols to <tt>null</tt>.
*
* @property {page.SLR1.Config[]} configs core and closure defining this state.
* @property {number} core number of marked rules in the core.
* @property {Map} actions maps possible next symbols to actions.
*/
page.SLR1.State = function (_configs, _core, _actions) {
this.configs = _configs;
this.core = _core;
this.actions = _actions;
};
page.baseclass(page.SLR1.State, 'page.SLR1.State');
/** Displays core configurations and actions.
* @returns {string}
*/
page.SLR1.State.prototype.toString = function () {
return this.dump(true);
};
/** Displays all configurations and actions.
* @param {boolean} _core if true, only displays core configurations.
* @returns {string}
*/
page.SLR1.State.prototype.dump = function (_core) {
var result = ' ' + (_core ? this.configs.slice(0, this.core) : this.configs).map(function (config) {
return config.toString();
}).join('\n ') + '\n';
for (var a in this.actions)
result += '\n ' + this.actions[a];
return result;
};
/** Compares a core of marked rules to this state's core.
*
* @param {page.SLR1.Config[]} _core to compare to <tt>this</tt>.
*
* @returns true if this state has the same core (in any order).
*/
page.SLR1.State.prototype.equals = function (_core) {
this.assert('__WHERE__', _core instanceof Array);
_core.forEach(function (config) { this.assert('__WHERE__', config instanceof page.SLR1.Config); }, this);
// same core sizes?
return this.core == _core.length &&
// same elements?
this.configs.slice(0, this.core).every(function (a) {
return _core.some(function (b) {
return a.equals(b);
})
});
};
/** Creates and populates the state/symbol/action table. Fills in `reduce` for
* complete configurations, `shift` for terminals, `accept`
* for the end of input terminal, and `goto` for non-terminals.
* For conflict resolution see {@link page.SLR1}.
*
* @param {page.SLR1} _factory the keeper of the state table, factory for new states.
* @param {number} _stateNumber this state's number.
*/
page.SLR1.State.prototype.advance = function (_factory, _stateNumber) {
var self = this;
self.assert('__WHERE__', _factory instanceof page.SLR1);
self.assert('__WHERE__', typeof _stateNumber == 'number');
// following construction, actions maps every literal/token/non-terminal
// which can follow this state to null.
// create reduce actions for complete configurations
self.configs.forEach(function (config) {
if (config.complete) {
var rule = config.rule; // rule we are in
// for each terminal which can follow the rule in the grammar
for (var t in rule.nt.follow) { // ordinal number
var f = rule.nt.follow[t]; // terminal which can follow
if (!(t in self.actions)) { // can it follow in this state?
// if t is not in actions it cannot follow this state -> reduce
rule.reduced = true;
self.actions[t] = _factory.reduce(f, rule);
} else if (self.actions[t] == null)
// if (t, null) is in action, depending on precedences we might have a s/r conflict
if (rule.prec && 'prec' in f) // rule and terminal have defined precedence
if (rule.prec.level > f.prec.level) { // rule's precedence is higher -> reduce
rule.reduced = true;
self.actions[t] = _factory.reduce(f, rule);
} else if (rule.prec.level < f.prec.level) {
// rule's precedence is lower -> shift (below)
} else // equal precedence
switch (rule.prec.assoc) {
case 'left': // left-associative -> reduce
rule.reduced = true;
self.actions[t] = _factory.reduce(f, rule);
case 'right': // right-associative -> shift
break;
case 'nonassoc': // non-associative -> error action
rule.reduced = true; // avoid message
delete self.actions[t]; // i.e. f as input would be an error
}
else { // no precedence available
++ _factory.sr;
self.message('state', _stateNumber, 'has a shift/reduce conflict:', f, 'and rule', '(' + rule + ')');
} // -> shift (below)
else {
// t is in actions then actions[t] is already set as a reduce
self.assert('__WHERE__', self.actions[t] instanceof page.SLR1.Action
&& self.actions[t].action == 'reduce'
&& self.actions[t].info instanceof page.BNF.Rule);
var r2 = self.actions[t].info; // the conflict
++ _factory.rr;
self.message('state', _stateNumber, 'for', f, 'reduce/reduce conflict between', '(' + rule + ')', 'and', '(' + r2 + ')');
// resolve for rule which is first in the grammar
if (rule.index < r2.index) self.actions[t].info = rule;
} // done with this t
} // done with every t which can follow
} // done with every complete configuration
});
// create accept/shift actions for each next symbol which has none
for (var a in self.actions)
if (self.actions[a] == null)
if (a == _factory.bnf.lit().ord) {
// special case: $eof
self.actions[a] = _factory.accept();
_factory.bnf.rules[0].reduced = true;
} else {
// create next core by advancing marker over one symbol
var next = [ ];
var symbol = null;
self.configs.forEach(function (config) {
// find a as next symbol in all configs
if (!config.complete && a == config.rule.symbols[config.position].ord) {
// remember symbol and push config with marker after symbol
symbol = config.rule.symbols[config.position];
next.push(config.advance(_factory));
}
});
self.assert('__WHERE__', next.length > 0 && symbol);
// add new state with next as core, if any
// shift/goto existent or new state
if (!_factory.states.some(
function (state, s) {
if (!state.equals(next)) return false;
self.actions[a] = _factory.shift_or_goto(symbol, s);
return true;
})) {
self.actions[a] = _factory.shift_or_goto(symbol, _factory.states.length);
_factory.states.push(_factory.state(next));
}
}
for (var a in self.actions) self.assert('__WHERE__', self.actions[a]);
};
page