Why is this grammar conflicts?

Question

It is compiled with Lemon, which is a LALR(1) parser generator :

program ::= statement.

statement ::= ifstatement Newline.
statement ::= returnstatement Newline.

ifstatement ::= If Number A statement B.
ifstatement ::= If Number A statement B Newline Else A statement B.

returnstatement ::= Return Number.

The error message is :

user@/tmp > lemon test.lm
test.lm:6: This rule can not be reduced.

1 parsing conflicts.

The debug output is :

State 0:
          program ::= * statement
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                       program accept
                     statement shift  13
                   ifstatement shift  12
               returnstatement shift  11

State 1:
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          ifstatement ::= If Number A statement B Newline Else A * statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                     statement shift  4
                   ifstatement shift  12
               returnstatement shift  11

State 2:
          statement ::= * ifstatement Newline
          statement ::= * returnstatement Newline
          ifstatement ::= * If Number A statement B
          ifstatement ::= If Number A * statement B
          ifstatement ::= * If Number A statement B Newline Else A statement B
          ifstatement ::= If Number A * statement B Newline Else A statement B
          returnstatement ::= * Return Number

                            If shift  10
                        Return shift  3
                     statement shift  8
                   ifstatement shift  12
               returnstatement shift  11

State 3:
          returnstatement ::= Return * Number

                        Number shift  14

State 4:
          ifstatement ::= If Number A statement B Newline Else A statement * B

                             B shift  15

State 5:
          ifstatement ::= If Number A statement B Newline Else * A statement B

                             A shift  1

State 6:
          ifstatement ::= If Number A statement B Newline * Else A statement B

                          Else shift  5

State 7:
      (3) ifstatement ::= If Number A statement B *
          ifstatement ::= If Number A statement B * Newline Else A statement B

                       Newline shift  6
                       Newline reduce 3   ** Parsing conflict **

State 8:
          ifstatement ::= If Number A statement * B
          ifstatement ::= If Number A statement * B Newline Else A statement B

                             B shift  7

State 9:
          ifstatement ::= If Number * A statement B
          ifstatement ::= If Number * A statement B Newline Else A statement B

                             A shift  2

State 10:
          ifstatement ::= If * Number A statement B
          ifstatement ::= If * Number A statement B Newline Else A statement B

                        Number shift  9

State 11:
          statement ::= returnstatement * Newline

                       Newline shift  16

State 12:
          statement ::= ifstatement * Newline

                       Newline shift  17

State 13:
      (0) program ::= statement *

                             $ reduce 0

State 14:
      (5) returnstatement ::= Return Number *

                     {default} reduce 5

State 15:
      (4) ifstatement ::= If Number A statement B Newline Else A statement B *

                     {default} reduce 4

State 16:
      (2) statement ::= returnstatement Newline *

                     {default} reduce 2

State 17:
      (1) statement ::= ifstatement Newline *

                     {default} reduce 1

----------------------------------------------------
Symbols:
    0: $:
    1: Newline
    2: If
    3: Number
    4: A
    5: B
    6: Else
    7: Return
    8: error:
    9: program: If Return
   10: statement: If Return
   11: ifstatement: If
   12: returnstatement: Return

Answer 1

Take a look at state 7 from debug output. It describes the case when parser already accepted the next set of tokens:

    ifstatement ::= If Number A statement B *

Here are two options that the parser can choose from when Newline token comes in this case:

1. Remember it and switch to State 6. This shift is prescribed by the next rule from your grammar:

   ifstatement ::= If Number A statement B Newline Else A statement B.
   

2. Consider current rule as completed and return to rule of upper level. This reduce is prescribed by this rule from your grammar:

   ifstatement ::= If Number A statement B.
   

LALR(1) parser has no other option as to fail in this case due to the fact that it can't take a look ahead for next tokens in the stream. It can't predict Else coming after Newline.

Revise you grammar to avoid this conflicting situation. I can only add that new line characters are commonly not included to the language grammar. Tokenizer usually consider them as token boundary similarly to other white space characters.