search

mewmew / uc

A compiler for the µC language.
58 stars 5 forks source link

parser: Dangling else #31

Closed mewmew closed 8 years ago

mewmew commented 8 years ago

The dangling else problem is the cannonical example of a shift reduce conflict for LR grammars.

It is present in the µC grammar:

1 LR-1 conflicts: 
    S271
        symbol: else
            Shift(277)
            Reduce(32:ElsePart : empty  <<  >>)

To solve this specific ambiguity, we've decided to use the automatic conflict resolution of Gocc, which always shifts when encountering a shift-reduce conflict, as is the expected resolution for C language grammars.

Below follows an extract from the Gocc user guide on this topic.

When automatic LR(1) conflict resolution is selected by the -a option, gocc resolves this conflict in the same way as specified in the C language specification: by shifting and parsing the longest valid production (maximal-munch). This means recognising the else-statement as part of the second if.

mewmew commented 8 years ago

Automatic LR(1) conflict resolution (the -a flag) is already used in the parser generation rule of the Makefile. Closing this issue for now.

sangisos commented 8 years ago

Update: In commit 4076a343917f80c98014416282801fbc605a5d73 this was changed to be solved in grammar for greater understanding, consistency, and less dependency on one specific parser generator.

With help from the dragon book and Parsifal Software's Resolving the General Dangling Else/If-Else Ambiguity, the dangling else shift reduce conflict was solved according to the C99 spec. draft n1256 ¶6.8.4.1.3:

An else is associated with the lexically nearest preceding if that is allowed by the syntax.

The production rule for the while-statement was the culprit as the statement Non-terminal could loop back to the wrong type of matched or open statement causing a shift-reduce conflict.