reduce-reduce, shift-reduce conflicts in a grammar

Question

expression -> expression OPER expression
expression -> PREFIX expression
expression -> expression POSTFIX
expression -> expression ‘?’ expression ‘:’ expression
expression -> expression ‘[’ expression ‘]’
expression -> expression ‘(’ expression ‘)’
expression -> ID
expression -> CONSTANT
expression ->‘(’ expression ‘)’

Which are the reduce-reduce and shift-reduce conflicts in this grammar during analysis by LR parser?

Answer 1

There is no reduce-reduce conflict in that excerpt, but there are certainly shift-reduce conflicts all over the place. All of them have the same cause: the grammar makes no attempt to define the precedence of the various operators, with the result that any expression with more than one operator is ambiguous.

For example, PREFIX ID POSTFIX could be parsed as though written (PREFIX ID) POSTFIX or as PREFIX (ID POSTFIX). This clearly creates a shift-reduce conflict after the ID is reduced to expression:

Stack: PREFIX expression
Lookahead: POSTFIX

At this point, the parser could reduce the stack to expression using expression -> PREFIX expression. But it could also shift POStFIX from the input onto the stack, in preparation for the reduction expression -> expression POSTFIX.

The same ambiguity will be find with every other operator.

Answer 2

Reduce-reduce means that it has reached a state that, in front of a language symbol, it can reduce two different rules, leading to two different syntax trees representing your sentence. As the next symbol is valid in both scenarios, and being a one symbol ahead parser, this means that your grammar is ambiguous, and you need to provide more information (like precedence rules, or similar) in order to make the parser to take one reduction or the other.

You can receive this error from a yacc type grammar compiler, or a shift-reduce which means, again, ambiguity in your grammar. While there's no solution but changing the way your grammar is defined, or to switch to a grammar based on operator precedence to solve this problems, in both cases we are looking at some kind of ambiguity that leads to two different syntax trees describibin your language sentence.

In your case, the rule

expression : expression OPER expression

Is full of ambiguities, as you cannot guess if:

3 + 5 + 8

will result in a parse tree:

   /--- <3>         expression : CONSTANT
<+>                 expression : expression OPER expression
   \       /--- <5> expression : CONSTANT
    \--- <+>        expression : expression OPER
           \--- <8> expression : CONSTANT

or

           /--- <3> expression : CONSTANT
    /--- <+>        expression : expression OPER expression
   /       \--- <5> expression : CONSTANT
<+>                 expression : expression OPER expression
   \--- <8>         expression : CONSTANT

the first indicating that the expression is parsed as (in full parenthesized notation) (3 + (5 + 8)), and the second meaning your parser has interpreted ((3 + 5) + 8).