sphinx_grammar.bnf

(* 
    Syntactic Grammer Definition
    
    Notation is homebrew BNF (see bnf.sublime_syntax for highlighting).
    
    I plan to implement a recursive descent parser, so care needs to be taken to avoid any left recursion in the grammar.
*)

(*** Type Annotations ***)

type_expression ::= (* TODO *) ;



(*** Expressions ***)

(* 
    This expression production is left recursive, and as such, the actual recursive descent parser implementation differs somewhat (see the bottom of this file)
*)
expression ::= primary
             | anon_function
             | if_expression
             | block_expression
             | UNARY_OP expression
             | expression BINARY_OP expression
             | assignment_expression
             | declaration_expression
             | decorator_expression
             | function_def
             | class_def
             | object_constructor
             | tuple_constructor ;

expression_list ::= expression ( "," expression )* ;

(*** Primary expressions ***)

atom ::= LITERAL | IDENTIFIER | "self" | "super" | group ;

primary ::= atom ( access_item )* ; 
access_item ::= member_access | index_access | invocation | object_constructor ;
index_access ::= "[" expression "]" ;
member_access ::= "." IDENTIFIER ;

group ::= "(" expression ( ":" type_expression )? ")" ; (* can be type annotated *)

(*** if/block Expressions ***)

if_expression ::= "if" expression "then" statement_list ( "elif" expression "then" statement_list )* ( "else" statement_list )? "end" ;
block_expression ::= ( label )? "begin" ( statement )* ( control_flow )? "end" ;  (* break can be supplied a value inside of begin_blocks *)

(*** Assignment ***)

(* 
    The "var" keyword creates the variable in current scope, otherwise the global scope is searched for an 
    existing variable if cannot be not found locally. If it still can't be found, then the assignment is an error.
    
    Assignment statements support sequence destructuring, assignment expressions do not.
*)

(* right associative *)
lvalue ::= IDENTIFIER | primary index_access | primary member_access ;

lvalue_expression ::= lvalue | lvalue_list | "(" lvalue_expression ")" ;   (* lvalues, tuples of lvalues, and grouped lvalues *)
lvalue_list ::= lvalue_expression ( "," lvalue_expression )* ;

lvalue_annotated ::= lvalue ( ":" type_expression )? ;
lvalue_expr_annotated ::= lvalue_expression ( ":" type_expression )? ; 


assignment_op ::= "=" | "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "|=" | "^=" | "<<=" | ">>=" ;
assignment_expression ::= ( "nonlocal" )? ( lvalue_annotated assignment_op | lvalue_expr_annotated "=" ) expression ;

declaration_expression ::= ( "let" | "var" ) lvalue_expr_annotated "=" expression ;

decorator_expression ::= "@" expression ( assignment_expression | declaration_expression ) ;


(*** Function/Method Calls ***)

invocation ::= "(" ")" | "(" expression_list ( "..." )? ")" ; 

(*** Constructors ***)

object_constructor ::= "{" member_initializer ( "," member_initializer )* "}" ;
member_initializer ::= ( IDENTIFIER | "[" primary "]" ) ( ":" type_expression )? "=" expression ;


(* syntax for tuple_constructor has special casing for single_element tuples and the empty tuple *)
tuple_constructor ::= expression_list | "(" expression "," ")" | "(" ")" ;



(*** Statements ***)

statement ::= ";"
            | loop
            | while_loop
            | for_loop 
            | expression ;

statement_list ::= ( statement )* ( control_flow )? ;  (* control flow only allowed at end of block, much like Lua *)
control_flow ::= "continue" ( label )? | "break" ( label )? ( expression )? | "return" ( expression )? ;

loop ::= ( label )? "loop" statement_list "end" ;

while_loop ::=  ( label )? "while" expression "do" statement_list "end" ;

for_loop ::= ( label )? "for" lvalue_list "in" expression "end" ;

label ::= "::" LABELNAME ;


(*** Function Defs ***)

function_def ::= "fun" lvalue parameter_list ( "->" type_expression ":" )?  statement_list "end" ;
anon_function ::= "fun" parameter_list ( "->" type_expression ":" )?  statement_list "end" ;

parameter_list ::= "(" ")" ;

parameter_list ::= "(" ")" 
                 | "(" variadic_parameter ")"
                 | "(" ( positional_params )? ( default_params )? ( "," variadic_parameter )? ")" ;

required_params ::= parameter ( "," parameter )* ;
default_params ::= default_parameter ( "," default_parameter )* ;

parameter ::= ( "var" )? IDENTIFIER ( ":" type_expression )? ;
default_parameter ::= parameter ( "=" expression ) ;

variadic_parameter ::= ( "var" )? IDENTIFIER "..." ( ":" type_expression )? ;


(*** Class Defs ***)

class_def ::= (* TODO *) ;




(***** Non left_recursive version of `expression` for implementation *****)

(* Single_element tuple literals are not allowed. Use a built_in constructor function to create single element tuples *)
tuple_constructor ::= expression ( "," expression )+ | "(" ")" ;

primary_expression ::= immediate_expression | primary | tuple_constructor | "(" expression ")" ;

(* These expressions can all be identified by their first symbol *)
immediate_expression ::= class_def
                       | function_def
                       | if_expression
                       | object_constructor ;

unary_expression ::= UNARY_OP unary_expression | primary_expression ;

(*
    Operator precendence in order from strong to weak binding
    (left associative unless otherwise specified)
     
     1:  (unary -) (unary +) (unary ~) not          (right associative)
     2:  **  ( right associative)
     3:  * / %
     4:  + - 
     5:  << >>
     6:  & 
     7:  ^  
     8:  | 
     9:  < > <= >=
    10:  == !=
    11:  and 
    12:  or

*)

operand[1] ::= unary_expression ;
operand[N] ::= operand[N-1] ( OPERATOR[N] operand[N-1] )* ;
binary_op ::= operand[10] ;

(* top_level tuples don't require parens - however, single element tuples are not allowed here, use tuple_constructor instead *)
naked_tuple ::= binary_op ( "," binary_op )*;

assignment ::= naked_tuple | assignment_expression | declaration_expression ;

expression ::= assignment (* top level of recursive descent *)