Grammars And Parsers

Grammars are immutable Grid values. A grammar declares language semantics; a parser generator declares an execution strategy; applying one to the other produces a parser value. Parsing returns a result value containing either a parse tree or a structured parse error.

These values can be named, imported from .gs modules, passed through ordinary bindings, inspected, and resolved without converting them to source text.

Choose Semantics First

Grid supports several grammar formalisms without treating them as aliases:

AUTO chooses only within the grammar's declared formalism. It never turns a CFG into a PEG or changes ordered choice into unordered choice. An explicitly incompatible pairing produces GRID_PARSER_GENERATOR_INCOMPATIBLE.

CFG Example

GRAMMAR arithmetic IS CFG
  TOKEN NUMBER = /(?:0|[1-9][0-9]*)(?:\.[0-9]+)?/
  SKIP /\s+/
  START expression
  expression = expression "+" term | term
  term = term "*" primary | primary
  primary = value:NUMBER | "(" expression ")"
END
 
fast = arithmetic USING LALR
general = arithmetic USING EARLEY
result = PARSE("1 + 2 * 3", fast)

LALR rejects conflicts while building the parser. Earley accepts general CFGs and reports an ambiguous input as GRID_PARSE_AMBIGUOUS by default. Select one deterministic derivation explicitly when that is the intended contract:

first = arithmetic USING EARLEY(ambiguity = FIRST)

PEG And Regular Examples

PEG uses / for ordered choice:

GRAMMAR command IS PEG
  START command
  command = "start" / "stop"
END
 
parser = command USING PACKRAT
result = PARSE("start", parser)

A regular grammar has exactly one MATCH declaration:

GRAMMAR identifier IS REGULAR
  MATCH /[A-Za-z_][A-Za-z0-9_]*/
END
 
parser = identifier USING DFA
result = PARSE("grid_21", parser)

Generators Are Values

Use GENERATOR when the strategy itself should be named or shared:

bounded = GENERATOR DFA(
  max_input_bytes = 4096,
  max_steps = 100000,
  max_nodes = 10000
)
 
parser = identifier USING bounded

The same binding can live in a .gs module and be imported with USE. Canonical formatting omits options that retain their defaults.

Grammar Body

CFG and PEG blocks accept:

• START rule to select the entry rule; the first rule is the default.
• SKIP /pattern/ for ignored text between tokens.
• TOKEN name [PRIORITY integer] = /pattern/ for named tokens.
• rule = expression for productions.
• literals ("text"), inline patterns (/pattern/), token/rule names, grouping, named captures (name:expression), and postfix ?, *, +, or {min,max} repetition.
• BUILDS constructor(capture, ...) after a production alternative names the semantic constructor for the node that alternative produces — BUILDS add(left, right), or nullary BUILDS zero(). BUILDS capture (a bare capture name) passes that child through without adding a node.

The declared constructors form the grammar's tree signature. Every grammar-bound tree declaration (PATTERN, THEORY, ALGEBRA, TRANSFORM, TRANSLATE, SOLVER, THEOREM) binds a rule's sort with ON grammar.rule — for example ON calc.expression — and its pattern, law, and goal fragments are written in the grammar's own concrete notation: for a grammar that spells addition plus(x, zero), a law reads plus(x, zero) == x, using the grammar's spelling rather than the constructor name. Metavariables carry no sigil, and constructors are not author-facing functions.

Token ties at the same priority are errors rather than source-order guesses. Token references are case-insensitive, while their authored spelling is preserved in trees and formatted source. String literals accept ordinary UTF-8 and \uXXXX / \u{...} escapes. Regex delimiters are escaped as \/.

Zero-width token, skip, and literal patterns are rejected. Write () for an intentional empty production; this keeps nullable structure visible instead of hiding it in an empty string.

Grammar-Bound Trees

The TREE authoring and implementation surface is available through TREE-11. Release certification is currently through TREE-6: TREE-7 is being revalidated through the release matrix after its focused implementation closeout passed, and TREE-8 through TREE-11 remain on promotion hold while their transactional cancellation and native-codec gates are completed. Availability does not waive those release gates. TREE-7's production decision kernels are sorted-reader-native; a recursive owned value is constructed only at a bounded, interruption-aware public portability, publication, or replay freeze after the decision. Live callback decision and traversal work debits the caller-owned meter once; physical canonical encoding polls the same operation-local interruption fence in bounded chunks without a duplicate logical byte charge. TREE-10's generic compiler transform is likewise real, but it executes only in explicit qualification. The faster handwritten fold is the only normal compiler path, so ordinary compilation performs neither dual execution nor a discarded Tree result.

