grammar.ebnf

(* @taxonomy: spec/grammar *)
(* SPDX-License-Identifier: MPL-2.0 *)
(* Copyright (c) 2026 Jonathan D.A. Jewell (hyperpolymath) <j.d.a.jewell@open.ac.uk> *)
(* Error-Lang Grammar - EBNF Specification *)
(* A Turing-complete teaching language with intentional error injection *)

(* ============================================ *)
(* PROGRAM STRUCTURE                           *)
(* ============================================ *)

program = { declaration } ;

declaration = function_decl
            | struct_decl
            | main_block
            | statement ;

main_block = "main" , block ;

block = { statement } , "end" ;

(* ============================================ *)
(* DECLARATIONS                                *)
(* ============================================ *)

function_decl = "function" , IDENTIFIER , "(" , [ param_list ] , ")" ,
                [ ":" , type_expr ] , block ;

param_list = param , { "," , param } ;

param = IDENTIFIER , [ ":" , type_expr ] ;

struct_decl = "struct" , IDENTIFIER ,
              { IDENTIFIER , ":" , type_expr } , "end" ;

type_expr = "Int" | "Float" | "String" | "Bool" | "Array" , "<" , type_expr , ">"
          | IDENTIFIER ;

(* ============================================ *)
(* STATEMENTS                                  *)
(* ============================================ *)

statement = let_stmt
          | assign_stmt
          | if_stmt
          | while_stmt
          | for_stmt
          | return_stmt
          | break_stmt
          | continue_stmt
          | print_stmt
          | gutter_block
          | expression_stmt ;

let_stmt = "let" , [ "mutable" ] , IDENTIFIER , [ ":" , type_expr ] , "=" , expression ;

assign_stmt = IDENTIFIER , [ "[" , expression , "]" ] , "=" , expression ;

if_stmt = "if" , expression , block ,
          { "elseif" , expression , block } ,
          [ "else" , block ] ;

while_stmt = "while" , expression , block ;

for_stmt = "for" , IDENTIFIER , "in" , expression , block ;

return_stmt = "return" , [ expression ] ;

break_stmt = "break" ;

continue_stmt = "continue" ;

print_stmt = ( "print" | "println" ) , "(" , [ expression_list ] , ")" ;

expression_stmt = expression ;

(* ============================================ *)
(* GUTTER - ERROR INJECTION ZONE               *)
(* ============================================ *)

(* The gutter block is intentionally loosely defined.
   During parsing, errors WILL be injected here.
   Parser must recover and continue after 'end'. *)

gutter_block = "gutter" , { any_token } , "end" ;

any_token = (* any valid or invalid token - parser recovers *) ;

(* ============================================ *)
(* EXPRESSIONS                                 *)
(* ============================================ *)

expression_list = expression , { "," , expression } ;

expression = ternary ;

ternary = logical_or , [ "?" , expression , ":" , expression ] ;

logical_or = logical_and , { "or" , logical_and } ;

logical_and = equality , { "and" , equality } ;

equality = comparison , { ( "==" | "!=" ) , comparison } ;

comparison = bitwise_or , { ( "<" | ">" | "<=" | ">=" ) , bitwise_or } ;

bitwise_or = bitwise_xor , { "|" , bitwise_xor } ;

bitwise_xor = bitwise_and , { "^" , bitwise_and } ;

bitwise_and = shift , { "&" , shift } ;

shift = term , { ( "<<" | ">>" ) , term } ;

term = factor , { ( "+" | "-" ) , factor } ;

factor = unary , { ( "*" | "/" | "%" ) , unary } ;

unary = ( "-" | "not" | "~" ) , unary
      | postfix ;

postfix = primary , { call | index | member } ;

call = "(" , [ expression_list ] , ")" ;

index = "[" , expression , "]" ;

member = "." , IDENTIFIER ;

primary = INTEGER
        | FLOAT
        | STRING
        | BOOL
        | "nil"
        | IDENTIFIER
        | array_literal
        | lambda_expr
        | "(" , expression , ")" ;

array_literal = "[" , [ expression_list ] , "]" ;

lambda_expr = "fn" , "(" , [ param_list ] , ")" , "->" , expression
            | "fn" , "(" , [ param_list ] , ")" , block ;

(* ============================================ *)
(* LEXICAL TOKENS                              *)
(* ============================================ *)

IDENTIFIER = LETTER , { LETTER | DIGIT | "_" } ;

