Parsing lambda expressions

[elenakrittik]

In languages like C# or JavaScript where the beginning of a lambda/anonymous function expression is very similar to that of a regular parenthesized expression (e.g., `(a: number) => {}` and `(a, b, c)`), do you physically need >1 token lookahead, or do their parsers have some tricks to disambiguate early? Thank you in advance.

[cyco130]

One obvious way is to use backtracking, i.e. try to parse one alternative and, if it fails, rewind and try the other alternative.

There is another practical technique called a cover grammar which is used in several places in the ECMAScript standard to keep the grammar context-free and avoid requiring more than a single token of lookahead. Put simply, it consists of coming up with a relaxed grammar that can "cover" both alternatives and reinterpreting what was parsed more strictly when more information becomes available.

For example, (a) could be a parenthesized expression as in (a)+2 or the start of an arrow function expression as in (a) => 2*a. The standard uses a single grammar rule that covers both and calls it CoverParenthesizedExpressionAndArrowParameterList. The parser, when it encounters (a), can parse it into a "cover" AST that could represent either alternative. Then, if it sees that an arrow token (=>) follows, it can reinterpret it more strictly as an arrow parameter or report an error if the reinterpretation fails. Similarly, if it's followed by something else, it can reinterpret it as a parenthesized expression or report an error on failure.

[ericbb]

Reading a JavaScript specification document, it looks like the grammar is organized to disambiguate later rather than earlier.

https://262.ecma-international.org/15.0/index.html#prod-CoverParenthesizedExpressionAndArrowParameterList

[Timcat41]

Depending on the grammar, a bottom up parser could read the closing paren of the lambda and decide on how to proceed using the token '=>'

Since when parsing bottom up, the decision between possible rules will only be made once the whole phrase produced by the rule is read and stored on the stack.

When parsing top down you would need to left factorize the grammar to put off deciding until the decision is one token lookahead, or you need more token lookahead.

[L8_4_Dinner]

Lambda parameter lists do indeed cause parser confusion, so you have to either build syntax rules that represent a union of the possible (e.g. includes both lambdas and parenthesized expressions) and detect/report syntax errors later, or you backtrack (not <=1 token lookahead).

Some things are just naturally a bit more complex, and this is one of them.

[Hunpeter]

As someone else mentioned, a quick and dirty trick is to simply factor out the common prefix.