Resolving Lua Grammar Ambiguities with Can-Match Callbacks

Hi Will,

The problem there is that both the "variable" and the second "variableOrExpression" alternation are capable of starting with "openParenthesis + expression + @closeParenthesis".  Parsing over an "expression" would be too much to do in a can-match.

If I had this grammar, I'd probably change it to something like:

variableOrExpression.Production =
  @openParenthesis + expression + @closeParenthesis + variableSuffix.ZeroOrMore()
  | @identifier + variableSuffix.ZeroOrMore();

I believe that handles all the scenarios in your original "variableOrExpression" and doesn't require a can-match.

Can-match callbacks are typically just going to match the bare minimum number of tokens to determine a path (an alternation option) to take for an alternation that has has ambiguities.  They replace the "first set" of tokens for a production and let you programmatically determine if a particular non-terminal can be matched.  You generally want to avoid them if possible though and try to find other ways like the options given in this reply to remove ambiguity.

Yes, can-match callbacks will consume tokens since you have direct access to the TokenReader.  So you must use Push()/Pop() around any changes to TokenReader.

For the second ambiguity, I'd do something like there where you split out the common "localKeyword" into a separate production:

localStatement.Production = @localKeyword + 
  (
    @functionKeyword + @identifier + functionBody
    | attributeIdentifierList + (assignment + expressionList).Optional()
  );

And call that from "statement" as a single alternation option in place of the two alternation options that begin with "localKeyword".

No can-match is needed there either then.

Thank you for the thorough and helpful response. It's good information to have that rewriting productions is the preferred technique over employing can-match callbacks. I'll add substituting and expanding terminals, and factoring out initial keywords into a separate production, as techniques in my ambiguity-resolving toolkit.

Unfortunately, I must ask you for further help resolving a specific case of ambiguity that fixing the variableOrExpression production revealed.

As can be seen in my initial post, the second and third alternation of the statement terminal start with variableList and functionCall, respectively.

The variableList terminal unsurprisingly looks like:

variableList.Production = variable + (@comma + variable).ZeroOrMore();

And this is the functionCall terminal:

functionCall.Production = variableOrExpression + identifierAndArguments.OneOrMore();

Both variableList and functionCall indirectly start with both @identifier + variableSuffix.ZeroOrMore() and @openParenthesis + expression + @closeParenthesis. The crux of the problem seems to be that variable and variableOrExpression are nearly identical except for the fact that variable has one or more variableSuffix instead of zero or more after the @openParenthesis + expression + @closeParenthesis, which is preventing me from recombining the productions around a common term like you showed me.

You could try "widening" the allowed syntax so that you have something like:

variableListOrFunctionCall.Production = variableOrExpression + (
  (@comma + variable).ZeroOrMore()
  | identifierAndArguments.OneOrMore()
);

Then in a custom tree construction node or OnComplete callback, you could report a syntax error if it ends up being an Expression at the start but the first child alternation is has match results.

Thanks for answering my follow-up question. I was able to successfully remove all the ambiguities from my grammar and start running the parser debugger on sample code. I appreciate your help.