Chapter 12

Grammar Syntax

This chapter collects the syntax of a grammar file in one place. The grammar below is written in SyntaxIR itself and summarizes token structure and expression forms. The chapters that define each construct remain normative for validation and meaning.

The repository holds a full grammar of the language, sxir.sxir, which is the input of the generated parser of grammar files. Its actions produce a typed source tree with comments, source forms, and recoverable error nodes. This tree is separate from the public ast.Grammar AST.

The grammar is checked by tests, which run both views on every .sxir file of the repository and on every sxir code block of the documentation and require them to agree with the parser of the reference implementation on whether the text is a valid grammar. They also compare the errors of mutated texts that are not valid, in numbers of sources per class: the first error is at the same place, or at another place for the same mistake, such as the next token or the end of a block or group that the text does not close. The comparison is a measurement on a generated corpus, not a proof, and an error before the first error of the reference is accepted only in the named forms.

Simple Grammar

In a string or a character class the grammar accepts any character after a backslash. A literal with an unknown or invalid escape is still an error, found when the literal is decoded, so that a definition with such a mistake is kept in a partial parse.

This syntax view omits result types, Value Actions, captures, metadata attributes and recovery handling. Unnecessary grouping is removed while retaining parentheses required by precedence or source layout. Predicate Actions and matching pragmas remain, including the state that controls physical newlines. Generate the view with sxir fmt -syntax sxir.sxir or grammar.FormatSyntax(g) in Go. This is a readable projection: in other grammars, a predicate may depend on captures, constructed values or types that the simplified view omits.

// SyntaxIR grammar syntax and typed source tree.
// Source forms are preserved before semantic validation and compilation.
package sxir

// ml reports whether line breaks are allowed between tokens inside the enclosing delimiters.
var ml bool
// junk is set while a declaration is parsed again after it failed: text that cannot continue a complete
// declaration is then skipped, and the declaration is kept.
var junk bool

