CODEWITHSUNDEEP
grammarbisonyacclalr
Sam Tatasurya
Sam Tatasurya

Reputation: 223

Shift/reduce LALR(1) conflict due to parentheses

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
    | ...

Upvotes: 0

Views: 611

Answers (1)

kdhp
kdhp

Reputation: 2116

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).

Upvotes: 2

Related Questions