Problem to solve a conflict

Aug 23, 2011 at 2:26 PM
Edited Aug 23, 2011 at 2:28 PM

Hi!

I'm trying to resolve a simple grammar conflict without having to resolve it once the ast is created.

I have the following sequence:  

modifier1 = ":" + identifier

modifier2 = ":" + keyword1 + "(" identifier + ")"

modifier3 = ":" + keyword2 + "(" + identifier+ ")"

initialValue = "=" + value
type  + identifier  + modifier1? + modifier2? + modifier3* + initialValue?

It is obvious that the ":" is conflicting with modifier1, modifier2, modifier3. The easy way is to create a

 modifier = ":" + (identifier | keyword1 + "(" identifier + ")" | keyword2 + "(" + identifier + ")")

and use it like this:

type  + identifier  + modifier* + initialValue?

But It requires to post-validate the ast and verify that there is only (0,1) modifier1  (0,1) modifier2 (*) modifier3

What is the best way to resolve this kind of conflicts with Irony?

Thanks for your help!

Coordinator
Aug 23, 2011 at 6:53 PM

I don't quite understand the phrase ":" is conflicting with ... 

and i do not see where's the conflict. It seems, there should be no conflict - provided you marked keyword1 and keyword2 as reserved word (using MarkReservedWords method). Please provide more info. 

As for solution with Post-validate, I actually do not see anything wrong with, and in fact it is better in one respect: it allows you to provide much more clear error message if input is invalid. Like:

"No more than 2 modifiers are allowed"

"Modifier X is not allowed with construct Y"

 - instead of simply "unexpected symbol, identifier expected" that Irony parser would give by default. 

The best way - I would say there's no best way, it all depends....

Roman

Aug 23, 2011 at 11:13 PM

Thanks for your response. If solution 2 is fine, I will probably go for 2.

Though I would like to understand how to resolve those conflicts. Here is the grammar:

 

using Irony.Parsing;
namespace TestGrammar
{
    [Language("test", "1.0", "Test grammar")]
    public class TestGrammar : Grammar
    {
        public TestGrammar()
        {
            var identifier = TerminalFactory.CreateCSharpIdentifier("Identifier");

            // scalars
            var type = ToTerm("type");
            var modifier1 = new NonTerminal("Modifier1") { Rule = ":" + identifier };
            var modifier2 = new NonTerminal("Modifier2") { Rule = ToTerm(":") + "keyword1" + "(" + identifier + ")" };
            var modifier3 = new NonTerminal("Modifier3") { Rule = ToTerm(":") + "keyword2" + "(" + identifier + ")" };

            var modifier1Opt = new NonTerminal("Modifier1Opt") { Rule = Empty | modifier1 };
            var modifier2Opt = new NonTerminal("Modifier2Opt") { Rule = Empty | modifier2 };
            var modifier3List = new NonTerminal("Modifer3List");
            MakeStarRule(modifier3List, null, modifier3);

            var variable = new NonTerminal("Variable") { Rule = type + identifier + modifier1Opt + modifier2Opt + modifier3List + ";" };

            MarkReservedWords("keyword1", "keyword2");
            MarkTransient(modifier1Opt, modifier2Opt);
            Delimiters = "():;";
            MarkPunctuation(";", ",", "(", ")", "{", "}", "[", "]", ":");
            LineTerminators = "\r\n"; 
            WhitespaceChars = " \t\r\n\v";

            Root = variable.Star();
        }
    }
}

 

In the tabs Grammar Errors of the Grammar Explorer, It complains about:

Shift-reduce conflict. State S5, lookaheads [:]. Selected shift as preferred action.

 

State S5 (Inadequate)
  Shift items:
    Variable -> type Identifier �Modifier1Opt Modifier2Opt Modifer3List ; 
    Modifier1Opt -> �Modifier1 
    Modifier1 -> �: Identifier 
  Reduce items:
    Modifier1Opt -> � [: ;]
  Transitions: Modifier1Opt->S6, Modifier1->S7, :->S8

Same for S6:

 

State S6 (Inadequate)
  Shift items:
    Variable -> type Identifier Modifier1Opt �Modifier2Opt Modifer3List ; 
    Modifier2Opt -> �Modifier2 
    Modifier2 -> �: keyword1 ( Identifier ) 
  Reduce items:
    Modifier2Opt -> � [; :]
  Transitions: Modifier2Opt->S9, Modifier2->S10, :->S11
I don't see why there are shift-reduce conflicts here.

Aug 24, 2011 at 1:54 AM

I managed it by making an explicit declaration of the different combinations:

            var modifiers = new NonTerminal("Modifiers")
            {
                Rule =
                    Empty
                    | modifier1
                    | modifier1 + modifier2 
                    | modifier1 + modifier2 + modifier3List 
                    | modifier2
                    | modifier2 + modifier3List
                    | modifier3List
            };

            var variable = new NonTerminal("Variable")
            {
                Rule = type + identifier + modifiers + ";"
            };

Coordinator
Aug 27, 2011 at 4:36 AM

yep, you've got it right, that's one way to get rid of conflicts like this - explicitly list the sequences, without optional elements. There's a thread somewhere there, we discuss this approach, and its obvious disadvantages. Another approach, to add conflict resolution based on token preview (problem #32 from suggested list of task to work on, here's discussion: http://irony.codeplex.com/discussions/267217). This is a solution for this kind of conflict, first version is already in sources (not in zip), have a look.