Changeset 10051

Timestamp:

10/17/13 15:19:45 (11 years ago)

Author:

gkronber

Message:

#2026 worked on a plugin for grammars (work-in-progress)

Location:

branches/HeuristicLab.Problems.GPDL

Files:

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

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

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text.RegularExpressions;
 
 namespace HeuristicLab.Grammars {
-  using Sequence = IEnumerable<string>;
+  public class Grammar : IGrammar {
+    public static readonly ISymbol EmptySymbol = new Symbol("EPS");
+    private Dictionary<ISymbol, List<Sequence>> rules = new Dictionary<ISymbol, List<Sequence>>();
+    private HashSet<ISymbol> allSymbols = new HashSet<ISymbol>();
 
-  public class Grammar : IGrammar {
-    private Dictionary<string, List<Sequence>> rules = new Dictionary<string, List<Sequence>>();
-    private HashSet<string> allSymbols = new HashSet<string>();
+    public ISymbol StartSymbol { get; set; }
+    public IEnumerable<ISymbol> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
+    public IEnumerable<ISymbol> NonTerminalSymbols { get { return rules.Keys; } }
+    public IEnumerable<ISymbol> Symbols { get { return allSymbols; } }
 
-    public string StartSymbol { get; set; }
-    public IEnumerable<string> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
-    public IEnumerable<string> NonTerminalSymbols { get { return rules.Keys; } }
-    public IEnumerable<string> Symbols { get { return allSymbols; } }
-
-    public Grammar(string startSymbol) {
+    public Grammar(ISymbol startSymbol) {
+      Debug.Assert(startSymbol != EmptySymbol);
       this.StartSymbol = startSymbol;
     }
 
-    public int NumberOfAlternatives(string ntSymbol) {
+    public int NumberOfAlternatives(ISymbol ntSymbol) {
       return rules[ntSymbol].Count;
     }
 
-    public IEnumerable<Sequence> GetAlternatives(string ntSymbol) {
+    public IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol) {
       return rules[ntSymbol].AsReadOnly();
     }
 
-    public Sequence GetAlternative(string ntSymbol, int index) {
+    public Sequence GetAlternative(ISymbol ntSymbol, int index) {
       return rules[ntSymbol][index];
     }
 
-    public void AddProductionRule(string ntSymbol, Sequence production) {
+    public void AddProductionRule(ISymbol ntSymbol, Sequence production) {
+      Debug.Assert(ntSymbol != EmptySymbol);
+
       List<Sequence> l;
       if (!rules.TryGetValue(ntSymbol, out l)) {
@@ -61 +64 @@
         allSymbols.Add(ntSymbol); // register new nt-symbol
       }
+      // check if the same production exists already
+      Debug.Assert(!l.Any(s => s.SequenceEqual(production)));
+
       l.Add(production);
 
@@ -66 +72 @@
     }
 
+    public bool IsTerminal(ISymbol symbol) {
+      return !rules.ContainsKey(symbol) && allSymbols.Contains(symbol);
+    }
+    public bool IsNonTerminal(ISymbol symbol) {
+      return rules.ContainsKey(symbol);
+    }
+
+    // checks if a rule exists for each NT symbol
+    public bool IsComplete() {
+      return rules.ContainsKey(StartSymbol) &&
+             NonTerminalSymbols.All(nt => rules.ContainsKey(nt));
+    }
+
     private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*->\s*(?<alternative>\w+(?:\s+\w+)*)(?:\s*\|\s*(?<alternative>\w+(?:\s+\w+)*))*");
     private static Regex empty = new Regex(@"^\s*$");
-    public static IGrammar FromString(string gStr) {
+    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
@@ -74 +93 @@
       // first line is the rule for the start-symbol
       var m = ruleExpr.Match(lines.First());
-      var startSymbol = m.Groups["ntSymbol"].Value;
+      var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
       var g = new Grammar(startSymbol);
       foreach (var alt in m.Groups["alternative"].Captures) {
-        g.AddProductionRule(startSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
+        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 = m.Groups["ntSymbol"].Value;
+        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
         foreach (var alt in m.Groups["alternative"].Captures) {
-          g.AddProductionRule(ntSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
+          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/HeuristicLab.Grammars-3.3.csproj

@@ -7 +7 @@
     <SchemaVersion>2.0</SchemaVersion>
     <ProjectGuid>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</ProjectGuid>
-    <OutputType>Library</OutputType>
+    <OutputType>Exe</OutputType>
     <AppDesignerFolder>Properties</AppDesignerFolder>
     <RootNamespace>HeuristicLab.Grammars</RootNamespace>
@@ -93 +93 @@
     <CodeAnalysisRuleSet>AllRules.ruleset</CodeAnalysisRuleSet>
   </PropertyGroup>
+  <PropertyGroup>
+    <StartupObject />
+  </PropertyGroup>
   <ItemGroup>
     <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
@@ -115 +118 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="AttributedGrammar.cs" />
+    <Compile Include="Attribute.cs" />
+    <Compile Include="Sequence.cs" />
+    <Compile Include="Test.cs" />
+    <Compile Include="Symbol.cs" />
+    <Compile Include="Language.cs" />
     <Compile Include="Grammar.cs" />
     <Compile Include="Interfaces\IAttribute.cs" />
-    <Compile Include="Interfaces\IAttributedGrammar.cs" />
     <Compile Include="Interfaces\ISymbol.cs" />
     <Compile Include="Interfaces\IGrammar.cs" />

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

@@ -22 +22 @@
 namespace HeuristicLab.Grammars {
   public enum AttributeType { In, Out, Ref };
-  interface IAttribute {
+  public interface IAttribute {
     AttributeType AttributeType { get; }
     string Type { get; }

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

@@ -24 +24 @@
 namespace HeuristicLab.Grammars {
   interface IAttributedGrammar : IGrammar {
-    IEnumerable<IAttribute> GetAttributes(string symbol);
-    void AddAttribute(string symbol, IAttribute attribute);
+    ISymbol StartSymbol { get; set; }
+    IEnumerable<ISymbol> TerminalSymbols { get; }
+    IEnumerable<ISymbol> NonTerminalSymbols { get; }
+    IEnumerable<ISymbol> Symbols { get; }
+    bool IsTerminal(ISymbol symbol);
+    bool IsNonTerminal(ISymbol symbol);
+
+    int NumberOfAlternatives(ISymbol ntSymbol);
+    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
+    Sequence GetAlternative(ISymbol ntSymbol, int index);
+
+    void AddProductionRule(ISymbol ntSymbol, Sequence production);
   }
 }

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

@@ -23 +23 @@
 
 namespace HeuristicLab.Grammars {
-  using Sequence = IEnumerable<string>;
 
   public interface IGrammar {
-    string StartSymbol { get; set; }
-    IEnumerable<string> TerminalSymbols { get; }
-    IEnumerable<string> NonTerminalSymbols { get; }
-    IEnumerable<string> Symbols { get; }
+    ISymbol StartSymbol { get; set; }
+    IEnumerable<ISymbol> TerminalSymbols { get; }
+    IEnumerable<ISymbol> NonTerminalSymbols { get; }
+    IEnumerable<ISymbol> Symbols { get; }
+    bool IsTerminal(ISymbol symbol);
+    bool IsNonTerminal(ISymbol symbol);
 
-    int NumberOfAlternatives(string ntSymbol);
-    IEnumerable<Sequence> GetAlternatives(string ntSymbol);
-    Sequence GetAlternative(string ntSymbol, int index);
+    int NumberOfAlternatives(ISymbol ntSymbol);
+    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
+    Sequence GetAlternative(ISymbol ntSymbol, int index);
 
-    void AddProductionRule(string ntSymbol, Sequence production);
+    void AddProductionRule(ISymbol ntSymbol, Sequence production);
   }
 }

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

@@ -20 +20 @@
 #endregion
 
-/*
 namespace HeuristicLab.Grammars {
-  interface ISymbol {
+  public interface ISymbol {
     string Name { get; }
-    bool IsTerminal { get; }
+    IAttribute Attribute { get; }
   }
 }
-*/

branches/HeuristicLab.Problems.GPDL/Test/Test.csproj

@@ -22 +22 @@
     <DebugType>full</DebugType>
     <Optimize>false</Optimize>
-    <OutputPath>..\trunk\sources\bin\</OutputPath>
+    <OutputPath>..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>DEBUG;TRACE</DefineConstants>
     <ErrorReport>prompt</ErrorReport>
@@ -128 +128 @@
       <Name>HeuristicLab.Grammars-3.3</Name>
     </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GPDL.CodeGen\3.4\HeuristicLab.Problems.GPDL.CodeGen-3.4.csproj">
+      <Project>{F8481248-2A5B-48A0-A485-D3E1619C1E44}</Project>
+      <Name>HeuristicLab.Problems.GPDL.CodeGen-3.4</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GPDL.Views\3.4\HeuristicLab.Problems.GPDL.Views-3.4.csproj">
       <Project>{3f9e665a-3dcb-49c3-8806-0e47fc48ea52}</Project>

branches/HeuristicLab.Problems.GPDL/Test/TestGpdlExamples.cs

@@ -27 +27 @@
 using HeuristicLab.Algorithms.GeneticAlgorithm;
 using HeuristicLab.Problems.GPDL;
+using HeuristicLab.Problems.GPDL.CodeGen;
 using HeuristicLab.Problems.GPDL.Views;
 using HeuristicLab.SequentialEngine;
@@ -41 +42 @@
         Parser parser = new Parser(scanner);
         parser.Parse();
-        Assert.IsNotNull(parser.problem);
+        Assert.IsNotNull(parser.AbstractSyntaxTree);
 
         // test: run one generation
@@ -48 +49 @@
         ga.PopulationSize.Value = 100;
         ga.MaximumGenerations.Value = 1;
-        ga.Problem = parser.problem;
+
+        var problemGenerator = new ProblemGenerator();
+        ga.Problem = problemGenerator.GenerateFromAst(parser.AbstractSyntaxTree);
 
         var wh = new AutoResetEvent(false);

branches/HeuristicLab.Problems.GPDL/Test/TestGrammar.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Linq;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -31 +33 @@
         @"S -> A
           A->a B
-          B ->S b | S a|B b 
-          B-> a  aa   aaa
+          B ->S b | S a|C b 
+          C-> a  aa   aaa
          ";
       var g = HeuristicLab.Grammars.Grammar.FromString(gStr);
-      Assert.AreEqual(g.StartSymbol, "S");
+      Assert.AreEqual(g.StartSymbol, new Symbol("S"));
       Assert.AreEqual(g.TerminalSymbols.Count(), 4);
-      Assert.AreEqual(g.NonTerminalSymbols.Count(), 3);
-      Assert.IsTrue(g.TerminalSymbols.Contains("aaa"));
-      Assert.IsTrue(g.TerminalSymbols.Contains("aa"));
-      Assert.IsTrue(g.NonTerminalSymbols.Contains("S"));
-      Assert.IsTrue(g.NonTerminalSymbols.Contains("B"));
-      Assert.IsTrue(g.NonTerminalSymbols.Contains("A"));
+      Assert.AreEqual(g.NonTerminalSymbols.Count(), 4);
+      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aaa")));
+      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aa")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("S")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("B")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("C")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("A")));
+    }
+
+
+    [TestMethod]
+    public void TestAttributedGrammar() {
+      var gStr =
+        @"S -> A
+          A<int a0, out int a1>->a B<a0, a1>
+          B<int a0, ref int a1> ->S b | S a|C<a0, a1> b 
+          C<int a0, ref int a1> -> a  aa   aaa
+         ";
+      var g = HeuristicLab.Grammars.AttributedGrammar.FromString(gStr);
+      Assert.AreEqual(g.StartSymbol, new Symbol("S"));
+      Assert.AreEqual(g.TerminalSymbols.Count(), 4);
+      Assert.AreEqual(g.NonTerminalSymbols.Count(), 4);
+      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aaa")));
+      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aa")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("S")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("B")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("A")));
+      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("C")));
+    }
+
+
+    [TestMethod]
+    public void TestLanguage() {
+      var gStr =
+        @"S -> a B | b A
+          A-> a | a S | b A A 
+          B -> b | b S | a B B
+         ";
+      var g = HeuristicLab.Grammars.Grammar.FromString(gStr);
+      var l = new Language(g);
+      var s2 = new string[][]
+        {
+          new string[] {"a", "b"},
+          new string[] {"b", "a"}
+        };
+      var s4 = new string[][]
+        {
+          new [] {"a", "a", "b", "b"},
+          new [] {"a", "b", "a", "b"},
+          new [] {"a", "b", "b", "a"},
+          new [] {"b", "b", "a", "a"},
+          new [] {"b", "a", "b", "a"},
+          new [] {"b", "a", "a", "b"}
+        };
+
+
+      var l2 = l.Where(s => s.Count() == 2).Take(2);
+      var l4 = l.Where(s => s.Count() == 4).Take(6);
+
+      Assert.IsTrue(l2.Intersect(s2, new SequenceComparer()).Count() == l2.Count());
+      Assert.IsTrue(l4.Intersect(s4, new SequenceComparer()).Count() == l4.Count());
+    }
+  }
+
+  public class SequenceComparer : IEqualityComparer<IEnumerable<string>> {
+    public bool Equals(IEnumerable<string> x, IEnumerable<string> y) {
+      return x.Count() == y.Count() &&
+        x.Zip(y, (s, t) => s == t).All(eq => eq);
+    }
+
+    public int GetHashCode(IEnumerable<string> obj) {
+      if (!obj.Any()) return 0;
+      else return obj.First().GetHashCode();
     }
   }