Bison Shift/Reduce conflicts for small language parser

Question

My objective is to create a parser for a small language. It is currently giving me one shift/reduce error.

My CFG is ambiguous somewhere, but I can't figure out where

prog:    PROGRAM beg                   {$$ = "program" $2;}
    |   PROGRAM stmt beg               {$$ = "program" $2 $3;}

beg:    BEG stmt END                   {$$ = "begin" $2 "end";}
    | BEG END                      {$$ = "begin" "end";}


stmt:   beg             {$$ = $1;}
    | if_stmt                   {$$ = $1;}/*
    | IF expr THEN stmt                 {$$ = $1 $2 $3 $4;}*/
    | WHILE expr beg                    {$$ = "while" $2 $3;}
    | VAR COLEQUALS arithexpr SEMI      {$$ = $1 ":=" $3 ";";}
    | VAR COLON INTEGER SEMI            {$$ = $1 ":" "integer" ";";} /*Declaring an integer */
    | VAR COLON REAL SEMI               {$$ $1 ":" "real" ";";}   /*declaring a real */

if_stmt:  IF expr THEN stmt            {$$ = "if" $2 "then" $4;}
    | IF expr THEN stmt ELSE stmt      {$$ = "if" $2 "then" $4 "else" $6;}

expr:   NOT VAR                        {$$ = "!" $2;}
| VAR GREATERTHAN arithexpr        {$$ = $1 ">" $3;}
    | VAR LESSTHAN arithexpr           {$$ = $1 "<" $3;}
    | VAR GREATERTHANEQUALTO arithexpr {$$ = $1 ">=" $3;}
    | VAR LESSTHANEQUALTO arithexpr    {$$ = $1 "<=" $3;}
    | VAR EQUALS arithexpr             {$$ = $1 "==" $3;}
    | VAR NOTEQUALS arithexpr          {$$ = $1 "!=" $3;}
    | arithexpr AND arithexpr          {$$ = $1 "&&" $3;}
    | arithexpr OR arithexpr           {$$ = $1 "||" $3;}


arithexpr:  arithexpr PLUS term            {$$ = $1 + $3;}
    |  arithexpr MINUS term            {$$ = $1 - $3;}
    |   term                   {$$ = $1;}

term:   term TIMES factor          {$$ = $1 * $3;}
    | term DIVIDE factor           {$$ = $1 / $3;}
    | factor               {$$ = $1;}

factor:   VAL                              {$$ = $1;}

Answer 1

The "error" comes from the ambiguity in the if_stmt's else part: stmt can be an if_stmt, and it's not clear to which if a else-part belongs, e.g. if you write:

if y1 then if y2 then x=1 else x=2

Then the else-part could either belong to the first if or the second one.

This question has been asked in variations many times, just search for if then else shift reduce

For diagnosis (to find out that you are also a victim of that if then else shift reduce problem) you can tell bison to produce an output-file with

bison -r all  myparser.y

which will produce a file myparser.output, in which you can find for your case:

State 50 conflicts: 1 shift/reduce
....
state 50

   11 if_stmt: IF expr THEN stmt .  [ELSE, BEG, END]
   12        | IF expr THEN stmt . ELSE stmt

    ELSE  shift, and go to state 60

    ELSE      [reduce using rule 11 (if_stmt)]
    $default  reduce using rule 11 (if_stmt)


state 51
...

One solution for this would be to introduce a block-statement and only alow these as statements in the if and else part:

stmt: ...
    | blk_stmt
blk_stmt: BEGIN stmt END
if_stmt:  IF expr THEN blk_stmt
    | IF expr THEN blk_stmt ELSE blk_stmt

Which would for a modified c-language mean that only

if x1 then {if x2 then {y=1}} else {y=2}

be possible (with { representing the BEGIN-token and }representing the END-token) thus resolving the ambiguity.