Help understanding reduce-reduce conflict

Sep 29, 2015 at 4:21 PM
The language I'm building a grammar for is generating a reduce-reduce conflict and I'm not sure how to read the conflict. I'm assuming in this case I should insert a ReduceHere() call somewhere in my grammar to clear up the conflict but I lack the understanding currently to know where this goes and exactly why (I assume it to be a conflict between potential expressions using ++, +, -- and -). The conflict message is as follows:
State S53 (Inadequate)
Reduce-reduce conflicts on inputs: ++ -- < || && ^ == != > <= >= << >> + - * / % in
Reduce items:
Unary Expression -> Unary Operator Primary Expression · [++ -- < || && ^ == != > <= >= << >> + - * / % in Semicolon Comma }]
Expression -> Primary Expression · [++ -- < || && ^ == != > <= >= << >> + - * / % in]
Transitions:
My grammar includes operators common to C# such as ++, --, ==, !=, etc. as you can see. I used the example C# grammar in irony as a starting point. I actually ran into a number of conflicts initially, so I stripped the grammar down to a simplified version with the intention of slowly adding grammar parts back until I hit a conflict and then solving the conflict. I'm hoping by better understanding this conflict and the proper solution I can apply that knowledge to future conflicts and not nag folks with questions ;). In the current stripped down state the entire grammar is as follows:
using System;
using Irony.Parsing;

