Reforming the grammar to remove shift reduce conflict in if-then-else

Question

How do I remove shift-reduce conflict for bison for the given grammar?

 selection-stmt -> if ( expression ) statement |
                      if ( expression ) statement else statement

A solution giving the modified grammar would be highly appreciated.

Pomerania

For future individuals, this page helped me through a similar issue. Also, pass in switches --debug and --verbose to bison and look at the generated files. Not all the information is printed to standard out. – Monochromatic

Answer 1

There is a much simpler solution. If you know how LR parsers work, then you know that the conflict happens here:

if ( expression ) statement * else statement

where the star marks the current position of the cursor. The question the parser must answer is "should I shift, or should I reduce". Usually, you want to bind the else to the closest if, which means you want to shift the else token now. Reducing now would mean that you want the else to wait to be bound to an "older" if.

Now you want to "tell" your parser generator that "when there is a shift/reduce conflict between the token "else" and the rule "stm -> if ( exp ) stm", then the token must win". To do so, "give a name" to the precedence of your rule (e.g., "then"), and specify that "then" has less precedence than "else". Something like:

// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

using Bison syntax.

I'm uneasy with the %nonassoc here, because it really says that "then" and "else" are non associative, which is true in most grammars, but I only meant to give them precedence levels, not associativity. Bison provides %precedence to this end:

// Precedences go increasing, so "then" < "else".
%precedence "then"
%precedence "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

Actually, my favorite answer is even to give "then" and "else" the same precedence. When the precedences are equal, to break the tie between the token that wants to be shifted, and the rule that wants to be reduced, Bison/Yacc will look at associativity. Here, you want to promote right-associativity so to speak (more exactly, you want to promote "shift"), so:

%right "then" "else" // Same precedence, but "shift" wins.

will suffice.

According to Bison manual (3.8.1), "Neither solution is perfect however."

Redhot

How can I do the same if there is a non-terminal N after statement as follows: IF_KEYWORD '(' expression N ')' M statement N ELSE_KEYWORD M statement Here, M and N are non-terminal symbols. – Bareilly

@VishwasJain It all depends on your if-then rule. If the "else" M part is optional, then the same approach should apply. – Redhot

Problem Solved! – Rotorua

Answer 2

You need to recognize the fact that the middle statement in the if-else case cannot be (or end with) a dangling if (an if with no else.) The easiest way to do that is to split the stmt rule in two:

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if ->
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if |
    ...other statements not ending with dangling if...
stmt-ending-with-dangling-if ->
    if ( expression ) stmt |
    if ( expression ) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if |
    ...other statements ending with dangling if...

Any other stmt -> whatever rule where whatever doesn't end with a stmt goes in the stmt-not-ending-with-if rule, while any stmt rule that DOES end in stmt get split in two versions; an not-ending-with-if version in the not-ending-with-if rule and a dangling-if version in the dangling-if rule.

edit

A more complete grammar with other productions:

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if :
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if |
    WHILE '(' expr ')' stmt-not-ending-with-dangling-if |
    DO stmt WHILE '(' expr ')' ';' |
    expr ';' |
    '{' stmt-list '}'
stmt-ending-with-dangling-if:
    IF '(' expr ')' stmt |
    IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if |
    WHILE '(' expr ')' stmt-ending-with-dangling-if

Rules like WHILE (expr) stmt get split in two (as they end with stmt), while rules like expr; do not.

Rigmarole

Can you please elaborate on the ...other statements....i have no other productions with selection-stmt, but i am still getting an error saying using useless nonterminals This is what i did: selection-stmt : open | closed ; open : IF LFT_BRKT expression RGT_BRKT statement | IF LFT_BRKT expression RGT_BRKT closed ELSE open ; closed : IF LFT_BRKT expression RGT_BRKT closed ELSE closed ; – Pomerania

#12720719 The complete grammar is here – Pomerania

you need to rid of all the xxx-stmt intermediate non-terminals, combining all the stmt rules into a single group, and then split them into dangling/non-dangling if versions. – Rigmarole

what is this stmt that you are using. And also where did the DO come from? Kindly look at the grammar in the link and post the answer. Thanks – Pomerania

@AakashAnuj: stmt here replaces statement in you grammar. Delete all the rules that end in -stmt in your grammar, and replace your statement rule with the stmt rule above. You can delete the DO rule if you don't want it and add ';' | return expression ';' | return ';'. – Rigmarole

Answer 3

make if else higher level than normal statements, like:

statements:
  statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
  if ( statement )
;
IfElse:
  IfStat else statement
;

Redshank

I don't think this could fix the issue. – Leucocytosis