Appendix B: Bridger Concrete Grammar

This appendix gives Bridger’s concrete grammar: the rules that decide which strings of characters are Bridger programs and how each one groups into its parts. The grammar is presented one sublanguage at a time; the final section collects every production into one listing.

The distinction between the text as written and the structure underneath it (concrete versus abstract syntax) is the subject of Syntax and semantics; the grammar here describes the concrete side, which strings the provided parser accepts as a program. The abstract syntax that parser produces, the values a program computes, and the rules that give them meaning (evaluation, typing, and purity) are fixed formally in the language reference. In the AST chapter, we further detail the abstract syntax of Bridger including the Rust enum output by the provided Bridger parser.

Reading the notation

The productions are written in a variant of Extended Backus–Naur Form. A production names a syntactic category on the left of ::= and gives its forms on the right, built from the terminals, other categories, and the metasyntax below:

{ x }     zero or more repetitions of x
[ x ]     an optional x
( x )     grouping
x | y     either x or y
'…'       a terminal, written verbatim
<desc>    an informally described set of characters
(* … *)   a comment

Identifiers, Literals, Comments

Bridger uses two identifier conventions: snake_case for variables, functions, relations, struct fields, and methods, UpperCamelCase for type names, constructors, and traits. We denote the two classes of identifiers ident and UpperIdent, respectively.

(* snake_case *)
ident       ::= letter_lc { letter_lc | digit | '_' ( letter_lc | digit ) } ;
(* UpperCamelCase *)
UpperIdent  ::= letter_uc { letter | digit } ;

letter      ::= letter_lc | letter_uc ;
letter_lc   ::= 'a' | 'b' | … | 'z' ;
letter_uc   ::= 'A' | 'B' | … | 'Z' ;
digit       ::= '0' | digit_nz ;
digit_nz    ::= '1' | '2' | … | '9' ;

An ident may separate words with single underscores, but may not start with, end with, or double underscores. For example, _foo, bar_, and foo__bar are not identifiers.

A Bridger program operates over integer, Boolean, string, and unit values. A literal is a string representing a concrete value. In Bridger, an integer literal is a decimal number (optionally with ‘_’ to group by thousands). Boolean literals are either “true” or “false” and unit has a single value denoted “()”. A string literal is a sequence of characters on a single line between quotation marks ". Any Unicode character may be written directly (in UTF-8 encoding); a quotation mark, backslash, or control character (such as a newline) is written with an escape: \n, \t, \r, \0, \", \\, or \u{…} for an arbitrary code point (\u{1F600} is 😀).

literal     ::= int_lit | bool_lit | string_lit | unit_lit ;
int_lit     ::= [ '-' ] ( '0' | pos_int ) ;
pos_int     ::= digit_nz { digit }
              | digit_nz [ digit [ digit ] ] { '_' digit digit digit } ;
bool_lit    ::= 'true' | 'false' ;
unit_lit    ::= '(' ')' ;
string_lit  ::= '"' { string_char } '"' ;
string_char ::= <any Unicode scalar value except '"', '\', or a control character>
              | escape ;
escape      ::= '\n' | '\t' | '\r' | '\0' | '\"' | '\\'
              | '\u{' hex_digit { hex_digit } '}' ;
hex_digit   ::= digit | 'a' | 'b' | … | 'f' | 'A' | 'B' | … | 'F' ;

An int_lit denotes a 64-bit signed integer, so a pos_int is at most 9223372036854775807 — or 9223372036854775808 when it follows -, since -9223372036854775808 is the least integer and is a literal only with its sign. The sign belongs to the literal when - stands directly before the digits and cannot be subtraction — that is, when the token before it is not an identifier, a literal, self, a closing bracket, or ?. Elsewhere - is an operator: x -1 subtracts, and - 1, with a space, negates 1. :- is one token wherever it appears, so a negative field value is written a: -1, with a space. Lists ([1, 2, 3]) and tuples ((a, b)) are built from subexpressions, so they appear under The expression language rather than here as literals.