namespace Org.Edgerunner.MooSharp.Parser
{
    [Language("Moo#", "1.0", "The Moo# programming language, an extended version of the original Moo language")]
    public class MooSharpGrammar : Irony.Parsing.Grammar
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="MooSharpGrammar"/> class.
        /// </summary>
        public MooSharpGrammar()
            : base(false)
        {
            #region declarations
            StringLiteral stringLiteral = MooTerminalFactory.CreateMooString("StringLiteral");
            Irony.Parsing.NumberLiteral number = MooTerminalFactory.CreateMooNumber("Number");
            ObjectLiteral objectLiteral = new ObjectLiteral("Object");
            ErrorTerminal error = new ErrorTerminal("ErrorCode", typeof(string));
            IdentifierTerminal identifier = MooTerminalFactory.CreateMooIdentifier("Identifier");

            KeyTerm lcbr = ToTerm("{");
            KeyTerm rcbr = ToTerm("}");
            KeyTerm comma = ToTerm(",", "Comma");
            KeyTerm semi = ToTerm(";", "Semicolon");
            KeyTerm at = ToTerm("@", "at");

            CommentTerminal singleLineComment = new CommentTerminal("SingleLineComment", "//", "\r", "\n", "\u2085", "\u2028", "\u2029");
            CommentTerminal delimitedComment = new CommentTerminal("DelimitedComment", "/*", "*/");
            NonGrammarTerminals.Add(singleLineComment);
            NonGrammarTerminals.Add(delimitedComment);
                        
            var literal = new NonTerminal("Literal");
            var incrOrDecr = new NonTerminal("Incr Or Decr");
            var incrOrDecrOpt = new NonTerminal("Incr Or Decr Opt");
            var preIncrDecrExpression = new NonTerminal("Pre Incr Decr Expression");
            var postIncrDecrExpression = new NonTerminal("Post Incr Decr Expression");
            var expression = new NonTerminal("Expression");
            var primaryExpression = new NonTerminal("Primary Expression");
            var listLiteral = new NonTerminal("List Literal");
            var unaryOperator = new NonTerminal("Unary Operator");
            var unaryExpression = new NonTerminal("Unary Expression");
            var spliceExpression = new NonTerminal("Splice Expression");
            var listMemberExpression = new NonTerminal("List Member Expression");
            var listMemberExpressionListOpt = new NonTerminal("List Member Expression List Optional");
            var binOpExpression = new NonTerminal("Binary Operation Expression");
            var binOp = new NonTerminal("Binary Operator", "operator symbol");
            var statement = new NonTerminal("Statement");
            var simpleStatement = new NonTerminal("Simple Statement");
            var simpleStatementOpt = new NonTerminal("Simple Statement Optional");
            var statementList = new NonTerminal("Statement List");
            var CodeBody = new NonTerminal("Code Body");
            #endregion

            RegisterOperators(1, "||");
            RegisterOperators(2, "&&");
            RegisterOperators(4, "^");
            RegisterOperators(6, "==", "!=");
            RegisterOperators(7, "<", ">", "<=", ">=");
            RegisterOperators(8, "<<", ">>");
            RegisterOperators(9, "+", "-");
            RegisterOperators(10, "*", "/", "%");
            RegisterOperators(11, ".", ":", "in", "@");
            RegisterOperators(12, "++", "--");
            RegisterOperators(-3, "=", "+=", "-=", "*=", "/=", "%=", "&=", "|=", "^=", "<<=", ">>=");
            RegisterOperators(-2, "?");

            this.MarkPunctuation(";", ",", "(", ")", "{", "}", "[", "]");

            Root = CodeBody;

            expression.Rule = primaryExpression | binOpExpression;
            
            spliceExpression.Rule = at + expression;
            listMemberExpression.Rule = spliceExpression | expression;
            listMemberExpressionListOpt.Rule = MakeStarRule(listMemberExpressionListOpt, comma, listMemberExpression);
            listLiteral.Rule = lcbr + listMemberExpressionListOpt + rcbr;
            literal.Rule = stringLiteral | error | objectLiteral | number | "true" | "false" | listLiteral;
            incrOrDecrOpt.Rule = Empty | ToTerm("++") | "--";
            incrOrDecr.Rule = ToTerm("++") | "--";
            preIncrDecrExpression.Rule = incrOrDecr + expression;
            postIncrDecrExpression.Rule = expression + incrOrDecr;
            binOp.Rule = ToTerm("<") | "||" | "&&" | "^" | "==" | "!=" | ">" | "<=" | ">=" | "<<" | ">>" | "+" | "-" | "*" | "/" | "%" | "in";
            binOpExpression.Rule = expression + binOp + expression;
            primaryExpression.Rule =
                identifier
                | unaryExpression
                | preIncrDecrExpression
                | postIncrDecrExpression
                | literal;

            unaryOperator.Rule = ToTerm("+") | "-" | "!" | "~" | "*";
            unaryExpression.Rule = unaryOperator + primaryExpression;
        
            simpleStatementOpt.Rule = expression | Empty;
            simpleStatement.Rule = simpleStatementOpt + semi;
            statement.Rule = simpleStatement;
            statementList.Rule = MakePlusRule(statementList, null, statement);
            CodeBody.Rule = Empty | statementList;
        }
    }
}
Sep 29, 2015 at 5:47 PM
Reduce-reduce means there's more than one way some sentence (code) can be parsed (this is called ambiguity). In this case there a sentence where the parser can't decide if the preceding part should be a Expression or a Unary Expression.

I don't immediately see the problem, but the problematic state is hit with +1++;. However this shouldn't be a problem because ++ has a higher precedence than +.
Sep 29, 2015 at 6:46 PM
Thank you, that makes sense. I thought it had something to do with that, but every sample I tried parsing came out as I would expect (I'm guessing because of operator precedence as you mention). Am I right to assume that a call to ReduceHere() in the right spot would solve the conflict?
Sep 29, 2015 at 6:57 PM
So this may not be the best approach, but I just tried inserting a ReduceHere() call throughout the expression and unary expression rules and found the following change made the grammar conflict go away:
expression.Rule = primaryExpression + ReduceHere() | binOpExpression;
Also I noticed that the expression +1++ was being parsed as (+1)++ and now it is being parsed as +(1++). I'm not going to pretend to fully understand why the ReduceHere() call fixes it when placed in that particular spot, but that should still help me debug further reduce-reduce conflicts. Thanks again for the help.
Marked as answer by WiredWiz on 9/29/2015 at 1:00 PM