Shift/reduce LALR(1) conflict due to parentheses

Question

I'm currently writing a Visual Basic-like LALR(1) grammar, and face this particular shift/reduce conflict which I have no idea how to solve it properly.

The problematic parts of the grammar are (Please see EDIT 1 and EDIT 2 for clarification):

Expression
    : IndexExpression
    | /* other expressions */

IndexExpression
    : MemberExpression
    | MemberExpression '(' ArgumentList ')'

MemberExpression
    : ParenthesizedExpression
    | Identifier

ParenthesizedExpression
    : '(' Expression ')'

ArgumentList
    : Expression
    | Expression ',' ArgumentList
    | ',' ArgumentList

And the shift/reduce conflict is this:

State 109
  237 ParenthesizedExpression: '(' Expression ')' .
    $default    reduce using rule 237 (ParenthesizedExpression)

...
State 295

  231 IndexExpression: MemberExpression '(' . ArgumentList ')'
  237 ParenthesizedExpression: '(' . Expression ')'
    ...
    Expression    go to state 352

...
State 352
  182 ArgumentList: Expression .
  183             | Expression . ',' ArgumentList
  237 ParenthesizedExpression: '(' Expression . ')'
    ...
    ')'    shift, and go to state 109

    ')'    [reduce using rule 182 (ArgumentList)]

In other words, the parser is unsure when facing an expression wrapped by parentheses, whether it is an ArgumentList with a single expression or a ParenthesizedExpression.

Is there any way to fix this conflict, while maintaining the grammar to be LALR(1)?

Thank you.

EDIT 1:

/* other expressions */ in Expression is actually not an empty expression, I just wrote it in such a way for brevity. In actuality it has other alternative expressions:

Expression
    : IndexExpression
    | Expression '+' Expression
    | ...

EDIT 2:

Here are additional parts of the grammar which @rici points out might be problematic (particularly the 1st right-hand rule of Statement):

Statement
    : MemberExpression ArgumentList
    | MemberExpression '=' Expression
    | MemberExpression '(' ArgumentList ')' '=' Expression
    | ...

You need to show more of your grammar. Or, even better, create a reall compilable grammar with the same problem but only a few productions. By the way, that argument_list syntax is very odd. Why do you find it useful to write it with left-recursion, which should generally be avoided in LALR(1) parsers? And what do multiple missing arguments mean? And if all the other arguments can be omitted, why can't the last one be? — rici
Do you allow the VB syntax where functions which take one argument can be called without parentheses? If so, that is likely your problem. — rici
@rici missing arguments: in this particular VB dialect, it allows for an argument list to have empty argument(s), except the very last one. Since I don't really want for an Expression to be empty, I ended up placing that 3rd rule on ArgumentList. one argument w/o parentheses: yes! In fact after diving deeper trying to find the root cause yesterday, I came to a conclusion that this might be the cause. Do you have any suggestion on how to include this syntax? — Sam Tatasurya
It's really hard to make suggestions about grammars when you can only see a little part of the grammar. This is a general statement about helping other people with problems; if you just dole out little pieces of information, it is much harder to help you because we have to spend our time trying to deduce or guess the parts of the problem you're not explaining. The best way to ask questions is to make a minimal reproducible example, which is also a good way to start to solve problems yourself because it focuses on what is actually essential (rather than what you think might be interesting). — rici
I dont' see any obvious path to the conflict from the little excerpts you've provided, but it could be that you have another statement type which starts with an expression. By the way, I don't think it's good style to bloat your grammar with productions like ParenthesizedExpression: '(' Expression ')'. That's the grammar equivalent of Redundant Comment Syndrome( ++count; /* Increase the count by 1 */) — rici

kdhp kdhp · Accepted Answer · 2017-02-23T00:41:09

The errors are because Expression is allowed to be empty, because of the commented rule /* other expressions */, and is assumed to not be empty.

The following shows where the use of Expression results in two equivalent rules:

ArgumentList
    : Expression
    | Expression ',' ArgumentList /* degenerates into "',' ArgumentList" */
    | ',' ArgumentList
    ;

The number of shift/reduce conflicts are the number of times ArgumentList is referenced is used (once in IndexExpression and twice in ArgumentList itself)

To remove the conflicts either fix ArgumentList for the case of an empty Expression:

ArgumentList
    : Expression
    | ArgumentList ',' Expression
    ;

Or ensure that Expression is never empty (delete the commented rule).

Shift/reduce LALR(1) conflict due to parentheses

1 Answers