page

Class: SLR1

page. SLR1

Tests and wraps a SLR(1) grammar for bottom-up parsing. An object of this class supports one execution of the parsing algorithm at any one time. The object is serially reusable.

page.SLR1#parse is a stack-based parsing algorithm for page.BNF grammars (which can be derived from page.EBNF grammars).

new SLR1(_grammar [, _observer])

Wraps a suitable grammar for bottom-up parsing. The page.BNF grammar is checked to be SLR(1). The state/symbol/action table is created which results in the discovery of any conflicts.

shift actions are generated for all terminals anticipated by traversing the grammar. reduce actions are generated for all terminals in the follow set of a rule.

reduce/reduce conflicts are reported and resolved in favor of the rule defined first. shift/reduce conflicts are reported and resolved in favor of shift unless they can be resolved through precedences.

If precedences are available, a rule is reduced if it has higher precedence than a follow terminal. The follow terminal is shifted if it has higher precedence than the rule. If the precedences are equal, a left-associative rule is reduced, a right-associative rule causes the follow terminal to be shifted, and for a non-associative rule the follow terminal is considered an error, i.e., it is removed from the action table.

All rules are checked that they can be reduced: The constructor deletes a boolean field .reduced from all rules of the page.BNF grammar. It then creates state 0 from rule zero marked in position zero and tells each state to page.SLR1.State#advance. This adds a boolean field .reduced to each page.BNF.Rule which can be reduced. If rules cannot be reduced they will be reported as errors.

Parameters:
Name Type Argument Description
_grammar page.BNF | page.EBNF

to be used for parsing. Left-recursive grammars and precedence grammars are more efficient. The underlying BNF (precedence) grammar is checked whether it is SLR(1).
_observer Observer <optional>

to observe recognition.
Properties:
Name Type Description
bnf page.BNF

BNF (precedence) grammar to control recognition.
ebnf page.EBNF

EBNF (precedence) grammar, if available.
observer Observer

to observe recognition.
states Array.<page.SLR1.State>

state/symbol/action table.
errors number

number of errors in creating the state table.
sr number

number of shift/reduce conflicts.
rr number

number of reduce/reduce conflicts.
stack Array.<object>

currently active states and associated values, exists only while page.SLR1#parse is used.

Properties
Name Type Description
state number

state number.
value object

returned by observer for shift and goto into the state.
Source:
See:

Classes

Action
Config
State

Methods

accept()

Factory method to create the accept action for $eof.

Source:
Returns:

an object representing the action.

Type
page.SLR1.Action

config(_rule, _position)

Factory method to represent a mark in a rule.

Parameters:
Name Type Description
_rule page.BNF.Rule

rule to mark.
_position number

position in rule, before a symbol or after all.
Source:
Returns:

an object representing the marked rule.

Type
page.SLR1.Config

dump()

Displays state table with closures, number of errors and conflicts, and delegates to the grammar.

Source:
Returns:
Type
string

parse(_input [, _observer])

Checks bottom-up 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.

The method uses a state stack 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.

Create parsers and scanner
var parser = new page.SLR1(page.BNF.from(' ... grammar described in BNF ...'));
var parser = new page.SLR1(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)
Parameters:
Name Type Argument Description
_input Array.<page.Tuple> | Tokenizer

either the next portion of input and null or an empty array will match $eof, or a Tokenizer which will be called without arguments and each time must return the next portion of input, null, or an empty array.
_observer Observer <optional>

to observe recognition; cannot be specified once parsing is in progress.
Source:
See:
Throws:

a message from the observer to abort parsing.

Type
Error
Returns:

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.

Type
boolean | object

reduce(_t, _rule)

Factory method to create a reduce action.

Parameters:
Name Type Description
_t page.BNF.T

terminal on which to take the action.
_rule page.BNF.Rule

rule to reduce.
Source:
Returns:

an object representing the action.

Type
page.SLR1.Action

reflect( [_env] [, _obj])

Creates a function which can observe page.SLR1#parse.

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. Conceptually, it works exactly like page.LL1#reflect, i.e., it maintains a stack of value lists as follows:

action effect
'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; returns the top-level value list or the interaction result.
'goto' concatenates or appends the result of the preceding 'reduce' to the next level value list and returns null.
'accept' returns the top-level value list.
'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 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.

For the immediately following 'goto', if the 'reduce' result is an array it is concatenated to the next level value list; otherwise the result is pushed onto the next level value list.

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.

Parameters:
Name Type Argument Description
_env object <optional>

environment, passed through to the functions found through the properties in _obj.
_obj object <optional>

collection of Builder functions, i.e., semantic actions.
Source:
See:
Returns:

a function to observe a parser.

Type
Observer

shift_or_goto(_symbol, _state)

Factory method to create a shift or goto action.

Parameters:
Name Type Description
_symbol page.BNF.T | page.BNF.NT

on which to take the action.
_state number

state to shift to.
Source:
Returns:

an object representing the action.

Type
page.SLR1.Action

state(_core)

Factory method to represent a state of the SLR(1) automaton. The state is created from the core configurations; rules in the closure are added.

Parameters:
Name Type Description
_core Array.<page.SLR1.Config>

list of configurations in the core.
Source:
Returns:

an object representing the state.

Type
page.SLR1.State

tokenizer( [_skip])

Delegates to .bnf to create a function which tokenizes a string.

Parameters:
Name Type Argument Description
_skip string | RegExp <optional>

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.
Source:
See:
Returns:

a function which takes a string and returns a list of 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.

Type
Tokenizer

toString()

Displays state table, number of errors and conflicts, if any, and delegates to the grammar.

Source:
Returns:
Type
string

yaccpar( [_env] [, _obj])

Creates a function which can observe page.SLR1#parse. Unlike page.SLR1#reflect this observer collects the values associated with all terminal symbols and offers them to _obj.

Parameters:
Name Type Argument Description
_env object <optional>

environment, passed through to the functions found through the properties in _obj.
_obj object <optional>

collection of Builder functions, i.e., semantic actions.
Source:
See:
Returns:

a function to observe a parser.

Type
Observer