Skip to content
Source on GitHubVisitors

4. ATD grammar notation

Contents of ATD 0.1

ATD's grammar is written in ATD grammar notation, a subset of the grammar language of Lark (https://github.com/lark-parser/lark), stated here so that it can be implemented without Lark. The same notation is used by a binding that carries a grammar (section 11.9). grammar/notation.lark is the notation written as a grammar; every module of ATD's grammar reads under it.

4.1 The subset

Admitted Not admitted
a rule name: expansion | expansion, and a terminal NAME: "x" | /re/ templates _rule{x}
?rule (inlined when it has one child), _rule and _TERMINAL (filtered from the tree) rule priorities rule.2
x?, x*, x+, [x], ( … ) %declare, %override, %extend
an alias -> name %import of anything outside the language's modules (in a binding, outside the binding's own files beside it)
a terminal priority TERMINAL.2 the flags of regular expressions (/x/i), and every flag of a string but i
a string matched in any case of its ASCII letters, "x"i, whose text is ASCII (section 3.6)
%ignore TERMINAL terminals outside the subset of section 3.5
%import .module (names) keep-all-tokens rules !rule, ranges "a".."z", repetitions x ~ 3

Rule names are lowercase, terminal names uppercase. Comments are // to the end of the line. A definition starts with its name and colon and runs to the next definition; an alternative may continue on the next line after |.

4.2 Meaning

  • A rule's expansions are its alternatives; an expansion is a sequence of items; an item is a rule, a terminal, an anonymous string (a terminal whose pattern is that string), an anonymous regular expression, or a group.
  • x? and [x] are x or nothing; x* is any number of x; x+ one or more; ( … ) groups alternatives.
  • A terminal is a string, a string with i, which matches its text in any case of its ASCII letters, a regular expression, or a sequence and choice of other terminals; it matches as section 3.6 says. In grammar/notation.lark a string and its i are one token, GRAMMAR_STRING, so that the flag is never read as a reference to a rule i.
  • %ignore T makes T a candidate in every state and drops what it matches.

4.3 Modules and imports

The grammar of ATD 0.1 is the root module grammar/atd.lark and the modules it imports: core, cel, script, canvas, form, text, binding and notation. Every module's symbols share one grammar:

  • In the root, %import .m (a, b, …) makes the symbols a, b of module m the root's own.
  • A module uses symbols of other modules by name, without an import of its own; the root's import list for that module names each such symbol, which then resolves to the root's symbol of that name. Every terminal a module defines is in the root's import list for it.
  • Every other symbol of module m is private to it, and is named m__symbol (_m__symbol for a symbol that starts with _) in the grammar the modules compose.

These are the rules of Lark's %import, so that Lark builds the grammar from atd.lark directly (contracts/grammar.md, rule 1).

4.4 From notation to rules

An implementation builds its tables from the grammar after this expansion, which is Lark's, so that two implementations build the same automaton:

  1. A group of alternatives inside an expansion is distributed: a (b | c) d becomes the two expansions a b d and a c d.
  2. x? and [x] become two expansions, one with x and one without.
  3. x+ becomes a new rule H: x | H x, and x is replaced by H.
  4. x* becomes the same rule H, and two expansions, one with H and one without.
  5. Two repetitions of the same item share one rule H, wherever they stand.
  6. Duplicate expansions of a rule are kept once.
  7. The start symbol is description. The automaton is augmented as an LR automaton is: the state the start state reaches on description accepts at $END; the augmenting rule is not one of the grammar's rules.

4.5 The parse tree

A conforming parser need not build Lark's tree; ATD's own tree is the abstract tree of $defs/Tree, which an implementation lowers from the parse (section 5.5). For a grammar a binding carries, the tree is shaped as Lark shapes it, since a binding's selectors name its nodes (section 11.9): a node per rule, named by the rule or its alias; ?rule replaced by its child when it has one; _rule replaced by its children; _TERMINAL and anonymous strings dropped; and [x] that matched nothing kept as an empty child.

4.6 The flattened grammar

grammar/atd.flat.lark is the whole grammar in one file, generated by atd-grammar.py --flatten: the modules' definitions with the names of section 4.3, no %import, the root's %ignores, and the rule start: description that model services look for. It builds the same tables as the modules, and LLGuidance's Lark front end, the context-free engine behind grammar-constrained output in the major model services, accepts it (FR-090). It is the file to hand an agent (section 19.4).

4.7 Parse tables

grammar/atd.tables.json ($defs/ParseTables) is the LALR(1) automaton of the grammar, normalized so that two implementations can be compared byte for byte: terminals by name, an anonymous string terminal named by its quoted string, a string with i carrying "flags": "i"; the rules after section 4.4, sorted and numbered, the rule H of a repetition named (<alternatives>)+, its expansions that do not start with H, sorted and joined with |; and the states numbered breadth first from the start state, visiting the shifted symbols in sorted order, each with its actions on terminals (s<state>, r<rule>, accept) and its gotos. atd-grammar.py --tables writes it from Lark; atd tables writes it from another implementation. The grammar builds with no shift/reduce and no reduce/reduce conflict, and no two pattern terminals of one priority that a state accepts match the same text (FR-002, SC-001); a keyword and the pattern that spells it are rule 1 of section 3.6, not such a pair.

Referenced from