Changeset 10067 for branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars

Timestamp:

10/18/13 21:33:56 (11 years ago)

Author:

gkronber

Message:

#2026 worked on brute force solver for GPDL problems.

Location:

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3

Files:

• Attribute.cs (modified) (1 diff)
• AttributedGrammar.cs (modified) (2 diffs)
• Grammar.cs (modified) (3 diffs)
• HeuristicLab.Grammars-3.3.csproj (modified) (1 diff)
• Interfaces/IAttribute.cs (modified) (1 diff)
• Interfaces/ISymbol.cs (modified) (1 diff)
• Language.cs (modified) (4 diffs)
• SemanticSymbol.cs (added)
• Sequence.cs (modified) (2 diffs)
• Symbol.cs (modified) (3 diffs)

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Attribute.cs

@@ -23 +23 @@
 
 namespace HeuristicLab.Grammars {
+  public sealed class AttributeType {
+    public static readonly AttributeType In = new AttributeType("");
+    public static readonly AttributeType Out = new AttributeType("out");
+    public static readonly AttributeType Ref = new AttributeType("ref");
+    private string attributeType;
+    private AttributeType(string attributeType) {
+      this.attributeType = attributeType;
+    }
+
+    public static AttributeType Parse(string attributeType) {
+      if (string.IsNullOrEmpty(attributeType)) return In;
+      else if (attributeType == "ref") return Ref;
+      else if (attributeType == "out") return Out;
+      else throw new ArgumentException("Unknown attribute type string.", attributeType);
+    }
+
+    public override string ToString() {
+      return attributeType;
+    }
+  };
+
   public class Attribute : IAttribute {
     public AttributeType AttributeType { get; private set; }
     public string Type { get; private set; }
     public string Name { get; private set; }
+
+    public Attribute(string name, string type)
+      : this(name, type, AttributeType.In) {
+    }
+
+    public Attribute(string name, string type, AttributeType attributeType) {
+      this.Name = name;
+      this.Type = type;
+      this.AttributeType = attributeType;
+    }
+
+    public override string ToString() {
+      return AttributeType + " " + Type + " " + Name;
+    }
   }
 }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/AttributedGrammar.cs

@@ -24 +24 @@
 using System.Diagnostics;
 using System.Linq;