TREE-0 provides the contextual declaration scanner, source-preserving syntax model, namespace/callable checks, exact fragment partition diagnostics, and canonical formatting. TREE-1 adds grammar-rooted native syntax_tree, tree_term, and tree_context values. Current models can inspect sorts, structure, terminals, fingerprints, origins, free names, and bindings; render validated trees; select subtrees; form contexts; and perform bounded hygienic context plugging. TREE-2 adds eager portable grammar-bound PATTERN/tree_pattern values, source-ordered WITHOUT fragments, exact bounded scalar/optional/sequence matching, canonical matches/captures/contexts, and TREE.MATCH backed by compiled structural discriminators and variadic-boundary pruning. These operations execute only inside the owning model's compiler-admitted grammar/signature authority and cross native process or HTTP boundaries only through the authenticated native Tree transport. TREE-3 adds eager immutable THEORY values with regular and non-regular many-sorted conditional equations, heterogeneous inclusion/import, assumed authority, and binding-valid direction metadata. Theory declarations are inert: they do not add a Workbook value, Graph or Predicate region, analysis operation, or executable expression. TREE-3 also makes Predicate-backed WHEN conditions on PATTERN current. A conditional match uses candidate-local structural facts plus the model's exact Predicate program and resident Graph revision, and succeeds only with supported-and-not-refuted evidence. TREE-4 adds eager immutable ALGEBRA/tree_algebra values whose explicit associative, commutative, one-sided identity, idempotent, and alpha roles cite exact theory laws. MODULO patterns use those profiles for bounded variadic ACUI matching while publishing original occurrence paths and origins. TREE.NORMALIZE(tree, algebra, work) performs the same exact bottom-up canonicalization atomically and returns a replay-authorized tree_operation_result. TREE-5 adds eager immutable TRANSFORM/tree_transform values, mixed theory-law and directed-rule candidate streams, captured/derived/fresh bindings, exact or algebraic matching, author-selected orientation, top-down/bottom-up and once/repeat traversal, THEN composition, hygienic transactional replacement, and refusal-biased REQUIRE TERMINATING / REQUIRE CONFLUENT certificates. A named transform is called directly with one tree; TREE.APPLY(operation, tree) applies an aliased or selected handle under the transform's identity-bearing limit and returns the same bounded, replay-authorized tree_operation_result. Predicate-backed conditions admit a candidate only in the exact supported evidence state. TREE-6 adds eager immutable TRANSLATE/tree_translation values over independently authenticated source and target grammar domains. Exact sort-pair rules combine captured, derived, and fresh target bindings with explicit token maps and converters, strict-descendant recursion, exact delegation, optional and sequence splicing, target-language hygiene, signature validation, and render/reparse validation. Named one-tree calls and dynamic TREE.APPLY(operation, tree) use the same transactional executor and publish the same authenticated complete or incomplete operation result, derivation, condition evidence, and replay transport.

TREE-7 is implemented across authoring, evaluation, native transport, and public catalog surfaces, with release promotion still under the revalidation described above. TREE.UNIFY(left, right, algebra_or_exact, family_limit, work) returns canonical complete or sound-prefix constrained families. TREE.SUBSTITUTE(term, family, context, work) has exactly four arguments; context is :left, :right, or :qualified, and no three-argument or side-inferred form exists. TREE.NARROW(term, theory, algebra_or_exact, step_limit, work) returns one-step successors in occurrence, flattened-law, and direction order. A flattened semantic law retains its complete ordered source-origin vector as authority but still contributes one attempt per direction, not one attempt per origin. Symbolic results remain tree_term values through the append-only GRIDUTRM owner. Newly produced symbolic values use GRIDUTRM schema 2: a cycle-free envelope retains the exact substitution or narrowing invocation so the value can be cold-replayed from its authenticated producer entry without trusting a live result cache. Capture-avoidance terminals retain their stable original source, exact grammar-owned quoting/wrapper recipe, authenticated rename transcript prefix, and complete origin; rename chains require no intermediate symbolic value. Legacy schema-1 owner bytes remain readable only with their exact retained live replay authority and are never silently upgraded. GRIDTVRS stays at schema 2 with its existing native tags. TREE-7-reachable patterns use self-contained GRIDPATT schema 5, and narrowing theories use self-contained executable GRIDTHTY schema 2; each exact render companion is identity-bearing inside the public value, so a ground result renders and reparses without a constructor printer or companion registry. Reachability is the frozen whole-module conservative may-flow fixed point seeded by the exact term, theory, and algebra operands of TREE.UNIFY, TREE.SUBSTITUTE, and TREE.NARROW after imports and callables are finalized. It follows every assignment revision, alias, container or branch, rule writer, callable parameter/capture/return, theory include, and algebra theory reference. One exact immutable producer uses one upgraded representation for all consumers; dynamic inputs must already carry that representation at runtime, unreachable TREE-0-through-TREE-6 values retain their bytes, and a missing exact companion fails lowering rather than being guessed or rebuilt.

