Allowing `}` as a statement terminator in an expression-based language?

Question

My language is expression based; many of its language constructs are not statements, but rather expressions that return a value. However, since everything is an expression, my grammar looks like

code  := stmt*
stmt  := expr ';'
expr  := var | loop | if | ... | literal | ident | block
block := '{' code '}'
if    := 'if' expr block ('else' (block | if))?

which leads to code with standalone constructs like if in their own statements, or at the end of statements:

let x = if condition { 1 } else { -1 };
if foo {};
if bar {} else {};
if woo {} else if daar {};
if baz {} else if quuz {} else {};

which have a nasty }; at the end.

How can I modify my grammar so that I can eliminate }; and use } as a statement ender?

Answer 1

As I understand the question, the intent is that whenever an expression statement ends in a '}', the terminating ';' can be omitted, even with statements like

{ let x = 2*if cond { foobar(); 42; } else { 666; }
  foo();
}

As can be seen, using ';' as a terminator in an expression language "clashes"; it might be worth considering whether the value yielded by a block should be followed by ';' as in my example. (I noticed that it was omitted from the examples in the question, which would be a syntax error with the provided grammar.)

Perhaps it is better to use ';' as a separator, and let it be optional, except in cases where two adjacent expressions would be parsed as one expression. (Using line breaks as separation hints might also be a good idea.) This way:

{ let x = 2*if cond {42} else {666}
  foo()
}

would not need any (assuming that a function call cannot follow at that point), but

{ let x = 2*if cond {42} else {666}
  *p = foo()
}

would be parsed as a multiplication by p unless the prefix '*' was separated from the preceding expression by ';'.

Designing this in a formal grammar would be easier than making a grammar that distinguishes expressions that end in '}' from ones that don't. However, in a hand-written recursive descent parser it would not be too hard to hack the expression parser function to provide information on whether its last symbol was a '}'. Just add a bool curlycue flag to the CST nodes for expressions, and then inspect it in the stmt parse function:

CST stmt() {
    ExprCST ex = expr();
    if(!ex->curlycue) expect(';');
    return new StmtCST(ex);
}

All parse functions for subexpressions just need to check for curlycue and propagate it up in the parse tree, for example:

ExprCST mult_expr() {
    ExprCST left_operand = cast_expr();
    while(sym() == '*' || sym() == '/' || sym() == '%') {
        int op = sym(); nextsym();
        ExprCST right_operand = cast_expr();
        left_operand = new BinaryExprCST(op, left_operand, right_operand);
        left_operand->curlycue = right_operand->curlycue;
    }
    return left_operand;
}

Alternatively, a special expect_semi parser function could be used (assuming sym() gives the current token as an int, nextsym() advances to the next token, you'll also need a prevsym() that un-gets the current token):

void expect_semi() {
    prevsym(); // un-gets the last token of a preceding expression.
    if(sym() == '}') { nextsym(); } // skip it, but do nothing further
    else { nextsym(); //skip whatever else it may have been
        if(sym() == ';') { nextsym(); } // but require a semicolon now.
        else { syntax_error("semicolon expected"); }
    }
}

Note however, that this will still not solve the issue with separating two expressions that could be parsed as one, when the second begins with an unary operator that is also an infix operator. I'd not recommend doing this. The only reason to have it seems to be a desire to mimic the absence of ';' after compound-statements in C, which I actually always have thought was a bit strange. In Algol (and descendants like Pascal), ';' is a separator and is not omitted after the end keyword of blocks and compound-statements.

Answer 2

You could do something like this:

stmt := expr ';' | block | if

This way, a block counts as a statement on it's own and doesn't need the ; like a expression would have.

Answer 3

I have the same issue in my language, and I've decided to take the Go solution and just add implicit semicolons during lexing.

The issue with implicit semicolons is that it forces a certain programming style at the compilation level. I'm working on a very opionated language, so this is fine for me.

Edit: one style quirk is that in Go

if (x)
{
}

This style isn't allowed since a semicolon is inserted after the ) after the condition. Thus, you must keep the opening brace on the same same.

if (x) {
}

Answer 4

My own language does this, and it disambiguates between if statements and if expressions:

code    := stmt*
stmt    := expr ';' | if_stmt | block
expr    := var | loop | if_expr | ... | literal | ident | block
block   := '{' code '}'
if_stmt := 'if' expr block ('else' (block | if))?
if_expr := if_stmt

Yes, that grammar seems redundant, but it adds an extra state that can then be used to differentiate the cases.

Basically, the parser knows when it parsing an if that is a standalone statement versus an expression and expects the semicolon only in the latter case.

Answer 5

This is one the things easier to resolve manually than implementing a grammar.

Something like this ought to work:

stmt          := expr_no_block ';' | expr_block
expr_no_block := var_no_block | literal | ident
expr_block    := if | block | loop | var_block
expr_any      := expr_no_block | expr_block
block         := '{' (stmt* expr_any)? '}'
if            := 'if' expr_any block ('else' (block | if))?

This also allows you to elide the final ; in a block. If you don't want that then block := '{' stmt* '}' is sufficient.