Is there a problem in this BN form language? I am working on a simple text query language.  I am using the SLY parser, which itself is an LR parser/shift-reduce parser.  I am running into problems with the following language specification, but I don't understand why.  All I'm trying to do is appropriately group logical statements involving the operators AND and OR (in which AND gets precedence over OR and the statements are left associative) and "words", which is basically anything other than "AND" or "OR".  The language is below.  What is the problem?

LOGICAL ::= &lt;WORD&gt; &lt;OPERATOR&gt; &lt;WORD&gt; 
        | &lt;WORD&gt; &lt;OPERATOR&gt; &lt;LOGICAL&gt;
        | &lt;LOGICAL&gt; &lt;OPERATOR&gt; &lt;WORD&gt;
        | &lt;LOGICAL&gt; &lt;OPERATOR&gt; &lt;WORD&gt;

OPERATOR ::= "AND"
            | "OR"

WORD ::= any string other than "AND" or "OR"


Also, for the record I don't know how to express "WORD" in a more formal way, so I'd appreciate any input.
That grammar has two problems.


It's ambiguous. You say that you want to give AND precedence over OR and make both operators left-associative, but your grammar does not reflect that goal since it does not distinguish AND from OR and it explicitly accepts both left- and right-associative parses:

&lt;WORD&gt; &lt;OPERATOR&gt; &lt;LOGICAL&gt;    (* right associative *)
&lt;LOGICAL&gt; &lt;OPERATOR&gt; &lt;WORD&gt;    (* left associative *)

On a more minor level, probably a typo, your third and fourth productions are identical.


It's possible that you have tried to fix the issue by using precedence declarations in your parser generator tool. Precedence declarations are not part of BNF, and incorrect precedence declarations are really a programming error, rather than an issue in parser theory.

If you have such a problem, you should probably ask a question on a programming site, such as StackOverflow, and comply with the usual rules of including a complete reproducible example. However, in the usual approach to using precedence to resolve parser ambiguity, it is important that you don't have explicit parser ambiguity, as above. Thus, a "traditional" precedence-augmented BNF grammar (as per the Dragon book) would look like this:

%left &lt;OR&gt;
%left &lt;AND&gt;

&lt;LOGICAL&gt; ::= &lt;WORD&gt;
          |   &lt;LOGICAL&gt; &lt;OR&gt; &lt;LOGICAL&gt;
          |   &lt;LOGICAL&gt; &lt;AND&gt; &lt;LOGICAL&gt;