Changeset 10051


Ignore:
Timestamp:
10/17/13 15:19:45 (7 years ago)
Author:
gkronber
Message:

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

Location:
branches/HeuristicLab.Problems.GPDL
Files:
6 added
9 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

    r10031 r10051  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Diagnostics;
    2425using System.Linq;
    2526using System.Text.RegularExpressions;
    2627
    2728namespace HeuristicLab.Grammars {
    28   using Sequence = IEnumerable<string>;
     29  public class Grammar : IGrammar {
     30    public static readonly ISymbol EmptySymbol = new Symbol("EPS");
     31    private Dictionary<ISymbol, List<Sequence>> rules = new Dictionary<ISymbol, List<Sequence>>();
     32    private HashSet<ISymbol> allSymbols = new HashSet<ISymbol>();
    2933
    30   public class Grammar : IGrammar {
    31     private Dictionary<string, List<Sequence>> rules = new Dictionary<string, List<Sequence>>();
    32     private HashSet<string> allSymbols = new HashSet<string>();
     34    public ISymbol StartSymbol { get; set; }
     35    public IEnumerable<ISymbol> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
     36    public IEnumerable<ISymbol> NonTerminalSymbols { get { return rules.Keys; } }
     37    public IEnumerable<ISymbol> Symbols { get { return allSymbols; } }
    3338
    34     public string StartSymbol { get; set; }
    35     public IEnumerable<string> TerminalSymbols { get { return allSymbols.Except(NonTerminalSymbols); } }
    36     public IEnumerable<string> NonTerminalSymbols { get { return rules.Keys; } }
    37     public IEnumerable<string> Symbols { get { return allSymbols; } }
    38 
    39     public Grammar(string startSymbol) {
     39    public Grammar(ISymbol startSymbol) {
     40      Debug.Assert(startSymbol != EmptySymbol);
    4041      this.StartSymbol = startSymbol;
    4142    }
    4243
    43     public int NumberOfAlternatives(string ntSymbol) {
     44    public int NumberOfAlternatives(ISymbol ntSymbol) {
    4445      return rules[ntSymbol].Count;
    4546    }
    4647
    47     public IEnumerable<Sequence> GetAlternatives(string ntSymbol) {
     48    public IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol) {
    4849      return rules[ntSymbol].AsReadOnly();
    4950    }
    5051
    51     public Sequence GetAlternative(string ntSymbol, int index) {
     52    public Sequence GetAlternative(ISymbol ntSymbol, int index) {
    5253      return rules[ntSymbol][index];
    5354    }
    5455
    55     public void AddProductionRule(string ntSymbol, Sequence production) {
     56    public void AddProductionRule(ISymbol ntSymbol, Sequence production) {
     57      Debug.Assert(ntSymbol != EmptySymbol);
     58
    5659      List<Sequence> l;
    5760      if (!rules.TryGetValue(ntSymbol, out l)) {
     
    6164        allSymbols.Add(ntSymbol); // register new nt-symbol
    6265      }
     66      // check if the same production exists already
     67      Debug.Assert(!l.Any(s => s.SequenceEqual(production)));
     68
    6369      l.Add(production);
    6470
     
    6672    }
    6773
     74    public bool IsTerminal(ISymbol symbol) {
     75      return !rules.ContainsKey(symbol) && allSymbols.Contains(symbol);
     76    }
     77    public bool IsNonTerminal(ISymbol symbol) {
     78      return rules.ContainsKey(symbol);
     79    }
     80
     81    // checks if a rule exists for each NT symbol
     82    public bool IsComplete() {
     83      return rules.ContainsKey(StartSymbol) &&
     84             NonTerminalSymbols.All(nt => rules.ContainsKey(nt));
     85    }
     86
    6887    private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*->\s*(?<alternative>\w+(?:\s+\w+)*)(?:\s*\|\s*(?<alternative>\w+(?:\s+\w+)*))*");
    6988    private static Regex empty = new Regex(@"^\s*$");
    70     public static IGrammar FromString(string gStr) {
     89    public static Grammar FromString(string gStr) {
    7190      var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
    7291      lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
     
    7493      // first line is the rule for the start-symbol
    7594      var m = ruleExpr.Match(lines.First());
    76       var startSymbol = m.Groups["ntSymbol"].Value;
     95      var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    7796      var g = new Grammar(startSymbol);
    7897      foreach (var alt in m.Groups["alternative"].Captures) {
    79         g.AddProductionRule(startSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
     98        g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
    8099      }
    81100      foreach (var line in lines.Skip(1)) {
    82101        m = ruleExpr.Match(line);
    83         var ntSymbol = m.Groups["ntSymbol"].Value;
     102        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    84103        foreach (var alt in m.Groups["alternative"].Captures) {
    85           g.AddProductionRule(ntSymbol, alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries));
     104          g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
    86105        }
    87106      }
     107
    88108      return g;
    89109    }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/HeuristicLab.Grammars-3.3.csproj

    r10031 r10051  
    77    <SchemaVersion>2.0</SchemaVersion>
    88    <ProjectGuid>{A5452B63-B33B-4F9F-9E81-98B75EDB5612}</ProjectGuid>
    9     <OutputType>Library</OutputType>
     9    <OutputType>Exe</OutputType>
    1010    <AppDesignerFolder>Properties</AppDesignerFolder>
    1111    <RootNamespace>HeuristicLab.Grammars</RootNamespace>
     
    9393    <CodeAnalysisRuleSet>AllRules.ruleset</CodeAnalysisRuleSet>
    9494  </PropertyGroup>
     95  <PropertyGroup>
     96    <StartupObject />
     97  </PropertyGroup>
    9598  <ItemGroup>
    9699    <Reference Include="HeuristicLab.PluginInfrastructure-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     
    115118  </ItemGroup>
    116119  <ItemGroup>
     120    <Compile Include="AttributedGrammar.cs" />
     121    <Compile Include="Attribute.cs" />
     122    <Compile Include="Sequence.cs" />
     123    <Compile Include="Test.cs" />
     124    <Compile Include="Symbol.cs" />
     125    <Compile Include="Language.cs" />
    117126    <Compile Include="Grammar.cs" />
    118127    <Compile Include="Interfaces\IAttribute.cs" />
    119     <Compile Include="Interfaces\IAttributedGrammar.cs" />
    120128    <Compile Include="Interfaces\ISymbol.cs" />
    121129    <Compile Include="Interfaces\IGrammar.cs" />
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttribute.cs

    r10031 r10051  
    2222namespace HeuristicLab.Grammars {
    2323  public enum AttributeType { In, Out, Ref };
    24   interface IAttribute {
     24  public interface IAttribute {
    2525    AttributeType AttributeType { get; }
    2626    string Type { get; }
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IAttributedGrammar.cs

    r10031 r10051  
    2424namespace HeuristicLab.Grammars {
    2525  interface IAttributedGrammar : IGrammar {
    26     IEnumerable<IAttribute> GetAttributes(string symbol);
    27     void AddAttribute(string symbol, IAttribute attribute);
     26    ISymbol StartSymbol { get; set; }
     27    IEnumerable<ISymbol> TerminalSymbols { get; }
     28    IEnumerable<ISymbol> NonTerminalSymbols { get; }
     29    IEnumerable<ISymbol> Symbols { get; }
     30    bool IsTerminal(ISymbol symbol);
     31    bool IsNonTerminal(ISymbol symbol);
     32
     33    int NumberOfAlternatives(ISymbol ntSymbol);
     34    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
     35    Sequence GetAlternative(ISymbol ntSymbol, int index);
     36
     37    void AddProductionRule(ISymbol ntSymbol, Sequence production);
    2838  }
    2939}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/IGrammar.cs

    r10031 r10051  
    2323
    2424namespace HeuristicLab.Grammars {
    25   using Sequence = IEnumerable<string>;
    2625
    2726  public interface IGrammar {
    28     string StartSymbol { get; set; }
    29     IEnumerable<string> TerminalSymbols { get; }
    30     IEnumerable<string> NonTerminalSymbols { get; }
    31     IEnumerable<string> Symbols { get; }
     27    ISymbol StartSymbol { get; set; }
     28    IEnumerable<ISymbol> TerminalSymbols { get; }
     29    IEnumerable<ISymbol> NonTerminalSymbols { get; }
     30    IEnumerable<ISymbol> Symbols { get; }
     31    bool IsTerminal(ISymbol symbol);
     32    bool IsNonTerminal(ISymbol symbol);
    3233
    33     int NumberOfAlternatives(string ntSymbol);
    34     IEnumerable<Sequence> GetAlternatives(string ntSymbol);
    35     Sequence GetAlternative(string ntSymbol, int index);
     34    int NumberOfAlternatives(ISymbol ntSymbol);
     35    IEnumerable<Sequence> GetAlternatives(ISymbol ntSymbol);
     36    Sequence GetAlternative(ISymbol ntSymbol, int index);
    3637
    37     void AddProductionRule(string ntSymbol, Sequence production);
     38    void AddProductionRule(ISymbol ntSymbol, Sequence production);
    3839  }
    3940}
  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Interfaces/ISymbol.cs

    r10031 r10051  
    2020#endregion
    2121
    22 /*
    2322namespace HeuristicLab.Grammars {
    24   interface ISymbol {
     23  public interface ISymbol {
    2524    string Name { get; }
    26     bool IsTerminal { get; }
     25    IAttribute Attribute { get; }
    2726  }
    2827}
    29 */
  • branches/HeuristicLab.Problems.GPDL/Test/Test.csproj

    r10031 r10051  
    2222    <DebugType>full</DebugType>
    2323    <Optimize>false</Optimize>
    24     <OutputPath>..\trunk\sources\bin\</OutputPath>
     24    <OutputPath>..\..\..\trunk\sources\bin\</OutputPath>
    2525    <DefineConstants>DEBUG;TRACE</DefineConstants>
    2626    <ErrorReport>prompt</ErrorReport>
     
    128128      <Name>HeuristicLab.Grammars-3.3</Name>
    129129    </ProjectReference>
     130    <ProjectReference Include="..\HeuristicLab.Problems.GPDL.CodeGen\3.4\HeuristicLab.Problems.GPDL.CodeGen-3.4.csproj">
     131      <Project>{F8481248-2A5B-48A0-A485-D3E1619C1E44}</Project>
     132      <Name>HeuristicLab.Problems.GPDL.CodeGen-3.4</Name>
     133    </ProjectReference>
    130134    <ProjectReference Include="..\HeuristicLab.Problems.GPDL.Views\3.4\HeuristicLab.Problems.GPDL.Views-3.4.csproj">
    131135      <Project>{3f9e665a-3dcb-49c3-8806-0e47fc48ea52}</Project>
  • branches/HeuristicLab.Problems.GPDL/Test/TestGpdlExamples.cs

    r9846 r10051  
    2727using HeuristicLab.Algorithms.GeneticAlgorithm;
    2828using HeuristicLab.Problems.GPDL;
     29using HeuristicLab.Problems.GPDL.CodeGen;
    2930using HeuristicLab.Problems.GPDL.Views;
    3031using HeuristicLab.SequentialEngine;
     
    4142        Parser parser = new Parser(scanner);
    4243        parser.Parse();
    43         Assert.IsNotNull(parser.problem);
     44        Assert.IsNotNull(parser.AbstractSyntaxTree);
    4445
    4546        // test: run one generation
     
    4849        ga.PopulationSize.Value = 100;
    4950        ga.MaximumGenerations.Value = 1;
    50         ga.Problem = parser.problem;
     51
     52        var problemGenerator = new ProblemGenerator();
     53        ga.Problem = problemGenerator.GenerateFromAst(parser.AbstractSyntaxTree);
    5154
    5255        var wh = new AutoResetEvent(false);
  • branches/HeuristicLab.Problems.GPDL/Test/TestGrammar.cs

    r10031 r10051  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using System.Linq;
    2325using Microsoft.VisualStudio.TestTools.UnitTesting;
     
    3133        @"S -> A
    3234          A->a B
    33           B ->S b | S a|B b
    34           B-> a  aa   aaa
     35          B ->S b | S a|C b
     36          C-> a  aa   aaa
    3537         ";
    3638      var g = HeuristicLab.Grammars.Grammar.FromString(gStr);
    37       Assert.AreEqual(g.StartSymbol, "S");
     39      Assert.AreEqual(g.StartSymbol, new Symbol("S"));
    3840      Assert.AreEqual(g.TerminalSymbols.Count(), 4);
    39       Assert.AreEqual(g.NonTerminalSymbols.Count(), 3);
    40       Assert.IsTrue(g.TerminalSymbols.Contains("aaa"));
    41       Assert.IsTrue(g.TerminalSymbols.Contains("aa"));
    42       Assert.IsTrue(g.NonTerminalSymbols.Contains("S"));
    43       Assert.IsTrue(g.NonTerminalSymbols.Contains("B"));
    44       Assert.IsTrue(g.NonTerminalSymbols.Contains("A"));
     41      Assert.AreEqual(g.NonTerminalSymbols.Count(), 4);
     42      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aaa")));
     43      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aa")));
     44      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("S")));
     45      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("B")));
     46      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("C")));
     47      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("A")));
     48    }
     49
     50
     51    [TestMethod]
     52    public void TestAttributedGrammar() {
     53      var gStr =
     54        @"S -> A
     55          A<int a0, out int a1>->a B<a0, a1>
     56          B<int a0, ref int a1> ->S b | S a|C<a0, a1> b
     57          C<int a0, ref int a1> -> a  aa   aaa
     58         ";
     59      var g = HeuristicLab.Grammars.AttributedGrammar.FromString(gStr);
     60      Assert.AreEqual(g.StartSymbol, new Symbol("S"));
     61      Assert.AreEqual(g.TerminalSymbols.Count(), 4);
     62      Assert.AreEqual(g.NonTerminalSymbols.Count(), 4);
     63      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aaa")));
     64      Assert.IsTrue(g.TerminalSymbols.Contains(new Symbol("aa")));
     65      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("S")));
     66      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("B")));
     67      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("A")));
     68      Assert.IsTrue(g.NonTerminalSymbols.Contains(new Symbol("C")));
     69    }
     70
     71
     72    [TestMethod]
     73    public void TestLanguage() {
     74      var gStr =
     75        @"S -> a B | b A
     76          A-> a | a S | b A A
     77          B -> b | b S | a B B
     78         ";
     79      var g = HeuristicLab.Grammars.Grammar.FromString(gStr);
     80      var l = new Language(g);
     81      var s2 = new string[][]
     82        {
     83          new string[] {"a", "b"},
     84          new string[] {"b", "a"}
     85        };
     86      var s4 = new string[][]
     87        {
     88          new [] {"a", "a", "b", "b"},
     89          new [] {"a", "b", "a", "b"},
     90          new [] {"a", "b", "b", "a"},
     91          new [] {"b", "b", "a", "a"},
     92          new [] {"b", "a", "b", "a"},
     93          new [] {"b", "a", "a", "b"}
     94        };
     95
     96
     97      var l2 = l.Where(s => s.Count() == 2).Take(2);
     98      var l4 = l.Where(s => s.Count() == 4).Take(6);
     99
     100      Assert.IsTrue(l2.Intersect(s2, new SequenceComparer()).Count() == l2.Count());
     101      Assert.IsTrue(l4.Intersect(s4, new SequenceComparer()).Count() == l4.Count());
     102    }
     103  }
     104
     105  public class SequenceComparer : IEqualityComparer<IEnumerable<string>> {
     106    public bool Equals(IEnumerable<string> x, IEnumerable<string> y) {
     107      return x.Count() == y.Count() &&
     108        x.Zip(y, (s, t) => s == t).All(eq => eq);
     109    }
     110
     111    public int GetHashCode(IEnumerable<string> obj) {
     112      if (!obj.Any()) return 0;
     113      else return obj.First().GetHashCode();
    45114    }
    46115  }
Note: See TracChangeset for help on using the changeset viewer.