Bison dangling else

2
votes

I have the following rule in my grammar:

block:                  TLBRACE statements TRBRACE
                        | TLBRACE TRBRACE
                        ;


statements:             statement 
                        | statements statement 
                        ;

statement:              TIF TLPAREN expression TRPAREN TTHEN statement
                        | TIF TLPAREN expression TRPAREN TTHEN statement TELSE statement
                        | TWHILE TLPAREN expression TRPAREN statement 
                        | TDO statement TLPAREN expression TRPAREN 
                        | TFOR TLPAREN forinits TSEMICOLON expression TSEMICOLON expressions TRPAREN statement 
                        | block 
                        | declaration TSEMICOLON
                        | expression TSEMICOLON
                        ;

I'm aware of the dangling else problem. That's why I specified "%left TELSE" at the top of the grammar file. Anyway, even if I instructed Bison to give precedence to TELSE token a shift/reduce conflict is generated. I tried also to remove the "%left TELSE" command (just to see if it makes any difference) and nothing changes. I always have the same shift/reduce conflict.

The output I get with the --verbose flag to Bison is:

State 117

   32 statement: "if" "(" expression ")" "then" statement .  ["identifier", "string value", "double", "int", "lint", "message", "string", "double value", "int value", "(", "{", "}", "-", "do", "else", "for", "if", "while", "binary not"]
   33          | "if" "(" expression ")" "then" statement . "else" statement

    "else"  shift and going to state 122

    "else"    [reducing with rule 32 (statement)]
    $default  reducing with rule 32 (statement)
3
if-statementcompiler-constructiongrammarbison
shift/reduce is a warning, not an error. - stark
I expect not to have a shift/reduce conflic if I specify "%left TELSE". Nowhere is written that something is an error. - Salvatore
What's the production rule that uses statement? It looks like you may be using token "else" twice in your grammar. - Josh
I edit the question to answer. - Salvatore

3 Answers

2
votes

I got rid of the conflict when declaring %left TTHEN. I can't give you a full explanation but operator precedence has something to do with comparing operators after one and another.

1
votes

The best way for solve this problem using %nonassoc.

%nonassoc THEN

%nonassoc ELSE

%%


statement:              TIF TLPAREN expression TRPAREN TTHEN statement %prec THEN

                        | TIF TLPAREN expression TRPAREN TTHEN statement TELSE statement


%%

Here, the parser pushes the tokens into the stack, and when IF expressions are pushed, and the next token is ELSE, there will be a conflict.

The parser should reduce the IF expressions according to if_statement rule, or it should shift the next ELSE token into the stack. You have to determine the priorities of your rules, in this case you have to give the ELSE token more priority than if_statement by using %nonassoc and %prec. In the %nonassoc priority of ELSE is more than THEN, and by using %prec priority of if_statment is less than the if_else_statment and the conflict is resolved.

0
votes

This is a frequently asked question. Have a look at Reforming the grammar to remove shift reduce conflict in if-then-else which explains how the conflict resolution works.