nearley

To use Nearley effectively, it is important to understand the core terminology used in its grammar definitions and parsing processes:

Core Components

• token: The smallest meaningful unit (the "words") of your language.
• lexer: A function that converts a sequence of characters to a sequence of tokens.
• string: A sequence of tokens.
• language: A set of strings.
• grammar: A set of production rules that together specify a language.

Grammar Elements

• symbol: A generic term for a member of a production rule, which can be either a terminal or a nonterminal.
• terminal: A symbol that directly specifies a set of tokens that match.
• nonterminal: A symbol that specifies a set of other production rules that match.
• production rule: A set of strings specified as a sequence of symbols. A rule matches a string if it is a concatenation of strings matched by the respective symbols.
• epsilon: The empty production rule, matching only the empty string.
• nullable rule: A production rule that matches the empty string, even if it is not explicitly the epsilon rule (e.g., the concatenation of epsilon with epsilon).

Parsing and Output

• recognizer: A function that takes a grammar and a string and returns whether the grammar matches the string (yes/no).
• parser: A function that takes a grammar and a string and returns a derivation of that string.
• derivation: The recursive application of production rules to obtain a string.
• parse tree: A tree representation of a derivation.
• abstract syntax tree (AST): A version of a parse tree that has been simplified by postprocessors (e.g., omitting whitespace).
• ambiguity: A situation where more than one derivation exists for a single string. Note that nearley returns all possible derivations in the case of ambiguity.

Technical Concepts

• Earley algorithm: The parsing algorithm used by nearley to efficiently parse all context-free grammars.
• preprocessor: The dialect of JavaScript targeted by nearleyc (e.g., emitting TypeScript instead of plain JavaScript).
• postprocessor: A function associated with a production rule used to transform a parse tree into an AST.
• left-recursion: A situation where a nonterminal refers to a production rule whose first symbol matches the same nonterminal.

If you need to compile grammars dynamically in a browser (e.g., for an IDE), you can bundle the nearley NPM package using a module bundler like Webpack or Rollup. You can then use the nearley/lib/compile, nearley/lib/generate, and nearley/lib/nearley-language-bootstrapped modules to perform the compilation process manually.

const nearley = require("nearley");
const compile = require("nearley/lib/compile");
const generate = require("nearley/lib/generate");
const nearleyGrammar = require("nearley/lib/nearley-language-bootstrapped");

function compileGrammar(sourceCode) {
    // Parse the grammar source into an AST
    const grammarParser = new nearley.Parser(nearleyGrammar);
    grammarParser.feed(sourceCode);
    const grammarAst = grammarParser.results[0]; // TODO check for errors

    // Compile the AST into a set of rules
    const grammarInfoObject = compile(grammarAst, {});
    // Generate JavaScript code from the rules
    const grammarJs = generate(grammarInfoObject, "grammar");

    // Pretend this is a CommonJS environment to catch exports from the grammar.
    const module = { exports: {} };
    eval(grammarJs);

    return module.exports;
}

const grammar = compileGrammar("main -> foo | bar");

const parser = new nearley.Parser(nearley.Grammar.fromCompiled(grammar));

By default, Nearley uses scannerless parsing (splitting input into characters). To improve performance and grammar clarity, you can use a tokenizer (lexer) to split input into larger units called tokens. Nearley recommends using Moo for this purpose.

To use a lexer:

1. Define the lexer inside a Javascript block using moo.compile.
2. Use the @lexer directive to pass the lexer object to Nearley.
3. Match tokens in your grammar using either %type (to match by token type) or "text" (to match by the literal text of the token).

When using a lexer, you call parser.feed(data) as usual.

@{%
const moo = require("moo");

const lexer = moo.compile({
  ws:     /[ \t]+/,
  number: /[0-9]+/,
  word: { match: /[a-z]+/, type: moo.keywords({ times: "x" }) },
  times:  /\*/
});
%}

@lexer lexer

expr -> multiplication {% id %} | trig {% id %}

# Use %token to match by type
multiplication -> %number %ws %times %ws %number {% ([first, , , , second]) => first * second %}

# Use literal strings to match by text
trig -> "sin" %ws %number {% ([, , x]) => Math.sin(x) %}