// File and statements. Delimiter-owned expressions enable multiline trivia;
// declaration and item lists keep physical newlines as statement boundaries.
@start(default)
rule main = file
@start
rule file = &source_comments &source_gaps &.* #atomic file_contents
rule file_contents = (
    {ml := false}
    &source_head
    package_entry?
    decl*
    comments $$
)
rule package_entry = &(comments (package_attrs / "package" !ident_char)) package_stmt
// The attributes of the package clause reach a line that starts with "package".
rule package_attrs = "@" (!("package" !ident_char) attr_unit / nl comments &"@")* nl comments "package" !ident_char
rule package_stmt = (
    &source_remaining comments
    package_body &source_item_tail stmt_end
)
rule package_body = (
    (attr decl_attr_gap)*
    "package" -word_end #cut ident
)
rule decl = (
    !(comments $$)
    (type_decl / var_decl / rule_decl / junk_decl / _|_)
)
// A declaration that failed is parsed again with junk set, so that a complete declaration followed by text
// that is not a separator is kept and the text is reported. The first parse stays strict, so the errors of a
// declaration that has not ended are reported where the farthest attempt stopped.
rule junk_decl = {junk := true} (type_decl / var_decl / rule_decl) {junk := false}
// A declaration that is complete but followed by a closing bracket instead of a separator is kept: the
// error is reported and the rest of its statement is skipped. Any other text there could continue the
// declaration, so the declaration fails as a whole, and the error is where the farthest attempt stopped.
rule stmt_end = horizontal (stmt_sep / stmt_skip / stmt_junk)
rule stmt_skip = &[)\]}] stmt_sep
rule stmt_junk = {junk} &(decl_keyword !ident_char / "=" ![=>] / "/*") stmt_sep
rule item_end = horizontal item_sep
rule field_end = horizontal field_sep
rule stmt_sep = block_sep / empty_stmt_sep
rule item_sep = block_sep / empty_item_sep
rule field_sep = block_sep / empty_field_sep
rule block_sep = block_with_line
rule empty_stmt_sep = ";" / nl / &$$
// An item or a field may end at the end of the input; the list that is not closed reports the missing brace.
rule empty_item_sep = ";" / nl / &"}" / &$$
rule empty_field_sep = ";" / nl / &"}" / &$$
// Recovery of a declaration skips from the start of the failed declaration to the next one. The skip
// follows the brackets that the declaration opens. At the top level, a
// line or a statement after a semicolon that starts with rule, type or var, or the attributes of a rule,
// starts the next declaration. A balanced group (...), {...} or [...] and the arguments of an attribute
// are skipped whole, so that a line inside them is not taken for a declaration, whatever it starts with.
// A group that is not closed before a place with the shape of a declaration (below) is not skipped whole:
// from its opening bracket on, only such a place resumes. Strings, classes and comments are skipped as
// units, so that a bracket or a keyword inside them counts for nothing. As for the lexer, a "[" directly
// after a name, ")" or "]" opens a bracket, and any other "[" that is not "[]" starts a class, which ends at
// its "]" or at the end of the line; so a "[" that does not close on its line is never tried as a bracket
// group too. The item and field recoveries consume their own separator and stop before the next item.
rule stmt_sync = -comments (attrs_prefix / sync_unit) sync_top* (sync_open (!decl_start (sync_attrs / sync_unit))*)? (";" / nl / &$$)
rule sync_top = attr_call / sync_class / sync_closed / sync_word / !sync_open !top_start (sync_top_attrs / sync_unit)
rule sync_open = "(" / "{" / "[" / (!digit ident_char+ / ")" / "]") "["
rule sync_class = "[" !"]" ("\\" . / [^\]\\\n])* "]"?
rule attr_call = "@" ident_char+ space_no_line* attr_paren
// A name or a closed group with the brackets that follow it. It fails if one of them is not closed.
rule sync_word = !digit ident_char+ sync_index
rule sync_closed = (sync_closed_paren / sync_closed_bracket) sync_index / sync_closed_brace
rule sync_index = sync_closed_bracket* !"["
rule sync_inner = attr_call / sync_class / sync_closed / sync_word
rule sync_closed_paren = "(" (sync_inner / !")" !sync_open !decl_start (sync_attrs / sync_unit))* ")"
rule sync_closed_brace = "{" (sync_inner / !"}" !sync_open !decl_start (sync_attrs / sync_unit))* "}"
rule sync_closed_bracket = "[" (sync_inner / !"]" !sync_open !decl_start (sync_attrs / sync_unit))* "]"
// A declaration at the top level: a keyword that is not part of a longer name, the attributes of a rule, or
// an attribute named like a keyword.
rule top_start = (nl / ";") comments (decl_keyword !ident_char / attrs_start / "@" decl_keyword !ident_char)
// The attributes at the start of a declaration are skipped whole: a line inside their arguments that starts
// with a keyword is an argument, not a declaration.
rule attrs_prefix = "@" (!("rule" !ident_char) attr_unit / nl comments &"@")*
// A place inside a bracket that starts a declaration: a line or a statement after a semicolon that has the
// shape of one, or attributes before a rule that has it.
rule decl_start = (nl / ";") comments (decl_shape / attrs_decl)
rule decl_keyword = "rule" / "type" / "var"
// The shape of a declaration: rule, type or var, then on the same line a bare = or ~ (not part of an
// operator such as :=, ==, !=, <=, >=, += or =>) before any ; { } ( or ), outside strings, classes and block
// comments. No field, item or statement has it. What stands between them is not checked, so a declaration
// whose name is missing or wrong is still a place to resume at. So is a word that ends the source, with or
// without a name: the end of a truncated declaration. A field, a statement or a name that is called rule,
// type or var, such as `type string`, `var := 1`, `var / t`, `var != "="` or `rule Foo`, does not have the
// shape, so a body that is valid is not read as declarations, also when another declaration follows on the
// same line. A declaration without the = or ~ (`var x int`) is a place to resume at only at the top level.
rule decl_shape = decl_keyword !ident_char decl_tail
rule rule_shape = "rule" !ident_char decl_tail
rule decl_tail = decl_shape_line / decl_shape_end
rule decl_shape_line = space_no_line+ !(":" / "/") (assign_op / source_string / source_class / inline_comment / !nl !"//" !("=" / "~" / ";" / "{" / "}" / "(" / ")") .)* ("=" / "~")
rule decl_shape_end = (space_no_line+ ident_char+)? space_no_line* &$$
rule assign_op = [:!<>=+*/%&|\^\-] "=" / "=>"
// The start of a declaration inside an item list ends the list instead of being taken for its items.
rule declaration_ahead = &(comments decl_shape)
rule sync_unit = source_string / source_class / inline_comment / comment_line / incomplete_comment / ident_char+ / .
// The attributes of a rule: an @ that starts a line and reaches the keyword rule, on the same line or a
// later one, through attributes alone. Inside a bracket the rule must have the shape of a declaration.
rule attrs_start = "@" (!("rule" !ident_char) attr_unit / nl comments &"@")* (nl comments)? "rule" !ident_char
rule attrs_decl = "@" (!("rule" !ident_char) attr_unit / nl comments &"@")* (nl comments)? &rule_shape
// A line of attributes where no declaration starts is skipped with the lines of attributes that follow it,
// so that the places to resume at are not looked for again from each of these lines: from any of them, the
// attributes reach the same end, where no rule follows. At the top level, a line that starts with an
// attribute named like a keyword starts a declaration, so the skip stops before it.
rule sync_attrs = (nl / ";") comments "@" (!("rule" !ident_char) attr_unit / nl comments &"@")*
rule sync_top_attrs = (nl / ";") comments "@" (!("rule" !ident_char) attr_unit / nl comments &("@" !(decl_keyword !ident_char)))*
rule attr_unit = ident_char / space_no_line / "@" / source_string / inline_comment / comment_line / attr_paren
rule attr_paren = "(" (attr_paren / source_string / inline_comment / comment_line / !("(" / ")") .)* ")"
rule item_sync = -comments (sync_ml / !(";" / nl / "}") .)* (";" / nl / &"}" / &$$)
rule field_sync = -comments (sync_ml / !(";" / nl / "}") .)* (";" / nl / &"}" / &$$)