-using System.Text.RegularExpressions;
 
 namespace HeuristicLab.Grammars {
   public class AttributedGrammar : Grammar {
+    private Dictionary<ISymbol, string> localDefinitions = new Dictionary<ISymbol, string>();
+    private Dictionary<ISymbol, IList<Sequence>> alternatives = new Dictionary<ISymbol, IList<Sequence>>();
+
     public AttributedGrammar(ISymbol startSymbol)
       : base(startSymbol) {
@@ -34 +36 @@
     }
 
-    private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*(?<formPar>\<\w+\>)+\s*->\s*(?<alternative>\w+\s*(?<actPar>\<\w+\>)+(?:\s+\w+\s*(?<actPar>\<\w+\>)+)*)(?:\s*\|\s*(?<alternative>\w+\s*(?<formPar>\<\w+\>)+(?:\s+\w+\s*(?<formPar>\<\w+\>)+)*))*");
-    private static Regex empty = new Regex(@"^\s*$");
-    public static Grammar FromString(string gStr) {
-      var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
-      lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
+    public IEnumerable<Sequence> GetAlternativesWithSemanticActions(ISymbol ntSymbol) {
+      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
+      return alternatives[ntSymbol];
+    }
+    public Sequence GetAlternativeWithSemanticActions(ISymbol ntSymbol, int index) {
+      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
+      return alternatives[ntSymbol][index];
+    }
 
-      // first line is the rule for the start-symbol
-      var m = ruleExpr.Match(lines.First());
-      var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
-      
-      var g = new Grammar(startSymbol);
-      foreach (var alt in m.Groups["alternative"].Captures) {
-        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
+    public override void AddProductionRule(ISymbol ntSymbol, Sequence production) {
+      base.AddProductionRule(ntSymbol, new Sequence(production.Where(symb => !(symb is SemanticSymbol)).ToList()));
+
+      IList<Sequence> list;
+      if (!alternatives.TryGetValue(ntSymbol, out list)) {
+        list = new List<Sequence>();
+        alternatives.Add(ntSymbol, list);
       }
-      foreach (var line in lines.Skip(1)) {
-        m = ruleExpr.Match(line);
-        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
-        foreach (var alt in m.Groups["alternative"].Captures) {
-          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
-        }
-      }
+      // make sure that there is not equivalent production registered already
+      Debug.Assert(!list.Any(s => s.SequenceEqual(production)));
 
-      return g;
+      list.Add(production);
     }
+
+    public void AddLocalDefinitions(ISymbol ntSymbol, string localDefCode) {
+      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
+      Debug.Assert(!localDefinitions.ContainsKey(ntSymbol));
+
+      localDefinitions.Add(ntSymbol, localDefCode);
+    }
+    public string GetLocalDefinitions(ISymbol ntSymbol) {
+      string code;
+      if (localDefinitions.TryGetValue(ntSymbol, out code)) return code;
+      else return string.Empty;
+    }
+
+
+
+    //private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*(?<formPar>\<\w+\>)+\s*->\s*(?<alternative>\w+\s*(?<actPar>\<\w+\>)+(?:\s+\w+\s*(?<actPar>\<\w+\>)+)*)(?:\s*\|\s*(?<alternative>\w+\s*(?<formPar>\<\w+\>)+(?:\s+\w+\s*(?<formPar>\<\w+\>)+)*))*");
+    //private static Regex empty = new Regex(@"^\s*$");
+    //public static Grammar FromString(string gStr) {
+    //  var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
+    //  lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
+
+    //  // first line is the rule for the start-symbol
+    //  var m = ruleExpr.Match(lines.First());
+    //  var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
+
+    //  var g = new Grammar(startSymbol);
+    //  foreach (var alt in m.Groups["alternative"].Captures) {
+    //    g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
+    //  }
+    //  foreach (var line in lines.Skip(1)) {
+    //    m = ruleExpr.Match(line);
+    //    var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
+    //    foreach (var alt in m.Groups["alternative"].Captures) {
+    //      g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
+    //    }
+    //  }
+
+    //  return g;
+    //}
   }
 }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

@@ -54 +54 @@
     }
 
-    public void AddProductionRule(ISymbol ntSymbol, Sequence production) {
+    public virtual void AddProductionRule(ISymbol ntSymbol, Sequence production) {
       Debug.Assert(ntSymbol != EmptySymbol);
 
@@ -96 +96 @@
       var g = new Grammar(startSymbol);
       foreach (var alt in m.Groups["alternative"].Captures) {
-        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
+        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
       }
       foreach (var line in lines.Skip(1)) {
@@ -102 +102 @@
         var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
         foreach (var alt in m.Groups["alternative"].Captures) {
-          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
+          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
         }
       }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj

@@ -105 +105 @@
     <Compile Include="AttributedGrammar.cs" />
     <Compile Include="Attribute.cs" />
+    <Compile Include="SemanticSymbol.cs" />
     <Compile Include="Sequence.cs" />
     <Compile Include="Test.cs" />

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttribute.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+
 namespace HeuristicLab.Grammars {
-  public enum AttributeType { In, Out, Ref };
+
   public interface IAttribute {
     AttributeType AttributeType { get; }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/ISymbol.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
+
 namespace HeuristicLab.Grammars {
   public interface ISymbol {
     string Name { get; }
-    IAttribute Attribute { get; }
+    IEnumerable<IAttribute> Attributes { get; }
+    string GetAttributeString();
   }
 }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Language.cs

@@ -31 +31 @@
   public class Language : IEnumerable<IEnumerable<string>> {
     private class PartiallyProcessedSequence {
-      private Sequence terminalSeq;
+      private List<ISymbol> terminalSeq;
       private Sequence remainingSeq;
       private IGrammar grammar;
@@ -38 +38 @@
       private PartiallyProcessedSequence(PartiallyProcessedSequence parent) {
         this.parent = parent;
-        this.terminalSeq = new Sequence();
+        this.terminalSeq = new List<ISymbol>();
       }
 
       public PartiallyProcessedSequence(Sequence seq, IGrammar g) {
-        this.terminalSeq = new Sequence();
+        this.terminalSeq = new List<ISymbol>();
         this.remainingSeq = seq;
         this.grammar = g;
@@ -59 +59 @@
           ntSymbol = enumerator.Current;
 
-          remainingSeq = new Sequence(remainingSeq.Skip(i + 1));
+          remainingSeq = new Sequence(remainingSeq.Skip(i + 1).ToList());
           return true;
         }
@@ -66 +66 @@
         var p = new PartiallyProcessedSequence(this);
         p.grammar = grammar;
-        p.remainingSeq = new Sequence(seq.Concat(remainingSeq));
+        p.remainingSeq = new Sequence(seq.Concat(remainingSeq).ToList());
         return p;
       }
-      public Sequence GetSequence() {
+      public IList<ISymbol> GetSequence() {
         if (parent == null) return terminalSeq;
         else {
-          return new Sequence(parent.GetSequence().Concat(terminalSeq));
+          return new Sequence(parent.GetSequence().Concat(terminalSeq).ToList());
         }
       }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Sequence.cs

@@ -21 +21 @@
 
 using System.Collections.Generic;
+using System.Collections.ObjectModel;
 using System.Linq;
 using System.Text;
 
 namespace HeuristicLab.Grammars {
-  public class Sequence : List<ISymbol> {
-    public Sequence()
-      : base() {
-    }
-
-    public Sequence(IEnumerable<ISymbol> seq)
-      : base() {
-      this.AddRange(seq);
-    }
-    public IEnumerator<ISymbol> GetEnumerator() {
-      return (IEnumerator<ISymbol>)base.GetEnumerator();
+  public class Sequence : ReadOnlyCollection<ISymbol> {
+    public Sequence(IList<ISymbol> seq)
+      : base(seq) {
     }
 
@@ -50 +43 @@
 
     public override string ToString() {
-      var b = new StringBuilder();
-      ForEach(s => b.AppendFormat("{0} ", s));
-      return b.ToString();
+      return this.Aggregate("", (str, symb) => str + symb);
     }
   }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Symbol.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
+using System.Linq;
+
 namespace HeuristicLab.Grammars {
-  public class Symbol : ISymbol, IEquatable<ISymbol> {
+  public class Symbol : ISymbol {
     public string Name { get; private set; }
-    public IAttribute Attribute { get; private set; }
-    public Symbol(string name, IAttribute attribute = null) {
+    public IEnumerable<IAttribute> Attributes { get; private set; }
+    public Symbol(string name, IEnumerable<IAttribute> attributes = null) {
       this.Name = name;
-      this.Attribute = attribute;
+      if (attributes != null) this.Attributes = attributes;
+      else this.Attributes = Enumerable.Empty<IAttribute>();
     }
 
-    public bool Equals(ISymbol other) {
-      return Name == other.Name;
+    public string GetAttributeString() {
+      if (!Attributes.Any()) return string.Empty;
+      return Attributes.Skip(1).Aggregate(Attributes.First().ToString(), (str, a) => str + ", " + a.ToString());
     }
 
@@ -37 +42 @@
       if (obj == null) return false;
       if (obj == this) return true;
-      var other = obj as ISymbol;
+      var other = obj as Symbol;
       if (other == null) return false;
-      return Equals(other);
+      return this.Name == other.Name; // compare names only
     }
 
@@ -45 +50 @@
       return Name.GetHashCode();
     }
+
+    public override string ToString() {
+      return Name + "<" + GetAttributeString() + ">";
+    }
   }
 }