INTEGER = [ "-" ] , DIGIT , { DIGIT }
        | "0x" , HEX_DIGIT , { HEX_DIGIT }
        | "0b" , BIN_DIGIT , { BIN_DIGIT } ;

FLOAT = [ "-" ] , DIGIT , { DIGIT } , "." , DIGIT , { DIGIT } , [ exponent ] ;

exponent = ( "e" | "E" ) , [ "+" | "-" ] , DIGIT , { DIGIT } ;

STRING = '"' , { string_char } , '"'
       | '"""' , { multiline_char } , '"""' ;

string_char = PRINTABLE - '"' - "\\"
            | escape_seq ;

multiline_char = PRINTABLE | NEWLINE ;

escape_seq = "\\" , ( "n" | "r" | "t" | "\\" | '"' | "0" | "x" , HEX_DIGIT , HEX_DIGIT ) ;

BOOL = "true" | "false" ;

COMMENT = "#" , { PRINTABLE } , NEWLINE ;

(* ============================================ *)
(* CHARACTER CLASSES                           *)
(* ============================================ *)

LETTER = "A".."Z" | "a".."z" | "_" ;

DIGIT = "0".."9" ;

HEX_DIGIT = DIGIT | "A".."F" | "a".."f" ;

BIN_DIGIT = "0" | "1" ;

PRINTABLE = (* any Unicode printable character *) ;

NEWLINE = "\n" | "\r\n" ;

WHITESPACE = " " | "\t" | NEWLINE ;

(* ============================================ *)
(* KEYWORDS (Reserved)                         *)
(* ============================================ *)

(*
The following identifiers are reserved keywords:

Control Flow:
  if, elseif, else, while, for, in, break, continue, return

Declarations:
  let, mutable, function, struct, main, end

Operators:
  and, or, not

Literals:
  true, false, nil

Types:
  Int, Float, String, Bool, Array

Special:
  gutter, fn

Built-in Functions:
  print, println, len, push, pop, type, str, int, float
*)

(* ============================================ *)
(* OPERATOR PRECEDENCE (lowest to highest)     *)
(* ============================================ *)

(*
1.  ? :     (ternary, right-associative)
2.  or      (logical or)
3.  and     (logical and)
4.  == !=   (equality)
5.  < > <= >= (comparison)
6.  |       (bitwise or)
7.  ^       (bitwise xor)
8.  &       (bitwise and)
9.  << >>   (shift)
10. + -     (additive)
11. * / %   (multiplicative)
12. - not ~ (unary, right-associative)
13. () [] . (postfix: call, index, member)
*)

(* ============================================ *)
(* TURING COMPLETENESS PROOF                   *)
(* ============================================ *)

(* Error-Lang is Turing complete because it provides:

1. UNBOUNDED STORAGE
   - Mutable variables (let mutable)
   - Arrays with dynamic length
   - Recursive data structures via structs

2. CONDITIONAL BRANCHING
   - if/elseif/else statements
   - Ternary expressions
   - Boolean operators (and, or, not)

3. ITERATION/RECURSION
   - while loops
   - for loops
   - Recursive function calls

4. ARBITRARY COMPUTATION
   - Integer and float arithmetic
   - Bitwise operations
   - First-class functions (lambdas)

Example: Universal Turing Machine simulation is possible
by encoding tape as an array and transition function
as a lookup table or switch/if chain.

Note: Turing completeness is probabilistic due to error
injection. On runs where critical code falls in a gutter
block, the program may not complete correctly. This is
intentional and part of the teaching methodology.
*)

(* ============================================ *)
(* EXAMPLE PROGRAMS                            *)
(* ============================================ *)

(*
Example 1: Hello World
------------------------
main
    println("Hello, Error-Lang!")
end


Example 2: Fibonacci (recursive)
---------------------------------
function fib(n: Int): Int
    if n <= 1
        return n
    end
    return fib(n - 1) + fib(n - 2)
end

main
    println("Fibonacci of 10: ", fib(10))
end


Example 3: With Gutter (error zone)
------------------------------------
main
    let x = 42

    gutter
        # Something will break here on some runs
        let y = "unterminated
        let z = @#$%
    end

    # This still executes!
    println("x = ", x)
end


Example 4: Lambda and Higher-Order
-----------------------------------
function map(arr, f)
    let mutable result = []
    for item in arr
        push(result, f(item))
    end
    return result
end

main
    let numbers = [1, 2, 3, 4, 5]
    let squared = map(numbers, fn(x) -> x * x)
    println(squared)  # [1, 4, 9, 16, 25]
end
*)