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
             | decorator_expression
             | function_def
             | class_def
             | table_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 | table_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 ***)

lvalue_primary ::= IDENTIFIER | primary index_access | primary member_access ;
assign_modifier ::= "let" | "var" | "local" | "nonlocal" ;

(* There are three principal types of lvalues: primary lvalues, tuples of lvalues, and grouped lvalues *)

(* these productions are set up so that modifiers only appear either at toplevel, or inside parens *)
assign_target ::= assign_modifier? lvalue_inner ;
lvalue_inner ::= lvalue_item | lvalue_list ;
lvalue_item ::= lvalue_primary | "(" assign_target ")" ;
lvalue_list ::= lvalue_item ( "," lvalue_item )* ( "..." )? ;

(* lvalue_annotated ::= ... ( ":" type_expression )? ; TODO work out type annotations later *)

assignment_op ::= "=" | "+=" | "-=" | "*=" | "/=" | "%=" | "&=" | "|=" | "^=" | "<<=" | ">>=" ;
assignment_expression ::= assign_target assignment_op expression ;

decorator_expression ::= "@" expression assignment_expression ;



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

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



(*** Constructors ***)

table_constructor ::= "{" member_initializer ( "," member_initializer )* "}" ;
member_initializer ::= ( ( "let" | "var" )? IDENTIFIER | "[" expression "]" ) ( ":" 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" pattern 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
                       | table_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 ;

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