Chapter 6

Operators Rule

An Operators Rule Declaration Statement defines a rule body that parses expressions by declaring operator parts at binding levels, each with a precedence and an associativity. Operand and operator shapes are ordinary Rule Expressions. Their combination follows a parsing algorithm inspired by Pratt parsing.

An Operators Rule is written with the #operators pragma, which stands where an expression would and is valid only as the whole body of a rule: rule e = #operators { ... }. Anywhere else it is a syntax error. The word operators has no special meaning and is an ordinary identifier.

type Num = node[string]
type Ident = node[string]
type Comma = { L Expr; R Expr }
type Assign = { L Expr; R Expr }
type Cond = { Cond Expr; Then Expr; Else Expr }
type Bin = { L Expr; Op node[string]; R Expr }
type Unary = { Op node[string]; X Expr }
type Call = { Fn Expr; Args []Expr }
type Index = { X Expr; Index Expr }
type Member = { X Expr; Name Ident }
type Expr ~ Num | Ident | Comma | Assign | Cond | Bin | Unary | Call | Index | Member

rule expr Expr = #operators {
    skip ws
    operand number
    operand ident
    operand "(" e:expr ws ")" => $e

    level comma { infix left "," => Comma{L: $lhs, R: $rhs} }
    level assignment { infix right "=" => Assign{L: $lhs, R: $rhs} }
    level conditional { infix right "?" then:expr ws ":" => Cond{Cond: $lhs, Then: $then, Else: $rhs} }
    level equality { infix none "==" / "!=" => Bin{L: $lhs, Op: $op, R: $rhs} }
    level additive { infix left "+" / "-" => Bin{L: $lhs, Op: $op, R: $rhs} }
    level multiplicative { infix left "*" / "/" => Bin{L: $lhs, Op: $op, R: $rhs} }
    level prefix { prefix "-" / "!" => Unary{Op: $op, X: $rhs} }
    level power { infix right "**" => Bin{L: $lhs, Op: $op, R: $rhs} }
    level postfix {
        postfix "(" xs:args? ws ")" => Call{Fn: $lhs, Args: concat($xs)}
        postfix "[" i:expr ws "]" => Index{X: $lhs, Index: $i}
        postfix "." name:ident => Member{X: $lhs, Name: $name}
    }
}

rule args = first:level(expr, assignment) rest:(-ws "," x:level(expr, assignment))* => concat(list($first), map($rest, (r) => r.$x))

rule number Num = ([0-9]+) #atomic
rule ident Ident = ([a-z]+) #atomic
rule ws = [ \t\r\n]*

#Syntax

rule <name> [<Type Expression>] = #operators {
    skip <Rule Expression>
    operand <Rule Expression> [=> <action>]
    level [<level name>] {
        prefix <operator part> [=> <action>]
        postfix <operator part> [=> <action>]
        infix (left | right | none) <operator part> [=> <action>]
    }
} [#ignorecase]

• An Operators Rule uses a dedicated rule <name> [<Type Expression>] = operators form. It cannot appear inside another Rule Expression. Its optional type follows the rule name; when omitted, the type is inferred from operands and operators.
• #ignorecase may follow the closing } on the same line and makes the string literals of the whole rule case-insensitive (see #ignorecase). No other pragma may follow it.
• An action after an operand or operator declaration uses => and applies to that complete operand or operator entry.
• A rule-level Value Action after the closing } may be omitted or use the explicit => ... default form. Any other rule-level Value Action is a compile-time error.
• Semicolons separate Declaration Statement items when needed; line boundaries may also make the separation unambiguous. Struct fields use semicolons or newlines; constructor fields and arguments use commas.
• An Operators Rule has at most one skip, at least one operand, and any number of levels. A level contains any number of operators.
• An operator part is an arbitrary Rule Expression. It MAY call other rules, including the rule that contains the Operators Rule.

#Items

#skip

The skip expression is implicitly inserted, with its result discarded, before each operand and before each operator part. It is used for whitespace and comments. If skip does not match, nothing is skipped. Failures inside skip are not included in the expected items of a syntax error. skip MUST NOT contain captures.

