Changeset 10086 for branches

Timestamp:

10/27/13 20:17:17 (10 years ago)

Author:

gkronber

Message:

#2026 worked on random search solver (now all examples are working)

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/BruteForceCodeGen.cs (modified) (6 diffs)
• CodeGenerator/RandomSearchCodeGen.cs (modified) (15 diffs)
• Examples/symbreg HEAL.txt (modified) (5 diffs)
• Examples/symbreg Koza.txt (modified) (7 diffs)
• HeuristicLab.Grammars/3.3/AttributedGrammar.cs (modified) (3 diffs)
• HeuristicLab.Grammars/3.3/Grammar.cs (modified) (4 diffs)
• HeuristicLab.Problems.GPDL.sln (modified) (2 diffs)
• TestExamples.bat (added)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

@@ -81 +81 @@
             nextAlternative = (nextAlternative + 1) % subTrees.Length;
           } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
-
-          // from the nodes which are not done take the first with minimum count
-          //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
-          //                   where subTrees[i] == null || !subTrees[i].Done
-          //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
-          //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
         } else {
           // for sequenceNodes update all sub-trees
@@ -177 +171 @@
 
     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
+
+      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
+      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
       string startSymbolName = ast.Rules.First().NtSymbol;
-      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
+
       // create startSymbol
-      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
+      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
+      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
+
+      // add all production rules
       foreach (var rule in ast.Rules) {
-        // create nt-symbol
-        var ntSymbolName = rule.NtSymbol;
-        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
-        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
-        var ntSymbol = new Symbol(ntSymbolName, attributes);
-        foreach (var alt in GetAlternatives(rule.Alternatives)) {
+        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
+        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
           g.AddProductionRule(ntSymbol, alt);
         }
@@ -196 +192 @@
     }
 
-    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
+    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
       return (from fieldDef in Util.ExtractParameters(formalParameters)
               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
@@ -202 +198 @@
     }
 
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
       foreach (var alt in altNode.Alternatives) {
-        yield return GetSequence(alt.Sequence);
-      }
-    }
-
-    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
+        yield return GetSequence(alt.Sequence, allSymbols);
+      }
+    }
+
+    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
       Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
       var l = new List<ISymbol>();
@@ -215 +211 @@
         var actionNode = node as RuleActionNode;
         if (callSymbolNode != null) {
-          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
+          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
+          // create a new symbol with actual parameters
+          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
         } else if (actionNode != null) {
           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
@@ -313 +311 @@
 
       // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
-      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
+      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
+        .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
 
       if (altsWithSemActions.Length > 1) {

branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

@@ -20 +20 @@
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
+    public sealed class SolverState {
+      private int currentSeed;
+      public Random random;
+      public int depth;
+      public int steps;
+      public int maxDepth;
+      public SolverState(int seed) {
+        this.currentSeed = seed;
+      }
+
+      public SolverState IncDepth() {
+        depth++;
+        if(depth>maxDepth) maxDepth = depth;
+        return this;
+      }
+      public SolverState Prepare() {
+        this.random = new Random(currentSeed);
+        depth = 0;
+        maxDepth = 0;
+        steps = 0;
+        return this;
+      }
+    }
 
     public static void Main(string[] args) {
@@ -38 +61 @@
     }
 
-
-    private Random seedRandom;
-    private int currentSeed;
+    private double TerminalProbForDepth(int depth) {
+      const double baseProb = 0.05;  // 5% of all samples are only a terminal node
+      const double probIncPerLevel = 0.05; // for each level the probability to sample a terminal grows by 5%
+      return baseProb + depth * probIncPerLevel;
+    }
+
+    private SolverState _state;
     private void Start() {
-      seedRandom = new Random();
+      var seedRandom = new Random();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
@@ -51 +78 @@
         // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
         // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
-        currentSeed = seedRandom.Next();
+        
+        _state = new SolverState(seedRandom.Next());
+
         var f = Calculate();
 
         n++;
-        if (IsBetter(f, bestF)) bestF = f;
-        if (n % 100 == 0) {
+        if (IsBetter(f, bestF)) {
+          bestF = f;
+          Console.WriteLine(""{0}\t{1}\t(depth={2})"", n, bestF, _state.maxDepth);
+        }
+        if (n % 1000 == 0) {
           sw.Stop();
-          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
+          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 1000.0 / sw.ElapsedMilliseconds);
           sw.Reset();
           sw.Start();
@@ -112 +144 @@
     }
 
+    #region create grammar instance from AST
     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
+
+      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
+      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
       string startSymbolName = ast.Rules.First().NtSymbol;
-      var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
+
       // create startSymbol
-      var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
+      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
+      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
+
+      // add all production rules
       foreach (var rule in ast.Rules) {
-        // create nt-symbol
-        var ntSymbolName = rule.NtSymbol;
-        var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
-        var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
-        var ntSymbol = new Symbol(ntSymbolName, attributes);
-        foreach (var alt in GetAlternatives(rule.Alternatives)) {
+        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
+        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
           g.AddProductionRule(ntSymbol, alt);
         }
@@ -132 +167 @@
     }
 
-    private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
+    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
       return (from fieldDef in Util.ExtractParameters(formalParameters)
               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
@@ -138 +173 @@
     }
 
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
       foreach (var alt in altNode.Alternatives) {
-        yield return GetSequence(alt.Sequence);
-      }
-    }
-
-    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
+        yield return GetSequence(alt.Sequence, allSymbols);
+      }
+    }
+
+    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
       Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
       var l = new List<ISymbol>();
