Bison complained "conflicts: 1 shift/reduce"

Question

Bison complained "conflicts: 1 shift/reduce". I can't see what's wrong. Please help. Thanks,

%token OR AND NUMBER
%%

search_condition:
        |       search_condition AND search_condition { printf(" AND "); }
        |       '(' search_condition ')'
        |       predicate
        ;

predicate:
                NUMBER { printf("%d\n", $1);  }
        ;

Answer 1

A conflict means that the grammar you gave to bison is not LALR(1), so it can't decide what action to take in every possible case in order to correctly parse the grammar.

In your case, the problem is that your grammar is ambiguous. If you give it an input like

NUMBER AND NUMBER AND NUMBER

it can't decide if it should parse it as equivalent to

( NUMBER AND NUMBER ) AND NUMBER

or

NUMBER AND ( NUMBER AND NUMBER )

There are a number of ways you can resolve this:

• you can use %left AND or %right AND to tell bison that it should treat AND as a left- or right-associative infix operator

• you can refactor the search_condition rule to make it unambiguous:

  search_condition : search_condition AND primary
                   | primary
                   ;
  primary : '( search_condition ')'
          | predicate
          ;