tart-PEG

Parsing Expression Grammar (PEG) tools (tart module)

Usage

To run the below example run:

npm run readme

"use strict";

//var log = console.log;
var log = function () {};

var tart = require('tart');
var sponsor = tart.minimal({
    fail: function (e) {
        console.log('ERROR!', e);
    }
});

var PEG = require('../PEG.js');
var input = require('../input.js');

var pf = PEG.factory(sponsor);
var ns = pf.namespace(log);

/*
Assign <- Name "=" Assign
        / Expr
*/
ns.define('Assign',
    pf.choice([
        pf.sequence([
            ns.call('Name'),
            pf.terminal('='),
            ns.call('Assign')
        ]),
        ns.call('Expr')
    ])
);

/*
Name   <- [a-zA-Z]
*/
ns.define('Name',
    pf.predicate(function (token) {
        return /[a-zA-Z]/.test(token);
    })
);

/*
Expr   <- Term ([-+] Term)*
*/
ns.define('Expr',
    pf.sequence([
        ns.call('Term'),
        pf.zeroOrMore(
            pf.sequence([
                pf.predicate(function (token) {
                    return /[-+]/.test(token);
                }),
                ns.call('Term')
            ])
        )
    ])
);

/*
Term   <- Factor ([/*] Factor)*
*/
ns.define('Term',
    pf.sequence([
        ns.call('Factor'),
        pf.zeroOrMore(
            pf.sequence([
                pf.predicate(function (token) {
                    return /[/*]/.test(token);
                }),
                ns.call('Factor')
            ])
        )
    ])
);

/*
Factor <- "(" Assign ")"
        / Name
        / [0-9]+
*/
ns.define('Factor',
    pf.choice([
        pf.sequence([
            pf.terminal('('),
            ns.call('Assign'),
            pf.terminal(')')
        ]),
        ns.call('Name'),
        pf.oneOrMore(
            pf.predicate(function (token) {
                return /[0-9]/.test(token);
            })
        )
    ])
);

var ok = sponsor(function okBeh(m) {
    console.log('OK:', JSON.stringify(m, null, '  '));
});
var fail = sponsor(function failBeh(m) {
    console.log('FAIL:', JSON.stringify(m, null, '  '));
});

var start = ns.call('Assign');
var matcher = pf.matcher(start, ok, fail);
var next = input.fromString(sponsor, 'x=y=10-2/3+4*5/(6-7)');
next(matcher);

Tests

npm test

Message Protocol

A location within a stream is represented with an object like this:

• value: Object Token at current position, if any.
• pos: Number Position in the stream (zero-based).
• next: Actor Actor used to access the next stream position.

Line-oriented character streams have these additional attributes:

• row: Number Line offset (zero-based).
• col: Number Position within the line (zero-based).

PEG parsing actors expect a message with the following attributes:

• input: Object Input stream location (described above).
• ok: Actor Send result message to this actor on success.
• fail: Actor Send result message to this actor on failure.

On success/failure the ok/fail actors expect a result message with the following attributes:

• start: Object Stream location where matching began.
• end: Object Stream location where matching should continue.
• value: Any Result value, if any.

Actor Behaviors

PEG parsing actors are created to check for a match at a given input position. Their behavior is configured by one of the following factory methods. Use sponsor(behavior) to create a pattern-matching actor.

• PEG.fail
• PEG.empty
• PEG.anything
• PEG.terminal(token)
• PEG.predicate(condition)
• PEG.not(pattern)
• PEG.follow(pattern)
• PEG.sequence(list)
• PEG.choice(list)
• PEG.zeroOrMore(pattern)
• PEG.oneOrMore(pattern)
• PEG.zeroOrOne(pattern)
• PEG.object(object)
• PEG.memoize(pattern, [name, [log]])

PEG.fail

Always fail to match, consuming no input. The result value is undefined.

PEG.empty

Always successfully match, consuming no input. The result value is [].

PEG.anything

PEG.dot

Match and consume the current input Character/Token. Fail if there is no further input available. On success, the result value is the consumed input Character/Token.

PEG.terminal(token)

• token: Any The token to expect.

Match and consume the current input Character/Token, if == token. Otherwise fail, consuming no input. On success, the result value is the consumed token.

PEG.predicate(condition)

• condition: Function function (token) {} Evaluates true if the token meets the matching condition.

Match and consume the current input Character/Token, if it meets the condition. Otherwise fail, consuming no input. On success, the result value is the consumed input Character/Token.

PEG.not(pattern)

• pattern: Actor The pattern to check for look-ahead.

Match, but do not consume any input, if pattern fails at the current position. The result value is undefined.

PEG.follow(pattern)

• pattern: Actor The pattern to check for look-ahead.

Match, but do not consume any input, if pattern matches at the current position. The result value is undefined.

PEG.sequence(list)

• list: Array The patterns to match in sequential order.

Iterate through the list consuming input as long as each pattern matches sequentially. If any pattern fails, the sequence fails, consuming no input (reverting to the original position). On success, the result value is an Array (possibly empty) of the matched values.

PEG.choice(list)

• list: Array The patterns to match as an ordered (prioritized) choice.

Iterate through the list trying each pattern in order. The first pattern to successfully match makes the choice successful, consuming the corresponding input. Remaining patterns are not considered after a successful match. Otherwise, each subsequent pattern is tried starting from the original position. If no pattern matches, the choice fails, consuming no input (reverting to the original position). On success, the result value is the matched value.

PEG.zeroOrMore(pattern)

PEG.star(pattern)

• pattern: Actor The pattern to check for possible repetition.

The pattern is matched as many times as possible (maybe 0 times), consuming all the corresponding input. When the pattern fails, the repetition matches up to the failed input position. The result value is an Array (possibly empty) of the matched values.

PEG.oneOrMore(pattern)

PEG.plus(pattern)

• pattern: Actor The pattern to check for repetition.

The pattern is matched as many times as possible (at least 1 time), consuming all the corresponding input. If the first occurance fails, the repetition fails, consuming no input. After the first occurance, when the pattern fails, the repetition matches up to the failed input position. On success, the result value is an Array of the matched values.

PEG.zeroOrOne(pattern)

PEG.question(pattern)

PEG.optional(pattern)

• pattern: Actor The pattern to check for optional occurance.

Match regardless if pattern matches or fails at the current position. If pattern matches, the corresponding input is consumed. Otherwise, no input is consumed. The result value is an Array (possibly empty) of the matched values.

PEG.object(object)

• object: Object An object containing expected property values.

Match and consume the current input Token, if it matches object. Otherwise fail, consuming no input. On success, the result value is the consumed input Token.

PEG.memoize(pattern, [name, [log]])

PEG.packrat(pattern, [name, [log]])

• pattern: Actor The pattern for which successful results will be remembered.
• name: String (Default: '') The name used to label this pattern, if any.
• log: Function (Default: console.log) Used to log informative messages.

Match and remember result if pattern matches. Subsequent attempts to match at the same position will immediately return the remembered result.

Utilities

These utilities ease construction and use of PEG parsing actors.

• PEG.namespace([log])
• PEG.start(pattern, ok, fail)
• PEG.factory(sponsor)

PEG.namespace([log])

• log: Function (Default: console.log) Used to log informative messages.

Establish a collection of related pattern actors which form a cohesive grammar. Pattern actors within the namespace my refer to each other by name. This allows for mutually recursive references within the grammar. A namespace object is returned with the following attributes:

• define: Function function (name, pattern) {} Establishes a name for this pattern in the grammar namespace.
• lookup: Function function (name) {} Returns a behavior that matches the pattern with this name in the grammar namespace.
• transform: Function function (name, transform) {} Establishes a result transform function for the pattern with this name in the grammar namespace.

A result transform function has the form function (name, value, result) {} and returns an new result object with the following attributes:

• name: String The name established for this pattern in the grammar namespace.
• value: Any Result value, if any.
• start: Object (Default: result.start) Stream location where matching began.
• end: Object (Default: result.end) Stream location where matching should continue.

The default transform function simply injects the pattern name into the result.

A namespace object is configurable using the following additional attributes:

• wrapper: Function function (rule) {} Returns a behavior ...
• transformWrapper: Function function (rule) {} Returns a behavior ...
• stackingWrapper: Function function (pattern, rule) {} Returns a behavior ...

Each of these has appropriate defaults which are designed to work together. Be careful if you choose override them.

PEG.start(pattern, ok, fail)

• pattern: Actor The initial pattern for matching this grammar.
• ok: Actor Send result message to this actor on success.
• fail: Actor Send result message to this actor on failure.

Returns a parser bootstrap behavior. Use an Actor with this behavior as the customer for reading from an actor-based input stream. This will start the pattern matching process.

PEG.factory(sponsor)

• sponsor: Function The sponsor used to create actors.

Returns a factory for creating pattern-matching actors with a common sponsor. The factory has helpers (and aliases) for nearly all of the PEG methods, including:

• fail: Actor with PEG.fail behavior.
• empty: Actor with PEG.empty behavior.
• anything|any|dot: Actor with PEG.anything behavior.
• terminal|term: Function function (token) {} uses PEG.terminal(token) behavior.
• predicate|cond|if: Function function (condition) {} uses PEG.predicate(condition) behavior.
• not: Function function (pattern) {} uses PEG.not(pattern) behavior.
• follow: Function function (pattern) {} uses PEG.follow(pattern) behavior.
• sequence|seq: Function function (list) {} uses PEG.sequence(list) behavior.
• choice|alt: Function function (list) {} uses PEG.choice(list) behavior.
• zeroOrMore|star: Function function (pattern) {} uses PEG.zeroOrMore(pattern) behavior.
• oneOrMore|plus: Function function (pattern) {} uses PEG.oneOrMore(pattern) behavior.
• zeroOrOne|question|optional|opt: Function function (pattern) {} uses PEG.zeroOrOne(pattern) behavior.
• object|like: Function function (object) {} uses PEG.object(object) behavior.
• packrat|memoize|memo: Function function (pattern, [name, [log]]) {} uses PEG.memoize(pattern,...) behavior.
• namespace|scope: Function function ([log]) {} augments PEG.namespace([log]) with:
  • factory: Object The factory that created this namespace
  • call: Function function (name) {} Returns an Actor that matches the pattern with this (late bound) name.
• start|match|matcher: Function function (pattern, ok, fail) uses PEG.start(pattern, ok, fail) behavior.

Contributors

@dalnefre, @tristanls