Grammar and parser

The authoritative grammar for what the parser accepts, plus a quick tour of the AST node table and the parser’s structure.

Grammar - EBNF

This grammar describes the token stream after preprocessing - file splices (include STRING ;) are expanded before the parser runs, so they don’t appear here. Library imports (use IDENT ;) and module imports (import STRING [ "as" IDENT ] ;) do reach the parser: use becomes an ImportStmt, import a ModuleImportStmt.

Terminals in CAPITALS are token classes from the lexer (see Lexer > Token types); quoted strings are keywords or punctuation that match the corresponding token’s lexeme.

program     = { useStmt | moduleImport | exported | methodDef | structDef | statement } EOF ;
exported    = "export" ( methodDef | structDef | constDefine ) ;
                                       (* `export` publishes a name from a
                                          module; it may only precede a
                                          `func`, `def struct`, or `def const`.
                                          Whether a program may contain
                                          `export` at all (module vs script)
                                          is decided at load time, not by the
                                          grammar. *)
useStmt     = "use" IDENT [ "as" IDENT ] ";" ;      (* library import; the
                                                       optional "as ALIAS"
                                                       renames the namespace
                                                       at the use site *)
moduleImport = "import" STRING [ "as" IDENT ] ";" ;  (* module import; the
                                                       STRING path must end
                                                       in ".j". Top-level
                                                       only - a module is a
                                                       declaration, so an
                                                       import inside a block
                                                       is a parse error *)
methodDef   = "func" IDENT "(" [ paramList ] ")" block ;
paramList   = param { "," param } ;
param       = IDENT "as" type ;
block       = "{" { statement } "}" ;

structDef   = "def" "struct" IDENT "{" structField { "," structField } [ "," ] "}" ";" ;
                                       (* top-level only;
                                          IDENT names the struct type;
                                          field names follow the IDENT
                                          rule too. Hoisted before the
                                          first top-level statement runs. *)
structField = IDENT "as" type ;

statement   = defineStmt
            | assignStmt
            | indexAssign
            | fieldAssign
            | appendStmt
            | returnStmt
            | ifStmt
            | whileStmt
            | forStmt
            | forEachStmt
            | tryStmt
            | throwStmt
            | exprStmt ;

tryStmt     = "try" block "catch" "(" IDENT ")" block ;
                                       (* IDENT is the catch
                                          binding, follows the
                                          iteration-variable name rule
                                          (letters only). No `finally`
                                          in v1. *)
throwStmt   = "throw" expr ";" ;
                                       (* expr may produce any
                                          value; convention is an
                                          `Error` struct. *)

returnStmt  = "return" [ expr ] ";" ;

constDefine = "def" "const" IDENT "as" type "init" expr ";" ; (* the const
                                          form of defineStmt - the only `def`
                                          an `export` may mark *)
defineStmt  = "def" [ "const" ] IDENT "as" type [ "init" expr ] ";" ;
                                       (* constants require "init" and an
                                          uppercase name matching
                                          [A-Z]+(_[A-Z]+)* (uppercase
                                          chunks joined by single `_`;
                                          no leading, trailing or
                                          consecutive `_`); variables may
                                          omit "init" and get zero-value,
                                          and use the letters-only IDENT
                                          form *)

assignStmt  = VARREF "=" expr ";" ;

indexAssign = VARREF lvalueTail { lvalueTail } "[" expr "]" "=" expr ";" ;
                                       (* l-value chain ending in `[index]`;
                                          root is a VARREF. Tail
                                          steps may freely mix `[index]`
                                          and `.field`. *)

fieldAssign = VARREF lvalueTail { lvalueTail } "." IDENT "=" expr ";" ;
                                       (* l-value chain ending in `.field`.
                                          Root is a VARREF; tail
                                          may mix `[index]` and `.field`. *)

lvalueTail  = "[" expr "]" | "." IDENT ;

appendStmt  = VARREF "[" "]" "=" expr ";" ;
                                       (* append sugar: write-only
                                          target meaning "the position
                                          just past the end of the
                                          list"; read use `e[]` is a
                                          parse error. Only one bare
                                          VARREF root - chained forms
                                          like `$xs[0][]` are not supported
                                          (yet). *)

