Select appropriate production on RR conflict

Jun 15, 2015 at 5:00 PM
Edited Jun 15, 2015 at 5:04 PM
In the Microsoft Excel formula language, a comma is both the function argument separator and a "union" operator.

My first attempt was doing this like you would normally do binops (see the PS), but this failed miserably. I tried instead with an comma-separated list between brackets because in practice brackets are nearly always needed.

I now have a working grammar, except it has a Reduce Reduce conflict and by default chooses the wrong production. What hint do I need to resolve the conflict and select the proper rule?

The error is as follows:
State S10 (Inadequate)
  Reduce-reduce conflicts on inputs: )
  Shift items:
    Reference -> Reference ·: Reference 
  Reduce items:
    Union -> Reference · [) ,]
    Formula -> Reference · [)]
  Transitions: :->S8
Example sentence: "(A1)"

The (vastly simplified) grammar is as follows:
            var Reference = new NonTerminal("Reference");
            var Union = new NonTerminal("Union");
            var Formula = new NonTerminal("Formula");
            var Arguments = new NonTerminal("Arguments");

            var ReferenceItem = ToTerm("A1");
            var Constant = ToTerm("1");

            Reference.Rule = ReferenceItem
                             | Reference + ":" + Reference
                           //| Reference + "," + Reference
                             | "(" + Union + ")"
                ;

            Formula.Rule = Reference
                | "(" + Formula + ")"
                | "F(" + Arguments + ")"
                | Constant
                ;

            Union.Rule = MakePlusRule(Union, ToTerm(","), Reference);
            Arguments.Rule = MakeStarRule(Arguments, ToTerm(","), Formula);

            RegisterOperators(1, Associativity.Left, ":");
            //RegisterOperators(1, Associativity.Left, ",");

            Root = Formula;
P.S.
I first tried doing the "proper" thing and making the comma an operator, but that caused numerous problems, mainly because the rules with the operator were "chosen" above those where a comma is the argument separator while it should be the other way around. E.g. "F(A1,A1,1)" would not parse because "1" cannot be used inside an union.

My current approach seems to work better, and even though it's not correct in all cases it covers the vast majority of sane cases. The operator approach might me better, but then I'd need a way to "favor" the argument separator rules and I couldn't figure out which grammar hints to use. The commented out lines above show my original approach.
Coordinator
Jun 19, 2015 at 7:39 AM
Edited Jun 19, 2015 at 7:42 AM
You should use ReduceHere() hint as shown below. Your trouble is expressions like '(A1)' -
which can be interpreted either as Union with one element, or formula (ref in parenthesis). Both interpretations are correct (!), so it's up to you, grammar writer to prefer one to another. Using the hint, you tell parser that you prefer the formula interpretation.
public PlaygroundExcelGrammar()
  : base(false) {
    var Reference = new NonTerminal("Reference");
    var Union = new NonTerminal("Union");
    var Formula = new NonTerminal("Formula");
    var Arguments = new NonTerminal("Arguments");

    var ReferenceItem = ToTerm("A1");
    var Constant = ToTerm("1");

    Reference.Rule = ReferenceItem
                     | Reference + ":" + Reference
      //| Reference + "," + Reference
                     | "(" + Union + ")"
        ;
    Formula.Rule = Reference + ReduceHere()
        | "(" + Formula + ")"
        | ToTerm("F") + "(" + Arguments + ")"
        | Constant            ;
    Union.Rule = MakePlusRule(Union, ToTerm(","), Reference);
    Arguments.Rule = MakeStarRule(Arguments, ToTerm(","), Formula);
    RegisterOperators(1, Associativity.Left, ":");
    //RegisterOperators(1, Associativity.Left, ",");

    Root = Formula;
}
Jun 19, 2015 at 8:29 PM
Thanks! I understood the problem and ambiguity, but didn't understand where to place the grammar hint.