Whitespace between tokens is any Unicode whitespace, line breaks included; it separates tokens and means nothing else, so layout is free. Comments are line comments, which run to the end of the line, and block comments, which nest. Inside a block comment every /* opens a nested comment and every */ closes one, so the delimiters must balance: /* /* */ */ is one comment, while /* /* */ is unterminated and /* */ */ closes after the first */, leaving a stray */.

line_comment  ::= '//' { <any character except a line break> } ;
block_comment ::= '/*' { block_comment
                       | <any character not beginning '/*' or '*/'> } '*/' ;

The keywords are reserved and may not be used as identifiers:

fn  let  if  else  while  match  type  struct  trait  impl  for  in
relation  rule  add  clear  solutions  not  and  or  true  false
ref  deref  self  Self  return  mut

Three of these are keywords only in one position: add, clear, and solutions are read as keywords when a relation name follows them (add edge(1, 2), clear edge, solutions path(0, ?x)) and as ordinary identifiers everywhere else, so set.add(x), fn clear(…), and a field or variable named solutions are all allowed; the one exception is solutions(r(?x)), which the parser rejects with a note that the keyword form takes no parentheses. mut is reserved without a use: it lets let mut x be explained rather than parsed, since a mutable cell is written ref x = e;.

Programs, definitions, and blocks

A program is a sequence of definitions: functions, types, structs, traits, impl blocks, relations, rules, and top-level let and ref bindings. Their order is free, since definitions are mutually visible, and each top-level name is declared once — a repeated name is rejected. Execution starts at main, an ordinary fn main() taking no arguments; a program that is run must define exactly one, and its result, whatever its type, is the program’s value.

program     ::= { def } ;

def         ::= fn_def | type_def | struct_def | trait_def | impl_def
              | relation_def | rule_def
              | let_binding | ref_binding ;

block       ::= '{' { block_item } [ expr ] '}' ;

block_item  ::= let_binding | ref_binding
              | ( if_expr | match_expr | while_expr | for_expr | block ) [ ';' ]
              | expr_stmt ;

let_binding ::= 'let' ident [ ':' type ] '=' expr ';' ;
ref_binding ::= 'ref' ident [ ':' type ] '=' expr ';' ;
expr_stmt   ::= expr ';' ;

A block is a sequence of let/ref bindings, expressions, and nested blocks. Neither an expr_stmt nor the block’s trailing expression begins with a braced form — if, match, while, for, or a block — since those stand as items in their own right: { x } + 1; is not a statement, a braced form that ends the block with no ; after it is the block’s value, a ; after one makes it a statement, and an operator after one needs parentheses, { (if c { 1 } else { 2 }) + 3 }; let y = { x } + 1; is fine. The definition forms (fn, type, struct, trait, impl, relation, rule) are top-level only, so a local function is written as a lambda. A ref_binding is surface sugar: ref x = e; reads as let x = ref e;.

The expression language

An expression (expr) is a lambda function (lambda), a returned value (return), or an operation (assign).

expr        ::= lambda | return_expr | assign ;

The operation grammar is a precedence cascade from the loosest-binding operator (assignment :=) down to the tightest (the postfix cluster), each level taking its operands from the one below. The cascade bottoms out at primary (atomic operands).

assign      ::= or_expr [ ':=' or_expr ] ;
or_expr     ::= and_expr { 'or' and_expr } ;
and_expr    ::= cmp_expr { 'and' cmp_expr } ;
cmp_expr    ::= cat_expr [ cmp_op cat_expr ] ;
cmp_op      ::= '==' | '!=' | '<' | '<=' | '>' | '>=' ;
cat_expr    ::= add_expr [ ('++' | '::') cat_expr ] ;
add_expr    ::= mul_expr { ('+' | '-') mul_expr } ;
mul_expr    ::= unary   { ('*' | '/' | '%') unary } ;
unary       ::= ('deref' | 'ref' | '-' | 'not') unary | postfix ;
postfix     ::= primary { '(' [ args ] ')' | '.' ident [ '(' [ args ] ')' ]
                        | '.' ( '0' | pos_int ) | '?' } ;
