Reduce-Reduce conflicts with MakePlusRule

Mar 2, 2011 at 7:39 PM

I have been having a lot of issues with the following defined BNF grammar:

condition := predicate {AND predicate} | predicate {OR predicate}       (where {} denotes zero or more times)

This form is required because it is possible to have multiple ANDs or ORa but this grammar does not allow both ANDs and ORs in the same statement without using braces.  Initially I interpreted it as follows:

            condition.Rule = predicate | predicate + condition_and | predicate + condition_or;
            condition_and.Rule = MakePlusRule(condition_and, predicate + AND);
            condition_or.Rule = MakePlusRule(condition_or, predicate + OR);

But this simply created four reduce-reduce conflicts, two for "AND" and two for "OR"  . I tried all sorts of variations around the MakePlusRule, including using "AND" as the separator but nothing worked.

Eventually, after looking at the MakePlusRule code itself, I hit upon the following idea:

            condition.Rule = predicate | condition_and | condition_or;
            condition_and.Rule = predicate + AND + predicate | condition_and + AND + predicate;
            condition_or.Rule = predicate + OR + predicate | condition_or + OR + predicate;

 Which now works just fine with no conflicts, but is no longer a list.  Any ideas as to why I was hitting this issue and how I might turn it back into a simple list of "predicate"s?


Coordinator
Mar 2, 2011 at 9:18 PM

I think this is standard SR conflict with chain of operators. In you original version, the parser does not know how to interpret "pred AND pred AND pred":

As "(pred AND pred) AND pred" or as "pred AND (pred AND pred)"

This should be resolved if you register AND and OR as operators with LeftAssociation, precedence does not matter as they don't mix in one expression.

The other way to go is to define condition as

andCond.Rule = MakePlusRule(andCond, "AND", pred);

orCond.Rule = MakePlusRule(orCond, "OR", pred);

cond.Rule = andCond | orCond; 

Coordinator
Mar 3, 2011 at 1:07 AM

Sorry, I think I was a bit confused, the problem with your original version is not associativity. When I looked at it closely, it appears to have a mistake. According to your definition of condition_and, a list containing a single element is: "predicate AND".

Combined with the rule for condition, it follows that the following is a valid condition:

predicate predicate AND

Something is wrong here :)

Mar 3, 2011 at 9:27 AM
Edited Mar 3, 2011 at 9:29 AM

My appologies. As you rightly point out I have messed up the post above!  But I promise you (this time!) that I tried both of the following

            condition.Rule = predicate | condition_and + predicate | condition_or + predicate;
            condition_and.Rule = MakePlusRule(condition_and, predicate + AND);
            condition_or.Rule = MakePlusRule(condition_or, predicate + OR);

            condition.Rule = predicate | predicate + condition_and | predicate + condition_or;
            condition_and.Rule = MakePlusRule(condition_and, AND + predicate );
            condition_or.Rule = MakePlusRule(condition_or, OR + predicate );

which should now read "(predicate AND) predicate" or "predicate (AND predicate)" respectively.  I know that I had these forms working because in some instances they worked and others they didnt, (I therefore assumed the inconsistent behaviour was the reduce-reduce conflict?)

I also tried the list approach you mention without success.

            condition.Rule = predicate | condition_and | condition_or ;
            condition_and.Rule = MakePlusRule(condition_and, AND , predicate );
            condition_or.Rule = MakePlusRule(condition_or, OR , predicate );

I still got the reduce-reduce conflict. 

The only form that I have found that works is the one I had posted previously (which I have doubled checked against my code and is also correctly copied and pasted :) ).  This form also appears to parse sucessfully on a consistent basis:

            condition.Rule = predicate | condition_and | condition_or;
            condition_and.Rule = predicate + AND + predicate | condition_and + AND + predicate;
            condition_or.Rule = predicate + OR + predicate | condition_or + OR + predicate;

 

Coordinator
Mar 3, 2011 at 5:40 PM

Now it's clear I think. Look at "condition" definition, in either case. It says that condition is one of 3: a single predicate, or sequence of 1+ predicates joined by AND, or sequence of 1+ predicates joined by OR.

Each of this variants is a distinctive parsing alternative, and parser has to know when to use which. Now the problem: if we have a single predicate as an input, it can be interpreted as any of these 3 alternative: it is standalone predicate (bing!), and it is an AND sequence with a single element, and it is OR sequence with single element. Parse has no way of deciding based on the grammar - that's what it is reporting in conflict errors!

The solution I think is to define condition as a binary expression, with operations AND, OR - see expression evaluator grammar, the same way. The extra restriction that AND should not mix with ORs can be enforced after parsing, either in AstNote.Init method, or in a separate visitor walk.

Roman

Mar 3, 2011 at 6:34 PM

Yes, I think you are right.  I have learnt three things here. 

First, although I have an "official grammar" to follow, that does not mean it can be parsed directly in the form as "officially" defined.  I have seen comments to that extent in other posts and I now understand that.  I like your suggestion of using the ExpressionEvaluator structure.

Second I am making the assumption that the parser will recognise that there will always be at least one "AND predicate" with the MakePlusRule when distinguishing between the alternatives (as opposed to MakeStarRule where it wouldnt necessarily even see one case). While logically you might reason that should be the case, in practice that appears to be an invalid assumption when designing the rule.  I have stumbled into other cases similar that. 

Finally, dont try to do work best done post parsing.  I will go and learn a little bit more about AST.

Many thanks.  Will let you know how I get on.

 

Mar 4, 2011 at 11:06 PM

All solved.  No more conflicts.

Using the ExpressionEvaluator grammar rather than the "official" grammar was the way forward.  Still need to sort out the post-parse processing, but that is under my complete control and should now be relatively easy.

Thanks again for your help.

Will.