NewLineStar generating conflicts?

Dec 11, 2009 at 6:48 PM

I was playing with Irony and decided to make a small utility to read gold parser grammars and "convert" them to Irony grammar classes.

And  while working on this app, I found a strange behavior:

Rules declared like the one below give me shift/reduce conflicts

Parameter.Rule = parametername + NewLineStar + "=" + Parameter_Body + NewLinePlus;

If I change this rule to the following format, the conflicts are gone.

Parameter.Rule = parametername + NewLinePlus + "=" + Parameter_Body + NewLinePlus
                           | parametername + "=" + Parameter_Body + NewLinePlus;

Am I missing something or is it actually an issue?

 

Coordinator
Dec 11, 2009 at 8:54 PM

Not sure, but seems strange. Can you please send me your grammar if possible? I'll play with it to see what's going on.

Coordinator
Dec 11, 2009 at 10:16 PM

I'm trying with a simple grammar but don't see any conflicts:

namespace Irony.Samples {
  public class QuickTestGrammar : Grammar {
    public QuickTestGrammar() {
      var Parameter = new NonTerminal("parameter");
      var parametername = new IdentifierTerminal("paramentername");
      var Parameter_Body = new IdentifierTerminal("paramBody");

      Parameter.Rule = parametername + NewLineStar + "=" + Parameter_Body + NewLinePlus;
      this.Root = Parameter;
    }
 
  }//class
}

Looks like it is a problem specific to your grammar. I've tried on version 40596, latest source

Dec 11, 2009 at 10:59 PM

It seems like the problem occurs once there are two or more rules using the pattern.

But then again, it could be me, something I've missed...

follows the grammar, with two versions of the same rule (Parameter_Body).

The one uncommented raises conflicts. The commented one, below, doesn't.

If you leave just one rule using NewLineStar, there's no conflict.

And if all of the rules declare alternate versions, with and without the newline, also no conflicts.

------------------------------------------------------------------------------------------------------------------------------------------------------

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Irony.Parsing;
using Irony.Ast;

