Re: ANSI C grammar without shift-reduce conflict on 'ELSE'

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>Rares GalaN wrote:
>
>> I'm trying to use the ANSI C Grammar from
>> http://www.lysator.liu.se/c/ANSI-C-grammar-y.html and I'm getting a
>> "shift - reduce on ELSE" error. I'm quite new with this, so it would
>> really be useful if I could get a grammar that's conflict free. Any
>> suggestions will help.
>
>The C grammar is not conflict free. I thought shift-reduce was
>a warning in yacc.
>
>-- glen
>[It is indeed a warning, but it also warns you that the generated
>parser doesn't quite parse the input grammar. -John]


It may or may not be a parser for the input grammar (that's why it is
a warning). In the case of the dangling else the input grammar is
ambiguous, and the resulting parser is correct; in this cases
resolving the conflict just resolved the ambiguity.


In other cases the conflict resolution may cut away parses that are
not covered in a different way, and then the parser is incorrect.
That's why it's a good idea to either transform the grammar until the
conflict goes away, or check that the conflict resolution is harmless;
the former is probably more obvious to other readers and easier to
maintain.


For the dangling else problem an appropriately transformed grammar is
this:


                S: Matched
                  | Unmatched
                  ;
    Matched: if E then Matched else Matched
                  | Other_S
                  ;
Unmatched: if E then S
                  | if E then Matched else Unmatched
                  ;


A nice explanation of this construction can be found at
<http://marvin.cs.uidaho.edu/~heckendo/CS445F07/danglingElse.html>.


BTW, isn't this a FAQ?


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.