args        ::= expr { ',' expr } ;

Two associativity choices are visible in the shapes: comparisons recur on neither side, since they are non-associative and cannot be chained; ++ and :: recur on their right operand, so they associate to the right, and 1 :: 2 :: xs prepends two elements. The postfix cluster is function call f(...), field access e.field, method call e.m(args), tuple projection e.0, and the ? operator; the projection index is an integer literal. A name after . that is followed by an argument list is always a method call, so a function held in a field is called through parentheses, (e.f)(args). A primary is an atom or a bracketed form; the UpperIdent alternative is a constructor application, or the bare name of a nullary constructor, a struct, or a type (the receiver of an associated call, Point.origin()):

primary     ::= literal | ident | '(' expr ')' | tuple | list | block | struct_lit
              | UpperIdent [ '(' args ')' ]
              | if_expr | match_expr | while_expr | for_expr
              | 'add' query | 'clear' ident | 'solutions' query | query
              | 'self' ;

tuple       ::= '(' expr ',' expr { ',' expr } ')' ;
list        ::= '[' [ expr { ',' expr } ] ']' ;
struct_lit  ::= UpperIdent '{' [ ident ':' expr { ',' ident ':' expr } [','] ] '}' ;

A one-element parenthesization (e) is just grouping; any expr may sit inside, a while or := included. The unit literal is (); a tuple needs arity two or more. A block { … } is a primary as well, so a braced sequence may stand anywhere an operand is expected. The add, clear, solutions, and bare-query primaries belong to the relations sublanguage and are described below; each of the three keywords is followed directly by its relation atom or name, with no parentheses of its own.

Point { x: 1, y: 2 }

Precedence and associativity

The operator cascade fixes precedence and associativity by its shape. A primary is the operand the operators combine; here they are, tightest-binding first:

Assignment := binds loosest of all, which is why r := deref r + 1 reads as r := (deref r + 1). The prefix operators bind tighter than any infix one and stack (deref ref e, not not b), so -a * b is (-a) * b and not a == b is (not a) == b.

Control flow

Next we consider conditional expressions, matching expressions, looping expressions, lambda functions, and return expressions.

if_expr     ::= 'if' expr block [ 'else' ( block | if_expr ) ] ;
match_expr  ::= 'match' expr '{' arm { ',' arm } [','] '}' ;
arm         ::= pattern [ 'if' expr ] '=>' expr ;
while_expr  ::= 'while' expr block ;
for_expr    ::= 'for' ident 'in' expr block      (* list iteration *)
              | 'for' query block ;              (* relational iteration *)
return_expr ::= 'return' expr ;
lambda      ::= '|' [ lparam { ',' lparam } ] '|' expr ;
lparam      ::= ident [ ':' type ] ;

A match arm may carry a guard — the if after its pattern — and a lambda’s parameters sit between single bars, so a nullary lambda is ||.

match xs {
    []      => 0,
    [h, ...t] if h > 0 => h,
    _       => 1,
}

|x: Int, y: Int| x + y
|| 0

Functions, types, and data

Function definitions, the type language, and the type/struct/trait/impl declarations.

fn_def      ::= 'fn' ident [ generics ] '(' [ params ] ')'
                [ '->' type ] fn_body ;
fn_body     ::= '=' expr ';' | block ;
params      ::= param { ',' param } ;
param       ::= ident ':' type ;
generics    ::= '<' tparam { ',' tparam } '>' ;
tparam      ::= UpperIdent [ ':' trait_ref ] ;

An omitted result type is (), so fn f() = 1; is a type error and fn f() -> Int = 1; is the function meant.