namespace Irony.Generator
{
    [Language("GOLD Meta-Language", "2.6.0", "This grammar defines the GOLD Meta-Language.")]
    public class GOLD_MetaLanguage : Grammar
    {
        public GOLD_MetaLanguage()
            : base(false)
        {


            //////////////////////////////////////////////////////////////////////////////
            ///////////////////////////////////Comments///////////////////////////////////
            //////////////////////////////////////////////////////////////////////////////

            CommentTerminal comment = new CommentTerminal("comment", "!*", "*!");
            NonGrammarTerminals.Add(comment);
            CommentTerminal lineComment = new CommentTerminal("lineComment", "!", "\n", "\r\n");
            NonGrammarTerminals.Add(lineComment);

            //////////////////////////////////////////////////////////////////////////////
            ///////////////////////////////Special Terminals//////////////////////////////
            //////////////////////////////////////////////////////////////////////////////


            QuotedValueLiteral parametername = new QuotedValueLiteral("parametername", "\"", TypeCode.String);
            QuotedValueLiteral nonterminal = new QuotedValueLiteral("nonterminal", "<", ">", TypeCode.String);
            QuotedValueLiteral setliteral = new QuotedValueLiteral("setliteral", "[", "]", TypeCode.String);
            QuotedValueLiteral setvalue = new QuotedValueLiteral("setvalue", "'", TypeCode.String);
            QuotedValueLiteral setname = new QuotedValueLiteral("setname", "{", "}", TypeCode.String);
            IdentifierTerminal terminalid = new IdentifierTerminal("terminal2");

            NonTerminal termRule = new NonTerminal("termRule");
            termRule.Rule = terminalid | setvalue;

            //////////////////////////////////////////////////////////////////////////////
            ///////////////////////////////////Key words//////////////////////////////////
            //////////////////////////////////////////////////////////////////////////////



            //////////////////////////////////////////////////////////////////////////////
            /////////////////////////////////Non Terminals////////////////////////////////
            //////////////////////////////////////////////////////////////////////////////


            NonTerminal Grammar = new NonTerminal("Grammar");
            NonTerminal Content = new NonTerminal("Content");
            NonTerminal Definition = new NonTerminal("Definition");

            NonTerminal Parameter = new NonTerminal("Parameter");
            NonTerminal Parameter_Body = new NonTerminal("Parameter_Body");
            NonTerminal Parameter_Items = new NonTerminal("Parameter_Items");
            NonTerminal Parameter_Item = new NonTerminal("Parameter_Item");
            NonTerminal Set_Decl = new NonTerminal("Set_Decl");
            NonTerminal Set_Exp = new NonTerminal("Set_Exp");
            NonTerminal Set_Item = new NonTerminal("Set_Item");
            NonTerminal Terminal_Decl = new NonTerminal("Terminal_Decl");
            NonTerminal Terminal_Name = new NonTerminal("Terminal_Name");
            NonTerminal Reg_Exp = new NonTerminal("Reg_Exp");
            NonTerminal Reg_Exp_Seq = new NonTerminal("Reg_Exp_Seq");
            NonTerminal Reg_Exp_Item = new NonTerminal("Reg_Exp_Item");
            NonTerminal Reg_Exp_2 = new NonTerminal("Reg_Exp_2");
            NonTerminal Kleene_Opt = new NonTerminal("Kleene_Opt");
            NonTerminal Rule_Decl = new NonTerminal("Rule_Decl");
            NonTerminal Handles = new NonTerminal("Handles");
            NonTerminal Handle = new NonTerminal("Handle");
            NonTerminal Symbol = new NonTerminal("Symbol");



            //////////////////////////////////////////////////////////////////////////////
            ///////////////////////////////Rule Declaration///////////////////////////////
            //////////////////////////////////////////////////////////////////////////////

            this.Root = Grammar;

            Grammar.Rule = NewLineStar + Content;

            Content.Rule = MakeStarRule(Content, Definition);

            Definition.Rule = Parameter
                            | Set_Decl
                            | Terminal_Decl
                            | Rule_Decl;

            Parameter.Rule = parametername + NewLineStar + "=" + Parameter_Body + NewLinePlus;


            Parameter_Body.Rule = Parameter_Body + NewLineStar + "|" + Parameter_Items
                              | Parameter_Items;


            //Parameter_Body.Rule = Parameter_Body + NewLinePlus + "|" + Parameter_Items
            //                    | Parameter_Body + "|" + Parameter_Items
            //                    | Parameter_Items;

            Parameter_Items.Rule = Parameter_Items + Parameter_Item
                            | Parameter_Item;

            Parameter_Item.Rule = parametername
                            | termRule
                            | setliteral
                            | setname
                            | nonterminal;

            Set_Decl.Rule = setname + NewLinePlus + "=" + Set_Exp + NewLinePlus
                          | setname + "=" + Set_Exp + NewLinePlus;

            Set_Exp.Rule = Set_Exp + NewLinePlus + "+" + Set_Item
                            | Set_Exp + NewLinePlus + "-" + Set_Item
                            | Set_Item
                            | Set_Exp  + "+" + Set_Item
                            | Set_Exp  + "-" + Set_Item;

            Set_Item.Rule = setliteral
                            | setname;

            Terminal_Decl.Rule = Terminal_Name + NewLinePlus + "=" + Reg_Exp + NewLinePlus
                               | Terminal_Name + "=" + Reg_Exp + NewLinePlus;

            Terminal_Name.Rule = Terminal_Name + termRule
                            | termRule;

            Reg_Exp.Rule = Reg_Exp + NewLinePlus + "|" + Reg_Exp_Seq
                            | Reg_Exp + "|" + Reg_Exp_Seq
                            | Reg_Exp_Seq;

            Reg_Exp_Seq.Rule = Reg_Exp_Seq + Reg_Exp_Item
                            | Reg_Exp_Item;

            Reg_Exp_Item.Rule = setliteral + Kleene_Opt
                            | setname + Kleene_Opt
                            | termRule + Kleene_Opt
                            | "(" + Reg_Exp_2 + ")" + Kleene_Opt;

            Reg_Exp_2.Rule = Reg_Exp_2 + "|" + Reg_Exp_Seq
                            | Reg_Exp_Seq;

            Kleene_Opt.Rule = Empty
                            | "+"
                            | "?"
                            | "*";


            Rule_Decl.Rule = nonterminal + NewLinePlus + "::=" + Handles + NewLinePlus
                           | nonterminal + "::=" + Handles + NewLinePlus;

            Handles.Rule = Handles + NewLinePlus + "|" + Handle
                           | Handles + "|" + Handle
                           | Handle;

            Handle.Rule = Handle + Symbol
                            | Empty;

            Symbol.Rule = termRule
                            | nonterminal;



            //////////////////////////////////////////////////////////////////////////////
            ////////Uncoment the following section to declare operators precedence////////
            //////////////////////////////////////////////////////////////////////////////


            //RegisterOperators(10, "*", "/", "%");
            //RegisterOperators(9, "+", "-");
            //RegisterOperators(8, "=", ">", "<", ">=", "<=", "<>", "!=", "!<", "!>");
            //RegisterOperators(6, "&&", "||", "!");


            //////////////////////////////////////////////////////////////////////////////
            ////////////////////////Punctuation and Transient Items///////////////////////
            //////////////////////////////////////////////////////////////////////////////
            RegisterPunctuation("|", "::=", "=");

            MarkTransient(Content, Definition, termRule, Parameter_Body, Parameter_Items, Parameter_Item,
                Set_Exp, Set_Item, Reg_Exp, Reg_Exp_Seq, Reg_Exp_2);

            MarkTransient(Handle, Handles);

        }
    }
}

Coordinator
Dec 12, 2009 at 8:28 AM

Nope, looks like Irony reports everything correctly, this is a real conflict caused by "optional" nature of NewLineStar element. The alternative that does not have conflict does this by eliminating the so-called epsilon-rule (NewLineStar -> Empty). This is a known fact, and a trick used to fix these conflicts. Look at conflict state printout:

State S45 (Inadequate)
  Shift items:
    Parameter -> parametername LF* = Parameter_Body ·LF+
    LF+ -> ·LF
    LF+ -> ·LF+ LF
    Parameter_Body -> Parameter_Body ·LF* | Parameter_Items
    LF* -> ·LF* LF
  Reduce items:
    LF* -> · [| LF]
  Transitions: LF+->S75, LF->S20, LF*->S76,

Irony cannot decide if the LF it sees as a lookahead is part of 'LF+' at the end of Parameter's rule (in this case it should shift), or is it a part of optional delimiter LF* inside ParameterBody (in this case it should do a reduce on empty production). It is this empty reduce that is a problem, and it comes from the rule LF*->Empty inside NewLineStar.

So nothing strange here, and the fact that alternative version, without NewLineStar, has no conflict, is no surprise. You should probably stay with the second version without conflicts. The only inconvenience with this rule is that alternatives in the rule for Parameter_body have different number of elements, so AST node constructor would need an extra analysis of child nodes, to correctly recognize what is what - it cannot blindly use child node index to retrieve child in particular role.

 

 

 

 

Dec 15, 2009 at 2:07 PM

Hi there.

Sorry for the delay.

You're right. My bad.

Btw, I'm having loads of fun with Irony. Keep up with the nice work!