Skip to content
Logo

Defining grammars

A grammar is a chain of .define() calls on grammar(), finished by .compose(). Each call adds one rule, and its builder function receives references to the rules defined before it:

const version = grammar()
  .define("digit", () => range("0", "9"))
  .define("number", ({ digit }) => oneOrMore(digit))
  .define("version", ({ number }) =>
    sequence([number, literal("."), number, literal("."), number]),
  )
  .compose();

A builder can't see the rule it defines, or any later one, so a grammar can't recurse. That keeps every grammar regular, which is what lets it have a regex form at all.

Builders are immutable. .define() returns a new builder and leaves the old one as it was, so two grammars can share a prefix:

const base = grammar().define("digit", () => range("0", "9"));
const year = base
  .define("year", ({ digit }) => repeat(digit, { min: 4, max: 4 }))
  .compose();
const hour = base
  .define("hour", ({ digit }) => repeat(digit, { min: 2, max: 2 }))
  .compose();

Combinators

A rule's body is built from these. Each one also decides what its part of the rule's node looks like:

combinatormatchescontributes
literal("-")exactly that textthe text, string
range("a", "z")one code point in the inclusive rangethe code point, string
sequence([a, b])a then ba tuple, readonly [A, B]
either(a, b)a or b, preferring a{ alternative: 0, value: A } | { alternative: 1, value: B }
optional(a)a or nothing, preferring aA | undefined
zeroOrMore(a), oneOrMore(a)a repeated, as many times as can matchreadonly A[], every iteration
repeat(a, { min: 2, max: 4 })a from min to max timesreadonly A[], every iteration
a reference, such as digitthe referenced rulethat rule's node, Node<"digit", …>

Leave out max in repeat for no upper bound. zeroOrMore(a) is repeat(a, { min: 0 }), and oneOrMore(a) is repeat(a, { min: 1 }).

Nodes and children

Every named rule produces a Node<Name, Children>:

  • rule: the rule's name.
  • text: the text it matched.
  • span: where in the input, as { start, end }. See Spans and positions.
  • children: what the rule's body contributes, by the table above.

Anonymous combinators produce no node of their own. Their contributions nest inside the nearest named rule's children:

import {
  ,
  ,
  ,
  ,
  ,
  ,
  ,
  ,
} from "@ghostry/aster";
 
const {  } = ();
 
const  = ()
  .("letter", () => ("a", "z"))
  .("name", ({  }) => ())
  .("number", () => (("0", "9")))
  .("value", ({ ,  }) => (, ))
  .("list", ({  }) =>
    ([, (([(","), ]))]),
  )
  .();
 
const  = (, "list")("ab,12,c");
if (.) {
  const [, ] = ..;
  .childrenArrow
.; // 0, the name
.(([, ]) => .); // ["12", "c"] }

A regex capture group inside a loop keeps only its last iteration. Here every iteration of zeroOrMore is in rest.

To name a node's type, use AstOf:

type ListNode = AstOf<typeof list, "list">;

Which reading wins

A string matches a rule when some way of reading it works, the way a regex does:

const abc = grammar()
  .define("abc", () =>
    sequence([either(literal("a"), literal("ab")), literal("c")]),
  )
  .compose();
 
toParser(abc, "abc")("abc").ok; // true: "a" fails at "b", so "ab" is tried

When more than one reading works, the parser returns the one the regex engine would find first:

  • An either prefers its earlier alternatives.
  • optional prefers to match.
  • A loop prefers one more iteration.

Preference only decides which reading you get back, never whether the input matches.

Definition checks

.define() checks each rule as it's added, so a grammar that composes is one every output can compile. Each error is on the AsterError namespace and names the rule:

errorwhen
DuplicateRuleErrorthe name is already defined
UnknownReferenceErrorthe body refers to a rule not defined before it
InvalidRangeErroran endpoint isn't exactly one code point, or the endpoints are reversed
InvalidRepetitionErrormin or max isn't a whole number, max is below 1, or max < min
EmptyEitherErroran either has no alternatives
NullableQuantifierErrorthe body of a loop or an optional can match the empty string
InvalidExpressionErrorthe body contains something that isn't an expression

TypeScript catches most of these first: a duplicate name, or a reference to a rule the builder doesn't have.

NullableQuantifierError needs a word. optional(zeroOrMore(x)) is ambiguous about how many times an empty match repeats, and JS regex resolves that in a way a linear-time parser can't reproduce. It never costs anything to fix: drop the optional, since zeroOrMore(x) already matches nothing. For a loop over something that can be empty, move the optional outside the loop.