Galley Compiler

Appearance

Grammar Writing Guidelines ​

Table of Contents ​

This guide details the syntax, conventions, and compile-time annotations supported by this repository's parser generators (LL and LR).

1. File Structure & Rule Syntax (.grm files) ​

  • Rule Structure: Each grammar rule is defined by the LHS (Left-Hand Side) variable symbol on a single line, followed by its alternative productions.

  • Unique Rule Headers: Each variable must have exactly one LHS header. Put all of its alternatives on consecutive | lines beneath that header; declaring the same LHS again is an error.

  • Alternation: Each alternative production must start with a pipe character | on a new line, followed by space-separated symbols:

    Value
| "{" OptionalBlank ObjectMembers OptionalBlank
| "null" OptionalBlank

  • Epsilon (Empty Productions): An empty production is represented by a single pipe | with no trailing symbols:

    OptionalBlank
| space _OptionalBlankTail
|

  • Formatting: Rules must be separated by at least one blank line. The first variable defined in the file is automatically treated as the parser's entry point.

2. Variable Naming & AST Generation ​

The parser generator statically configures the Abstract Syntax Tree (AST) node creation based on the naming style of the variable symbols:

  • PascalCase Validation: All variable names must be written in PascalCase. The generator validates this at compile-time.
  • AST-Enabled Variables: Variables starting with a Capital letter (e.g. Value, ObjectMembers) allocate an AST node when matched.
  • AST-Suppressed Helper Variables: Variables starting with an underscore (e.g. _StringContent, _OptionalBlank) are helper rules. The generator completely skips allocating AST nodes for them, optimizing runtime parsing performance and memory footprint.

3. Terminal Symbols ​

Terminals in rules represent either exact character literals or pre-defined generative character classes:

  • Normal Terminals: Exact character/string matches can be written in one of two quoting styles:
    • Double-quoted: Wrapped in double quotes (e.g., "{", "null", "+").
    • Single-quoted: Wrapped in single quotes at the start and terminating with the \x03 (0x03) byte (e.g., '"\x03 representing the " character).
  • Generative Character Terminals: Unquoted keyword names map to specific sets of ASCII characters:
    • digit: Matches '0'-'9'
    • letter: Matches 'a'-'z' and 'A'-'Z'
    • lowercase_letter: Matches 'a'-'z'
    • uppercase_letter: Matches 'A'-'Z'
    • whitespace: Matches whitespace characters (\t, \n, \r, \x0b, \x0c, )
    • punctuation: Matches standard punctuation characters
    • character: Matches letters, digits, punctuation, and whitespace
    • operator: Matches operator symbols (+, *, /, &, |, >, >=, <, <=, =)
    • new_line: Matches \n
    • space: Matches space ' '
    • block_start: Matches control character \x01 (representing the start of a block when indentation syntax is enabled for the parser, see Language Configuration for details)
    • block_end: Matches control character \x02 (representing the end of a block when indentation syntax is enabled for the parser, see Language Configuration for details)
  • Generative Suffix Exceptions: Any generative terminal can have exceptions appended as a suffix chain introduced by the ^ character followed by a normal terminal (e.g., character^"\n", character^'"\x03, or multiple chained exceptions like digit^"1"^"3"). The exception terminal's characters are excluded from the allowed terminal characters of the generative class.

4. Procedure Hooks (@procedure_name) ​

Galley provides three explicit hook placements, registered by appending a procedure name with @, and a fourth family of automatic reduction hooks:

  1. LHS Variable Hook: Attaches to the left-hand-side variable definition, executing whenever this variable is reduced anywhere:

    Value@dropChildren
| Object OptionalBlank
| Array OptionalBlank

  2. RHS Symbol Hook: Attaches to a right-hand-side symbol (either a variable, or a terminal symbol if --ast-for-terminals is active), executing only when matched in that position:

    Parent
| Value Child@validateChild "]"

Number
| digit@recordDigit _PositiveIntegerNumberTail

  3. Production Hook: Attaches to the left-hand-side variable for a specific right-hand-side production. It is placed immediately after the pipe (|) and executes on the resulting left-hand-side node only when that particular production is reduced:

    FloatTail
|@normalizeFraction "." PositiveIntegerNumber
|

  4. Automatic Reduction Hooks: Exporting conventionally named public procedures from procedures.zig binds them without grammar annotations:

    • reduction_<SymbolName>_<RhsIndex> runs only for the zero-based production index of that symbol. Indices follow the consecutive | lines beneath the variable's unique LHS header.
    • reduction_<SymbolName> runs whenever that symbol produces an AST node.
    • reduction runs for every eligible variable reduction and AST-enabled terminal match.

Multiple procedures can be chained on any explicit hook target (for example, Number@hook1@hook2). Chaining runs the procedures from left to right; it is not a separate hook kind.

For each variable reduction, hooks run in this order: RHS occurrence hooks, production hooks, reduction_<SymbolName>_<RhsIndex>, LHS hooks, reduction_<SymbolName>, then the general reduction hook. Each explicit chain runs left to right, and each phase receives the node produced by the preceding phase.

For an AST-enabled terminal, the occurrence chain runs first, followed by reduction_<SymbolName> and then reduction. Terminal hooks receive args.rule = null. LR generation reports error.AmbiguousProcedureHooks if the parser cannot distinguish occurrences with different chains at the match or reduction point.

For detailed information on automatic hooks, nested reduction ordering, compiler AST requirements, and how to write hook functions in Zig, see the Reduction Procedures User Guide.

5. Explicit Syntax Recovery (!) ​

Recovery annotations declare synchronization terminals on an LHS variable, a production, or an RHS variable occurrence:

text
Statement!^"}"!";"^@hook
|!","^ Expression
| Block Statement!^"}"
  • !^"}" resumes immediately before } and preserves the terminal for the surrounding parser state.
  • !";"^ resumes immediately after ; and consumes the terminal.
  • Consecutive annotations provide multiple candidates for one target. They must appear before any @ hooks on that target.
  • Recovery terminals accept the same two quoted exact-terminal forms as normal grammar terminals. Empty terminals, NUL-containing terminals, and generative terminals are invalid.
  • An RHS recovery annotation may only attach to a variable occurrence, not a terminal occurrence.

When error recovery generation is enabled and the grammar has no annotations, Galley uses automatic recovery. The presence of any recovery annotation selects explicit-only recovery for the generated parser; an error outside committed annotated scopes fails immediately without automatic fallback. When recovery generation is disabled, annotations remain in the grammar model but are inert, and generation emits one warning.

After a mismatch, Galley tries committed scopes from the most specific to the most general: the active RHS occurrence, its selected production, its LHS variable, then enclosing reductions. Within one target it chooses the earliest candidate in the input, then the longest terminal, then source order. A successful recovery preserves the original mismatch diagnostic, adds structured recovery context, neutral-completes the damaged variable, and skips hooks belonging to the damaged occurrence, production, and variable.

Galley's own LL grammar and LR grammar are maintained examples. They recover a damaged Symbol before its newline, discard a damaged RightHandSideLine after its newline, and fall back from a damaged Rule to the blank line before the next rule. Run zig build compare-galley-recovery to see the annotated LL grammar and an annotation-free clone parse the same malformed grammar in explicit and automatic modes.