The type language:

type        ::= 'Int' | 'Bool' | 'String' | '(' ')' | 'Self'
              | '(' type ',' type { ',' type } ')'
              | '[' type ']'
              | 'fn' '(' [ type { ',' type } ] ')' '->' type
              | 'ref' '<' type '>'
              | UpperIdent [ '<' type { ',' type } '>' ] ;

Declarations introduce named types, structs, traits, and implementations.

type_def    ::= 'type' UpperIdent [ generics ] '='
                [ '|' ] variant { '|' variant } ';' ;
variant     ::= UpperIdent [ '(' type { ',' type } ')' ] ;

struct_def  ::= 'struct' UpperIdent [ generics ]
                '{' [ field { ',' field } [','] ] '}' ;
field       ::= ident ':' type ;

trait_def   ::= 'trait' UpperIdent [ generics ] '{' { fn_sig ';' } '}' ;
fn_sig      ::= 'fn' ident '(' [ 'self' [ ',' params ] | params ] ')' [ '->' type ] ;

impl_def    ::= 'impl' [ generics ] [ trait_ref 'for' ] type
                '{' { method } '}' ;
trait_ref   ::= UpperIdent [ '<' type { ',' type } '>' ] ;
method      ::= 'fn' ident '(' [ 'self' [ ',' params ] | params ] ')'
                [ '->' type ] fn_body ;

An impl block either stands alone or names a trait with for; a method’s first parameter may be self. With self it is a method, called on a value as e.m(args); without, it is an associated function of the type, called on the type’s name as Type.m(args) — the same postfix call syntax, with a bare type name as the receiver.

The Option below is the prelude’s own definition, shown for its shape; a program that declares it again collides with the prelude.

type Option<T> = None | Some(T);

struct Point { x: Int, y: Int }

trait Show { fn show(self) -> String; }

impl Show for Point {
    fn show(self) -> String = "point";
}

Patterns

Patterns appear in match arms. A pattern is the wildcard _, a literal, a variable, a constructor, a tuple, a list — with a :: cons form and an optional ... tail — a struct, or several patterns joined by |.

pattern     ::= '_' | literal | ident
              | UpperIdent [ '(' pattern { ',' pattern } ')' ]
              | '(' pattern ')'
              | '(' pattern ',' pattern { ',' pattern } ')'
              | '[' [ pattern { ',' pattern } [ ',' '...' ident ] ] ']'
              | pattern '::' pattern
              | UpperIdent '{' [ field_pat { ',' field_pat } [ ',' ] ] '}'
              | pattern '|' pattern ;
field_pat   ::= ident [ ':' pattern ] ;

In a pattern, :: binds tighter than | and associates to the right with an atomic head, so a | b :: t is a | (b :: t) and (a | b) :: t needs its parentheses.

The relations sublanguage

Bridger’s also includes a Datalog fragment that adds relation declarations, rules, and queries.

relation_def::= 'relation' ident ':' '(' type { ',' type } ')' ';' ;
rule_def    ::= 'rule' rule_atom [ ':-' body ] ';' ;
body        ::= conjunct { 'and' conjunct } ;
conjunct    ::= rule_atom      (* generator: binds logic variables *)
              | expr ;         (* filter: pure, binds nothing, no return *)
rule_atom   ::= ident '(' term { ',' term } ')' ;
term        ::= ident | literal ;   (* a lowercase ident is a logic variable *)

query       ::= ident '(' qarg { ',' qarg } ')' ;
qarg        ::= expr | hole ;
hole        ::= '?' [ ident ] ;     (* named ?x or anonymous ? *)

Syntactically, there is no difference between a query and a function call. Instead, the difference comes from its use and via name resolution.

rule ancestor(x, y) :- parent(x, y);

The complete grammar

Every production above, collected. This listing is the grammar as a whole; the sections above are the same rules broken out with commentary.

