CODEWITHSUNDEEP
parsingyacc
neuromancer
neuromancer

Reputation: 55489

What is the conflict in this yacc parser?

I used the -v option in yacc to produce a y.output file. At the top of the file it says

State 98 conflicts: 1 shift/reduce

Further down in the file is the following:

state 98

   30 selection_stmt: IF '(' expression ')' statement .
   31               | IF '(' expression ')' statement . ELSE statement

    ELSE  shift, and go to state 101

    ELSE      [reduce using rule 30 (selection_stmt)]
    $default  reduce using rule 30 (selection_stmt)

What is the conflict, and how can it be fixed?

Upvotes: 0

Views: 244

Answers (3)

DigitalRoss
DigitalRoss

Reputation: 146073

Ahem, the correct answer to this problem is usually: do nothing.

Shift/reduce conflicts are expected with ambiguous grammars. They are not errors, they are conflicts.

The conflict will be resolved by preferring shift over reduce, which just happens to solve the canonical dangling else problem.

And bison even has an %expect n statement so that you don't get a S/R conflict warning when there are exactly n conflicts.

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 881423

Just about every shift/reduce error with if/then/else statement is the infamous dangling else problem.

With this code segment:

if (f1):
    if (f2):
        c1
    else:
        c2

you (and Python due to it's bizarre indentation rules) know which if the else belongs to, but a parser is not so clever.

It can't tell whether the else belongs to the first or second if.

This link shows how to convert the LR(n) to an LR(1) equivalent which should solve the problem.

Another alternative is to change your base language definition (if possible) so that the ambiguity disappears:

: IF '(' cond ')' THEN statement ENDIF
| IF '(' cond ')' THEN statement ELSE statement ENDIF

Upvotes: 1

user184968
user184968

Reputation:

Try something like this:

election_stmt: IF '(' expression ')' statement . selection_stmt_else_part;
selection_stmt_else_part: ELSE statement 
                        | 
                        ;

Upvotes: 0

Related Questions