ifStmt      = "if" "(" expr ")" block
              { "elseif" "(" expr ")" block }
              [ "else" block ] ;

whileStmt   = "while" "(" expr ")" block ;

forStmt     = "for" "(" [ defineStmt | assignStmt | ";" ]
                        [ expr ] ";"
                        [ assignNoSemi ]
                  ")" block ;
assignNoSemi = VARREF "=" expr ;       (* same shape as assignStmt without trailing ";" *)

forEachStmt = "for" "(" "def" IDENT "in" expr ")" block ;
                                       (* iterates list elements (in order)
                                          or map keys (insertion order);
                                          the iteration variable is a fresh
                                          binding in the body's scope *)

exprStmt    = expr ";" ;

type        = primType | listType | mapType | taskType | structType ;
primType    = "int" | "float" | "string" | "bool" | "null" | "bytes" ;
listType    = "list" "of" type ;
mapType     = "map" "of" type "to" type ;
taskType    = "task" "of" type ;       (* `task of T` - handle to
                                          a `spawn`ed computation. Same
                                          shape as `list of T`; recurses
                                          the same way (`task of list of
                                          int` is legal). *)
                                       (* recursive; nesting like
                                          `list of list of int` and
                                          `map of string to list of int`
                                          falls out naturally *)
structType  = IDENT [ "." IDENT ] ;    (* User-defined struct type (bare
                                          IDENT) or library-provided
                                          namespaced struct type
                                          (`IDENT.IDENT`). Resolved
                                          at runtime against the
                                          user-struct table or the
                                          NSStructs table respectively;
                                          unknown names are positioned
                                          errors. *)

expr        = orExpr ;
orExpr      = andExpr { "or" andExpr } ;
andExpr     = notExpr { "and" notExpr } ;
notExpr     = "not" notExpr | compExpr ;
compExpr    = addExpr { ("<" | ">" | "<=" | ">=" | "==") addExpr } ;
addExpr     = mulExpr { ("+" | "-") mulExpr } ;
mulExpr     = unaryExpr { ("*" | "/" | "//" | "%") unaryExpr } ;
unaryExpr   = "-" unaryExpr | primary ;
primary     = ( INT | FLOAT | STRING | "true" | "false" | "null"
              | VARREF | qualifiedCall | qualifiedConstRef
              | call | typeCall | structLit | constRef | "(" expr ")"
              | listLit | mapLit | lenExpr | spawnExpr )
              { "[" expr "]" | "." IDENT } ;
                                       (* any primary can be index- or
                                          field-chained, including the
                                          `.field` form *)
spawnExpr   = "spawn" block ;          (* launches the block as a
                                          goroutine and evaluates
                                          immediately to a `task of T`
                                          where T is the body's return
                                          type at the use site. Bare
                                          `return;` produces `task of
                                          null`. Value-semantics
                                          capture: every binding visible
                                          at the spawn site is
                                          deep-copied into a fresh frame
                                          at launch. *)
lenExpr     = "len" "(" expr ")" ;     (* polymorphic
                                          structural-length built-in
                                          (string / list / map /
                                          bytes). Reserved keyword,
                                          not a library function; the
                                          `core` library that once
                                          hosted it no longer exists. *)
structLit   = IDENT [ "." IDENT ] "{" structLitField { "," structLitField } [ "," ] "}" ;
                                       (* struct literal.
                                          Bare IDENT names a user-defined
                                          struct; `IDENT.IDENT` names a
                                          library-provided namespaced
                                          struct. The recogniser must
                                          decide before the constant-name
                                          check because struct names are
                                          PascalCase / camelCase, not
                                          uppercase.
                                          The `{` after IDENT in
                                          expression position is the
                                          tie-breaker against `constRef`;
                                          empty struct literals are
                                          rejected (every field required). *)
structLitField = IDENT ":" expr ;
call        = IDENT "(" [ expr { "," expr } ] ")" ;
qualifiedCall      = IDENT "." IDENT "(" [ expr { "," expr } ] ")" ;
qualifiedConstRef  = IDENT "." IDENT ;
                                       (* qualifiedCall / qualifiedConstRef:
                                          IDENT "." IDENT, then `(` decides which.
                                          Resolved against the namespaced-builtin
                                          / constant registry, gated by `use lib;`
                                          (or alias-aware equivalent). *)
typeCall    = ("int" | "float" | "string" | "bool") "(" [ expr { "," expr } ] ")" ;
                                       (* type keywords usable as calls only when
                                          immediately followed by `(`; resolved as
                                          convert-library builtins at runtime *)
constRef    = IDENT ;                  (* bare-IDENT: constant reference; the
                                          parser disambiguates `call` vs
                                          `qualifiedCall` vs `constRef` by
                                          peeking for "." / "(". *)
listLit     = "[" [ expr { "," expr } [ "," ] ] "]" ;
mapLit      = "{" [ expr ":" expr { "," expr ":" expr } [ "," ] ] "}" ;
                                       (* `{` is also a block opener; only
                                          legal as a map literal in
                                          expression position, where the
                                          parser is unambiguous *)

Semantic notes that aren’t expressed in the grammar:

• Two separate keywords: def introduces a binding (variable or constant); func introduces a method. There’s no longer any lookahead disambiguation in this area - the parser dispatches purely on the keyword.
• The name in defineStmt is a bare IDENT. Writing def $x as int produces a parse error with a hint to drop the $ (it’s reserved for use-site references).
• Operator precedence (lowest to highest): or, and, unary not, comparison < > <= >= ==, additive + -, multiplicative * / %, unary -. Binary operators are left-associative; not and unary - are right-associative (not not x and --x are both valid).
• and and or short-circuit: the right operand is not evaluated when the left already decides the result. Both operands must be bool.
• Unary not requires bool; unary - requires int or float.
• Comparison operators produce bool; if/while/for conditions must be bool (no implicit truthiness).
• Mixed int/float arithmetic promotes int to float; the result is float. % requires int operands. + on two string values concatenates.
• / (true division) always returns float (Python 3 semantics). For integer-result division use //: 5 / 2 = 2.5, 5 // 2 = 2. // on float operands returns the floor as a float (5.7 // 2.0 = 2.0). Line comments are # (not //), which leaves // free for the operator and lets a Jennifer file start with a shebang (#!/usr/bin/env -S jennifer run).
• Floats always display with a . so the type stays visible: 5.0 prints as "5.0", not "5". See interpreter.DisplayFloat.
• Methods may only be defined at the top level. Variable definitions, assignments, control flow, and expression statements may appear at the top level or inside a block.
• Each block ({...}) introduces a new lexical scope. A binding is visible from its def to the end of the enclosing block, and is inherited by inner blocks; inner scopes cannot redeclare a name already visible.
• for opens a private scope for its init, cond, step, and body so the init variable does not leak out of the loop.
• There is no required entry point. Top-level statements execute in source order. Methods are hoisted (collected before any top-level statement runs) so they can be called regardless of textual order.
• Method bodies inherit the global scope as their outer scope, so top-level variables are visible inside methods (subject to the no-shadowing rule).
• Method parameters use bare IDENT (no $), same as variable definitions. Writing func f($x as int) errors with “parameter name has no $”.
• Call sites type-check arguments against the declared parameter types at runtime; both arity and per-argument kind are checked.
• Method return values are dynamically typed - methods don’t declare a return type, and callers receive whatever value the body returns (or null for a bare return; or a body that falls off the end).
• A bare IDENT in expression position is parsed as a CallExpr if immediately followed by (, otherwise as a ConstRefExpr. At runtime the latter must resolve to a constant in scope; a name that resolves to a variable produces a helpful error (“use $name”).
• Lists are array-backed sequences, not Lisp-style linked lists: def xs as list of int init [1, 2, 3]. Element access is $xs[i], 0-indexed, in-bounds-checked. Out-of-bounds reads and writes are positioned runtime errors.
• Maps preserve insertion order: iteration via for (def k in $m) visits keys in the order they were first inserted; updating an existing key does not move it; appending a new key extends. Reads of missing keys are runtime errors - use has($m, key) to test.
• Lists and maps are value-typed: $ys = $xs; copies, function parameters bind by copy, and const is deep (constness extends to every nested element). Aliasing is impossible; mutations through $xs[i] = ... only affect that binding.
• Index assignment ($xs[i][j] = ...) walks the chain on a copy of the root binding’s value, applies the write, and stores the result back via env.Assign. The const-target check fires once against the root binding; deep constness falls out of the value-semantics invariant.
• Iteration (for (def x in $coll)) opens a fresh scope per iteration. The loop variable is bound to each element (list) or key (map). The collection is evaluated once at loop entry; concurrent mutation of the original binding during iteration doesn’t affect the walk because the iterator works against a snapshot.
• { is overloaded: it opens a block in statement position and a map literal in expression position. The parser disambiguates by context; the formatter (which doesn’t run the parser) tracks the classification through a small stack so both forms get the right indentation and spacing.

Parser (internal/parser)

Recursive descent with precedence climbing for binary operators. The grammar the parser implements is the EBNF above.

The exported entry points (Parse, ParseTokens) return a raw *Program without running the scope-analysis pass. Callers that intend to execute the program must invoke parser.Resolve(prog) themselves (Interpreter.Run does this automatically). Splitting the two lets grammar tests focus on parse trees without wiring up scope context for every fragment; see scope analysis below.

AST nodes

Every node embeds a pos{File, Line, Col} for error reporting and exposes it via Node.Pos() (line/col) and Node.Filename() (file path). The file is populated from the originating token so cross-file diagnostics work.

Sprint(node) produces a stable textual representation used by tests.

Scope analysis

internal/parser/resolver.go is a post-parse pass that walks the AST and fills in the slot fields (Depth, Slot, NumSlots, Program.NumGlobals, Block.NumSlots, etc.). It also promotes two classes of error from first-execution runtime errors to positioned parse-time diagnostics:

• Undefined variables - Resolve walks its own scope stack in parallel with the AST and reports any VarExpr / AssignStmt whose name isn’t in scope.
• Shadowing - a def (variable or constant) whose name is already visible in an enclosing scope. Same rule the runtime’s name-based Define used to enforce; now caught earlier.

The resolver is idempotent: running twice on the same AST produces the same annotations. Interpreter.Run calls it before any structural check; EvalInteractive (REPL) does not (each REPL turn lacks the accumulated global context that would let resolution succeed). The runtime handles the resolver-less path by leaving all slot fields at the -1 sentinel and using name-based Environment methods.

Scope-frame model. The resolver tracks scopes as a stack. Each frame carries a name -> slot map and a count allocator. A frame is isRoot=true at the boundaries where the runtime chain jumps directly to globals (the globals frame itself, and a method’s callFrame). Reference lookup walks innermost-out, respects those root boundaries, and terminates at globals.

Three scope-shape carve-outs where the resolver deliberately deviates from “one AST scope = one runtime frame” to stay aligned with the interpreter:

• try body runs in the enclosing env at runtime; the resolver walks its stmts inline in the current scope rather than pushing a fresh frame.
• For-header init lands in forEnv (a frame the resolver pushes for the header), body lands in a nested body-frame (pushed by resolveBlock).
• Spawn body is skipped entirely. The runtime’s two-frame spawn snapshot doesn’t line up with a static single-frame view of the enclosing scope, so references inside a spawn body stay at (Depth=-1, Slot=-1) and the interpreter falls back to name-based lookup at runtime.

Method-call pre-resolution. The resolver also pre-fills CallExpr.Method whenever the callee names a hoisted top-level user method. The interpreter’s evalCall consults the pointer first and skips the i.methods hash lookup on every recursive call. Builtins keep Method = nil because the namespaced / global registries need the runtime use-activation check.

Namespaced-call pre-resolution. For QualifiedCallExpr.Fn and QualifiedConstRefExpr.Const the pre-fill happens on the interpreter side, not in the parser resolver, because the namespace / import tables don’t exist until processImports has run. Interpreter.resolveQualifiedRefs is a second pass invoked from Interpreter.Run after processImports that walks the same AST and stamps the exact Builtin / Value a call would otherwise look up.

Constant folding. internal/parser/fold.go runs from inside Resolve as a post-step on BinaryExpr / UnaryExpr. When both operands are literal (checked transitively through their own Folded fields via asLit), the operator is applied at parse time and the result stamped on Folded as a fresh literal node. Chains collapse in a single pass - ((1+2)*3)+4 folds to IntLit(11). Operations that would error at runtime (division by zero, negative shift count, unknown op) leave Folded nil so the runtime hits the error at its actual source position.

See interpreter.md > Environment for the runtime side.