(* --- lexical --- *)
ident       ::= letter_lc { letter_lc | digit | '_' ( letter_lc | digit ) } ;
UpperIdent  ::= letter_uc { letter | digit } ;
letter      ::= letter_lc | letter_uc ;
letter_lc   ::= 'a' | 'b' | … | 'z' ;
letter_uc   ::= 'A' | 'B' | … | 'Z' ;
digit       ::= '0' | digit_nz ;
digit_nz    ::= '1' | '2' | … | '9' ;

literal     ::= int_lit | bool_lit | string_lit | unit_lit ;
int_lit     ::= [ '-' ] ( '0' | pos_int ) ;
pos_int     ::= digit_nz { digit }
              | digit_nz [ digit [ digit ] ] { '_' digit digit digit } ;
bool_lit    ::= 'true' | 'false' ;
unit_lit    ::= '(' ')' ;
string_lit  ::= '"' { string_char } '"' ;
string_char ::= <any Unicode scalar value except '"', '\', or a control character>
              | escape ;
escape      ::= '\n' | '\t' | '\r' | '\0' | '\"' | '\\'
              | '\u{' hex_digit { hex_digit } '}' ;
hex_digit   ::= digit | 'a' | 'b' | … | 'f' | 'A' | 'B' | … | 'F' ;

line_comment  ::= '//' { <any character except a line break> } ;
block_comment ::= '/*' { block_comment
                       | <any character not beginning '/*' or '*/'> } '*/' ;

(* --- programs, items, blocks --- *)
program     ::= { def } ;
block       ::= '{' { block_item } [ expr ] '}' ;
def         ::= fn_def | type_def | struct_def | trait_def | impl_def
              | relation_def | rule_def
              | let_binding | ref_binding ;
block_item  ::= let_binding | ref_binding
              | ( if_expr | match_expr | while_expr | for_expr | block ) [ ';' ]
              | expr_stmt ;
let_binding ::= 'let' ident [ ':' type ] '=' expr ';' ;
ref_binding ::= 'ref' ident [ ':' type ] '=' expr ';' ;
expr_stmt   ::= expr ';' ;

(* --- expressions --- *)
expr        ::= lambda | return_expr | assign ;
assign      ::= or_expr [ ':=' or_expr ] ;
or_expr     ::= and_expr { 'or' and_expr } ;
and_expr    ::= cmp_expr { 'and' cmp_expr } ;
cmp_expr    ::= cat_expr [ cmp_op cat_expr ] ;
cmp_op      ::= '==' | '!=' | '<' | '<=' | '>' | '>=' ;
cat_expr    ::= add_expr [ ('++' | '::') cat_expr ] ;
add_expr    ::= mul_expr { ('+' | '-') mul_expr } ;
mul_expr    ::= unary   { ('*' | '/' | '%') unary } ;
unary       ::= ('deref' | 'ref' | '-' | 'not') unary | postfix ;
postfix     ::= primary { '(' [ args ] ')' | '.' ident [ '(' [ args ] ')' ]
                        | '.' ( '0' | pos_int ) | '?' } ;
args        ::= expr { ',' expr } ;
primary     ::= literal | ident | '(' expr ')' | tuple | list | block | struct_lit
              | UpperIdent [ '(' args ')' ]
              | if_expr | match_expr | while_expr | for_expr
              | 'add' query | 'clear' ident | 'solutions' query | query
              | 'self' ;
tuple       ::= '(' expr ',' expr { ',' expr } ')' ;
list        ::= '[' [ expr { ',' expr } ] ']' ;
struct_lit  ::= UpperIdent '{' [ ident ':' expr { ',' ident ':' expr } [','] ] '}' ;

