Flex and Bison Complexity

Question

Using Flex and Bison, I have a grammar specification for a logical query language that supports the logical operations "and", "or" and "not", as well as nested subexpressions using "()".

Everything was fine until I noticed that queries such as “A and B or C and D”, which I would analyze as “(A and B) | (C and D),” were actually interpreted as “A and ( B | (C and D)). " I am pretty sure that this is a problem of associativity, but it seems that I cannot find the correct explanation or example anywhere - this or I am missing something important.

Relevant information from boolpars.y:

%token TOKEN %token OPEN_PAREN CLOSE_PAREN %right NOT %left AND %left OR %% query: expression { ... } ; expression: expression AND expression { ... } | expression OR expression { ... } | NOT expression { ... } | OPEN_PAREN expression CLOSE_PAREN { ... } | TOKEN { ... } ; 

Can anyone find a flaw? I do not understand why Bison does not give an “or” corresponding priority.

Answer 1

From the bison docs:

Operator priority is determined by the ordering of the declaration lines; the higher the line number of the declaration (lower on the page or screen), the higher the priority.

So, in your case, OR on the screen below and has a higher priority. Change the order to

 %left OR %left AND 

(I did not test it)

Answer 2

Why not split production, as in this fragment from C-ish language

 logical_AND_expression: inclusive_OR_expression | logical_AND_expression ANDAND inclusive_OR_expression {$$ = N2(__logand__, $1, $3);} ; logical_OR_expression: logical_AND_expression | logical_OR_expression OROR logical_AND_expression {$$ = N2(__logor__, $1, $3);} ; 

Answer 3

I ran tests on my own implementation, and from my tests, marcin's answer is correct. If I define the priority as:

 %left OR %left AND 

Then the expression A & B | C & D will be reduced to ((A & B) | (C & D))

If I define the priority as:

 %left AND %left OR 

Then the expression A & B | C & D will be reduced to ((A & (B | C)) & D)

One differentiating expression will be:

 true & true | true & false 

The previous definition of priority will set this to true, while the latter will make it false. I tested both scenarios and both work as described.

Double check your tests to make sure. Also note that this is the order of% left,% right, etc. Definitions in the header part, which determine the priority, and not the order, which you determine by the rules themselves. If it still doesn't work, maybe this is some other area of ​​your code that messed it up, or maybe your version of the bison is different (I'm just shooting in the dark at this point).