The Book

Class: Grammar

BNF~ Grammar

Represents a context-free grammar to create SLR(1) parsers. Contains factory methods to create objects to represent the grammar as a tree and to represent the parsers' state table.

A `Grammar` object can be asked to generate scanners and [parsers](#parser) to process input sentences conforming to the grammar. If a parser is called with suitable actions it can transform input.

new Grammar( [grammar] [, tokens] [, config])

Creates a grammar representation. Creates the $accept non-terminal, $eof end of input literal, and $error token, and reserves rule zero: $accept: start $eof;. Defines tokens, if any.

Parameters:
Name Type Argument Description
grammar string <optional>
<nullable>

the grammar to represent, using the BNF grammar and BNF token and literal notation. This can be omitted to construct the rules directly using the factory methods.
tokens Object.<string, RegExp> <optional>
<nullable>

maps token names, if any, in the new grammar to their patterns which must not accept empty input, must not use d, g, or y flag, should not be anchored, and should use (:? ) rather than ( ) for grouping. tokens can map the empty string to a skip pattern which will be used to interpret the grammar string.
config Object.<string, Object> <optional>

overwrites configurable values' defaults; loaded first but can only be the third parameter.
Properties:
Name Type Argument Description
ebnf module:EBNF~Grammar <nullable>

set only if created from EBNF Grammar.
rules Array.<module:BNF~Rule>

list of grammar rules, can be pushed.
states Array.<module:BNF~State>

list of possible states for parser.
sr number

number of shift/reduce conflicts.
rr number

number of reduce/reduce conflicts.
config Object.<string, Object>

maps names to configurable values.

Properties
Name Type Argument Description
log function

function to print strings, by default console.log.
lits RegExp

restricts literal representation, by default single-quoted; must be anchored.
tokens RegExp

restricts token names, by default alphanumeric; must be anchored.
nts RegExp

restricts non-terminal names, by default alphanumeric; must be anchored.
uniq string

prefix for unique non-terminal names, by default $-.
error boolean <optional>

if true, insert $error when translating some.
lookahead boolean <optional>

if true, trace lookahead when parsing.
trace RegEx <optional>

if set, observe with grammar.trace( , config.trace); only affects grammar.parser().
build boolean <optional>

if set, build with grammar.build(); only affects grammar.parser().
lits Array.<module:Base~Lit>

list of unique literals, can be pushed.
litsByName Object.<string, module:Base~Lit>

maps 'x' to unique literal.
tokens Array.<module:Base~Token>

list of unique tokens, can be pushed.
tokensByName Object.<string, module:Base~Token>

maps name to unique token.
levels Array.<module:Base~Precedence>

list of precedence levels, can be pushed.
nts Array.<module:Base~NT>

list of unique non-terminals, can be pushed.
ntsByName Object.<string, module:Base~NT>

maps name to unique non-terminal.
errors number

incremented by error() method.
Source:
Throws:

an error for bad token definitions or syntax errors in the grammar.

Type
Error
Examples

LL(1) recursive descent parsing 

const e = new EBNF.Grammar(' ... grammar ... ')
e.parser(/ ... skip .../)(' ... input ... ')
e.parser(/ ... skip .../)(' ... input ... ', { ... actions ... })

equivalent SLR(1) stack-based parsing 

const b = BNF.Grammar.fromEBNF(e)
b.parser(/ ... skip .../)(' ... input ... ')
b.parser(/ ... skip .../)(' ... input ... ', { ... actions ... })

details 

const b = BNF.Grammar.fromEBNF(e)
const s = b.scanner(/ ... skip ... /)
new BNF.Parser(b).parse(s.scan(' ... input ... ').concat(null), b.build())
new BNF.Parser(b).parse(s.scan(' ... input ... ').concat(null), b.build({ ... actions ... }))

Extends

Members

<static, constant> bnf :string

Grammar describing the BNF notation accepted by new Grammar():

A *grammar* consists of an optional sequence of *precedence levels* followed by one or more rules.

Each *precedence level* consists of an associativity followed by one or more literals or token names and terminated with a semicolon. Precedence levels are increasing.

Each *rule* consists of a non-terminal name on the left-hand side, a colon, a *symbol sequence* on the right-hand side, and a semicolon. Rules with the same names are alternatives.

A *symbol sequence* contains zero or more items, such as a non-terminal name, a self-defining literal, or the name of a token.

Type:
  • string
Source:
Example

BNF grammars' grammar 

grammar:        precedences rules;
precedences:    ;
precedences:    precedences '%left' terminals ';';
precedences:    precedences '%right' terminals ';';
precedences:    precedences '%nonassoc' terminals ';';
terminals:      terminal;
terminals:      terminals terminal;
terminal:       lit;
terminal:       name;
rules:          rule;
rules:          rules rule;
rule:           Name ':' symbols ';';
rule:           Name ':' symbols '%prec' terminal ';';
symbols:        ;
symbols:        symbols name;
symbols:        symbols lit;
name:           Name;
lit:            Lit;

<static, constant> fromEBNF :function

Factory method to represent an EBNF grammar as a BNF grammar and check it.

Type:
  • function
Source:
Examples

Translating [ s | t | ... ] 

$-#:  ;
$-#: s;
$-#: t;
...

Translating { s | t | ... } 

$-##: $-#;
$-##: $-## $-#;
$-##: $error;
$-##: $-## $error;
$-#: s;
$-#: t;
...

<private, static, constant> grammar :module:BNF~Grammar

The BNF grammars' grammar; created when the module is loaded and used internally in new Grammar().

Type:
Source:
See:

<static, constant> terminals :Object.<string, RegExp>

Token definitions for Lit and Name in Grammar#bnf.

*Literals* represent themselves and are single-quoted strings using `\` only to escape single quotes and `\` itself.

A *Name* either represents a non-terminal or a *token*.

*Tokens* represent sets of inputs, such as names or numbers, and are alphanumeric names which must start with a letter and may include underscores.

`$error` is a special token to control error recovery.

Type:
  • Object.<string, RegExp>
Source:
See:
Example

BNF grammars' tokens 

{
  Lit:   /'(?:[^'\\]|\\['\\])+'/,
  Name:  /[A-Za-z][A-Za-z0-9_]*|\$error/
}

Methods

accept()

Factory method to create the accept message for $eof.

Source:
Returns:

an object representing the message.

Type
module:BNF~Message

add(item)

Adds a new symbol to the proper inventory or creates and adds new tokens. Must be called with a new, unique symbol or with a map of token names to patterns. Validates item names against .config. Token patterns must not accept empty input, must not use d, g, or y flag, should not be anchored, and should use (:? ) rather than ( ) for grouping.

Parameters:
Name Type Description
item Symbol | Object.<string, RegExp>

to add to the proper inventory or create and add.
Inherited From:
Overrides:
Source:

assert(condition, s)

Displays a message and throws an error if a condition is not met; primarily used for stronger argument typing.

Parameters:
Name Type Argument Description
condition boolean

should be true.
s Array.<?object> <repeatable>

message, to be displayed; joined by blanks.
Inherited From:
Overrides:
Source:
Throws:

message if condition is not met.

Type
string

check(start)

Completes the grammar representation and reports if there are errors; call exactly once. Creates rule zero: $accept: start $eof;. Sets ordinal number for literals, then tokens, then non-terminals. Checks that all rules are reached and all non-terminals can reduce to a terminal. Computes first and follow sets. Creates state table. Checks that all rules can be reduced.

Parameters:
Name Type Description
start module:BNF~NT

the start non-terminal.
Source:

dump(a, states)

Displays grammar, terminals, and non-terminals with name and contents of all sets. Displays number of errors if any.

Parameters:
Name Type Argument Description
a Object <nullable>

with one argument (kludge!) acts as a static method and displays the argument converting nested arrays to a string – useful because console.debug only reaches 3 levels.
states boolean

if true also displays states.
Overrides:
Source:
Returns:
Type
string

error(s)

Displays a message and counts it as an error.

Parameters:
Name Type Argument Description
s Array.<?object> <repeatable>

message, to be displayed; joined by blanks.
Inherited From:
Overrides:
Source:
Returns:

the message.

Type
string

lit( [literal] [, used])

Factory method to create a unique literal symbol, maintains .lits and .litsByName

Parameters:
Name Type Argument Description
literal string <optional>

literal's representation conforming to .config.lits. If omitted represents the $eof literal terminal.
used boolean <optional>

if true mark literal as used.
Source:
Returns:

a unique literal.

Type
module:BNF~Lit

mark(rule, position)

Factory method to represent a mark in a rule.

Parameters:
Name Type Description
rule module: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
module:BNF~Mark

message(s)

Displays a message on the configured .log.

Parameters:
Name Type Argument Description
s Array.<?object> <repeatable>

message, to be displayed; joined by blanks.
Inherited From:
Overrides:
Source:
Returns:

the message.

Type
string

nt( [name])

Factory method to create a unique non-terminal symbol, maintains .nts and .ntsByName.

Parameters:
Name Type Argument Description
name string <optional>

non-terminal's name conforming to config.nts; error if a token. If omitted represents the $accept non-terminal, if not a string creates a unique name (intended for EBNF translation).
Source:
Returns:

a unique non-terminal.

Type
module:BNF~NT

parser( [skip])

Factory method to create a parser to recognize and process input.

Parameters:
Name Type Argument Description
skip RegEx <optional>

a pattern to define ignorable character sequences, by default white space, must not accept empty input, must not use flags, must not be anchored, should use (:? )rather than ( ) for grouping.
Source:
Returns:

the parser.

Type
module:BNF~Parser

precedence(assoc, terminals)

Factory method to represent a list of terminals with equal precedence level and equal associativity. Creates a new Precedence object, adds it to .levels, adds .prec.level and .prec.assoc to all terminals in the list, and checks for duplicates.

Parameters:
Name Type Description
assoc string

associativity: '%left', '%right', or '%nonassoc'.
terminals Array.<?module:Base~T>

to add, null elements are ignored; no duplicates.
Inherited From:
Overrides:
Source:
Returns:

representing the set, or null if there are no terminals.

Type
module:Base~Precedence

reduce(t, rule)

Factory method to create a reduce message.

Parameters:
Name Type Description
t module:Base~T

terminal on which to send message.
rule module:BNF~Rule

rule to reduce.
Source:
Returns:

an object representing the message.

Type
module:BNF~Message

rule(nt [, symbols] [, terminal])

Factory method to create a rule representation for BNF. Maintains rule's non-terminal's .rules and this.rules. Maintains rule's non-terminal's .empty. Precedence levels have to be defined prior to using this method.

Parameters:
Name Type Argument Default Description
nt module:BNF~NT

left-hand side, non-terminal.
symbols Array.<module:Base~Symbol> <optional>

right-hand side, list of symbols.
terminal module:Base~T <optional>
<nullable>
 null

can define rule's precedence, by default the precedence of the rightmost terminal, if any.
Source:
Returns:

a new rule representation.

Type
module:BNF~Rule

scanner( [skip] [, terminals])

Factory method to create a scanner.

Parameters:
Name Type Argument Description
skip RegExp <optional>

a pattern to define ignorable character sequences, by default white space, must not accept empty input, must not use d, g, or y flag, should not be anchored, should use (:? ) rather than ( ) for grouping.
terminals Array.<T> <optional>

ordered list to create the lexical analysis pattern.
Inherited From:
Overrides:
Source:
Returns:

the scanner.

Type
module:Base~Scanner

shift_or_goto(symbol, state)

Factory method to create a shift or goto message.

Parameters:
Name Type Description
symbol module:Base~Symbol

symbol on which to send message.
state number

state to shift to.
Source:
Returns:

an object representing the message.

Type
module:BNF~Message

state(core)

Factory method to represent a state of the parser automaton. The state is created from the core marks; rules in the closure are added.

Parameters:
Name Type Description
core Array.<module:BNF~Mark>

list of marks in the core, closure is added.
Source:
Returns:

an object representing the state.

Type
module:BNF~State

toString( [states])

Displays description of grammar and number of errors if any.

Parameters:
Name Type Argument Description
states boolean <optional>

if true, also displays state table.
Source:
Returns:
Type
string

token( [name] [, pat] [, used])

Factory method to create a unique token symbol, maintains .tokens and .tokensByName.

Parameters:
Name Type Argument Description
name string <optional>

token's name conforming to .config.tokens; error if a non-terminal. If omitted represents the $error token with an empty RegExp.
pat RegExp <optional>

pattern to match values representing the token in input; used only when the token is created, must not accept empty input, must not use d, g, or y flag, should not be anchored, should use (:? ) rather than ( ) for grouping.
used boolean <optional>

if true mark token as used.
Source:
Returns:

a unique token.

Type
module:BNF~Token

tuple(lineno, t [, value])

Factory method to create an element of a tokenized input stream.

Parameters:
Name Type Argument Default Description
lineno number

input position.
t module:Base~T <nullable>

terminal, i.e., literal or token object; scan() uses null for an illegal character.
value string <optional>
<nullable>
 null

terminal's representation in the input.
Inherited From:
Overrides:
Source:
Returns:

an element of a tokenized input stream.

Type
module:Base~Tuple