Last updated: 2026-11-15

U
Undergraduate level
EPH
Ephemeral / Tooling โ€” Knowledge that evolves in months to a year โ€” check for updates

The canonical PEG grammar

For new readers

This is a deep-reference page, not an introduction โ€” "PEG" (Parsing Expression Grammar) is a formal notation for defining a language's exact syntax rules, and this page is the literal grammar file that defines PatLang's syntax (with the omissions listed below), used as an independent cross-check against PatLang's two hand-written parsers. Unless you specifically want to verify grammar edge cases or understand a parsing ambiguity, the Grammar & Syntax reference is a friendlier way to look up syntax.

PatLang version. This page describes PatLang's toolchain before version 2.0, when a program ran on the Rust interpreter (pat --ir-run) or was compiled by patc1.exe through rustc. In 2.0 the compiler is v2.exe and the interpreter v2_interp.exe, both written in PatLang, and no part of the toolchain uses Rust. The toolchain in PatLang 2.0 describes it, and what changed since v1 lists every change.

The grammar file, published in full: docs/grammar/patlang-full.peg, the single canonical Parsing Expression Grammar behind the PEG grammar validator dev tool. It's interpreted identically by two independent engines โ€” self_hosting/lib/peg.patlang and rust-runtime/src/ir/peg.rs โ€” that share nothing but this file and a thin per-side token adapter, giving PatLang a third, structurally independent answer to "is this valid PatLang," distinct from the two hand-written recursive-descent parsers (native Rust, self-hosted PatLang) that actually compile programs.

Standard PEG notation: Name <- Expression defines a rule; space-separated items are a sequence; / is ordered choice (try the left alternative first, only fall through to the right on failure โ€” this is what distinguishes PEG from plain BNF/EBNF, and is what lets rule Head(...) :- Body. and rule(...)-as-an-ordinary-call share the rule keyword with no reservation needed, see below); */+/? are the usual repetition/optional operators; quoted text is a literal terminal; a bare capitalized name is a reference to another rule.first match wins, even if later parsing then fails

Three things to notice while reading it, each a place where PatLang's grammar depends on something a plain PEG grammar has no native way to express, because the hand-written parsers handle it with parser-level state rather than grammar shape โ€” see the dev-tooling write-up for the full reasoning behind each:

  • Eq includes bare "=" as well as "==" โ€” a bare = means assignment at the start of a statement (see Assign, near the top) but equality mid-expression; Assign is tried as its own Stmt alternative before the generic ExprStmt fallback gets a chance to consume it as a comparison.
  • Two parallel expression towers, Expr/Pipeline/.../Postfix and CondExpr/CondPipeline/.../CondPostfix, structurally identical except that only the plain Postfix tier includes TrailingClosure. That's the whole mechanism behind f(x) { ... } attaching as a closure argument everywhere except inside an if/while condition, where the same trailing block must not be swallowed โ€” If/While call into the Cond* tower, everything else uses the general one.
  • RuleDecl requires no keyword reservation for rule โ€” Stmt's ordered choice just tries the declarative form first; if a `rule` token turns out to be followed by `(` and shaped like an ordinary call instead, that alternative fails cleanly and ExprStmt picks it up, PEG's own backtracking doing the disambiguation for free.