skip is not inserted inside an operator part or an operand, so an operator such as "?" t:expr ":" must spell out the whitespace before ":" (as in "?" t:expr ws ":" in the example above). Whitespace after the last token of the expression is not consumed either. Without a skip item, nothing is inserted.

#operand

An operand describes the leading element of an expression that does not start with a prefix operator. Multiple operand items form an ordered choice in declaration order.

An action (=>) applies to the whole operand item. To give different alternatives different actions, write them as separate operand items. An operand action can use the captures of its line.

An operand MUST NOT call its own rule at its start, since that would be left recursion. Write constructs that take an expression on their left as infix or postfix operators instead.

#level

A declaration level additive { ... } declares level additive on the Operators Rule target expr. The enclosing Operators Rule identifies the target. Levels declared earlier bind more loosely; levels declared later bind more tightly. All operators in the same level have the same precedence, and a level MAY mix prefix, infix and postfix operators. Every Operators Rule item, including each level declaration, uses the same hard-newline or semicolon statement boundary.

The level name is optional. When present, it MUST be unique within the target rule and may be used by level-restricted calls. Unnamed levels are valid but cannot be selected by level(rule, name); a level-restricted call must name an existing named level.

#Operators

An operator part can consist of several elements. The following declarations appear inside level name { ... } blocks:

infix right "?" then:expr ":" // conditional    lhs ? then : rhs
postfix "[" i:expr "]" // index          lhs[i]
prefix "if" c:expr "then" t:expr "else" // if expression  if c then t else rhs
infix left _ // application    f x (empty operator part)

#Parsing Rules

