The Book

Class: Grammar

EBNF~ Grammar

Represents a context-free LL(1) grammar to create recursive descent parsers. Contains factory methods to create objects to represent the grammar as a tree.

A Grammar object can be asked to generate scanners, and parsers 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. Defines tokens, if any.

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

the grammar to represent, using the EBNF grammar and EBNF 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 third parameter.
Properties:
Name Type Description
rules Array.<module:EBNF~Rule>

list of rules; rule zero is start rule.
prefix string

prefix for log; assign string to push, else pop.
config Object.<string, Object>

maps names to configurable values.

Properties
Name Type 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 $-.
shallow boolean

trace lookahead during shallow.
deep boolean

trace lookahead during deep.
follow boolean

trace follow during follow.
parse boolean

trace parse().
lookahead boolean

trace lookahead during parse().
actions boolean

trace actions, if any, during parse().
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:

Extends

Members

<static, constant> ebnf :string

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

A *grammar* consists of one or more rules.

Each *rule* has a unique name on the left-hand side and alternatives on the right-hand side *

*Alternatives* are one or more symbol sequences, separated by `|`.

A *symbol sequence* contains one or more items, such as a rule name, a self-defining literal, the name of a token, or alternatives enclosed by braces or brackets.

Braces denote that the enclosed alternatives appear one or more times in a sentence.

Brackets denote that the enclosed alternatives are optional, i.e., they may or may not appear (once) in a sentence. A symbol sequence must not only contain optional alternatives.

Type:
  • string
Source:
Example

EBNF grammars' grammar 

grammar: [{ level }] { rule };
level:   '%left' { term } ';' |
         '%right' { term } ';' |
         '%nonassoc' { term } ';';
rule:    Token ':' alt ';';
alt:     seq [{ '|' seq }];
seq:     { lit | ref | opt | some } [ '%prec' term ];
term:    lit | ref; 
lit:     Lit;
ref:     Token;
opt:     '[' alt ']';
some:    '{' alt '}';

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

The EBNF 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 Token in Grammar.ebnf.

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

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

A `Name` can include `$error` for translation to BNF.

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

EBNF grammars' tokens 

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

<static> tracing :Object.<string, Object.<string, function()>>

Common method cache for tracing grammar checking and parsing. cls.prototype.method is cached as Grammar.tracing[method][cls.name]. If Grammar.tracing[method] exists, tracing can only be turned off and vice versa.

Tracing grammar checking and parsing is static, i.e., common to all grammars that might be created, because the methods themselves are common to all grammars.

Type:
  • Object.<string, Object.<string, function()>>
Source:

Methods

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:

alt(seqs)

Factory method to represent a list of alternatives for EBNF.

Parameters:
Name Type Argument Description
seqs Array.<module:EBNF~Seq> <repeatable>

the alternatives, not empty.
Source:
Returns:

a new list of alternatives.

Type
module:EBNF~Alt

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()

Checks the grammar to be LL(1).

  • Calls expect() if necessary.
  • Computes follow for each node; a non-terminal obtains it from the rule.
  • Detects ambiguities.
Source:
Returns:

an error message on failure.

Type
udefined | string

dump( [a])

Displays the grammar and all symbols with name and contents of all sets. With argument (kludge!) acts as a static method and converts nested arrays to a string – useful because console.debug only reaches 3 levels.

Parameters:
Name Type Argument Description
a Object <optional>
<nullable>

the object to convert to a string.
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

expect()

Computes the expect sets; only call once.

  • Does not permit precedences.
  • There has to be at least one rule.
  • All non-terminals must be defined, each by a unique rule.
  • Detects left recursion as an error.
  • Computes expect for each node; a non-terminal obtains it from the rule.
  • All rules must be necessary, i.e., reachable from the first rule.
Source:
Returns:

an error message on failure.

Type
undefined | string

lit(literal [, used])

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

Parameters:
Name Type Argument Description
literal string

literal's representation conforming to .config.lits.
used boolean <optional>

if true mark literal as used.
Source:
Returns:

a unique literal.

Type
module:EBNF~Lit

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 not a string creates a unique name (intended for grammar extension).
Source:
Returns:

a unique non-terminal.

Type
module:EBNF~NT

opt(seqs)

Factory method to represent an optional list of alternatives for EBNF.

Parameters:
Name Type Argument Description
seqs Array.<module:EBNF~Seq> <repeatable>

the alternatives, not empty.
Source:
Returns:

a new optional list of alternatives.

Type
module:EBNF~Opt

parser( [skip])

Factory method to create a parser to recognize and process input. Requires that the expect sets for this grammar have been prepared.

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:EBNF~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

rule(nt, seqs)

Factory method to create a rule representation for EBNF. Maintains rule's non-terminal's .rule and this.rules.

Parameters:
Name Type Argument Description
nt module:EBNF~NT

left-hand side, non-terminal.
seqs Array.<module:EBNF~Seq> <repeatable>

right-hand side, list of alternative sequences.
Source:
Returns:

a new rule representation.

Type
module:EBNF~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

seq(nodes [, terminal])

Factory method to represent a sequence of nodes for EBNF. Precedence levels have to be defined prior to using this method.

Parameters:
Name Type Argument Default Description
nodes Array.<(module:Base~Symbol|module:EBNF~Opt|module:EBNF~Some)>

descendants, not empty, not all Opt.
terminal module:Base~T <optional>
<nullable>
 null

can define precedence for translation to BNF.
Source:
Returns:

a new sequence.

Type
module:EBNF~Seq

some(seqs)

Factory method to represent a repeatable list of alternatives for EBNF.

Parameters:
Name Type Argument Description
seqs Array.<module:EBNF~Seq> <repeatable>

the alternatives, not empty.
Source:
Returns:

a new repeatable list of alternatives.

Type
module:EBNF~Opt

toString()

Displays a description of the grammar.

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 (intended for BNF translation).
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:EBNF~Token

trace(what)

Installs and removes trace wrappers for grammar checking and parse methods; controlled by the configuration flags shallow, deep, follow, and parse, should only be called by expect() and parser.parse().

The tracing wrappers use .config.log and .prefix.

Grammar checking and parse methods are cached in Grammar.tracing globally per method and class.

Parameters:
Name Type Description
what string

one of shallow, deep, follow, or parse to trace that algorithm.
Source:

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