Deliberately scoped: this is Sliceย 2 of a staged effort, covering the full actively-used grammar โ€” including goal/pursue/activate, added the same day the real syntax itself landed, and when/budgeted/contracts, present since Sliceย 2's original pass. activate needed its own small design decision, not just a mechanical addition: a single shared production using the general expression tower for its own argument would have let if activate(p) { ... }'s trailing { } get swallowed as a closure argument to activate(p) instead of being recognised as the if's own body โ€” the ambiguity the Expr/CondExpr split above exists to prevent. Fixed with a dedicated CondActivateExpr using CondExpr for its argument, mirroring the same split every other condition-position construct already uses. Deliberately excluded: the legacy logic-DSL forms (fact, bare goal with no dependencies, reasoning, constrain, relationship, no-paren query) that the real parsers tokenise and silently discard as no-ops โ€” there's nothing there to validate against yet, since they don't currently do anything when compiled. Also excluded, and structurally impossible for one static grammar file to express at all: syntax NAME { ... }, PatLang's mechanism for a single source file to define its own dynamic, per-file grammar extensions. Two constructs are covered in full, though. Class declarations (class, inherits, traits, fields and methods) are one; match/case pattern matching, with its guard, list, comparison and glob patterns, is the other. A statement that starts with match, or with class not followed by (, is never read as an ordinary call: both real parsers commit to the declaration at that point, and without that rule a malformed class or match block would be accepted as a run of calls with trailing blocks. Rule and goal arguments are full expressions (rule dob(alice, 1996).), and ; is accepted after any statement. One limit comes from the fixed keyword list: the real parsers allow a variable named end (let end = n), but here end is reserved so that blocks can close, so a program that uses it as a name is rejected.

Statement separators are optional. Neither the language nor this grammar requires a newline or ; between consecutive statements: separators are decorative, and let x = 5 print(x) is a valid two-statement program for both real parsers. Stmt* mirrors that, so accepting the pair is correct.

Grammar source

Program    <- Stmt*

# A ";" after a statement is an optional separator, alongside the newline
# the grammar never requires.
Stmt       <- StmtCore ";"?
StmtCore   <- Let / Contract / When / RuleDecl / GoalDecl / ClassDecl / FuncDef / If / While
              / MatchStmt / MemberAssign / Assign / Return / PrintStmt / ExprStmt

Let        <- "let" "mut"? Identifier "=" Expr
MemberAssign <- Identifier ("." Identifier)+ "=" Expr
Assign     <- Identifier "=" Expr
Contract   <- ("require" / "ensure" / "assert") Expr
When       <- "when" Identifier Block
Return     <- "return" Expr?
PrintStmt  <- "print" Expr
# A statement that starts with "match", or with "class" not followed by
# "(", is never an ordinary expression: both real parsers commit to the
# declaration there and report its own error rather than reading the
# words as a call. Without this guard a malformed class or match block
# would fall through to ExprStmt and be accepted as calls with trailing
# blocks.
ExprStmt   <- !("match" / ("class" !"(")) Expr

RuleDecl   <- "rule" Identifier "(" ArgList ")" (":-" RuleBody)? "."
# Rule and goal arguments are ordinary expressions: identifiers and
# variables, but also numbers, strings and lists (rule dob(alice, 1996).).
ArgList    <- (Expr ("," Expr)*)?
RuleBody   <- RuleCall ("," RuleCall)*
RuleCall   <- Identifier "(" ArgList ")"

# goal NAME { dep1(args), dep2(args) } -- names a target state as a list
# of fact-terms, reusing RuleCall's shape (same convention a rule body's
# goals already use). "goal" deliberately stays non-reserved, exactly
# like "rule": ordered choice tries this production first and falls
# through to ExprStmt (an ordinary call) on failure, e.g. goal(x).
GoalDecl   <- "goal" Identifier "{" (RuleCall ("," RuleCall)*)? "}"

# class NAME [inherits PARENT] { members } -- or do ... end / begin ... end.
# A member is a traits line, a field with a default, or a method written
# as an ordinary "make a function called" definition. "class" stays
# non-reserved in call position, like "rule" and "goal": class(x) falls
# through to an ordinary call.
ClassDecl   <- "class" Identifier ("inherits" Identifier)? (ClassBrace / ClassWord)
ClassBrace  <- "{" ClassMember* "}"
ClassWord   <- ("do" / "begin") ClassMember* "end"
ClassMember <- TraitsLine / FieldDecl / MakeForm
TraitsLine  <- "traits" Identifier ("," Identifier)*
FieldDecl   <- "field" Identifier "=" Expr

# match EXPR do case PATTERN [when GUARD] then STMTS ... end
# An arm's statements run up to the next "case" or the closing "end";
# "end" is a reserved word so Stmt already stops there, and "case" is an
# ordinary identifier, hence the explicit lookahead in CaseBody.
MatchStmt   <- "match" Expr "do" CaseArm* "end"
CaseArm     <- "case" Pattern ("when" Expr)? "then" CaseBody
CaseBody    <- (!"case" Stmt)*

# Pattern kinds, in the order the parsers try them: list, comparison,
# glob (a leading "*", or an identifier directly followed by "*" or "?"),
# then literal or binding. "_" and true/false are plain identifiers here;
# a glob is a run of identifier, number, "*", "?" and "." tokens.
Pattern     <- ListPattern / CmpPattern / GlobPattern / Number / String / Identifier
ListPattern <- "[" (Pattern ("," Pattern)*)? "]"
CmpPattern  <- ("<=" / ">=" / "==" / "!=" / "<" / ">") Expr
GlobPattern <- "*" GlobPiece* / Identifier ("*" / "?") GlobPiece*
GlobPiece   <- "*" / "?" / "." / Identifier / Number

FuncDef    <- MakeForm / FnForm / FunctionForm
FnForm     <- "fn" Identifier "(" ParamList ")" BraceBlock
FunctionForm <- "function" Identifier "(" ParamList ")" BraceBlock
MakeForm   <- "make" "a" "function" "called" Identifier
              ("takes" ParamList)? ("returns" Identifier)?
              FuncBlock
ParamList  <- (Identifier ("," Identifier)*)?
FuncBlock  <- BraceBlock / FuncWordBlock
FuncWordBlock <- Stmt* "end"

Block      <- BraceBlock / WordBlock
BraceBlock <- "{" Stmt* "}"
WordBlock  <- ("then" / "do") Stmt* "end"

If            <- IfBrace / IfWord
IfBrace       <- "if" CondExpr BraceBlock ElifBraceTail? ElseBraceTail?
ElifBraceTail <- "elif" CondExpr BraceBlock ElifBraceTail?
ElseBraceTail <- "else" BraceBlock
IfWord        <- "if" CondExpr ("then" / "do") Stmt* ElifWordTail* ElseWordTail? "end"
ElifWordTail  <- "elif" CondExpr ("then" / "do") Stmt*
ElseWordTail  <- "else" Stmt*

While      <- WhileBrace / WhileWord
WhileBrace <- "while" CondExpr BraceBlock
WhileWord  <- "while" CondExpr ("do" / "then") Stmt* "end"

# General expression tower (allows a trailing '{ }' to attach to a call
# as sugar for a closure argument, e.g. f(x) { ... }).
Expr       <- Pipeline
Pipeline   <- Or (PipeOp Or)*
PipeOp     <- "|>" / ("|" ">")
Or         <- And ("or" And)*
And        <- Eq ("and" Eq)*
Eq         <- Cmp (("==" / "!=" / "=") Cmp)*
Cmp        <- Bitwise (("<=" / ">=" / "<" / ">") Bitwise)*
Bitwise    <- Shift (("band" / "bxor" / "bor") Shift)*
Shift      <- Add (("shl" / "shr") Add)*
Add        <- Mul (("+" / "-") Mul)*
Mul        <- Unary (("*" / "/" / "%") Unary)*
Unary      <- ("not" / "bnot" / "-") Unary / Postfix
Postfix    <- Primary PostfixOp*
PostfixOp  <- Call / Index / Member / TrailingClosure
Call       <- "(" (Expr ("," Expr)*)? ")"
Index      <- "[" Expr "]"
Member     <- "." Identifier
TrailingClosure <- BraceBlock
# PursueExpr/ActivateExpr must be tried before the bare Identifier
# alternative below -- "pursue"/"activate" aren't reserved keywords
# (same non-reservation as "rule"/"goal": pursue(x)/activate(x) fall
# through to an ordinary call via Identifier+Call on failure here), so
# without this ordering a bare Identifier match on "pursue" alone would
# silently swallow just the keyword and leave the goal name/plan
# expression as a dangling, separately-parsed statement -- accepting
# some malformed input (e.g. `pursue 123`) that the real parser rejects.
Primary    <- Number / String / PursueExpr / ActivateExpr / Identifier
              / "(" Expr ")" / ListLit / ClosureLit / BudgetedExpr
PursueExpr <- "pursue" Identifier
ActivateExpr <- "activate" Expr

# Condition expression tower -- structurally identical, but its Postfix
# tier deliberately excludes TrailingClosure so `if cond { ... }` doesn't
# swallow the block as a closure argument. Nested parens can freely use
# the general Expr tower again since that ambiguity only applies to the
# bare, unparenthesized condition itself.
CondExpr     <- CondPipeline
CondPipeline <- CondOr ("|>" CondOr)*
CondOr       <- CondAnd ("or" CondAnd)*
CondAnd      <- CondEq ("and" CondEq)*
CondEq       <- CondCmp (("==" / "!=" / "=") CondCmp)*
CondCmp      <- CondBitwise (("<=" / ">=" / "<" / ">") CondBitwise)*
CondBitwise  <- CondShift (("band" / "bxor" / "bor") CondShift)*
CondShift    <- CondAdd (("shl" / "shr") CondAdd)*
CondAdd      <- CondMul (("+" / "-") CondMul)*
CondMul      <- CondUnary (("*" / "/" / "%") CondUnary)*
CondUnary    <- ("not" / "bnot" / "-") CondUnary / CondPostfix
CondPostfix  <- CondPrimary CondPostfixOp*
CondPostfixOp <- Call / Index / Member
CondPrimary  <- Number / String / PursueExpr / CondActivateExpr / Identifier
                / "(" Expr ")" / ListLit / ClosureLit / BudgetedExpr
# A separate condition-tower activate production, using CondExpr (not
# Expr) for its own inner argument -- reusing the general ActivateExpr
# here would reintroduce exactly the trailing-block ambiguity the whole
# Expr/CondExpr split exists to prevent: `if activate(p) { ... }`'s
# general Expr tower would let TrailingClosure swallow the if's own
# body block as a closure argument to activate(p), leaving nothing for
# IfBrace's required BraceBlock afterward.
CondActivateExpr <- "activate" CondExpr

ListLit    <- "[" (Expr ("," Expr)*)? "]"
ClosureLit <- "|" ParamList "|" Block
BudgetedExpr <- "budgeted" "(" Expr ("," Expr)? ")" Block

Colour key: rule name (definition site) ยท PEG operator (<-, /, *, +, ?, !) ยท "quoted literal" ยท # comment. Bare unstyled words are references to other rules.

See also

The dev-tooling write-up for the design decisions behind this grammar, the engine that interprets it, and the benchmark result (~1.8ร— the native parser's wall-clock time). The Grammar & Syntax reference for the prose, per-stage compatibility documentation this file complements rather than replaces. Goal-Oriented Programming for a worked example of the goal/pursue/activate syntax this grammar covers.

Graduate Attributes

Modelled on this page

  • Subject Specialist: Technical distinctions between PEG and BNF are explained through specific operator behaviour and parsing mechanics.
  • Researcher: The grammar file serves as an independent structural check against two other parser implementations to validate syntax correctness.
  • Critical Thinker: Design choices regarding syntax ambiguity are justified by analysing potential parsing conflicts and their resolution.

University of Reading Graduate Attributes framework.