Exact and algebraic unification, capture-avoiding substitution, one-step narrowing, and theorem-facing reconstruction make their semantic decisions over sorted readers with bounded iterative traversal. Nested algebra, hygiene, residual, capture, and reconstruction work remains inside one caller-owned work/interruption fence. Physical canonical encoding polls that same fence in bounded chunks after the single logical traversal charge. A public recursive owner is therefore a portable result or replay image, not an internal execution language. Candidate owners stay private until final-public publication and deduplication; only a unique public result commits authority or a solver state.

TREE-8 implements immutable SOLVER/tree_solver values and model-scoped TREE.SOLVE; release promotion remains held. A solver binds one rooted grammar domain, one or more ordered USING, STEPS, or TACTICS sources, an optional algebra and orientation, exactly one EQUAL, root/subtree MATCH, or NORMAL goal, one deterministic search strategy, and explicit positive depth, state, solution, and work bounds. Breadth-first, iterative-deepening, best-first, bidirectional breadth-first, and bidirectional best-first use their frozen total orders. Equality search accepts only equality authority; current sources are assumed theory laws and explicitly equality-preserving transforms. Operational directed steps can reach MATCH or NORMAL but cannot appear in an equality certificate.

SOLVER equivalence ON calc.expression
  USING calc_laws
  GOAL EQUAL
  SEARCH BREADTH FIRST
  DEPTH 2
  STATES 32
  SOLUTIONS 1
  LIMIT 100000
END
 
proof = equivalence(left_tree, right_tree)

The calc grammar and calc_laws theory are the worked example in the cookbook, which assembles this solver, its theory, and a checked theorem into one complete model.

A named solver is called directly, like a named transform: an EQUAL solver takes two trees, while MATCH and NORMAL solvers take one. TREE.SOLVE(solver, input) executes a MATCH or NORMAL solver, while TREE.SOLVE(solver, left, right) executes an EQUAL solver. An arity/goal mismatch fails closed, a MATCH goal requires a pattern that retains its executable template companion (GRID_TREE_EXECUTABLE_PATTERN_REQUIRED), and an EQUAL solver whose sources carry no equality authority is rejected with GRID_TREE_SOLVER_EQUALITY_SOURCE. The returned tree_solver_result exposes the exact seven-field record status, solutions, explored, frontier, work, complete, stop; its authenticated logical checkpoint remains private. Only complete frontier exhaustion returns :unsolved. Depth, state, work, and stricter process bounds return incomplete :limit with the exact :depth, :states, :work, or :process stop. Reaching the solution quota returns :solved with :quota, and interruption returns incomplete :interrupted. Solutions retain replay-checked certificates and conditioned MATCH evidence, resident WHY uses those same derivations, and cold, warm, resumed, and parallel execution publish the same canonical prefix.

TREE-9 implements SEARCH SATURATE BY cost and THEOREM; release promotion remains held. Saturation uses bounded equality classes and congruence closure for assumed or proved equality while tracking operational directed reachability separately for MATCH and NORMAL; it preserves the ordinary source, condition, cost, bound, and proof semantics, and extraction uses the named cost.

A theorem states a universally quantified equation and requires proof by a named GOAL EQUAL solver over the same root:

THEOREM plus_zero(x) ON calc.expression USING equivalence:
  plus(x, zero) == x

Compact and indented law forms are both valid, with one optional outer WHEN proposition that becomes a scoped proof premise rather than a published model fact. Declared parameters are rigid during the proof, and every parameter must appear in the equation (GRID_TREE_PARAMETER_UNUSED). If the solver returns anything short of a complete replayable certificate, the declaration fails with GRID_THEOREM_UNPROVED. A proved theorem carries :proved authority — distinct from the :assumed authority of theory laws — and is accepted wherever a declaration clause accepts an equation source: THEORY ... INCLUDES theorem, an ALGEBRA role clause citing a bare theorem name in place of theory.law, TRANSFORM ... USING theorem, and SOLVER ... USING theorem. An algebra whose roles cite theorem-backed laws works in MODULO patterns like any other algebra. Production and cold replay retain exact theorem, statement, solver invocation, premise, source, residual, goal, and saturation-event coordinates.

The recognized declaration heads are PATTERN, THEORY, ALGEBRA, TRANSFORM, TRANSLATE, SOLVER, and THEOREM. PATTERN and THEORY are current through TREE-3, ALGEBRA is current at TREE-4, TRANSFORM is current at TREE-5, TRANSLATE is current at TREE-6, SOLVER is current at TREE-8, and THEOREM is current at TREE-9. The heads are contextual rather than globally reserved: an ordinary identifier with one of those spellings keeps its existing meaning unless the complete declaration header matches. Compact and indentation-delimited items retain the bound grammar's bytes. Formatting may normalize Grid-owned declaration indentation and the uniquely selected outer ==, =>, and WHEN separators, but it does not reflow or canonicalize the grammar-owned fragments between them.