@@ -151 +186 @@
         var actionNode = node as RuleActionNode;
         if (callSymbolNode != null) {
-          l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
+          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
+          // create a new symbol with actual parameters
+          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
         } else if (actionNode != null) {
           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
@@ -158 +195 @@
       return new Sequence(l);
     }
-
+    #endregion
+
+    #region helper methods for terminal symbols
     // produces helper methods for the attributes of all terminal nodes
     private string GenerateConstraintMethods(List<SymbolNode> symbols) {
@@ -177 +216 @@
           sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
+          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
         } else if (c.Type == ConstraintNodeType.Set) {
-          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-        }
-      }
-      return sb.ToString();
-    }
+          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
+          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ var tmp = GetAllowed{1}_{2}().ToArray(); return tmp[_state.random.Next(tmp.Length)]; }}", fieldType, t.Ident, c.Ident).AppendLine();
+        }
+      }
+      return sb.ToString();
+    }
+    #endregion
 
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
@@ -197 +239 @@
     }
 
-    private string GenerateTerminalInterpreterMethod(ISymbol s) {
-      var sb = new StringBuilder();
-      // if the terminal symbol has attributes then we must create values for these attributes
-      if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
-      else
-        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
-
-      // each field must match a formal parameter, assign a value for each parameter
-      foreach (var element in s.Attributes) {
-        // only works for "IN SET"-Constraints
-        sb.AppendFormat("{{ var tmp = GetAllowed{1}_{0}().ToArray(); {0} = tmp[random.Next(tmp.Length)]; }} ", element.Name, s.Name);
-      }
-      sb.AppendLine("}");
-      return sb.ToString();
-    }
-
     private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
       var sb = new StringBuilder();
+
       // if this is the start symbol we additionally have to create the method which can be called from the fitness function
-
       if (g.StartSymbol.Equals(s)) {
         if (!s.Attributes.Any())
@@ -234 +259 @@
           actualParameter = string.Empty;
 
-        sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
+        sb.AppendFormat("{0}(_state.Prepare(), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
         sb.AppendLine("}");
       }
 
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
+        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
+        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
 
       // generate local definitions
@@ -250 +275 @@
       var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
       var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
-      bool hasTerminalAlts = terminalAlts.Count() > 0;
-      bool hasNonTerminalAlts = nonTerminalAlts.Count() > 0;
+      bool hasTerminalAlts = terminalAlts.Any();
+      bool hasNonTerminalAlts = nonTerminalAlts.Any();
 
       if (altsWithSemActions.Length > 1) {
@@ -261 +286 @@
         // the probability of choosing terminals should depend on the depth of the tree (small likelihood to choose terminals for small depths, large likelihood for large depths)
         if (hasTerminalAlts && hasNonTerminalAlts) {
-          sb.AppendLine("if(random.NextDouble() < 0.5) {");
+          sb.AppendLine("if(_state.random.NextDouble() < TerminalProbForDepth(_state.depth)) {");
           // terminals
           sb.AppendLine("// terminals ");
@@ -287 +312 @@
 
     private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
-      sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
+      sb.AppendFormat("switch(_state.random.Next({0})) {{", alts.Count());
       // generate a case for each alternative
       int i = 0;
@@ -313 +338 @@
       } else {
         if (!s.Attributes.Any())
-          return string.Format("{0}(random);", s.Name);
+          return string.Format("{0}(_state.IncDepth()); _state.depth--;", s.Name);
         else
-          return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
-      }
+          return string.Format("{0}(_state.IncDepth(), {1}); _state.depth--;", s.Name, s.GetAttributeString());
+      }
+    }
+
+    private string GenerateTerminalInterpreterMethod(ISymbol s) {
+      var sb = new StringBuilder();
+      // if the terminal symbol has attributes then we must samples values for these attributes
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
+      else
+        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
+
+      // each field must match a formal parameter, assign a value for each parameter
+      foreach (var element in s.Attributes) {
+        sb.AppendFormat("{{ {0} = GetRandom{1}_{0}(_state); }} ", element.Name, s.Name);
+      }
+      sb.AppendLine("}");
+      return sb.ToString();
     }
   }

