CODEWITHSUNDEEP
parsingbisonebnf
spy91
spy91

Reputation: 1

Conflicting shift/reduce with conditions and PEMDAS EBNF in Bison

I currently have an error in my Bison with regards to my EBNF while creating the parsing for PEMDAS and conditions. I don't understand well on how I'm going to reduce the EBNF.

I got 1 shift/reduce error in the output file. Here's the part where the conflicting appears. The "expr" in "rel_cond" appears to be in conflict when I declared the "rel_expr" and "par_expr" rules.

cond    : rel_cond
        | par_cond
        ;

rel_cond    : expr relop cond
            | expr
            ;

par_cond    : PAR_START cond PAR_END
            ;

.
.

expr    : rel_expr
        | par_expr
        ;

par_expr    : PAR_START expr PAR_END
            ;

rel_expr    : term ADD expr 
            | term SUB expr
            | term
            ;

term    : factor MULT factor
        | factor DIV factor
        | factor
        ;


factor  : CONSTANT
        | ID
        ;

Here's what appears in the .output file

state 47

16 rel_cond: expr . relop expr
17         | expr .
32 par_expr: PAR_START expr . PAR_END

EQT      shift, and go to state 49
NOT_EQT  shift, and go to state 50
LT       shift, and go to state 51
GT       shift, and go to state 52
LT_EQT   shift, and go to state 53
GT_EQT   shift, and go to state 54
BIT_AND  shift, and go to state 55
LOG_AND  shift, and go to state 56
BIT_OR   shift, and go to state 57
LOG_OR   shift, and go to state 58
PAR_END  shift, and go to state 41

PAR_END  [reduce using rule 17 (rel_cond)]

relop  go to state 59

Upvotes: 0

Views: 129

Answers (1)

Chris Dodd
Chris Dodd

Reputation: 126408

Your ouput file doesn't correspond to your grammar, so you're not running bison on the input file you think you are. The output file has the rule

rel_cond: expr relop expr

while your rules have

rel_cond    : expr relop cond

but in either case the problem is the same -- the rule here is ambiguous because it doesn't specifiy whether it is right or left recursive. An input like

expr relop expr relop expr

can be parsed as either (expr relop expr) relop expr or expr relop (expr relop expr). The default "shift before reduce" conflict resolution means the resulting parser will be left recursive, but you can get rid of the conflict by using precedence rule, or by rewriting the grammar to be explicitly left or right recursive.

Upvotes: 1

Related Questions