The exact reserved direct heads are TREE.SORT, TREE.SIZE, TREE.DEPTH, TREE.CHILDREN, TREE.CONSTRUCTOR, TREE.SYMBOL, TREE.TERMINAL, TREE.FINGERPRINT, TREE.ORIGIN, TREE.FREE_NAMES, TREE.BINDINGS, TREE.RENDER, TREE.AT, TREE.CONTEXT, TREE.PLUG, TREE.MATCH, TREE.NORMALIZE, TREE.APPLY, TREE.UNIFY, TREE.SUBSTITUTE, TREE.NARROW, and TREE.SOLVE. A well-formed declaration or reserved call whose semantic milestone is not available receives one GRID_TREE_FEATURE_UNAVAILABLE diagnostic over the complete construct. The diagnostic names both the required milestone and the current TREE-11 source-availability ceiling. This code-facing ceiling is distinct from the release-certification boundary described above. Malformed constructs receive their specific syntax or fragment diagnostic instead.

Grid-native symbolic mathematics — contextual symbol declarations, ordinary operator composition over the shipped non-source math.expression term signature, and the closed SYMBOLIC.* registry — ships as its own subsystem on this substrate; see symbolic-mathematics.md. It is not part of the generic TREE authoring surface described here, and no separate symbolic source grammar exists: symbolic expressions are written as ordinary Grid formulas. A bundled authorable mathematical theory library and a domain-specific solver catalog for the TREE declarations above remain deferred.

Results, Bounds, And Persistence

PARSE(text, parser) is total: a language rejection is a parse-result value, not a failed workbook evaluation. PARSE_RESULT_OK, PARSE_RESULT_TREE, and PARSE_RESULT_ERROR provide formula-level projections. Errors are ordinary records with code, message, offset, expected, and found fields.

Successful trees retain their source. PARSE_TREE_SOURCE(tree) returns it, PARSE_TREE_ROOT(tree) returns a nested node record, and PARSE_TREE_CAPTURE(tree, "name") returns all matching node records in source order. Each node has symbol, capture, start, end, text, and children fields, so normal record and vector operations are sufficient for traversal.

Trees Are Native Graph Sources

A successful parse tree can directly seed a resident Graph. No node/edge Frame and no JSON conversion is involved:

result = PARSE("1 + 2 * 3", fast)
tree = PARSE_RESULT_TREE(result)
graph syntax = GRAPH(tree)
 
node_count = syntax.NODE_COUNT()
root_symbol = syntax.NODE_PROPERTY(1, "symbol")
frame children = syntax.NEIGHBORS(1)

The Graph is directed from parent to child and uses deterministic one-based preorder integer node IDs for the current tree revision. Each node carries kind = :parse_node, symbol, optional capture, byte-offset start/end, source_cell, root, and leaf. The root additionally carries tree_schema_version, grammar_fingerprint, and parser_generator.

Every edge carries kind = :child and a one-based ordinal; an edge whose child has a capture also carries that capture as field. Graph adjacency has canonical graph ordering, so syntax consumers must use ordinal whenever child order matters. Source text remains stored once in the native parse-tree value and is addressed through the node spans rather than duplicated into Graph properties.

Because this is an ordinary resident GraphHandle, persistent patches, traversal, path, pattern, view, and bounded Graph algorithms work unchanged. It may also be projected into Predicate reasoning:

KNOWLEDGE GRAPH syntax
predicate child is transitive
is_descendant = MUST(1 child 7)

WHY(is_descendant) retains the contributing child-edge identities and the source-cell byte spans of their child nodes. A rejected parse remains a parse-result error value; extract a successful tree before constructing its Graph.

Every generator carries deterministic input-byte, work-step, and parse-node budgets. Grammar normalization, LALR construction, and DFA construction also have hard compilation bounds. A parse budget failure is GRID_PARSE_BUDGET_EXCEEDED; a construction bound is reported before the parser becomes usable.

Authored limits may lower, but never raise, the process ceilings: 1 MiB of input, 10 million work steps, 1 million result nodes, and a parse-tree depth of 1024. Grammar definitions are also bounded to 4,096 rules/tokens, 16,384 expression nodes, and 8 MiB of aggregate authored grammar data.

Persisted compiled models store grammar definitions and parser recipes only. Compiled tables, memo caches, and DFA state are reconstructed process-locally after hydration and never enter the bytecode identity. Equal recipes share a weak process-local compiled artifact cache, while workbook and collection residency accounting includes the compiled automaton retained by each live parser value.