Pia grammar¶
Status: accepted for milestone M1 (#2), 2026-11-20. The disambiguation rules are recorded in ADR 0019.
This document is the specification. Two files make it executable:
grammar/pia_lexer.pyis the reference lexer, including the layout rule.grammar/pia.larkis the reference phrase grammar, run by Lark's Earley parser.
tests/grammar/test_grammar.py parses every ocaml code block in design.md, the cases in tests/grammar/valid/, and checks that every case in tests/grammar/invalid/ is rejected. The C++ front end (M2) must accept and reject the same corpus.
Run the tests with pip install -r tests/grammar/requirements.txt and then python3 tests/grammar/test_grammar.py. Bazel will wrap this as a py_test in M0.
Notation¶
The phrase grammar uses EBNF. x? is optional, x* is zero or more, x+ is one or more, ( ... ) groups, | separates alternatives, and quoted text is a literal token. Names in UPPER_CASE are tokens from the lexical grammar.
Lexical grammar¶
Whitespace and comments¶
Spaces, tabs and newlines separate tokens. Comments are (* ... *) and nest, as in OCaml. Because (* always opens a comment, the multiplication operator value is written ( * ) with spaces.
Identifiers and keywords¶
IDENT = ( letter | "_" ) { letter | digit | "_" | "'" } ;
A prime (') may follow the first character, as in x' and x''. Pia has no shadowing (ADR 0022), so primes are the usual way to name a value related to x. Nothing else in the language uses ': there are no character literals, and type variables are written <T>.
Reserved words:
let rec meta in type of where if then else match with for spread while do done
requires ensures invariant decreases assert assume forall exists
interface sig module struct end import operator true false
borrowed moved out inout fixed mutable mod
step is a keyword only inside a for or spread header, between the keyword and do. Everywhere else it is an ordinary identifier, so a function can still be called step.
Names such as result, old, dyn, concept, adapter, item, ident, prec, left and right are ordinary identifiers that the prelude or the contract checker gives meaning to.
Literals¶
INT = digits [ suffix ] | "0x" hexdigits [ suffix ] | "0b" bindigits [ suffix ] | "0o" octdigits [ suffix ] ;
FLOAT = digits "." digits [ exponent ] [ suffix ] | digits exponent [ suffix ] ;
suffix = ( "u" | "i" | "f" ) digits | "usize" | "isize" ; (* 42u8, 1i64, 0.5f32, 3usize *)
STRING = '"' { char | escape } '"' ;
Digits may contain _ separators (1_000_000). A float needs a digit after the point, so 0..n lexes as 0, .., n.
Operators¶
An operator is a maximal run of + - * / < > = | & ^ ~ ! % ?. A few spellings are reserved by the grammar:
| Token | Meaning |
|---|---|
= |
Binding, and the equality operator |
-> |
Function type, match arm |
=> |
Function literal |
<- |
Assignment |
\| |
Variant, match arm, union type, refinement |
Every other operator gets its precedence from the operator table. The table comes from the let meta operator declarations in the prelude (meta.md) and in the program. Operators not in the table get a level from their first character, as in OCaml.
| Level | Operators | Associativity |
|---|---|---|
| 1 | ==> <==> |
right |
| 2 | \|\| |
right |
| 3 | && |
right |
| 4 | = <> < > <= >= |
none |
| 5 | .. (range) |
none |
| 6 | + - +\| -\| |
left |
| 7 | * / % mod |
left |
| prefix | - |
|
| application | left | |
.f .[i] name<...> |
postfix |
The levels match the design's let meta operator ( + ) : prec 6 left. A user operator declared at a level above 7 binds tighter than * and looser than application.
Other punctuation¶
| Token | Spelling | Notes |
|---|---|---|
QUOTE_OPEN |
`( |
Quoted syntax, closed by ) |
QIDENT |
`name |
A quoted identifier, e.g. `sgemm_4x16 |
SPLICE_IDENT |
$name, $!name |
Splice a metaprogram value. $!name escapes hygiene (meta.md) |
SPLICE_OPEN |
$( |
Splice an expression, closed by ) |
ATTR, ATTR_OPEN |
@name, @name( |
Attributes; arguments follow ( with no space |
TARGS_OPEN |
< straight after an identifier |
Explicit type arguments, see below |
LBRACE_ADJ |
{ straight after an identifier |
Range types such as int{0..255} |
DOT_LBRACKET |
.[ |
Indexing and slicing |
QDOT |
. followed by whitespace |
Ends quantifier binders |
DOT |
. followed by anything else |
Field access and paths |
DOTDOT |
.. |
Ranges |
HOLE |
... |
A hole, see below |
SEMI, SEP |
;, ;; |
Sequencing; explicit item separator |
Adjacency rules¶
Spacing decides three things.
name<opens type arguments.sum<i64> xsandvec<u8, 16>instantiate. Less-than must be written with a space:a < b. Writingx<yis an error that names the rule. Inside the list,>closes it, and>>closes two lists.name{opens a range type.int{0..255}is a range-refined integer. A record literal passed to a function is written with a space,f { x = 1 }.- A dot followed by whitespace ends quantifier binders. In
forall i in 0..n. p ithe dot isQDOT. Field access never has a space after the dot.
Layout rule¶
Pia is not indentation-sensitive, except in one place. Top-level items start in column 1, and the lexer inserts an item separator (SEP) before a token in column 1 when three things hold:
- it is outside every bracket,
sig/struct ... endanddo ... done - it can start an item: an identifier, literal,
let,interface,module,import,(,[, a quote or a splice - it is not the first token in the file
So a continuation line is either indented or starts with a token that cannot start an item, such as =, |, && or end. This matches every example in the design: = for i in 0..n do ... done in column 1 continues the definition above it, and tiled_matmul ... in column 1 starts a new item. ;; is an explicit separator for anyone who wants to put two items on one line.
Without this rule, a bare top-level metaprogram call would be read as further arguments to the expression that ends the previous item.
Phrase grammar¶
Programs and items¶
program = [ item { SEP item } ] ;
item = let_item | meta_operator | interface | module | import | expr_item ;
expr_item = application ; (* a compile-time call that yields items *)
import = "import" path ;
path = IDENT { "." IDENT } ;
Bindings¶
let_item = "let" [ "rec" ] [ "meta" ] binder { param } [ ret_annot ] { contract } "=" seq ;
let_in = "let" [ "rec" ] binder { param } [ ret_annot ] { contract } "=" seq "in" seq ;
binder = IDENT | SPLICE_IDENT ;
param = IDENT | SPLICE_IDENT
| "(" ( IDENT | SPLICE_IDENT ) ":" annot ")"
| "(" ")" | "(" "..." ")" ;
ret_annot = ":" annot { attribute } | attribute { attribute } ;
contract = "requires" stmt | "ensures" stmt | "decreases" stmt ;
lambda = "let" lparam { lparam } "=>" seq ;
lparam = "(" pattern [ ":" annot ] ")" | "(" ")" ;
meta_operator = "let" "meta" "operator" "(" operator ")"
[ ":" "prec" INT ( "left" | "right" | "none" ) ]
[ "for" type ] "=" seq ;
let followed by ( is a function literal. let followed by a name is a binding. Pia has no tuple destructuring in let today; if it is added, the => still tells the two apart.
Annotations and types¶
annot = modifiers union_type [ "where" stmt ]
| arrow_type [ "where" stmt ] ;
modifiers = [ "borrowed" | "moved" ] [ "in" | "out" | "inout" ] [ "fixed" | "mutable" ] ;
type = arrow_type | union_type ;
arrow_type = arrow_dom "->" type ;
arrow_dom = modifiers union_type | "(" IDENT ":" annot ")" ;
union_type = app_type { "|" app_type } ;
app_type = type_atom { type_arg } ; (* pair u8 f32, adapter Eq f32 *)
type_arg = type_atom | INT | "(" expr ")" ;
type_atom = IDENT
| "type" (* the type of types *)
| IDENT "<" targ { "," targ } ">" (* vec<u8, 16>, tiled<cell, 256, 256, halo = 1> *)
| IDENT "{" expr ".." expr "}" (* int{0..255} *)
| "[" type "]" (* slice, length carried at run time *)
| "[" type ";" expr "]" (* array, length known to the prover *)
| "{" field_decl { ";" field_decl } [ ";" ] "}"
| "{" IDENT ":" type "|" stmt "}" (* refinement *)
| "(" type ")" | "(" ")"
| SPLICE_IDENT | "$(" expr ")" ;
targ = type | elem | IDENT "=" elem ;
field_decl = IDENT ":" annot ;
Modifiers come in a fixed order: ownership, then access, then mutability. Each one is optional. Before a function type they belong to its first parameter: borrowed in [pixel] -> [u8] takes a borrowed input slice.
A type value is an expression:
type_value = "type" ( variants | type ) { attribute } [ "where" stmt ] { attribute } ;
variants = "|" ctor { "|" ctor } ;
ctor = IDENT [ "of" app_type ] ;
attribute = "@" IDENT [ "(" attr_arg { "," attr_arg } ")" ] ;
attr_arg = stmt | IDENT "=" stmt ;
A constructor's payload is one type application. A union or function payload needs parentheses, since | A of t | B already means two constructors.
Expressions¶
Constructs that extend as far right as possible sit at the sequence level. The rest are ordered by the operator table.
expr = seq ;
seq = stmt [ ";" [ seq ] ] | let_in | match | lambda ;
elem = stmt | "let" lparam { lparam } "=>" elem ; (* list, record and argument elements *)
stmt = postfix "<-" stmt
| "if" seq "then" stmt [ "else" stmt ]
| "for" pattern "in" or_e [ "step" add_e ] { loop_annot } "do" seq "done"
| "spread" pattern "in" or_e { attribute } { loop_annot } "do" seq "done"
| "while" seq { loop_annot } "do" seq "done"
| quantifier
| "assert" imp_e | "assume" imp_e
| type_value
| imp_e ;
loop_annot = "invariant" stmt | "decreases" stmt ;
quantifier = ( "forall" | "exists" ) qbinder { qbinder } QDOT stmt ;
qbinder = IDENT [ ":" type ] | IDENT "in" range_e
| "(" IDENT ":" type ")" | "(" IDENT "in" range_e ")" ;
imp_e = or_e [ "==>" ( imp_e | quantifier ) ] ;
or_e = and_e [ "||" ( or_e | quantifier ) ] ;
and_e = cmp_e [ "&&" ( and_e | quantifier ) ] ;
cmp_e = range_e [ cmp_op ( range_e | quantifier ) ] ;
range_e = add_e [ ".." add_e ] ;
add_e = mul_e { add_op mul_e } ;
mul_e = unary { mul_op unary } ;
unary = "-" unary | application ;
application = postfix { postfix } ;
postfix = atom
| postfix "." ( IDENT | SPLICE_IDENT )
| postfix ".[" seq "]" (* xs.[i], frame.[0 .. w] *)
| postfix "<" targ { "," targ } ">" ; (* sum<i64> *)
atom = IDENT | INT | FLOAT | STRING | "true" | "false"
| QIDENT | "..."
| "(" seq ")" | "(" ")" | "(" operator ")"
| "[" [ elem { ";" elem } [ ";" ] ] "]"
| "{" field_init { ";" field_init } [ ";" ] "}"
| "{" postfix "with" field_init { ";" field_init } [ ";" ] "}"
| "`(" quoted ")"
| SPLICE_IDENT | "$(" seq ")" ;
field_init = IDENT "=" elem ;
quoted = let_item { [ SEP ] let_item } (* items *)
| IDENT ":" type (* a declaration: `( add : $t -> $t -> $t ) *)
| seq ; (* an expression *)
match = "match" seq "with" [ "|" ] arm { "|" arm } ;
arm = pattern "->" seq ;
Patterns¶
pattern = IDENT pattern_atom { pattern_atom } | pattern_atom ; (* Num n *)
pattern_atom = IDENT | INT | STRING | "true" | "false" | SPLICE_IDENT
| "(" pattern ":" type ")" | "(" pattern ")"
| "{" pfield { ";" pfield } [ ";" ] "}" ;
pfield = IDENT [ "=" pattern ] ;
_ is an ordinary identifier pattern that binds nothing.
Modules and interfaces¶
interface = "interface" IDENT "=" "sig" { sig_item } "end" ;
sig_item = "let" binder ":" annot { attribute } { contract } (* exported symbol *)
| "let" binder "=" type_value (* exported type *)
| "..." ;
module = "module" IDENT [ ":" path { "," path } ] "=" "struct" { item } "end" ;
Disambiguation¶
The grammar is ambiguous in a few places. Each one is settled by a rule, and each rule has a test in Disambiguation in the test file.
- Contract predicate before the body. A definition with contracts reads
let f ... ensures p = body, andpmay itself contain=. The predicate takes the longest reading: if it can end after a top-level comparison, it does, and the next=starts the body.ensures total g = old (total g) - drained g = step gtherefore ensurestotal g = old (total g) - drained g. If the last predicate has no comparison (requires sorted xs = body), there is only one reading. A body that is itself a comparison, after a predicate that is not, needs parentheses. A hand-written parser does this by parsing the predicate greedily and, if no body=follows, splitting the last top-level=of the final clause. - Comparisons do not associate.
a = b = cis an error. This is what makes rule 1 work. - Layout. A column-1 token that can start an item starts one. See Layout rule.
name<is instantiation. See Adjacency rules.- Named type arguments. In
tiled<cell, 256, halo = 1>,halo = 1is a named argument, not a comparison. - Type or value. Since types are values,
sum<f32, eq_f32>,pair u8 f32andadapter Numeric (fast f32)have arguments that could be types or expressions. The parser accepts both readings and Sema decides. - Right-extending constructs.
let ... in,match, function literals,ifand quantifiers extend as far right as they can, as in OCaml. Inside a list, record or argument list, a function literal stops at the next;or,. A nestedmatchneeds parentheses. - Modifiers before a function type belong to its first parameter.
Holes¶
... is a hole. The parser accepts it as an expression, a parameter list, a contract predicate, an interface item or a module body, so sketches like the ones in the design parse. Sema reports every hole as an unfinished definition, so a program with holes never compiles.
Not yet in the grammar¶
These are in the design's direction but have no syntax yet. Each will get an ADR when it is needed.
- Tuple types and tuple patterns
- Guards on match arms (
when) - Placement and task-graph syntax beyond
spreadand@place(M12) - Doc comments