Should we avoid mixing left-recursive and right-recursive grammar productions?

[gibson042]

I haven't checked the syntactic grammar, but our lexical(-ish) grammars seem to freely mix left- and right-recursion, sometimes in the same section.

Left-recursive

• IdentifierName
• NumericLiteral sub-productions (DecimalDigits, BinaryDigits, OctalDigits, HexDigits, LegacyOctalIntegerLiteral, NonOctalDecimalIntegerLiteral, LegacyOctalLikeDecimalIntegerLiteral)
• RegularExpressionLiteral sub-productions (RegularExpressionChars, RegularExpressionClassChars, RegularExpressionFlags)
• Regular Expression Pattern sub-productions (except UnicodePropertyValueCharacters)

Right-recursive

• SingleLineCommentChars
• StringLiteral sub-productions (DoubleStringCharacters and SingleStringCharacters)
• TemplateCharacters
• StrWhiteSpace
• UnicodePropertyValueCharacters

This is fine in a strict sense, but seems to add unnecessary friction—for comprehension, and likely also for implementation. I'd like to take a stance and ideally enforce it programatically, first for the above and then possibly also for syntactic grammars (keeping in mind potential interaction with [empty] and also production-ordering disambiguation, at least until the latter is resolved by e.g. #1727 and #2445).

That said, I'd like to know if spec consumers have reason to prefer one convention over the other.

[devsnek]

The left-recursive ones definitely read more intuitively to me, especially when I think about writing a parser. But I imagine this is somewhat subjective.

[jmdyck]

In the lexical-ish grammars, I think it would be almost trivial to change the currently right-recursive productions to left-recursive. The alternative, changing the left-recursive productions to right-recursive, would be not nearly as easy.

I haven't checked the syntactic grammar,

In the syntactic grammar, there are some right-recursive productions:

MemberExpression : `new` MemberExpression
NewExpression : `new` NewExpression
UnaryExpression : `delete|...` UnaryExpression
ExponentiationExpression : UpdateExpression `**` ExponentiationExpression
AssignmentExpression : LeftHandSideExpression `=|...` AssignmentExpression
WithEntries : AttributeKey `:` StringLiteral `,` WithEntries

but the majority of the recursive productions are left-recursive. (That's just looking at immediate recursion; there's also some indirect/hidden recursion.)

I think WithEntries could be made left-recursive fairly easily, but not the others.

[gibson042]

In the lexical-ish grammars, I think it would be almost trivial to change the currently right-recursive productions to left-recursive. The alternative, changing the left-recursive productions to right-recursive, would be not nearly as easy.

Perhaps not as easy, but not exactly difficult:

• IdentifierName → IdentifierStart IdentifierCharacters_opt
• IdentifierCharacters → IdentifierPart IdentifierCharacters_opt
• DecimalDigits_[Sep] → DecimalDigit DecimalDigits_{[?Sep] opt} | _[+Sep] DecimalDigit NumericLiteralSeparator DecimalDigits_[+Sep]
• RegularExpressionBody → RegularExpressionFirstChar RegularExpressionChars_opt
• RegularExpressionChars → RegularExpressionChar RegularExpressionChar_opt
• etc.

But this isn't really about specification effort, more about helping spec consumers.

In the syntactic grammar, there are some right-recursive productions:

MemberExpression : `new` MemberExpression
NewExpression : `new` NewExpression
UnaryExpression : `delete|...` UnaryExpression
ExponentiationExpression : UpdateExpression `**` ExponentiationExpression
AssignmentExpression : LeftHandSideExpression `=|...` AssignmentExpression
WithEntries : AttributeKey `:` StringLiteral `,` WithEntries

but the majority of the recursive productions are left-recursive. (That's just looking at immediate recursion; there's also some indirect/hidden recursion.)

I think WithEntries could be made left-recursive fairly easily, but not the others.

That is at least minor support for left-recursion, and probably more than that just to minimize churn, at least in the syntactic grammar (although certainly possible to overcome if there is a clear preference in the other direction).

[jmdyck]

Perhaps not as easy, but not exactly difficult:

Sorry, I was unclear: I was thinking about the difficulty of not just creating right-recursive productions, but also making collateral changes (e.g., rewriting the associated SDO rules).

[gibson042]

I was also factoring that in—there'd be some churn, but AFAICT nothing particularly intricate.

[gibson042]

This was discussed in today's editor call, and there was suspicion that some SDOs naturally favor one approach vs. the other and might do so in the opposite direction (e.g., MV avoids having a scale parameter by NumericLiteral sub-productions being left-recursive). But it seems worth trying out normalization, to left-recursive forms and with a limitation to lexical(-ish) grammars (as opposed to the syntactic grammar where correlated concerns such as associativity affect the relative benefits of mixed recursion).