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

anton@mips.complang.tuwien.ac.at (Anton Ertl)
Mon, 10 Dec 2007 09:30:10 GMT

          From comp.compilers

Related articles
ANSI C grammar without shift-reduce conflict on 'ELSE' ggrares@yahoo.com (Rares GalaN) (2007-12-09)
Re: ANSI C grammar without shift-reduce conflict on 'ELSE' cbarron3@ix.netcom.com (2007-12-09)
Re: ANSI C grammar without shift-reduce conflict on 'ELSE' gah@ugcs.caltech.edu (glen herrmannsfeldt) (2007-12-09)
Re: ANSI C grammar without shift-reduce conflict on 'ELSE' anton@mips.complang.tuwien.ac.at (2007-12-10)
Re: ANSI C grammar without shift-reduce conflict on 'ELSE' anton@mips.complang.tuwien.ac.at (2007-12-10)
Re: ANSI C grammar without shift-reduce conflict on 'ELSE' monnier@iro.umontreal.ca (Stefan Monnier) (2007-12-12)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: Mon, 10 Dec 2007 09:30:10 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 07-12-021 07-12-024
Keywords: C, yacc

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/


Post a followup to this message

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