@atomist/microgrammar

Parsing library written in TypeScript, filling the large gap between the sweet spots of regular expressions and full-blown BNF or equivalent grammars. It can parse and cleanly update structured content.

Concepts

Microgrammars are a powerful way of parsing structured content such as source code, described in this Stanford paper. Microgrammars are designed to recognize structures in a string or stream and extract their content: For example, to recognize a Java method that has a particular annotation and to extract particular parameters. They are more powerful and typically more readable than regular expressions for complex cases, although they can be built using regular expressions.

Atomist microgrammars go beyond the Stanford paper example in that they permit updating as well as matching, preserving positions. They also draw inspiration from other experience and sources such as the old SNOBOL programming language.

Examples

There are two styles of use:

• From definitions: Defining a grammar in JavaScript objects representing the subcomponents (lower level productions)
• From strings: Defining a grammar in a string that resembles input that will be matched

A microgrammar has a return type defined by its definitions. Each match implements this interface and also the PatternMatch interface, which exposes the offset within the input and matched value, which may differ from the exposed typed value. (For example, a Person might have a forename and surname, but its $matched value might include the entire matched string with whitespace.) The fields of the PatternMatch interface begin with a $ to ensure that they are out of band.

When you've defined a microgrammar, you can use it to match input: usually a string.

Generator-style iteration is usually most efficient, and looks like this:

const matches = myMicrogrammar.matchIterator(inputString);
for (const match of matches) {
	// Do with match. You can jump out of the generator here.
}

You can also get all matches in one pass, like this:

const matches = myMicrogrammar.findMatches(inputString);
for (const match of matches) {
	// Do with match
}

If you are seeking only one match, you can use a method that returns a match or undefined, as follows:

const match = myMicrogrammar.firstMatch(inputString);
if (match) {
	// Do with match
}

Definitions style

Here's a simple example:

const mg = microgrammar<{name: string, age: number}>({
    name: /[a-zA-Z0-9]+/,
    _col: ":",
    age: Integer
});

const results = mg.findMatches("-celine:61 greg*^ tom::: mandy:11");
assert(result.length === 2);
const first = results[0];
assert(first.$matched === "celine:61");
// The offset of this match was the 1st character, as the 0th was discarded
assert(first.$offset === 1);
assert(first.name === "celine");
assert(first.age === 61);

Some notes:

• A microgrammar definition is typically an object literal, with its properties being matched in turn. This is like concatenation in a BNF grammar.
• Matcher property values can be regular expressions (like /[a-zA-Z0-9]+/ here), string literals (like :), or custom matchers (like Integer). It's easy to define custom matchers for use in composition.
• All properties need to match for the whole microgrammar to match.
• Properties that match are bound to the result, unless their names begin with _, in which case the values are discarded.
• Certain out of band values, beginning with $, are added to the results, showing the exact text that matched, the offset etc.
• When using TypeScript, microgrammar returns can be strongly typed. In this case we've used an anonymous type, but we could also use an interface. We could also use untyped, JavaScript style.
• Matching skips junk such as greg*^ tom:::. In this case, greg and tom: will look like the start of valid matches, but the first will fail when it can't match a : and the second when there isn't a digit after the colon.
• We can match against a string or a stream. In this case we've used a string. In stream matching, we'd be more likely to use one an API offering callbacks rather than building an array, so we don't need to hold all our matches in memory at once.

Of course, such a simple example could easily be handled by a regular expression and capture groups. But the power becomes apparent with nested productions and more elaborate matchers.

A more complex example, showing composition:

export const CLASS_NAME = /[a-zA-Z_$][a-zA-Z0-9_$]+/;

// Any annotation we're not interested in
const DiscardedAnnotation = {
    _at: "@",
    _annotationName: CLASS_NAME,
    _content: optional(JavaParenthesizedExpression),
};

const SpringBootApp = microgrammar<{ name: string }>({
    _app: "@SpringBootApplication",
    _content: optional(JavaParenthesizedExpression),
    _otherAnnotations: zeroOrMore(DiscardedAnnotation),
    _visibility: optional("public"),
    _class: "class",
    name: CLASS_NAME,
});

This will match content like this:

@SpringBootApplication
@Foo
@Bar(name = "Baz", magicParam = 31754)
public class MySpringBootApplication

Notes:

• JavaParenthesizedExpression is a built-in matcher constant that matches any valid Java content within (...). It uses a state machine. It's easy to write such custom matchers.
• By default, microgrammars are tolerant of whitespace, treating it as a token separator. This is the behavior we want when parsing most languages or configuration formats.
• Because the other properties have names beginning with _, only the class name (MySpringBootApplication in our example) is bound to the result. We care about the structure of the rest of the class declaration, but we don't need to extract other values in this particular case.

String style

This is a higher level usage model in which a string resembling the desired input but with variable placeholders is used to define the grammar.

This style is ideally suited for simpler grammars. For example:

const ValuePredicateGrammar = microgrammar<Predicate>({
    phrase: "@${name}='${value}'"});

It can be combined with the definitional style through providing optional definitions for the named fields. For example, to constrain the match on a name in the above example using a regular expression:

const ValuePredicateGrammar = microgrammar<Predicate>({
    phrase: "@${name}='${value}'", 
    terms: {
    	name: /[a-z]+/
    }
});

As with the object definitional style, whitespace is ignored by default.

Further documentation can be found in the reference. You can also take a look at the tests in this repository.

Alternatives and when to use microgrammars

Microgrammars have obvious similarities to BNF grammars, but differ in some important respects:

• They are intended to match and explain parts of the input, rather than the whole input
• They excel at skipping content they are uninterested in
• They are not necessarily context free
• They do not need to construct a full AST, although they construct ASTs for structures they do match. Thus they can easily cope with partially structured data, happily skipping over incomprehensible content

Similarities are:

• The idea of productions
• Composability, including the ability to reuse productions in different grammars
• Operations such as alternative, optional and rep, that enable building complex structures.

Compared to regular expressions, microgrammars are:

• Capable of handing greater complexity
• More composable
• Higher level, able to use regular expressions as building blocks
• Capable of expressing nested structures
• Arbitrarily extensible through TypeScript function predicates and custom matchers

While it would be overkill to use a microgrammar for something that can be expressed in a simple regex, microgrammars tend to be clearer for complex cases.

Usage

The @atomist/microgrammar package contains both the TypeScript typings and compiled JavaScript. You can use this project by adding the dependency in your package.json.

$ npm install --save @atomist/microgrammar

Troubleshooting

If you struggle to make your microgrammars match, please refer to the troubleshooting page.

Performance considerations

See Writing efficient microgrammars.

Support

General support questions should be discussed in the #support channel in the Atomist community Slack workspace.

If you find a problem, please create an issue.

Development

You will need to install Node.js to build and test this project.

Build and test

Install dependencies.

$ npm install

Use the build package script to compile, test, lint, and build the documentation.

$ npm run build

Release

Releases are handled via the Atomist SDM. Just press the 'Approve' button in the Atomist dashboard or Slack.

Created by Atomist. Need Help? Join our Slack workspace.