// The recovery of an item skips the braces and parentheses that it opens, to their end on any later line,
// so that the lines of a nested block are not taken for items.
rule sync_ml = string / char_class / inline_comment / comment_line / sync_ml_paren / sync_ml_brace
rule sync_ml_paren = "(" (sync_ml / !("(" / ")") .)* ")"
rule sync_ml_brace = "{" (sync_ml / !("{" / "}") .)* "}"

// Types. Join is the weakest operation; list and optional prefixes nest.
// A type declaration is a type alias (type Name ~ Type) or a type definition
// (type Name = { ... } or type Name = node[T]).
rule type_decl = type_alias / type_def
rule type_alias_head = comments "type" -word_end ident -ws "~"
rule type_alias = &type_alias_head comments type_alias_body &source_item_tail stmt_end
rule type_def = comments type_def_body &source_item_tail stmt_end
// A body starts at the keyword and ends before the statement separator.
// Its typed node retains the actual parse span without repeating recovery.
rule type_alias_body = "type" -word_end #cut ident -ws "~" -ws type_expr
rule type_def_body = (
    "type" -word_end #cut ident -ws -type_def_spelling
    -(&("=" comments ("{" / "node[" !"]")) "=" -ws)
    (struct_type / node_type)
)
// A type definition written in a spelling that is not the syntax of a type definition fails
// with the definition in the syntax of the language. The check of each spelling stands outside its message, so a
// spelling that is absent leaves the expectations of the definition as they are.
rule type_def_spelling = (
    !(("struct" / "terminal") !ident_char / "=" !(comments ("{" / "node[" !"]")))
    / &("struct" !ident_char) _|_
    / &("terminal" !ident_char) _|_
    / &"=" _|_
)
// The node type of a named node type takes one type argument.
rule node_type = (
    &"node[" ident "[" {ml := true} -ws type_expr -ws ","? -ws
    -"]"
)
rule field_spec = !(comments "}") !declaration_ahead field
rule field = comments field_body &source_item_tail field_end
rule field_body = ident -ws type_expr
rule type_expr = #operators {
    skip ws
    operand bottom
    operand ident type_args
    operand ident
    operand type_group
    operand struct_type
    level join { infix left "|" }
    level meet { infix left "&" }
    level prefix {
        prefix "[]"
        prefix "*"
    }
}

// An unnamed struct type has the fields of a struct definition.
rule struct_type = (
    "{" {ml := false} &source_head_open field_spec* comments
    -"}"
)

// The brackets of type arguments follow the name directly.
rule type_args = "[" {ml := true} -ws type_expr (-ws "," -ws type_expr)* -ws ","? -ws "]"

// A rule of its own keeps ml from reaching the rest of the type. Parentheses
// around one type without a comma group it; any other parentheses form a tuple.
rule type_group = type_paren / type_tuple
rule type_paren = "(" {ml := true} -ws type_expr -ws ")"
rule type_tuple = "(" {ml := true} -ws (type_expr -ws "," -ws)* type_expr? -ws ")"

// A variable definition gives a name, a type, an initial value, or a type with a value.
rule var_decl = comments var_def_body &source_item_tail stmt_end
rule var_def_body = (
    "var" -word_end #cut ident var_type? var_value?
    var_junk_end
)
// An = after the name or the type starts the value even when the value fails, so it is not text after a
// complete declaration, and the error stays where the value failed.
rule var_junk_end = !({junk} horizontal "=" ![=>])
// The whitespace before the type and the value belongs to them, so a declaration with neither
// ends at its name and does not take in a trailing comment.
rule var_type = -ws type_expr
rule var_value = -ws "=" -ws action_expr