branches/HeuristicLab.Problems.GPDL/Examples/symbreg HEAL.txt

@@ -5 +5 @@
   double[] y;
   string[] variableNames;
+  int[] rows;
   Dictionary<string,int> nameToCol;
   
@@ -19 +20 @@
 
   double RSquared(IEnumerable<double> xs, IEnumerable<double> ys) {
-     HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError error;
-     var r2 = HeuristicLab.Problems.DataAnalysis.OnlinePearsonsRSquaredCalculator.Calculate(xs, ys, out error);
-     if(error == HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError.None) return r2;
-     else return 0.0;
-  }
+    // calculate Pearson's correlation in one pass over xs and ys
+    double sumx = 0.0;
+    double sumy = 0.0;
+    double sumxSq = 0.0;
+    double sumySq = 0.0;
+    double sumxy = 0.0;
+    int n = 0;
+    var xEnum = xs.GetEnumerator();
+    var yEnum = ys.GetEnumerator();
+    while(xEnum.MoveNext() & yEnum.MoveNext()) {
+      sumx += xEnum.Current;
+      sumy += yEnum.Current;
+      sumxSq += xEnum.Current * xEnum.Current;
+      sumySq += yEnum.Current * yEnum.Current;
+      sumxy += xEnum.Current * yEnum.Current;
+      n++;
+    }
+    System.Diagnostics.Debug.Assert(!(xEnum.MoveNext() | yEnum.MoveNext()));
+
+    double num;
+    double den;
+    double r = 0.0;
+    num = sumxy - ( ( sumx * sumy ) / n );
+    den = Math.Sqrt( ( sumxSq - ( sumx*sumx ) / n ) *
+                     ( sumySq - ( sumy*sumy ) / n ) );
+    if(den > 0){
+      r = num / den;
+    }
+    return r*r;
+  } 
 >>
 
@@ -33 +59 @@
   x = new double[n, 10];
   y = new double[n];
