EBNF and Extended Notations

BNF (Backus-Naur Form) is sufficient to describe any context-free grammar, but common patterns — optional elements, repetition, grouping — require verbose workarounds. EBNF (Extended BNF) adds shorthand for these patterns, and Alpaca's .Option and .List operators map directly to EBNF concepts.

BNF vs EBNF

BNF uses only: non-terminals, terminals, alternatives (|), and concatenation. To express "zero or more Xs" you write explicit recursion:

XList → ε
XList → XList X

EBNF adds three shorthands:

EBNF is purely syntactic sugar — it generates the same language as the equivalent BNF, just with less boilerplate.

Alpaca's EBNF Operators

Alpaca provides two EBNF operators that work on both Rule[R] and terminals:

.List — Zero or More

Rule.List(binding) matches zero or more occurrences and returns a List[R]. The macro generates two synthetic productions (see Desugaring to Plain BNF below for the exact expansion).

In Alpaca:

val root: Rule[BrainAST] = rule:
  case Operation.List(stmts) => BrainAST.Root(stmts)
  // stmts: List[BrainAST]

This is equivalent to the EBNF notation root → {Operation}.

.Option — Zero or One

Rule.Option(binding) matches zero or one occurrence and returns an Option[R]. The macro generates similar synthetic productions (see Desugaring to Plain BNF below).

In Alpaca:

val root = rule:
  case (Num(n), Num.Option(maybeNum)) =>
    (n, maybeNum)   // maybeNum: Option[Int]

This is equivalent to the EBNF notation root → Num [Num].

Desugaring to Plain BNF

Every use of .List and .Option desugars to plain BNF productions at compile time. The macro generates synthetic non-terminals with fresh names.

For the BrainFuck parser:

-- Source Alpaca:
root → Operation.List

-- Desugared BNF:
root         → OperationList
OperationList → ε
OperationList → OperationList Operation

For nested EBNF:

-- Source Alpaca:
While → jumpForward Operation.List jumpBack

-- Desugared BNF:
While         → jumpForward OperationList jumpBack
OperationList → ε
OperationList → OperationList Operation

In practice, the macro generates a fresh synthetic non-terminal (with a randomized name) for each .List occurrence. The OperationList name above is schematic — the actual generated names are internal.

When to Use EBNF vs Explicit Recursion

Use .List for unseparated sequences — elements that follow each other with no delimiter:

// Good: BrainFuck operations have no separators
case Operation.List(stmts) => BrainAST.Root(stmts)

Use explicit recursion for separator-delimited sequences (comma-separated lists, semicolon-separated statements):

// Good: JSON members are separated by commas
val ObjectMembers: Rule[List[(String, Any)]] = rule(
  { case ObjectMember(member) => scala.List(member) },
  { case (ObjectMembers(members), JsonLexer.`,`(_), ObjectMember(member)) =>
      members :+ member },
)

.List does not support separators yet — it produces a bare List → ε | List X recursion. For delimiter-separated lists, explicit rules give you control over where the separator appears.

EBNF in the BrainFuck Grammar

The BrainFuck parser uses .List in three places:

All three expand to the same kind of synthetic list recursion over Operation.

Cross-links

• See Context-Free Grammars for the formal BNF notation.
• See Parser for the .List and .Option API reference.
• See Extractors for how to pattern-match on .List and .Option results.