CODEWITHSUNDEEP
bisonyacc
sabu
sabu

Reputation: 307

how to remove reduce/reduce conflicts

I am trying to solve few yacc problems.And in few of my tries goes in vain after getting conflicts: reduce/reduce error. FOr an example, i am trying to solve "string which accpets more 0's than 1's" and I write this following code which shows reduce/reduce conflict(I am giving only the rules section here):

    s   :   s1 ';'   {printf("valid");exit(0);}
        ;
    s1  :   '0' '1' '0' s   
        |   '0' '0' '1' s
        |   '1' '0' '0' s
        |   '0' s
        | 
        ;

Can any one tell me what i have made wrong here I will appreciate if u advice me in future how to I get recovered from this error.

THank you,

Upvotes: 0

Views: 1222

Answers (1)

Jonathan Leffler
Jonathan Leffler

Reputation: 753455

You're using right-recursion rather than left-recursion. Generally, left-recursion is preferred in Bison and Yacc grammars. It is also a bit odd that you have s rather than s1 in the s1 rules.

The verbose output file (bison -v rrconf.y yields rrconf.output) says:

State 20 conflicts: 1 reduce/reduce
State 21 conflicts: 1 reduce/reduce

Grammar

    0 $accept: s $end

    1 s: s1 ';'

    2 s1: '0' '1' '0' s
    3   | '0' '0' '1' s
    4   | '1' '0' '0' s
    5   | '0' s
    6   | /* empty */

...

state 20

    2 s1: '0' '1' '0' s .
    5   | '0' s .

    ';'       reduce using rule 2 (s1)
    ';'       [reduce using rule 5 (s1)]
    $default  reduce using rule 2 (s1)


state 21

    4 s1: '1' '0' '0' s .
    5   | '0' s .

    ';'       reduce using rule 4 (s1)
    ';'       [reduce using rule 5 (s1)]
    $default  reduce using rule 4 (s1)

It's easy to change the grammar to use left-recursion:

%%
s   :   s1 ';'   {printf("valid");exit(0);}
    ;
s1  : s1 '0' '1' '0'
    | s1 '0' '0' '1'
    | s1 '1' '0' '0'
    | s1 '0'
    | 
    ;
%%

It leaves you with two shift/reduce conflicts (which are much less serious than reduce/reduce conflicts):

State 5 conflicts: 2 shift/reduce

Grammar

    0 $accept: s $end

    1 s: s1 ';'

    2 s1: s1 '0' '1' '0'
    3   | s1 '0' '0' '1'
    4   | s1 '1' '0' '0'
    5   | s1 '0'
    6   | /* empty */

...


state 5

    2 s1: s1 '0' . '1' '0'
    3   | s1 '0' . '0' '1'
    5   | s1 '0' .

    '0'  shift, and go to state 7
    '1'  shift, and go to state 8

    '0'       [reduce using rule 5 (s1)]
    '1'       [reduce using rule 5 (s1)]
    $default  reduce using rule 5 (s1)

Whether that's sufficient for you, I'm not sure.

You still have another problem, though — a high-level algorithm design problem. An input of 10 1's followed by 11 0's meets the requirement of more zeros than ones, but won't be recognized by this grammar.

Upvotes: 1

Related Questions