-  for(int row = 0; row < 500; row++) {
+  for(int row = 0; row < n; row++) {
     for(int col = 0; col < 10; col++) {
       x[row, col] = rand.NextDouble() * 2.0 - 1.0;
@@ -43 +69 @@
              x[row, 2] * x[row, 5] + x[row, 9];
   }
+
+  rows = System.Linq.Enumerable.Range(0, n).ToArray();
 >>
 
@@ -90 +118 @@
   .
 
-MAXIMIZE                                                   /* could also use the keyword MINIMIZE here */
+MAXIMIZE
   << 
-    var rows = System.Linq.Enumerable.Range(0, x.GetLength(0));
     var predicted = rows.Select(r => {
       double result;

branches/HeuristicLab.Problems.GPDL/Examples/symbreg Koza.txt

@@ -3 +3 @@
   double[,] x;
   double[] y;
+  int[] rows;
   string[] variableNames;
+  double[] randomConsts;
+  
   Dictionary<string,int> nameToCol;
   
@@ -18 +21 @@
 
   double RSquared(IEnumerable<double> xs, IEnumerable<double> ys) {
-     HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError error;
-     var r2 = HeuristicLab.Problems.DataAnalysis.OnlinePearsonsRSquaredCalculator.Calculate(xs, ys, out error);
-     if(error == HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError.None) return r2;
-     else return 0.0;
-  }
+    // calculate Pearson's correlation in one pass over xs and ys
+    double sumx = 0.0;
+    double sumy = 0.0;
+    double sumxSq = 0.0;
+    double sumySq = 0.0;
+    double sumxy = 0.0;
+    int n = 0;
+    var xEnum = xs.GetEnumerator();
+    var yEnum = ys.GetEnumerator();
+    while(xEnum.MoveNext() & yEnum.MoveNext()) {
+      sumx += xEnum.Current;
+      sumy += yEnum.Current;
+      sumxSq += xEnum.Current * xEnum.Current;
+      sumySq += yEnum.Current * yEnum.Current;
+      sumxy += xEnum.Current * yEnum.Current;
+      n++;
+    }
+    System.Diagnostics.Debug.Assert(!(xEnum.MoveNext() | yEnum.MoveNext()));
+
+    double num;
+    double den;
+    double r = 0.0;
+    num = sumxy - ( ( sumx * sumy ) / n );
+    den = Math.Sqrt( ( sumxSq - ( sumx*sumx ) / n ) *
+                     ( sumySq - ( sumy*sumy ) / n ) );
+    if(den > 0){
+      r = num / den;
+    }
+    return r*r;
+  } 
 >>
 
@@ -32 +60 @@
   x = new double[n, 10];
   y = new double[n];
-  for(int row = 0; row < 500; row++) {
+  for(int row = 0; row < n; row++) {
     for(int col = 0; col < 10; col++) {
       x[row, col] = rand.NextDouble() * 2.0 - 1.0;
@@ -42 +70 @@
              x[row, 2] * x[row, 5] + x[row, 9];
   }
+ 
+  rows = System.Linq.Enumerable.Range(0, n).ToArray();
+  
+  // generate 100 random constants in [-100.0 .. 100.0[
+  randomConsts = Enumerable.Range(0, 100).Select(i => rand.NextDouble()*200.0 - 100.0).ToArray();
 >>
 
@@ -55 +88 @@
   ERC<<out double val>> 
     CONSTRAINTS
-    val IN RANGE <<-100>> .. <<100>>
+      val IN SET << randomConsts >>
   .
 
   Var<<out string varName>> 
     CONSTRAINTS
-    varName IN SET <<variableNames>>
+      varName IN SET << variableNames >>
   .
 
@@ -73 +106 @@
     | Multiplication<<row, out val>>
     | Var<<out varName>>                                   SEM << val = GetValue(x, varName, row); >>
-    | ERC<<out val>>
+    /* | ERC<<out val>> */
   .
 
@@ -89 +122 @@
   .
 
-MAXIMIZE                                                   /* could also use the keyword MINIMIZE here */
+MAXIMIZE
   << 
-    var rows = System.Linq.Enumerable.Range(0, x.GetLength(0));
     var predicted = rows.Select(r => {
       double result;

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

@@ -27 +27 @@
 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>>();
+    private readonly Dictionary<ISymbol, string> localDefinitions;
+    private readonly Dictionary<ISymbol, List<Sequence>> alternatives;
 
-    public AttributedGrammar(ISymbol startSymbol)
-      : base(startSymbol) {
-      Debug.Assert(!startSymbol.Equals(EmptySymbol));
+    public AttributedGrammar(ISymbol startSymbol, IEnumerable<ISymbol> nonTerminals, IEnumerable<ISymbol> terminals)
+      : base(startSymbol, nonTerminals, terminals) {
       this.StartSymbol = startSymbol;
+      localDefinitions = nonTerminals.ToDictionary(nt => nt, nt => string.Empty);
+      alternatives = nonTerminals.ToDictionary(nt => nt, nt => new List<Sequence>());
     }
 
     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];
     }
@@ -48 +47 @@
       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);
-      }
+      IList<Sequence> list = alternatives[ntSymbol];
+
       // make sure that there is not equivalent production registered already
       Debug.Assert(!list.Any(s => s.SequenceEqual(production)));
@@ -61 +57 @@
     public void AddLocalDefinitions(ISymbol ntSymbol, string localDefCode) {
       Debug.Assert(!ntSymbol.Equals(EmptySymbol));
-      Debug.Assert(!localDefinitions.ContainsKey(ntSymbol));
 
-      localDefinitions.Add(ntSymbol, localDefCode);
+      localDefinitions[ntSymbol] = localDefCode;
     }
     public string GetLocalDefinitions(ISymbol ntSymbol) {
-      string code;
-      if (localDefinitions.TryGetValue(ntSymbol, out code)) return code;
-      else return string.Empty;
+      return localDefinitions[ntSymbol];
     }
-
-
-
-    //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

@@ -29 +29 @@
   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>();
+    private readonly Dictionary<ISymbol, List<Sequence>> rules;
+    private readonly HashSet<ISymbol> allSymbols;
 
     public ISymbol StartSymbol { get; set; }
@@ -37 +37 @@
     public IEnumerable<ISymbol> Symbols { get { return allSymbols; } }
 
-    public Grammar(ISymbol startSymbol) {
+    public Grammar(ISymbol startSymbol, IEnumerable<ISymbol> nonTerminals, IEnumerable<ISymbol> terminals) {
       Debug.Assert(startSymbol != EmptySymbol);
       this.StartSymbol = startSymbol;
+      this.allSymbols = new HashSet<ISymbol>(nonTerminals.Concat(terminals));
+      this.rules = nonTerminals.ToDictionary(nt => nt, nt => new List<Sequence>());
     }
 
@@ -56 +58 @@
     public virtual void AddProductionRule(ISymbol ntSymbol, Sequence production) {
       Debug.Assert(ntSymbol != EmptySymbol);
+      Debug.Assert(rules.ContainsKey(ntSymbol));
+      Debug.Assert(production.All(s => allSymbols.Contains(s)));
 
-      List<Sequence> l;
-      if (!rules.TryGetValue(ntSymbol, out l)) {
-        l = new List<Sequence>();
-        rules.Add(ntSymbol, l);
-
-        allSymbols.Add(ntSymbol); // register new nt-symbol
-      }
-      // check if the same production exists already
+      var l = rules[ntSymbol];
       Debug.Assert(!l.Any(s => s.SequenceEqual(production)));
 
       l.Add(production);
-
-      foreach (var s in production) allSymbols.Add(s); // register all symbols in the production
     }
 
     public bool IsTerminal(ISymbol symbol) {
+      // terminals must not have rules but must occur in the set of all symbols
       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));
     }
 
@@ -91 +82 @@
       lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
 
+      // make two passes: 1) find all symbols 2) add production rules
+      var nonTerminals = new List<ISymbol>();
+      var allSymbols = new List<ISymbol>();
+
       // 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);
+
+      nonTerminals.Add(startSymbol);
+      allSymbols.Add(startSymbol);
+
+      // parse first line
       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)).ToList<ISymbol>()));