• Precedence. The right operand of an operator includes only operators of binding levels that bind more tightly than the operator's own level; for a right operator, it also includes operators of its own level.
• Prefix operators. A prefix operator at the start of an operand position is not restricted by binding levels: 2 ** -1 parses even though ** binds more tightly than the prefix -.
• Operator selection. At each position, the parser selects, among the operator parts that match there, the one with the longest match; among matches of equal length, the operator declared first wins. The operator is selected before precedence is considered: if the selected operator cannot be applied because of its precedence, the parser does not fall back to a shorter candidate. A prefix or postfix operator part that matches the empty string is not a candidate (it could otherwise be applied indefinitely); infix operator parts may match the empty string, which is how juxtaposition is written. An infix operator that is applied without consuming any input (an empty operator part and an empty right operand, with no skip text) ends the expression after it is applied, as an iteration that consumes no input ends a repetition; otherwise it would be applied indefinitely.
• Backtracking. If an operator part matches but its right operand cannot be parsed, the operator is not applied and the expression ends before the operator. For a prefix operator, the parser then tries the operand items at the same position instead. If the operator part passed a cut (#cut), the whole Operators Rule fails instead. If no prefix operator part matches and any candidate failed after passing a cut, the whole expression also fails instead of trying operands. Failed candidates do not veto another successfully matching operator part; only the selected operator's own cut controls a later right-operand failure. Cuts remain local to their parser-expression choice or called rule. A prefix or postfix part rejected for matching empty input contributes a cut failure when it passed a cut, just as a part that failed while matching does.

For example, prefix "-" #cut "z" with operand "-x" rejects -x: no prefix candidate matches, and the attempted prefix passed a cut. Removing #cut allows operand fallback. This rule applies to every engine backend and standalone Go/TypeScript parsers.

#Level-Restricted Calls

When a rule that has an Operators Rule is called with a level name, as in level(expr, assignment), its tail applies only infix and postfix operators of the named level and of the levels that bind more tightly. Calling the rule without a level name (expr) allows tail operators of all levels. The level keyword and ( MUST be adjacent, and the named level MUST exist in the called rule.

The prefix-operator exception still applies: an operand position, including the start of a level-restricted call, MAY begin with a prefix operator from any level. Its right operand uses that prefix operator's own binding level, rather than the caller's minimum. Consequently, operators looser than the entry level can occur inside that right operand if they bind more tightly than the prefix. Level restriction is not a filter over every operator in the resulting tree. Calls written inside operator parts or operands also use their own level restrictions.

// Function arguments do not parse the comma operator (only assignment and tighter).
rule args = first:level(expr, assignment) rest:(-ws "," x:level(expr, assignment))*

For example, if ~ is a prefix in a level looser than addition and multiplication is a named tighter level, level(expr, multiplication) accepts ~x+y as ~(x+y). Without the prefix, it stops before the + in x+y. To exclude a lower-level prefix at entry, the caller must guard that input explicitly, accounting for any whitespace skip. For a rule without skip, !"~" level(expr, multiplication) excludes ~ at entry.

#Value Actions

An operator Value Action can refer to the following names.

Captures inside the operator part (such as then:expr) can be referred to as well. lhs, rhs and op MUST NOT be used as capture names in operator parts.

The node created by an operator action covers the operator expression: from the start of the left operand (or of the prefix operator) to the end of the right operand (or of the postfix operator).

#Types

If the rule is declared with type T, the values of all operand items and of all operators MUST be assignable to T, and $lhs and $rhs have type T. An operator without an action produces a tuple node of its operands and its operator part: node[(T, O, T)] for an infix operator and node[(O, T)] for a prefix operator, where O is the type of the operator part, with the captures lhs, op and rhs. When T does not accept these nodes, every operator needs an action; a recursive alias cannot name them, so a join that accepts them includes node[_].

If the rule has no declared type, its type is the join of the types of all operand items and operators.

#Named Node Types

If the declared type is exactly a named node type N (also through aliases), the rule converts the value of every operator it applies to N, as an ordinary rule converts its value (see Types and Errors):

• The value of each prefix, infix and postfix operator, at every nesting level of the expression, becomes a node of type N. This holds whether the operator has an action or not. For an operator without an action, the tuple node (lhs, op, rhs), (lhs, op) or (op, rhs) is converted, and it keeps its range, children and captures. For an operator with an action, the node that the action returns is converted, and it keeps its range and content; a node that already has type N, such as $lhs, is unchanged. The result is a node of type N throughout the tree of operators, so Node.Type() reports N and typed output yields *N for every operator node.
• The value of an operand item is not converted: it is the node the operand produces, with the type its own rule or action gives it. It MUST be assignable to N; otherwise it is a compile-time error, operand of r produces X, which is not assignable to N, because an operand is never converted. Declare the operand rule as N so that it converts its own value, or declare the Operators Rule as a join of N and the operand types, which converts nothing. A node held by an operator part, such as the value of $op, is not an operator node and keeps its type.
• The value of each operator MUST be convertible to N: a node whose underlying type is assignable to the underlying type of N. A tuple node of an operator without an action must therefore fit the underlying type, as node[_] does. Otherwise it is a compile-time error, operators of r without an action produce a tuple node, which cannot be converted to N or operatorsRule r produces X, which cannot be converted to N. With type checking off, an operator value that does not fit fails the parse.
• The converted node has no rule name, as for an ordinary rule.

type Expr = node[_]
rule expr Expr = #operators {
    operand num
    level { infix left "+" }
    level { prefix "-" }
}
rule num Expr = [0-9]+ #atomic

With this rule, every node of -1+2 that the operators build has type Expr, as do the operands 1 and 2, which num converts itself.

#Concrete Syntax Tree

An operator without an action produces a tuple node (its node type name is tuple) whose range covers the operator expression. When the rule is declared with a named node type, that node has the named type instead.

The elements are captured as lhs, op and rhs, which source information reports (see Nodes and Values). op is the value of the operator part: a string node for "+", a tuple for "[" i:e "]", whose elements include the captured i, and so on. A node of a nested operand or operator is not wrapped: the number of levels does not make the tree deeper.

The value of an operand item without an action appears unchanged; with source information, a node that it creates is labeled with the name of the rule.

rule e = #operators {
    operand [0-9]+ #atomic
    level additive { infix left "+" }
    level multiplicative { infix left "*" }
}

With this rule, 1+2*3 produces the following tree (in the S-expression format of pego parse -f sexpr -source-info, where @e is the rule name):

(lhs:"1"@e op:"+" rhs:(lhs:"2"@e op:"*" rhs:"3"@e)@e)@e

Without source information the same tree is ("1" "+" ("2" "*" "3")).