(* --- control flow --- *)
if_expr     ::= 'if' expr block [ 'else' ( block | if_expr ) ] ;
match_expr  ::= 'match' expr '{' arm { ',' arm } [','] '}' ;
arm         ::= pattern [ 'if' expr ] '=>' expr ;
while_expr  ::= 'while' expr block ;
for_expr    ::= 'for' ident 'in' expr block | 'for' query block ;
return_expr ::= 'return' expr ;
lambda      ::= '|' [ lparam { ',' lparam } ] '|' expr ;
lparam      ::= ident [ ':' type ] ;

(* --- functions, types, data --- *)
fn_def      ::= 'fn' ident [ generics ] '(' [ params ] ')'
                [ '->' type ] fn_body ;
fn_body     ::= '=' expr ';' | block ;
params      ::= param { ',' param } ;
param       ::= ident ':' type ;
generics    ::= '<' tparam { ',' tparam } '>' ;
tparam      ::= UpperIdent [ ':' trait_ref ] ;
type        ::= 'Int' | 'Bool' | 'String' | '(' ')' | 'Self'
              | '(' type ',' type { ',' type } ')' | '[' type ']'
              | 'fn' '(' [ type { ',' type } ] ')' '->' type
              | 'ref' '<' type '>'
              | UpperIdent [ '<' type { ',' type } '>' ] ;
type_def    ::= 'type' UpperIdent [ generics ] '='
                [ '|' ] variant { '|' variant } ';' ;
variant     ::= UpperIdent [ '(' type { ',' type } ')' ] ;
struct_def  ::= 'struct' UpperIdent [ generics ]
                '{' [ field { ',' field } [','] ] '}' ;
field       ::= ident ':' type ;
trait_def   ::= 'trait' UpperIdent [ generics ] '{' { fn_sig ';' } '}' ;
fn_sig      ::= 'fn' ident '(' [ 'self' [ ',' params ] | params ] ')' [ '->' type ] ;
impl_def    ::= 'impl' [ generics ] [ trait_ref 'for' ] type
                '{' { method } '}' ;
trait_ref   ::= UpperIdent [ '<' type { ',' type } '>' ] ;
method      ::= 'fn' ident '(' [ 'self' [ ',' params ] | params ] ')'
                [ '->' type ] fn_body ;

(* --- patterns --- *)
pattern     ::= '_' | literal | ident
              | UpperIdent [ '(' pattern { ',' pattern } ')' ]
              | '(' pattern ')'
              | '(' pattern ',' pattern { ',' pattern } ')'
              | '[' [ pattern { ',' pattern } [ ',' '...' ident ] ] ']'
              | pattern '::' pattern
              | UpperIdent '{' [ field_pat { ',' field_pat } [ ',' ] ] '}'
              | pattern '|' pattern ;
field_pat   ::= ident [ ':' pattern ] ;

(* --- relations --- *)
relation_def::= 'relation' ident ':' '(' type { ',' type } ')' ';' ;
rule_def    ::= 'rule' rule_atom [ ':-' body ] ';' ;
body        ::= conjunct { 'and' conjunct } ;
conjunct    ::= rule_atom | expr ;   (* an expr other than a return *)
rule_atom   ::= ident '(' term { ',' term } ')' ;
term        ::= ident | literal ;
query       ::= ident '(' qarg { ',' qarg } ')' ;
qarg        ::= expr | hole ;
hole        ::= '?' [ ident ] ;

The grammar is illustrative rather than massaged for a particular parsing algorithm; the provided parser resolves the usual details — a match arm’s => against an or-pattern’s |, and a struct literal in the head expression of an if, while, for, or match, where a { is read as the trailing block rather than the literal, so a struct literal at the top level of that head is parenthesized (if (Point { … }) { … }, if p == (Point { … }) { … }; one inside brackets or parentheses needs nothing). One keyword does double duty, resolved by lookahead: ref is both a prefix operator (ref e) and the binding keyword (ref x = e), and at the start of a block element ref ident = (or ref ident : type =) selects the binding sugar while any other continuation parses ref as the allocator. A hole ?x belongs to a query; a rule body names its logic variables directly, and a hole there is a parse error.