"use strict";
/** @fileOverview Implements `class page.LL1`.
* @author Axel T. Schreiner <ats@cs.rit.edu>
* @version 1.5.0
*/
/** The result of {@link page.trace}, {@link page.LL1#reflect}, or {@link page.SLR1#reflect}: a function which can observe a parser.
* @typedef Observer
* @type {function(number, page.Tuple, string, (page.BNF.Rule|page.BNF.T|string), object): object}
* @param {number} _at where the parser is, e.g., a rule or state number.
* @param {page.Tuple} _tuple current input.
* @param {string} _action `'rule'`, `'shift'`, or `'reduce'` for LL(1),
* `'shift'`, `'reduce'`, `'goto'`, or `'accept'` for SLR(1), or `'error'`.
* @param {page.BNF.Rule|page.BNF.T|number|string} _info a reference to the relevant rule, terminal,
* or state number, or an error message.
* @param {object} _sender of this message, e.g., {@link page.LL1} or {@link page.SLR1}.
* @returns {object} anything on success.
* @throws {string|Error} a string with an error message to continue parsing
* or an `Error` with an error message to abort further parsing.
*/
/** Builder function implementing a semantic action for {@link page.LL1#reflect} and {@link page.SLR1#reflect}.
* @typedef Builder
* @type {function (object[], object, page.Tuple, object) : object}
* @param {object[]} _values top-level value list, collected for this semantic action.
* @param {object} _env environment, originally connected to the observer.
* @param {page.Tuple} _tuple current input.
* @param {object} _sender of this message, e.g., {@link page.LL1} or {@link page.SLR1}.
* @returns {object|object[]} a value which will be pushed, or concatenated by the observer.
* @throws {string|Error} a string with an error message to continue parsing
* or an `Error` with an error message to abort further parsing.
*/
/** Wraps a suitable grammar for top-down parsing; checks if a grammar is suitable, i.e., LL(1).
* @class Tests and wraps a LL(1) grammar for top-down parsing.
* An object of this class supports one call to a parsing algorithm at any one time.
* The object is serially reusable.
*
* {@link page.LL1#parser} is a recursive parsing algorithm for {@link page.BNF} and {@link page.EBNF} grammars.
* {@link page.LL1#parse} is a stack-based parsing algorithm for {@link page.BNF} grammars (which can be derived from {@link page.EBNF} grammars).
* The algorithms have different strategies for error recovery.
*
* Either algorithm can pull input from a callback function. Successive pieces of input can be pushed
* to successive calls of {@link page.LL1#parse}.
*
* A BNF grammar undergoes the following tests:
*
* | node | check action |
* |------|--------------|
* | {@link page.BNF} | delegate to all non-terminals.
* | {@link page.BNF.NT} | `first` of alternative right-hand sides in rules should be pairwise disjoint, `first` and `follow` should not overlap if empty input is acceptable.
* | {@link page.BNF.T} | nothing to do.
*
* If a non-terminal is defined with left recursion, it will have ambiguous alternatives.
* Such a grammar should not be used here.
*
* An EBNF grammar could be checked by first converting to BNF.
* However, the following tests relate errors better to the original grammar:
*
* | node | check action |
* |------|--------------|
* | {@link page.EBNF} | delegate to rules' right-hand sides.
* | {@link page.EBNF.NT} | `first` and `follow` should not overlap if it accepts empty input.
* | {@link page.BNF.T } | nothing to do.
* | {@link page.EBNF.Alt} | `first` and `follow` should not overlap if it accepts empty input; `first` of choices should be pairwise disjoint; delegate to choices.
* | {@link page.EBNF.Lst} | `first` and `follow` should not overlap; `first` of body and delimiter should be pairwise disjoint if either accepts empty input; delegate to body and delimiter.
* | {@link page.EBNF.Rep} | `first` and `follow` should not overlap; delegate to body.
* | {@link page.EBNF.Seq} | `first` and `follow` should not overlap if it accepts empty input; delegate to terms.
*
* @param {page.BNF|page.EBNF} _grammar to be used for parsing; it should not be left-recursive.
* Either grammar is checked whether it is LL(1).
* @param {Observer} [_observer] to observe recognition.
*
* @property {page.BNF} bnf BNF grammar to control recognition.
* @property {page.EBNF} ebnf EBNF grammar to control recognition, if available.
* @property {Observer} observer to observe recognition.
* @property {number} greedy number of `first`/`follow` overlaps,
* would be resolved in favor of `first`.
* @property {number} ambiguous number of `first` overlaps in alternatives
* of the same non-terminal, would be resolved in favor of the first alternative
* but usually makes the grammar unsuitable because it can indicate left recursion.
* @property {number} errors counted by {@link page.error} method,
* reset just before parsing is started.
*
* @property {Array<{rule: page.BNF.Rule, position: number}>} states currently active rules,
* exists only while {@link page.LL1#parse} is used.
*
* @property {Array<Array<object>>} values currently active value lists,
* exists only while {@link page.LL1#reflect} is used.
*/
page.LL1 = function (_grammar, _observer) {
var self = this;
self.assert('__WHERE__', _grammar instanceof page.BNF);
!_observer || self.assert('__WHERE__', typeof _observer == 'function');
self.bnf = undefined;
self.ebnf = undefined;
if (_observer) self.observer = _observer;
self.greedy = 0;
self.ambiguous = 0;
self.errors = 0;
if (_grammar instanceof page.EBNF) {
self.ebnf = _grammar;
self.bnf = _grammar.bnf;
// import error count if any
self.errors = self.ebnf.errors; self.ebnf.errors = 0;
var visit = function (node) {
if (node instanceof page.EBNF.Alt) { // first and follow should not overlap if it accepts empty input
// first of choices should be pairwise disjoint
// delegate to choices.
if (node.empty && page.overlap(node.first, node.follow)) {
self.message(node.nt.name, 'has overlapping first and follow sets (alt)');
++ self.greedy;
}
// choices disjoint?
if (node.nodes.some(function (nodeA, a) {
return node.nodes.slice(a + 1).some(function (nodeB) {
return page.overlap(nodeA.first, nodeB.first);
})
})) {
self.message(node.nt.name, 'has ambiguous alternatives (alt)');
++ self.ambiguous;
}
// choices?
node.nodes.forEach(function (choice) { visit(choice); });
}
else if (node instanceof page.EBNF.Lst) { // first and follow should not overlap
// first of descendants should be disjoint if either accepts empty input
// delegate to descendants.
if (page.overlap(node.first, node.follow)) {
self.message(node.nt.name, 'has overlapping first and follow sets (list)');
++ self.greedy;
}
if ((node.node.empty || node.delim.empty) && page.overlap(node.node.first, node.delim.first)) {
self.message(node.nt.name, 'has overlapping body and delimiter');
++ self.greedy;
}
visit(node.node);
visit(node.delim);
}
else if (node instanceof page.EBNF.NT) { // first and follow should not overlap if it accepts empty input.
if (node.empty && page.overlap(node.first, node.follow)) {
self.message(node.name, 'has overlapping first and follow sets (nt)');
++ self.greedy;
}
}
else if (node instanceof page.EBNF.Rep) { // first and follow should not overlap
// delegate to descendant.
if (page.overlap(node.first, node.follow)) {
self.message(node.nt.name, 'has overlapping first and follow sets (rep)');
++ self.greedy;
}
visit(node.node);
}
else if (node instanceof page.EBNF.Seq) { // first and follow should not overlap if it accepts empty input
// delegate to descendants.
if (node.empty && page.overlap(node.first, node.follow)) {
self.message(node.nt.name, 'has overlapping first and follow sets (seq)');
++ self.greedy;
}
node.nodes.forEach(function (symbol) { visit(symbol); });
}
else if (node instanceof page.BNF.T) { // nothing to do
}
else self.assert('__WHERE__');
};
// check
// delegate to rules' right-hand sides.
self.ebnf.rules.forEach(function (rule) { visit(rule.symbol); });
} else {
self.bnf = _grammar;
// import error count if any
self.errors = self.bnf.errors; self.bnf.errors = 0;
// check if BNF grammar is LL(1)
self.bnf.nts.forEach(function (nt) {
// first/follow if empty?
if (nt.empty && page.overlap(nt.first, nt.follow)) {
self.message(nt.name, 'has overlapping first and follow sets');
++ self.greedy;
}
// alternatives?
if (nt.rules.some(function (ruleA, a) {
return nt.rules.slice(a + 1).some(function (ruleB) {
return page.overlap(ruleA.first, ruleB.first);
})
})) {
self.message(nt.name, 'has ambiguous alternatives');
++ self.ambiguous;
}
});
}
};
page.baseclass(page.LL1, 'page.LL1');
/** Delegates to `.bnf` to create a function which tokenizes a string.
*
* @param {string|RegExp} [_skip] a pattern to define ignorable character sequences;
* this pattern must not accept empty input and it must use `(:? )`
* rather than `( )` for grouping; the default is to skip white space.
*
* @returns {Tokenizer} a function which takes a string and returns a list of {@link page.Tuple} elements.
* The list contains one tuple with the `error` token for each
* character which is neither ignorable nor a literal or part of a token.
* The function is based on a regular expression which can be displayed as a member `.pattern`.
*
* @see page.BNF#tokenizer
*/
page.LL1.prototype.tokenizer = function (_skip) {
return this.bnf.tokenizer(_skip);
};
/** Displays number of errors and overlaps, if any.
* @override
*
* @returns {string}
*/
page.LL1.prototype.toString = function () {
var result = this.errors ? 'errors: ' + this.errors : '';
if (this.greedy || this.ambiguous) {
if (this.greedy > 0)
result += '\nfirst/follow overlaps: ' + this.greedy;
if (this.ambiguous > 0)
result += '\nambiguous alternatives: ' + this.ambiguous;
}
return result;
};
/** Displays errors, overlaps, and active rules and delegates to the grammar.
* @override
*
* @returns {string}
*/
page.LL1.prototype.dump = function () {
var result = this.toString();
if (result.length > 0) result += '\n\n';
if ('states' in this)
result += 'active rules\n ' +
this.states.slice(1).concat([ this.top ]).map(function (state) {
return state.rule.toString(state.position);
}).join('\n ') + '\n\n';
if ('values' in this)
result += 'collected values\n ' +
this.values.map(function (values) {
return '[ ' + values.join(', ') + ' ]';
}).join('\n ') + '\n\n';
return result + (this.ebnf ? this.ebnf.dump() : this.bnf.dump());
};
/** Checks top-down if input conforms to a BNF grammar.
* For an EBNF grammar this method uses the corresponding BNF grammar.
* This method can be called repeatedly with portions of input.
*
* | node | parse action |
* |------|--------------|
* | {@link page.BNF.NT} | compare next input and `first` to visit the first possible rule for the non-terminal and return the result. It is an error if no rule can be visited and the non-terminal cannot accept no input.
* | {@link page.BNF.Rule} | send a `'rule'` message to the observer if any; visit the descendants; send a `'reduce'` message. It is an error if the observer returns a string.
* | {@link page.BNF.T} | send a `'shift'` message to the observer if any and advance in input. It is an error if the observer returns a string.
*
* The method uses a stack of active rules and attempts error recovery.
* If an input symbol cannot be matched, the parser function will search the rest of the current
* and all outer active rules for a possible match with the input symbol.
* If there is no match, the input symbol is discarded and the search is tried again
* until an `irrecoverable error` is reported at end of input.
*
* The method is greedy, i.e., it will match input to a rule as long as possible;
* therefore, some types of ambiguous grammars are still suitable for parsing.
*
* ##### Create parsers and scanner
* var parser = new page.LL1(page.BNF.from(' ... grammar described in BNF ...'));
* var parser = new page.LL1(page.EBNF.from(' ... grammar described in EBNF ...'));
* var scanner = parser.tokenizer(/ skip pattern /);
*
* ##### Parse -- all input
* parser.parse(scanner('... input ...').concat([ null ]));
*
* ##### Parse -- push tuples
* var result = parser.parse(scanner('... start of input ...'));
* while (result === true)
* result = parser.parse(scanner('... more input ...')); // eventually null input
*
* ##### Parse a stream -- pull tuples
* function stream () { return scanner('... start/more input/null ...'); }
* parser.parse(stream);
*
* ##### Trace
* parser.parse(stream, page.trace());
*
* ##### Collect token values
* var result = parser.parse(stream, parser.reflect());
* print(result); // array with token values
*
* ##### Create observer for traced building
* var environment = ... something useful for the builder ...;
* var builder = {
* ruleName: // matched by reflection
* function (_values, _environment, _tuple, _sender) {
* return ... anything
* throw string for error message
* throw Error with message to abort
* }
* ...
* };
* var observer = page.trace(parser.reflect(environment, builder));
*
* ##### Build
* var result = parser.parse(stream, observer);
* print(result); // array with builder value(s)
*
* @param {page.Tuple[]|Tokenizer} _input either the next portion of input
* and `null` or an empty array will match `$eof`, or a {@link Tokenizer} which will be called *without arguments*
* and each time must return the next portion of input, `null`, or an empty array.
* @param {Observer} [_observer] to observe recognition;
* cannot be specified once parsing is in progress.
*
* @returns {boolean|object} `true` to request another input array,
* or the top-level value (which could be `null`) returned by the observer, if any, when the end of input is reached.
*
* @throws {Error} from the observer to abort parsing.
*
* @see page.trace
*/
page.LL1.prototype.parse = function (_input, _observer) {
var self = this; // closure
var current = null; // current input tuple, if any
var tuples = []; // available tuples
var index = 0; // index of next tuple
// set current to a new tuple, but not past $eof
// throw true to ask for more input
function next () {
if (index >= tuples.length) { // no tuples left
if (typeof _input == 'function') // call back for more
tuples = _input();
else if (_input) { // consume argument
tuples = _input;
_input = false;
} else if (_input === false) // throw true for more input
throw true;
else // null input: EOF
tuples = null;
if (!tuples || tuples.length == 0) // EOF
tuples = [ new page.Tuple(0, self.bnf.lit(), '') ];
index = 0;
}
// use 'index' tuple
if ((current = tuples[index]) == null)
current = tuples[index] = new page.Tuple(0, self.bnf.lit(), '');
// advance index (to later tokenize more) but don't run past $eof tuple
if (current.t != self.bnf.lit()) ++ index;
}
// inform observer, if any
// if error action: print result or info if any; return null
// rethrow Error; return result or null
function observe (_action, _info) {
var result = _action == 'error' ? _info : null;
var at = _action == 'rule' ? _info.index : self.top.rule.index;
if (self.observer)
try {
result = self.observer(at, current, _action, _info, self);
} catch (e) {
if (typeof e == 'string')
self.error(e);
else {
self.assert('__WHERE__', e instanceof Error)
throw 'lineNumber' in e ? new Error('('+e.lineNumber+') ' + e.message) : e;
}
}
if (_action == 'error') {
if (result) self.error(result);
return null;
}
return result;
}
// if current input matches somewhere in
// _config state stack element
// set elements position accordingly and return true.
function recover (_config) {
for (var pos = _config.position; pos < _config.rule.symbols.length; ++ pos)
if (current.t.ord in _config.rule.symbols[pos].first) {
_config.position = pos;
return true;
}
return false;
}
self.assert('__WHERE__', typeof _input != 'boolean');
if ('states' in self) {
// multiple calls in progress, only for tuple array, no new observer
!_input || self.assert('__WHERE__', _input instanceof Array);
self.assert('__WHERE__', !_observer);
} else {
!_input || self.assert('__WHERE__', _input instanceof Array || typeof _input == 'function');
!_observer || self.assert('__WHERE__', typeof _observer == 'function');
if (_observer) self.observer = _observer;
// begin parsing: create stack and initialize top to rule 0
self.states = [ null ];
self.top = { rule: self.bnf.rules[0], position: 0 };
next();
observe('rule', self.bnf.rules[0]);
}
try {
var result = null, throttle = false;
loop: while (self.top) { // any active rule?
if (! current) // input available?
next();
if (self.top.position < self.top.rule.symbols.length) { // symbol on rhs left?
var symbol = self.top.rule.symbols[self.top.position];
if (symbol instanceof page.BNF.T) { // terminal?
if (symbol == current.t) { // equal to input?
observe('shift', symbol);
++ self.top.position; // done with symbol
current = null; // done with input
throttle = false; // allow messages
continue loop;
}
} else if (current.t.ord in symbol.first) { // non-terminal, input in first?
if (symbol.rules.some(function (rule) { // input in first of some rule?
if (current.t.ord in rule.first) {
observe('rule', rule);
++ self.top.position; // done with symbol
self.states.push(self.top); // activate rule
self.top = { rule: rule, position: 0 };
return true;
}
return false;
}))
continue loop;
self.assert('__WHERE__'); // cannot happen: input must be in one of the first sets
} else if (symbol.empty && current.t.ord in symbol.follow) { // empty input ok?
++ self.top.position; // done with symbol
continue loop;
}
if (!throttle) {
// produce a message listing expected symbols in symbol.first along the rule
var msg = current + ' is not allowed in "'+ self.top.rule + '"\nexpecting:';
var expect = {};
for (var p = self.top.position; p < self.top.rule.symbols.length; ++ p) {
var s = self.top.rule.symbols[p];
page.merge(expect, s.first);
if (!s.empty) break;
}
if (p >= self.top.rule.symbols.length) page.merge(expect, self.top.rule.nt.follow);
for (var e in expect) msg += ' ' + expect[e];
// run the message past the observer (which may throw a string).
observe('error', msg);
throttle = true;
}
// try to recover back to the bottom of the stack.
if (recover(self.top)) continue loop;
for (var s = self.states.length; -- s > 0; )
if (recover(self.states[s])) {
self.top = self.states[s];
self.states = self.states.slice(0, s);
continue loop;
}
// if unable, discard current input (which may cause subsequent messages).
self.message('discarding ' + current);
current = null;
} else { // no symbol on rhs left, done with rule
result = observe('reduce', self.top.rule);
self.top = self.states.pop();
}
}
throw [ result ];
} catch (outcome) {
if (outcome === true) return true;
// end parsing: remove stack
delete self.states;
delete self.top;
delete self.values;
if (outcome instanceof Array) return outcome[0];
self.assert('__WHERE__', outcome instanceof Error);
throw 'lineNumber' in outcome ? new Error('('+outcome.lineNumber+') ' + outcome.message) : outcome;
}
};
/** Checks top-down if input conforms to an EBNF or BNF grammar.
*
* Starting with the start symbol, this method recursively visits the grammar.
* A node will only be visited if the next input symbol
* is in the set of first terminals of the node.
*
* | node | parse action |
* |------|--------------|
* | {@link page.EBNF.NT} | delegate to the corresponding rule.
* | {@link page.EBNF.Rule} | send a `'rule'` message to the observer if any; visit the descendant; send a `'reduce'` message. It is an error if the observer returns a string.
* | {@link page.EBNF.Alt} | visit the first possible alternative and return the result.
* | {@link page.EBNF.Lst} | visit the body and then delimiter and body as often as possible and allowed; return an error if there are not enough iterations, or return the last result or the first string returned by the descendant.
* | {@link page.EBNF.Rep} | visit the descendant as often as possible and allowed; return an error if there are not enough iterations, or return the last result or the first string returned by the descendant.
* | {@link page.EBNF.Seq} | visit the descendants; return an error if a descendant cannot be visited, or return `null` or the first string returned by a descendant.
* | {@link page.BNF.T} | send a `'shift'` message to the observer if any and advance in input. It is an error if the observer returns a string.
*
* The method employs recursion, rather than a rule stack, and cannot perform deep error recovery.
*
* The method is greedy, i.e., it will match input to a rule as long as possible;
* therefore, some types of ambiguous grammars are still suitable for parsing.
*
* ##### Create parsers and scanner
* var parser = new page.LL1(page.BNF.from(' ... grammar described in BNF ...'));
* var parser = new page.LL1(page.EBNF.from(' ... grammar described in EBNF ...'));
* var scanner = parser.tokenizer(/ skip pattern /);
*
* ##### Parse string
* parser.parser(scanner('... input ...'));
*
* ##### Parse a stream — pull tuples
* function stream () { return scanner('... start/more input/null ...'); }
* parser.parser(stream);
*
* ##### Trace
* parser.parser(stream, page.trace());
*
* ##### Collect token values
* var result = parser.parser(stream, parser.reflect());
* print(result); // array with token values
*
* ##### Create observer for traced building
* var environment = ... something useful for the builder ...;
* ruleName: // matched by reflection
* function (_values, _environment, _tuple, _sender) {
* return ... anything
* throw string for error message
* throw Error with message to abort
* }
* ...
* };
* var observer = page.trace(parser.reflect(environment, builder));
*
* ##### Build
* var result = parser.parser(stream, observer);
* print(result); // array with builder value(s)
*
* @param {page.Tuple[]|Tokenizer} _input either the complete input
* or a {@link Tokenizer} which will be called *without arguments*
* and each time must return the next portion of input, `null`, or an empty array.
* @param {Observer} [_observer] to observe recognition.
*
* @returns {object} the top-level value (which could be `null`) returned by the observer, if any, when the end of input is reached.
*
* @throws {Error} from the observer to abort parsing.
*
* @see page.trace
*/
page.LL1.prototype.parser = function (_input, _observer) {
var self = this;
self.assert('__WHERE__', _input instanceof Array || typeof _input == 'function');
!_observer || self.assert('__WHERE__', typeof _observer == 'function');
if (_observer) self.observer = _observer;
// begin parsing
self.errors = 0;
var grammar = self.ebnf ? self.ebnf : self.bnf; // grammar to use
var current = null; // current input tuple, if any
var currentRule = undefined; // index of current rule for observer
var tuples = []; // available tuples
var index = 0; // index of next tuple to become current
// set current to a new tuple, but not past $eof
function next () {
if (index >= tuples.length) { // no tuples left
if (typeof _input == 'function') // call back for more
tuples = _input();
else if (_input) { // consume argument
tuples = _input;
_input = false;
} else // consumed; set EOF
tuples = null;
if (!tuples || tuples.length == 0) // EOF
tuples = [ new page.Tuple(0, grammar.lit(), '') ];
index = 0;
}
// use 'index' tuple
if ((current = tuples[index]) == null)
current = tuples[index] = new page.Tuple(0, grammar.lit(), '');
// advance index (to later tokenize more) but don't run past $eof tuple
if (current.t != grammar.lit()) ++ index;
}
// if rule or reduce action: set currentRule
// inform observer, if any
// if error action: print result or info if any; return null
// rethrow Error; return result or null
function observe (_action, _info) {
var result = _action == 'error' ? _info : null;
if (_action == 'rule' || _action == 'reduce') currentRule = _info.index;
if (self.observer)
try {
result = self.observer(currentRule, current, _action, _info, self);
} catch (e) {
if (typeof e == 'string')
self.error(e);
else {
self.assert('__WHERE__', e instanceof Error)
throw 'lineNumber' in e ? new Error('('+e.lineNumber+') ' + e.message) : e;
}
}
if (_action == 'error') {
if (result) self.error(result);
return null;
}
return result;
}
// produce a message listing expected symbols
// context 'this' node being visited
// node to check for first and (if exists) follow
// follow of context to abandon visit
// run the message past the observer (which may throw a string).
// else discard input until current input fits one of
// return 1 for follow if any
// return 0 for node.follow if any
// return -1 for node.first
// or if $eof doesn't fit, throw irrecoverable error
function expecting (context, node, follow) {
var msg = current + ' is not allowed in "'+ context + '"\nexpecting:';
var expect = {};
page.merge(expect, node.first);
if (node.empty && node.follow) page.merge(node.follow);
for (var e in expect) msg += ' ' + expect[e];
observe('error', msg);
while (current.t != grammar.lit()) { // don't go past $eof
if (node.follow && current.t.ord in node.follow)
return 0; // bypass the node
if (follow && current.t.ord in follow)
return 1; // terminate visit
next(); // discard current input
if (current.t.ord in node.first) // new input fits?
return -1; // retry the node!
}
throw new Error(current + ' irrecoverable error'); // crash
}
// visitor, implements closure for each class
// invariant is NOT to visit unless current.t.ord in first
// returns result from observing a rule reduce action
function visit (node) {
self.assert('__WHERE__', current.t.ord in node.first);
if (node instanceof page.EBNF.Alt) { // visit first possible choice
if (! node.nodes.some(function (choice) {
if (current.t.ord in choice.first) {
visit(choice);
return true;
}
return false;
}))
self.assert('__WHERE__');
}
else if (node instanceof page.EBNF.Lst) { // alternately visit body and delimiter
loop: for (;;) {
if (current.t.ord in node.node.first) // try term
visit(node.node);
else if (node.node.empty && current.t.ord in node.delim.first) { // empty term, can do delim
} else // botched term
switch (expecting(node, node.node, node.follow)) {
case -1: continue loop; // ready for term
case 0:
if (current.t.ord in node.delim.first) break; // ready for delim
case 1:
break loop; // done with list
}
if (current.t.ord in node.delim.first) // try delim
visit(node.delim);
else if (node.delim.empty && current.t.ord in node.node.first) { // empty delim, can do term
} else break loop; // can't continue
}
}
else if (node instanceof page.EBNF.NT) { // visit rule
visit(node.rule);
}
else if (node instanceof page.BNF.NT) { // visit first possible rule
if (! node.rules.some(function (rule) {
if (current.t.ord in rule.first) {
visit(rule);
return true;
}
return false;
}))
self.assert('__WHERE__');
}
else if (node instanceof page.EBNF.Rep) { // visit body one or more times
do
visit(node.node);
while (!node.max && current.t.ord in node.first);
}
else if (node instanceof page.EBNF.Rule) { // 'rule', visit right-hand side, 'reduce', return observer value
// rule message
observe('rule', node);
// visit right-hand side
visit(node.symbol);
// reduce message
return observe('reduce', node);
}
else if (node instanceof page.BNF.Rule) { // 'rule', visit right-hand side, 'reduce', return observer value
// rule message
observe('rule', node);
// visit right-hand side
loop: for (var s = 0; s < node.symbols.length; ++ s) {
var symbol = node.symbols[s]
if (current.t.ord in symbol.first)
visit(symbol);
else if (symbol.empty && current.t.ord in symbol.follow) {
} else
switch (expecting(node, symbol, node.follow)) {
case 1:
break loop;
case -1: // retry
-- s;
case 0: // move on
continue loop;
}
}
// reduce message
return observe('reduce', node);
}
else if (node instanceof page.EBNF.Seq) { // visit each possible descendant
loop: for (var n = 0; n < node.nodes.length; ++ n) {
var symbol = node.nodes[n]
if (current.t.ord in symbol.first)
visit(symbol);
else if (symbol.empty && current.t.ord in symbol.follow) {
} else
switch (expecting(node, symbol, node.follow)) {
case 1:
break loop;
case -1: // retry
-- n;
case 0: // move on
continue loop;
}
}
}
else if (node instanceof page.BNF.T) { // 'shift', advance in input
// shift message
observe('shift', node);
// advance in input
next();
}
else self.assert('__WHERE__');
}
try { // call/cc: throw [ result ] to return result from the parser
// move to first tuple
next();
// top-level visit
if (current.t.ord in grammar.rules[0].first
|| expecting(grammar.rules[0], grammar.rules[0]) == -1)
throw [ visit(grammar.rules[0]) ];
throw new Error(current + ' irrecoverable error');
} catch (outcome) { // return outcome[0] from parser or rethrow (e.g., assert)
// end parsing
delete self.values;
if (outcome instanceof Array) return outcome[0];
self.assert('__WHERE__', outcome instanceof Error);
throw 'lineNumber' in outcome ? new Error('('+outcome.lineNumber+') ' + outcome.message) : outcome;
}
};
/** Creates a function which can observe {@link page.LL1#parse} or {@link page.LL1#parser}.
*
* The observer function collects a list of all token values and gives each rule a chance to structure the list of values
* collected for the rule. It maintains a stack of value lists as follows:
*
* | action | effect |
* |--------|--------|
* | `'rule'` | pushes the stack with an empty value list and returns `null`.
* | `'shift'` | ignores a current literal or pushes the current token's associated string value onto the top-level value list and returns `null`.
* | `'reduce'` | pops the top-level value list, interacts with `_obj` if possible, or concatenates the list to the next level value list and returns that.
* | `'error'` | returns the error message.
*
* For `'reduce'`, if a property with the rule's non-terminal's name can be found through `_obj`,
* it should be a {@link Builder} function which is then called with `_env` and the popped top-level value list
* which contains the values collected for the rule in order.
* If the result is an array it is concatenated to the next level value list;
* otherwise the result is pushed onto the next level value list.
* This new list is returned by the observer.
*
* The name of the non-terminal is searched in the properties of `_obj` or by inheritance, i.e.,
* if one property name is `{}` it's associated value is searched recursively.
*
* @param {object} [_env] environment, passed through to the functions found through the properties in `_obj`.
* @param {object} [_obj] collection of {@link Builder} functions, i.e., semantic actions.
*
* @returns {Observer} a function to observe a parser.
*
* @see page.trace
*/
page.LL1.prototype.reflect = function (_env, _obj) {
var self = this;
// closure
return function (_at, _tuple, _action, _info, _sender) {
self.assert('__WHERE__', typeof _at == 'number');
self.assert('__WHERE__', _tuple instanceof page.Tuple);
self.assert('__WHERE__', typeof _action == 'string');
!_info || self.assert('__WHERE__', typeof _info == 'string'
|| _info instanceof page.BNF.Rule || _info instanceof page.BNF.T);
self.assert('__WHERE__', _sender === self);
if (!('values' in self))
self.values = [[]]; // stack of value lists with empty sentinel
switch (_action) {
case 'rule': // push a new value list
self.values.push([]);
return null;
case 'shift': // terminal
self.assert('__WHERE__', self.values.length > 0);
if (_tuple.t instanceof page.BNF.Token)
// push top-level value list with associated string
self.values[self.values.length-1].push(_tuple.value);
return null;
case 'reduce': // rule
self.assert('__WHERE__', self.values.length > 1);
self.assert('__WHERE__', _info instanceof page.BNF.Rule);
// pop top-level value list
var top = self.values.pop();
// reflect
for (var o = _obj; o; o = o['{}'])
if (_info.nt.name in o) {
top = o[_info.nt.name](top, _env, _tuple, _sender);
break;
}
// attach result to the end of the new top-level list
self.values.push(self.values.pop().concat(top instanceof Array ? top : [ top ]));
// return new value list
return top;
case 'error': // report a message
self.assert('__WHERE__', typeof _info == 'string');
return _info;
}
self.assert('__WHERE__');
};
};
page