+        foreach (var s in alt.ToString()
+          .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
+          .Select(n => new Symbol(n))) allSymbols.Add(s);
       }
+      // parse all remaining lines
       foreach (var line in lines.Skip(1)) {
         m = ruleExpr.Match(line);
         var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
+        nonTerminals.Add(ntSymbol);
+        allSymbols.Add(ntSymbol);
+
         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)).ToList<ISymbol>()));
+          foreach (var s in alt.ToString()
+          .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
+          .Select(n => new Symbol(n))) allSymbols.Add(s);
+        }
+      }
+
+      var g = new Grammar(startSymbol, nonTerminals, allSymbols.Except(nonTerminals));
+
+      m = ruleExpr.Match(lines.First());
+      // add production rules
+      foreach (var alt in m.Groups["alternative"].Captures) {
+        g.AddProductionRule(startSymbol,
+          new Sequence(alt.ToString()
+            .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
+            .Select(n => allSymbols.Single(s => s.Name == n)).ToList<ISymbol>()));
+      }
+      // parse all remaining lines
+      foreach (var line in lines.Skip(1)) {
+        m = ruleExpr.Match(line);
+        var ntSymbol = nonTerminals.Single(s => s.Name == 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 => allSymbols.Single(s => s.Name == n)).ToList<ISymbol>()));
         }
       }

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL.sln

@@ -5 +5 @@
   ProjectSection(SolutionItems) = preProject
     GenerateFromAtg.cmd = GenerateFromAtg.cmd
+    Performance1.psess = Performance1.psess
     PreBuildEvent.cmd = PreBuildEvent.cmd
   EndProjectSection
@@ -111 +112 @@
     {E2060931-6700-464B-9E82-50846D7AE4E9} = {3768D612-38EB-47D8-9E79-75D8E5AB00A8}
   EndGlobalSection
+  GlobalSection(Performance) = preSolution
+    HasPerformanceSessions = true
+  EndGlobalSection
 EndGlobal