// Rule expressions. The empty infix operator represents adjacency, so
// juxtaposition does not need a separate sequence parser or require a space.
rule rule_decl = comments rule_def_body &source_item_tail stmt_end
rule rule_def_body = (
    (attr decl_attr_gap)*
    "rule" -word_end #cut ident -ws type_expr? -ws
    -"=" -ws -operators_spelling
    (ops_rule_body / rule_body_expr) trailing_action?
)
// Declaration attributes may share a line; the last one ends its line before "rule".
rule decl_attr_gap = decl_attr_same_line / decl_attr_line_end
rule decl_attr_same_line = decl_attr_trivia &"@"
rule decl_attr_line_end = decl_attr_trivia -nl comments
// A block comment between attributes may span lines; it does not end the line of the attribute before it.
rule decl_attr_trivia = -space_no_line* ((line_comment / inline_comment) -space_no_line*)*
rule whole_action = "=>" -ws action
// The spacing before an action belongs to the action, so a rule without one ends at its expression.
rule trailing_action = -ws whole_action
rule rule_expr = #operators {
    skip ws
    operand rule_group / predicate / level_call / bottom / top / begin_input / begin_line / end_input / end_line / any / cut / string / string_open / char_class / rule_ref / cut_spelling
    level ordered_choice { infix left "/" }
    level sequence { infix left _ }
    level prefix {
        prefix ident ":" !"="
        prefix "&" !"&" / "!"
        prefix "-" !"-"
    }
    level suffix {
        postfix "?"
        postfix "*"
        postfix "+"
        postfix "#atomic" !ident_char (empty_args / !"(")
        postfix "#stream" !ident_char (empty_args / !"(")
        postfix "#missing" !ident_char !"("
        postfix "#ignorecase" !ident_char !"("
        postfix "#repeat" !ident_char repeat_args
        postfix "#recover" !ident_char recover_args
        postfix attr
        postfix unknown_pragma
    }
}
// A pragma that does not exist is not parsed. The rule fails after the name, which is where
// the error is reported, and it never matches. #operators is a pragma only where an
// Operators Rule starts.
rule unknown_pragma = "#" !(known_pragma !ident_char) ident _|_
rule rule_body_expr = !legacy_operators_start rule_expr
rule operators_spelling = !legacy_operators_start / _|_
// An Operators Rule starts with #operators. A rule that starts with operators { and an item is an
// error; operators {x == 1} is a reference followed by a predicate.
rule legacy_operators_start = "operators" !ident_char horizontal "{" comments (
    ("skip" / "operand" / "level" / "prefix" / "postfix" / "infix") !ident_char
    (comments ("\"" / "[" / ident_start) / space comments "(")
    / "level" !ident_char comments "{" comments ("prefix" / "postfix" / "infix") !ident_char
)
rule known_pragma = "atomic" / "stream" / "missing" / "ignorecase" / "repeat" / "recover" / "cut" / "operators" &(horizontal "{")
rule rule_group = (
    "(" {ml := true} -ws (inline_action / rule_expr) -ws
    -")"
)
rule inline_action = rule_expr -ws "=>" -ws action
// A character class directly after a name is an error: it reads as an index, and a rule expression has none.
rule rule_ref = ident !"(" !"["
rule level_call = (
    "level(" {ml := true} -ws #cut ident -ws
    -"," -ws
    ident -ws
    -")"
)
rule top = ("_" !ident_char) #atomic
rule bottom = "_|_" #atomic
rule begin_input = "^^" #atomic
rule begin_line = "^" #atomic
rule end_input = "$$" #atomic
rule end_line = ("$" !(ident_start / digit)) #atomic
rule any = ("." !"..") #atomic
rule cut = ("#cut" !ident_char !"(") #atomic
// The cut is #cut, and -- is an error at the --: a recovery past it would let a declaration that
// fails later drop the error with it.
rule cut_spelling = &"--" _|_
rule predicate = action_block
rule repeat_args = (
    "(" {ml := true} -ws (repeat_range / repeat_count / _|_) -ws
    -")"
)
rule repeat_range = repeat_from / repeat_to
rule repeat_from = repeat_int -ws "," -ws repeat_int?
rule repeat_to = "," -ws repeat_int
rule repeat_count = repeat_int
rule repeat_int = (digit+ / "-" -ws "0"+ !digit) #atomic
rule recover_args = (
    "(" {ml := true} -ws -"skip" -word_end
    -"=" -ws rule_expr -ws
    -")"
)
rule empty_args = "(" {ml := true} -ws ")"
rule attr = "@" ident (attr_args / attr_no_args)
rule attr_args = (
    "(" {ml := true} -ws (attr_no_values / attr_named_args / attr_mixed_args) -ws
    -")"
)
rule attr_named_args = attr_named (-ws "," -ws attr_named)* (-ws "," -ws)?
rule attr_mixed_args = attr_slot (-ws "," -ws attr_slot)* (attr_named_tail / attr_trailing_comma)
rule attr_no_args = !"("
rule attr_no_values = &")"
rule attr_trailing_comma = (-ws "," -ws)?
rule attr_named_tail = -ws "," -ws attr_named_args
rule attr_slot = !(ident -ws "=") attr_value
rule attr_named = &(ident -ws "=") ident -ws "=" -ws attr_value
rule attr_value = true_lit / false_lit / nil_lit / signed_int / rule_expr
rule signed_int = (("-" -ws)? digit+ #atomic) #atomic

// #ignorecase may follow the block of an Operators Rule on its line, once or several times, and covers
// the literals of the whole rule. No other pragma may.
rule ops_rule_body = ops_rule_ignorecase / ops_rule_plain
rule ops_rule_ignorecase = (ops_rule_ignorecase / ops_rule_expr) -ws "#ignorecase" !ident_char !"("
rule ops_rule_plain = ops_rule_expr -(-ws &("#" !("ignorecase" !ident_char)) _|_)?
// Operators Rule items and each level recover independently. An absent level
// name remains nil; level(rule, name) can target only named levels.
rule ops_rule_expr = (
    &("#operators" !ident_char -ws "{") "#operators" -ws #cut "{" {ml := false} &source_head_open ops_stmt*
    comments -"}"
)
rule ops_stmt = (
    !(comments "}") !declaration_ahead
    (ops_skip_stmt / ops_operand_stmt / ops_level_stmt / _|_)
)
rule ops_skip_stmt = comments ops_skip_body &source_item_tail item_end
rule ops_skip_body = "skip" -word_end #cut rule_expr
rule ops_operand_stmt = comments ops_operand_body &source_item_tail item_end
rule ops_operand_body = "operand" -word_end #cut rule_expr trailing_action?
rule ops_level_stmt = comments ops_level_body &source_item_tail item_end
rule ops_level_body = (
    "level" -word_end #cut ident? -ws
    -"{" &source_head_open ops_operator*
    comments -"}"
)
rule ops_operator = (
    !(comments "}") !declaration_ahead
    (ops_prefix / ops_postfix / ops_infix / _|_)
)
rule ops_prefix = comments ops_prefix_body &source_item_tail item_end
rule ops_prefix_body = "prefix" -word_end #cut rule_expr trailing_action?
rule ops_postfix = comments ops_postfix_body &source_item_tail item_end
rule ops_postfix_body = "postfix" -word_end #cut rule_expr trailing_action?
rule ops_infix = comments ops_infix_body &source_item_tail item_end
rule ops_infix_body = (
    "infix" -word_end #cut
    ("left" / "right" / "none")
    -word_end rule_expr trailing_action?
)

// Predicate Actions and Value Actions share statement syntax. The source AST
// retains unsupported blocks for later compilation checks.
rule action = default_action / action_block / action_expr
rule default_action = "..." #atomic
rule action_block = (
    "{" {ml := false} action_block_stmt* comments
    -"}"
)
rule action_block_stmt = !(comments "}") !declaration_ahead action_block_value
rule action_block_value = -comments action_stmt -item_end
rule action_stmt = action_bind_stmt / action_expr
rule action_bind_stmt = ident -ws ":=" -ws action_expr
rule action_expr = lambda / action_ops
rule action_ops = #operators {
    skip !(ws "[" !"]") ws
    operand list_constructor / constructor / call / action_tuple / action_group / int / action_string / true_lit / false_lit / nil_lit / capture_ref / var_ref / index_capture
    level disjunction { infix left "||" }
    level conjunction { infix left "&&" }
    level comparison { infix none "==" / "!=" / "<=" / ">=" / "<" / ">" }
    level addition { infix left "+" / "-" !"-" }
    level multiplication { infix left "*" / "/" / "%" }
    level unary { prefix "-" !"-" / "!" !"=" }
    // x[i] indexes a list. The "[" of an index follows its operand directly: the skip leaves
    // white space and comments before a "[" unconsumed, so "x [i]" is an error. A list
    // constructor starts with "[]" and keeps its skip.
    level field_access {
        postfix "." -ws capture_ref
        postfix "." -ws cast_type
        postfix "." -ws -member_spelling ident
        postfix index_suffix
    }
}
// x.name with a lowercase name is an error at the name, because a capture is read with x.$name: the
// fields of a node start with an uppercase letter, and startPos, endPos, children, expected and
// message are members of every node. A name is ASCII, so the check is exact.
rule member_spelling = (
    !(!(("startPos" / "endPos" / "children" / "expected" / "message") !ident_char) [a-z_])
    / _|_
)
// The brackets of an index open their own delimiter, and a rule of its own keeps ml from
// reaching the rest of the action.
rule index_suffix = "[" {ml := true} -ws action_expr -ws "]"
// A rule of its own keeps ml from reaching the rest of the action.
rule cast_type = "(" {ml := true} -ws type_expr -ws ")"
rule lambda = lambda_head -ws "=>" -ws action_expr
// A rule of its own keeps ml from reaching the arrow and the body.
rule lambda_head = "(" {ml := true} -ws lambda_params? -ws ")"
rule lambda_params = lambda_param (-ws "," -ws lambda_param)* (-ws ",")?
// A parameter cannot take the name of a literal, which the literal would hide.
rule lambda_param = !((true_lit / false_lit / nil_lit) -ws &("," / ")")) ident
// Parentheses around one expression without a comma group it; any other
// parentheses form a tuple. The tuple rules fail on a group without an error.
rule action_tuple = action_unit / action_elems
rule action_unit = "(" {ml := true} -ws ")"
rule action_elems = (
    "(" {ml := true} -ws (action_expr -ws "," -ws)+ action_expr? -ws
    -")"
)
rule action_group = (
    "(" {ml := true} -ws action_expr -ws
    -")"
)
rule call = (
    var_name "(" {ml := true} -ws #cut action_args? -ws
    -")"
)
rule action_args = action_expr (-ws "," -ws action_expr)* (-ws "," -ws)?
rule list_constructor = (
    "[]" -ws #cut level(type_expr, prefix) -ws
    -"{" {ml := true} -ws
    action_args? comments -"}"
)
rule constructor = (
    var_name -ws "{" &source_head_open {ml := true} -ws #cut (constructor_fields / action_args)? comments
    -"}"
)
rule constructor_fields = init_field (-ws "," -ws init_field)* (-ws "," -ws)?
rule init_field = comments init_field_body &source_comma_tail
rule init_field_body = (
    ident -ws -":" -ws
    action_expr
)
// A "[" directly after a number or a string is not an index: the lexer reads it as a character class.
rule int = (digit+ !"[") #atomic
rule true_lit = ("true" !ident_char) #atomic
rule false_lit = ("false" !ident_char) #atomic
rule nil_lit = ("nil" !ident_char) #atomic
rule capture_ref = (&("$" ident) "$" ident #atomic) #atomic
// A capture is read by its label. $ and a number is an error at the $.
rule index_capture = &("$" digit) _|_
rule var_name = (!(true_lit / false_lit / nil_lit / bottom) ident) #atomic
rule var_ref = (!bottom ident !"(") #atomic

// Trivia. Space is discarded before and after each retained comment, keeping
// the resulting list homogeneous without introducing nil whitespace elements.
rule ws = {ml} comments / horizontal
rule comments = -space* (comment -space*)*
rule horizontal = -space_no_line* ((line_comment / block_no_line) -space_no_line*)*
rule word_end = !ident_char -ws
rule space_no_line = !nl space
rule nl = "\r\n" / [\r\n]
rule space = [ \t\n\u{b}\u{c}\r\u{85}\u{a0}\u{1680}\u{2000}-\u{200a}\u{2028}\u{2029}\u{202f}\u{205f}\u{3000}]
// A lexical comment view retains trivia inside parsing and action expressions.
// Incomplete tokens remain available to the error-recovering structural pass.
rule source_comments = -source_non_comment* (comment -source_non_comment*)* $$
rule source_non_comment = source_string / source_class / incomplete_comment / !("//" / "/*") .
rule source_string = "\"" ("\\" . / [^"\\\n])* "\""?
rule source_class = "[" ("\\" . / [^\]\\\n])* "]"?
rule incomplete_comment = !inline_comment comment_open .* $$
rule comment = comment_group / inline_comment
// White space and comments may stand between any two tokens. The source parser leaves them out of
// what a syntax error expects, by these names.
rule comment_open = "/*"
rule comment_group = comment_line (-nl -space_no_line* comment_line)*
rule line_comment = comment_line
rule comment_line = ("//" [^\n\r]*) #atomic
rule inline_comment = comment_open (inline_comment / !("/*" / "*/") .)* #atomic "*/"
rule block_no_line = comment_open (block_no_line / !("/*" / "*/" / nl) .)* #atomic "*/"
rule block_with_line = (
    comment_open
    ((block_no_line / !("/*" / "*/" / nl) .)* (nl / block_with_line) (inline_comment / !("/*" / "*/") .)*)
    #atomic "*/"
)
rule ident = (ident_start ident_char*) #atomic
rule ident_start = [a-zA-Z_]
rule ident_char = [a-zA-Z0-9_]
rule digit = [0-9]
// A backslash escapes any character: the decoding of the literal reports an unknown or invalid
// escape, so that the declaration with the mistake is kept.
rule string = ("\"" ("\\" . / [^"\\\n])* "\"" #atomic ("i" !ident_char)?) #atomic
// A string of a rule expression that is not closed on its line is recovered as an error that spans the
// string to the end of the line, where it stood for the literal the user is typing; the decoding of the
// source takes its text. A string of an action is not recovered: the rest of the action would then be read
// as statements, and the errors that follow would differ from the reference.
rule string_open = &"\"" _|_
rule string_open_text = "\"" ("\\" . / [^"\\\n])*
// A string of an action has no ignorecase suffix.
rule action_string = ("\"" ("\\" . / [^"\\\n])* "\"" !"[") #atomic
rule char_class = (
    "[" "^"? (char_class_rng / char_class_chr)+
    -"]"
)
rule char_class_rng = char_class_chr "-" !"]" char_class_chr
rule char_class_chr = ("\\" . / [^\]\\\n]) #atomic

// Normalized declaration ownership, independent of raw formatter comments.
// The lookahead rules never fail, so recording ownership cannot change what a
// statement accepts: an unrecognizable boundary has no comments and no next owner.
rule source_head = source_remaining / source_empty_boundary
rule source_head_open = source_after_delimiter_boundary / source_empty_boundary
rule source_empty_boundary = _

// The boundary after a statement. A separator, when present, is a token of its own
// with its own boundary after it: a trailing group there follows the groups before
// the separator, and the next sibling's leading groups come from the boundary after it.
rule source_item_tail = source_tail_after_separator_trailing / source_tail_after_separator / source_tail_plain / source_tail_empty
rule source_tail_after_separator_trailing = source_after_boundary source_semis source_after_boundary_trailing
rule source_tail_after_separator = source_after_boundary source_semis source_after_boundary
rule source_tail_plain = source_after_boundary
rule source_tail_empty = _
rule source_semis = ";" (-source_trivia* ";")*
rule source_trivia = source_space / source_line_comment / source_block_comment
// Constructor fields have a comma as their separator.
rule source_comma_tail = source_comma_after_separator_trailing / source_comma_after_separator / source_tail_plain / source_tail_empty
rule source_comma_after_separator_trailing = source_after_boundary "," source_after_boundary_trailing
rule source_comma_after_separator = source_after_boundary "," source_after_opener_boundary

rule source_after_boundary = (
    source_inline_line_boundary / source_inline_run_boundary / source_inline_block_boundary / source_ambiguous_block_boundary
    / source_newline_boundary / source_remaining
)
rule source_inline_line_boundary = -source_horizontal source_line_comment source_remaining
// The comments on the line of the previous token all trail it when a line break or
// the end of the scope follows them: block comments, then at most one line comment.
rule source_inline_run_boundary = (-source_horizontal source_block_comment)+ source_run_tail source_remaining
rule source_run_tail = source_run_line / source_run_end
rule source_run_line = -source_horizontal source_line_comment
rule source_run_end = &(source_horizontal (source_nl / source_scope_end))
rule source_inline_block_boundary = (
    -source_horizontal source_block_comment &(source_horizontal (source_nl / source_comment_start / source_scope_end))
    source_remaining
)
// The boundary after an opening delimiter or a comma. One inline block ending on
// the next token's line leads that token there.
rule source_after_opener_boundary = (
    source_inline_line_boundary / source_inline_run_boundary / source_inline_block_boundary / source_opener_block_boundary
    / source_newline_boundary / source_remaining
)
rule source_opener_block_boundary = -source_horizontal source_block_comment -source_horizontal &source_next_token
// The boundary after an opening delimiter, which is not a node. The comments on its line lead
// the next token as if they were on lines of their own; before a closing delimiter they stay
// the group of the delimiter.
rule source_after_delimiter_boundary = source_delimiter_scope_boundary / source_remaining
rule source_delimiter_scope_boundary = &source_scope_run source_after_opener_boundary
rule source_scope_run = -source_space* (source_comment -source_space*)* source_scope_end
// One inline block ending on the next token's line is ambiguous, not trailing.
rule source_ambiguous_block_boundary = -source_horizontal source_block_comment -source_horizontal &source_next_token
rule source_newline_boundary = -source_horizontal -source_nl -source_horizontal source_first_trailing source_remaining
// A boundary that has a trailing group, even an empty one. After a separator it
// replaces the trailing group found before the separator.
rule source_after_boundary_trailing = source_inline_line_boundary / source_inline_run_boundary / source_inline_block_boundary / source_newline_trailing_boundary
rule source_newline_trailing_boundary = -source_horizontal -source_nl -source_horizontal source_first_trailing source_remaining

// A first standalone group can trail the previous declaration when a blank
// line, another group, or the end of a scope flushes it before the next token.
rule source_first_trailing = source_line_group &source_line_flush / source_block_comment &source_block_flush
rule source_remaining = source_scope_tail / source_next_boundary
rule source_scope_tail = -source_space* (source_comment -source_space*)* &source_scope_end
rule source_next_boundary = -source_space* (source_detached_group -source_space*)* (source_leading_group / source_empty_comment) -source_space* &source_next_token
rule source_empty_comment = _
rule source_detached_group = source_line_group &source_line_flush / source_block_comment &source_block_flush
rule source_leading_group = source_comment -source_space* &source_next_token
rule source_line_flush = source_horizontal (source_nl / "/*" / source_scope_end)
rule source_block_flush = source_horizontal (source_nl source_horizontal (source_nl / source_comment_start / source_scope_end) / source_comment_start / source_scope_end)
rule source_next_token = !(source_space / source_comment_start / source_scope_end) .
rule source_scope_end = ")" / "]" / "}" / ";" / $$
rule source_comment_start = "//" / "/*"
rule source_comment = source_line_group / source_block_comment
rule source_line_group = source_line_comment (-source_horizontal source_line_comment)*
rule source_line_comment = "//" [^\r\n]* source_nl?
rule source_block_comment = "/*" source_block_line (source_nl -source_horizontal -source_block_star? source_block_line)* "*/"
rule source_block_star = "*" !"/"
rule source_block_line = source_block_piece*
rule source_block_piece = source_nested_piece / source_character_piece
rule source_nested_piece = source_block_comment
rule source_character_piece = (!(source_nl / "*/" / "/*") .) #atomic
rule source_nl = "\r\n" / [\r\n]
rule source_horizontal = source_horizontal_char*
rule source_horizontal_char = [ \t\u{b}\u{c}\u{85}\u{a0}\u{1680}\u{2000}-\u{200a}\u{2028}\u{2029}\u{202f}\u{205f}\u{3000}]
rule source_space = source_horizontal_char / source_nl

// Every gap between tokens that holds a comment, in source order. Tokens are
// the characters between trivia; strings and classes hide comment markers.
// A gap at the start of the input has no token before it and so no trailing
// group. The scan never fails, so recording gaps cannot change what is accepted.
rule source_gaps = source_gap_head? -source_gap_skip* ((-source_delimiter_char source_delimiter_gap / -"," source_open_gap / source_gap) -source_gap_skip*)* $$
// A bracket directly after a name, ")", "]" or "}" is a bracket, not a character class.
rule source_gap_skip = !source_gap_opens (source_string / source_bracket / source_class / incomplete_comment / source_space+ !(source_line_comment / source_block_comment) / !(source_space / source_comment_start) .)
// An opening delimiter or a comma followed by a comment: the gap after it belongs to the opener.
rule source_gap_opens = source_open_char &source_gap_run
rule source_open_char = source_bracket / [({,]
rule source_delimiter_char = source_bracket / [({]
rule source_bracket = (ident_char / ")" / "]" / "}") "["
// A gap starts with a comment, after any space, and runs to the next token.
rule source_gap_run = -source_space* (source_line_comment / source_block_comment) (source_space / source_line_comment / source_block_comment)*
rule source_gap_head = ^^ &source_gap_run &(source_remaining / source_empty_boundary) -source_gap_run
rule source_gap = &source_gap_run &(source_after_boundary / source_empty_boundary) source_gap_flag? -source_gap_run
rule source_open_gap = &source_gap_run &(source_after_opener_boundary / source_empty_boundary) source_gap_flag? -source_gap_run
rule source_delimiter_gap = &source_gap_run &(source_after_delimiter_boundary / source_empty_boundary) source_gap_flag? -source_gap_run
rule source_gap_flag = &source_after_boundary_trailing

What the Grammar Does Not Express

The grammar includes the ASCII identifier form. Names beginning with _ are parsed and preserved. Semantic validation rejects them, except as a rule name. The following additional constraints are checked outside this source grammar.

  • Reserved identifiers. Names beginning with _ are reserved, except the name of a Rule Definition and a reference to a rule, which hide the rule (see Lexical). The standalone Rule Expression _ is Top, which is distinct from a name.
  • Integer literals. An integer literal MUST be representable as an int.
  • Character class ranges. In lo-hi, hi MUST NOT be less than lo, and a class MUST contain at least one item.
  • Repetition bounds. In a #repeat(n,m), m MUST NOT be less than n.
  • Statement boundaries. Newlines and semicolons separate Declaration Statements, Operators Rule items, struct fields and action-block statements. A newline ends a statement, and a semicolon ends it only on the same line: a string // t followed by a line holding ; b string reads as a string, an empty statement, then b string. An empty statement, such as a repeated semicolon or a semicolon that starts a line, is an error in every statement list; comments between statements are fine. An expression may cross a newline only within its own open delimiter, so a type definition keeps = and its { or node[ on one line, => keeps its action or action block on its line, and in an action a newline before a binary operator, ., =>, a constructor { or an index [ ends the expression. Statement-list braces do not enable continuation of every nested expression. Indentation is not syntax.
  • Index brackets. In an action expression the [ of an index follows the indexed value directly, such as x[0], f(x)[0] or []int{1, 2}[0]. White space or a comment before it is an error; the brackets are an open delimiter, so their contents may span lines.
  • Attribute arguments. Positional arguments follow the generic value forms and precede named arguments; repeated named keys are rejected. The grammar models argument shape and ordering, not key uniqueness.
  • Contextual words. Declaration Statement and Operators Rule item introducers have their syntactic meaning only at those statement positions. They remain identifiers elsewhere.
  • Where constructs may appear. An Operators Rule MUST be a complete Rule Declaration Statement; a lambda MUST be an argument of foldl, foldr or map; and #stream MUST be at the top level of a rule body. A comment in a Declaration Statement or Operators Rule statement header is rejected by semantic analysis with a positioned diagnostic. These checks follow parsing.
  • Action blocks. Multiple-statement Predicate Actions and every braced Value Action are retained in the source AST but compilation rejects them.
  • Inline actions. (expression => action) is recognized in the source grammar and represented in the AST. Compilation executes it as a hidden rule at its position (see Actions); an inline braced Value Action is rejected.
  • Attribute placement. Attributes are postfix Rule Expression annotations, or declaration attributes on the lines before rule, where a newline separates the last attribute from rule. Other Declaration Statements take no attributes.

Operators

Rule Expressions bind in the order of the precedence table. Action Expressions in Value Actions and Predicate Actions bind in the order of the operator table: ||, &&, comparison (==, !=, <, <=, >, >=, which do not chain), + and -, *, / and %, and the unary - and !. Field access (.), capture access (.$), indexing ([i]) and function calls bind tighter than the operators. A [ written directly after a name, a capture reference, ) or ] is an index bracket; elsewhere it begins a character class. Each Operators Rule defines precedence by the order of its level declarations; associativity and operator order come from entries within each level. The Operators Rule represents adjacency with an empty infix operator and gives postfix modifiers tighter binding than capture, lookahead and discard. Ordered choice remains the weakest operation.