[SOLVED] Discriminating between a Lambda Parameter List and a Grouping Expression in a Recursive Descent Parser

Discriminating between a Lambda Parameter List and a Grouping Expression in a Recursive Descent Parser

I am writing a small scripting language for a project I am working on. I wrote a simple recursive-descent parser for it (similar to the one in the Crafting Interpreters). I wanted to add support for lambda (anonymous function) expressions and give them the following syntax:

let some_func = (param1, param2 = 1) {
    return param1 + param2
}

How can I differentiate between the lambda's parameter list and a grouping (parenthesised) expression like the following one, for example:

let some_expr = (var1 = 0) // Assignment is allowed as an expression.

let some_func = (param1, param2 = 0) {
    return param1 + param2
}

Solution

Lambda syntax like this (i.e. lambda syntax that starts directly with the parameter list instead of some keyword or symbol that denotes a lambda) is not LL(k) meaning you can't parse it with a finite amount of lookahead.

In other words you can't just switch on the current token as you could for an LL(1) grammar nor can you use an if condition of the form tokens.lookAhead(0).kind == X && tokens.lookAhead(1).kind == Y && ... && tokens.lookAhead(k).kind == Z as you could for an LL(k) grammar.

Instead, your options are to either use infinite lookahead to see whether there's a { after the ) or to use backtracking, i.e. to try to parse a lambda and if that parse fails, to continue on with the next precedence level (with the ( still being the current token).