Re: if then else shift/reduce Syndrome

Tarn Burton <tarnwb@holly.colostate.edu> wrote:
>Does anyone know how to get rid of the bison shift/reduce conflict in
>the C if then else.


    This is known as the `dangling else problem'. But it should be called the
`dangling if problem', for it is the `if' that is left to dangle.


    The best thing to do is to design the language without the problem. E.g.
the use the comb syntax of Algol'68, Ada, Euclid, etc.


    Most people don't get rid of the conflict. Since Yacc and friends
resolve the conflict in favour of the shift, the usual grammar `works'
even though it is ambiguous.


    Aho Sethi and Ullman show one way to do it (Sec 4.3).


    Here is my solution. Is it tidy? That's a matter of taste.
Start with a simple but ambiguous grammar.
Stmt : IF Exp Stmt ELSE Stmt
| IF Exp Stmt
| WHILE Exp Stmt
| '{' Block '}'
| Assignment
;


    The problem is that before the ELSE we only want to allow a subclass
of statements such that a following ELSE should not belong to them.
E.g. `IF a x:=1' is a statement, but if an ELSE follows it, then
`IF a THEN b' should not be treated as a statement. Thus `IF a x:=1'
is not in the class. We can define this subclass as
{x in [Stmt] | (for all y in [Stmt] :: (x ELSE y) not in [Stmt])}
(where [Stmt] stands for the {x in Terminals* | Stmt =>* x}). We call this
subclass of statements `Matched' and we change the grammar to:
Stmt : IF Exp Matched ELSE Stmt
| IF Exp Stmt
| WHILE Exp Stmt
| '{' Block '}'
| Assignment
;
Note that [Stmt] does not change. Now we need productions for `Matched'
-- the set of all statements such that a following ELSE should not
be a part of them.
Matched : IF Exp Matched ELSE Matched
| WHILE Exp Matched
| '{' Block '}'
| Assignment
;
Note the special treatment of WHILE. In a bigger language, we would have
to do the same for all statements that end with statements. In C, this
includes FOR and (perhaps surprisingly) SWITCH.


    Finally, the duplication of productions for statements that do not end with
statements is unfortunate, so we factor them as follows.
Stmt : IF Exp Matched ELSE Stmt
| IF Exp Stmt
| WHILE Exp Stmt
| Others
;
Matched : IF Exp Matched ELSE Matched
| WHILE Exp Matched
| Others
;
Others : '{' Block '}'
| Assignment
;


    The duplication of productions for statements that do end in statements
(WHILE in the example language) is unfortunate, but I see no way around it.


Theodore Norvell
Memorial University
--

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