3
\$\begingroup\$

I'm creating a small simple scripting language for fun and as a learning exercise. For the first iteration I want it to be very simple:

  • C-style syntax
  • Functions are defined globally as in C, no passing functions around (yet)
  • The interpreter calls the "main" function (if it finds one)
  • String and number datatypes, no objects or arrays

I have written a syntax (with help from this syntax for C) and a simple recursive descent parser. However while testing I discovered a few undesirable quirks; the parser works perfectly but some problems with the syntax itself are causing undesirable behaviour in the actual language. Therefore I thought it would be good to post the syntax here for review and to see if there are any other obvious issues

// program/script structure
program         : decl_list
decl_list       : decl_list decl
                | decl
decl            : var_decl
                | func_decl
var_decl        : 'let' identifier ';'
                | 'let' identifier '=' exp ';'
func_decl       : 'func' identifier '(' arguments_decl ')' block
                | 'func' identifier '(' ')' block
arguments_decl  : arguments_decl ',' identifier
                | identifier

// statements and flow control
block           : '{' statement_list '}'
statement_list  : statement_list statement
                | statement
statement       : if_construct
                | while_construct
                | var_decl
                | assign_stat
                | exp_stat
assign_stat     : identifier '=' exp ';' // TODO: more assignment operators (+=, -=, etc)
exp_stat        : exp ';'
if_construct    : if_block elif_list else_block
                | if_block else_block
                | if_block
if_block        : 'if' '(' exp ')' block
elif_list       : elif_list elif_block
                | elif_block
elif_block      : 'else' if_block
else_block      : 'else' block
while_construct : 'while' '(' exp ')' block
continue_stat   : 'continue' ';'
break_stat      : 'break' ';'
return_stat     : 'return' exp ';'
                | 'return' ';'


// expressions
exp             : cond_exp

// ternary expression
cond_exp        : logic_or_exp '?' cond_exp ':' cond_exp

// bitwise and logical binary operators
logic_or_exp    : logic_or_exp '||' logic_xor_exp
                | logic_xor_exp
logic_xor_exp   : logic_xor_exp '^^' logic_and_exp
                | logic_and_exp
logic_and_exp   : logic_and_exp '&&' bit_or_exp
                | bit_or_exp
bit_or_exp      : bit_or_exp '|' bit_xor_exp
                | bit_xor_exp
bit_xor_exp     : bit_xor_exp '^' bit_and_exp
                | bit_and_exp
bit_and_exp     : bit_and_exp '&' cmp_exp
                | cmp_exp

// comparison operators
cmp_exp         : cmp_exp '==' add_exp
                | cmp_exp '!=' add_exp
                | cmp_exp '<'  add_exp
                | cmp_exp '>'  add_exp
                | cmp_exp '<=' add_exp
                | cmp_exp '>=' add_exp
                | add_exp

// arithmetic binary operators
add_exp         : add_exp '+' mul_exp
                | add_exp '-' mul_exp
                | mul_exp
mul_exp         : mul_exp '*' pow_exp
                | mul_exp '/' pow_exp
                | mul_exp '//' pow_exp
                | pow_exp
pow_exp         : pow_exp '**' shift_exp
                | shift_exp
shift_exp:      : shift_exp '>>' unary_exp
                | shift_exp '<<' unary_exp
                | unary_exp

// unary operators
unary_exp:      : '+' unary_exp
                | '-' unary_exp
                | '!' unary_exp
                | '~' unary_exp
                | postfix_exp

// other expression types
postfix_exp     : postfix_exp '[' exp ']'           // array access operator
                | postfix_exp '(' arguments_list ')' // call operator
                | postfix_exp '(' ')'               // call (no arguments)
                | postfix_exp '.' identifier        // property access operator
                | primary_exp
primary_exp     : '(' exp ')'
                | literal_number
                | literal_string
                | identifier
arguments_list  : arguments_list ',' exp
                | exp

// omitted for simplicity
literal_number  : ...
literal_string  : ...
identifier      : ...

Example: In the previous iteration of this syntax, I had defined the "+" and "-" binary expressions separately like this:

add_exp         : add_exp '+' sub_exp
                | sub_exp
sub_exp         : sub_exp '-' mul_exp
                | mul_exp
mul_exp         ...

This causes '-' to always precede '+', this is the kind of mistake I want to avoid!

\$\endgroup\$

closed as off-topic by Peilonrayz, 200_success Jan 23 '18 at 17:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Peilonrayz, 200_success
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ What language is this grammar description in? Some generic BNF? Or does this serve as input to a parser generator tool? \$\endgroup\$ – 200_success Jan 19 '18 at 2:56
  • \$\begingroup\$ I wrote this grammar myself just as a reference while working on the interpreter, as I wrote the parser myself by hand, not using yacc/antlr or any generators. So it might be using the wrong symbols or not be a recognisable structure, for which I can only apologise and hope the meaning is still clear \$\endgroup\$ – JamesMac Jan 19 '18 at 12:10
  • \$\begingroup\$ This question is being discussed on meta \$\endgroup\$ – Mast Jan 19 '18 at 20:48
3
\$\begingroup\$

I cannot address your main concern about the undesirable behavior, and I am afraid nobody can: only you know what behavior is desirable. You may provide (failing) test cases, but that would jeopardize on-topikness of the question.

Some random observation on the grammar follow:

  • You disallow an empty statement_list, but you treat var_decl as a statement. It means that

    while (foo) {
    }
    

    is invalid, but

    while (foo) {
        let bar;
    }
    

    is valid.

    Does not make much sense for me.

  • The function argument list cannot be empty. Is it intentional?

  • I strongly recommend to factor the operators out. For example,

    cmp_exp    : cmp_exp cmp_op add_exp
               | add_exp
    

    and spell cmp_op in a separate rule.

  • It seems that cond_exp rule is incomplete. I'd expect

    cond_exp        : logic_or_exp '?' cond_exp ':' cond_exp
                    | logic_or_exp
    

    Besides, I have a feeling that the cond_exp ':' cond_exp part is extremely hard to parse meaningfully. The grammar you refer to

        conditional_exp     : logical_or_exp
                            | logical_or_exp '?' exp ':' conditional_exp
                            ;
    

    segregates exp and conditional_exp for a reason.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the great comments! The point about empty statement lists is good so I will fix that by allowing an empty block (as that's the only place statement_list is used. Thanks for the point on operators as well I might do that just to make my own life easier :) \$\endgroup\$ – JamesMac Jan 19 '18 at 12:15
  • \$\begingroup\$ Function argument list can be empty unless I am making a mistake? there is a rule for func_decl to define a function with no arguments, and there is a rule for postfix_exp to call something without any arguments \$\endgroup\$ – JamesMac Jan 19 '18 at 12:17
  • \$\begingroup\$ The cond_exp rule was wrong as well thanks, I'm not sure how that happened, perhaps I deleted a line by mistake when posting the question, because it's fine in my project! Parsing "cond_exp : cond_exp" hasn't been a problem at all for me, I have tested it very carefully; I can post the code that does this although i'm sure it's nothing special \$\endgroup\$ – JamesMac Jan 19 '18 at 12:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.