Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj	(revision 10099)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj	(revision 10100)
@@ -37,4 +37,6 @@
   <ItemGroup>
     <Compile Include="BruteForceCodeGen.cs" />
+    <Compile Include="ProblemCodeGen.cs" />
+    <Compile Include="SourceBuilder.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="RandomSearchCodeGen.cs" />
Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs	(revision 10100)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs	(revision 10100)
@@ -0,0 +1,315 @@
+﻿using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
+using System.Linq;
+using HeuristicLab.Grammars;
+using Attribute = HeuristicLab.Grammars.Attribute;
+
+namespace CodeGenerator {
+  // code generator for problem class
+  public class ProblemCodeGen {
+    private const string usings = @"
+using System.Collections.Generic;
+using System.Linq;
+using System;
+using System.Text.RegularExpressions;
+";
+
+    private const string problemTemplate = @"
+namespace ?PROBLEMNAME? {
+  public interface IGpdlProblem {
+    int GetCardinality(string terminalSymbol, string attribute);
+  }
+  public interface ISolverState {
+    void Reset();
+    int PeekNextAlternative();
+    void Follow(int idx);
+    void Unwind();
+  }
+
+  public sealed class ?IDENT?Problem : IGpdlProblem {
+   
+   private readonly Dictionary<string, Dictionary<string, int>> cardinalities = new Dictionary<string, Dictionary<string, int>>();
+   public ?IDENT?Problem() { 
+      Initialize();
+
+?CONSTRUCTORSOURCE?
+
+    }    
+
+    private void Initialize() {
+?INITSOURCE?
+    }
+
+    private ISolverState _state;
+    public double Evaluate(ISolverState _state) {
+      this._state = _state;
+?FITNESSFUNCTION?
+    }
+
+?ADDITIONALCODE?
+
+?INTERPRETERSOURCE?
+
+?CONSTRAINTSSOURCE?
+
+    public int GetCardinality(string terminal, string attribute) {
+      return cardinalities[terminal][attribute];
+    }
+  }
+}";
+
+
+    /// <summary>
+    /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
+    /// </summary>
+    /// <param name="ast">An abstract syntax tree for a GPDL file</param>
+    public void Generate(GPDefNode ast) {
+      var problemSourceCode = new SourceBuilder();
+      problemSourceCode.AppendLine(usings);
+
+      GenerateProblemSource(ast, problemSourceCode);
+      GenerateSolvers(ast, problemSourceCode);
+
+      problemSourceCode
+        .Replace("?PROBLEMNAME?", ast.Name)
+        .Replace("?IDENT?", ast.Name);
+
+
+      // write the source file to disk
+      using (var stream = new StreamWriter(ast.Name + ".cs")) {
+        stream.WriteLine(problemSourceCode.ToString());
+      }
+    }
+
+    private void GenerateProblemSource(GPDefNode ast, SourceBuilder problemSourceCode) {
+      var grammar = CreateGrammarFromAst(ast);
+      problemSourceCode
+        .AppendLine(problemTemplate)
+        .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
+        .Replace("?CONSTRUCTORSOURCE?", GenerateConstructorSource(ast))
+        .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
+        .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
+        .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
+        .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
+          ;
+    }
+
+    private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
+      var grammar = CreateGrammarFromAst(ast);
+      var randomSearchCodeGen = new RandomSearchCodeGen();
+      randomSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, ast.Terminals, solverSourceCode);
+    }
+
+    #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;
+
+      // create startSymbol
+      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) {
+        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
+        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
+          g.AddProductionRule(ntSymbol, alt);
+        }
+        // local initialization code
+        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
+      }
+      return g;
+    }
+
+    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
+      return (from fieldDef in Util.ExtractParameters(formalParameters)
+              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
+        ToList();
+    }
+
+    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
+      foreach (var alt in altNode.Alternatives) {
+        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>();
+      foreach (var node in sequence) {
+        var callSymbolNode = node as CallSymbolNode;
+        var actionNode = node as RuleActionNode;
+        if (callSymbolNode != null) {
+          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));
+        }
+      }
+      return new Sequence(l);
+    }
+    #endregion
+
+    #region helper methods for terminal symbols
+    // produces helper methods for the attributes of all terminal nodes
+    private string GenerateConstraintMethods(IEnumerable<SymbolNode> symbols) {
+      var sb = new SourceBuilder();
+      var terminals = symbols.OfType<TerminalNode>();
+      foreach (var t in terminals) {
+        GenerateConstraintMethods(t, sb);
+      }
+      return sb.ToString();
+    }
+
+
+    // generates helper methods for the attributes of a given terminal node
+    private void GenerateConstraintMethods(TerminalNode t, SourceBuilder sb) {
+      foreach (var c in t.Constraints) {
+        var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
+        if (c.Type == ConstraintNodeType.Range) {
+          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} Get{1}_{2}(ISolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
+          sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ throw new NotSupportedException(\"range constraints for terminals are not supported.\"); }}", 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();
+          sb.AppendFormat("private readonly {0}[] values_{1}_{2};", fieldType, t.Ident, c.Ident).AppendLine();
+          sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return values_{1}_{2}[_state.PeekNextAlternative()]; }}", fieldType, t.Ident, c.Ident).AppendLine();
+        }
+      }
+    }
+    private string GenerateConstructorSource(GPDefNode ast) {
+      var sb = new SourceBuilder();
+      // generate code to initialize the tables for terminals
+      foreach (var t in ast.Terminals.OfType<TerminalNode>()) {
+        if (t.Constraints.Any()) {
+          foreach (var constraint in t.Constraints) {
+            sb.AppendFormat("values_{0}_{1} = GetAllowed{0}_{1}().ToArray();", t.Ident, constraint.Ident);
+          }
+          sb.AppendFormat("cardinalities[\"{0}\"] = new Dictionary<string, int>() {{ ", t.Ident);
+          foreach (var constraint in t.Constraints) {
+            sb.AppendFormat("{{ \"{1}\", values_{0}_{1}.Length }}, ", t.Ident, constraint.Ident);
+          }
+          sb.Append("};").AppendLine();
+        }
+      }
+      return sb.ToString();
+    }
+
+
+    #endregion
+
+    private string GenerateInterpreterSource(AttributedGrammar grammar) {
+      var sb = new SourceBuilder();
+
+      // generate methods for all nonterminals and terminals using the grammar instance
+      foreach (var s in grammar.NonTerminalSymbols) {
+        GenerateInterpreterMethod(grammar, s, sb);
+      }
+      foreach (var s in grammar.TerminalSymbols) {
+        GenerateTerminalInterpreterMethod(s, sb);
+      }
+      return sb.ToString();
+    }
+
+    private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
+      // 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())
+          sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
+        else
+          sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+
+        // get formal parameters of start symbol
+        var attr = g.StartSymbol.Attributes;
+
+        // actual parameter are the same as formalparameter only without type identifier
+        string actualParameter;
+        if (attr.Any())
+          actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
+        else
+          actualParameter = string.Empty;
+        sb.AppendLine("_state.Reset();");
+        sb.AppendFormat("{0}(_state, {1});", g.StartSymbol.Name, actualParameter).AppendLine();
+        sb.AppendLine("}").EndBlock();
+      }
+
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
+      else
+        sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+
+      // generate local definitions
+      sb.AppendLine(g.GetLocalDefinitions(s));
+
+      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
+
+      if (altsWithSemActions.Length > 1) {
+        GenerateSwitchStatement(altsWithSemActions, sb);
+      } else {
+        int i = 0;
+        foreach (var altSymb in altsWithSemActions.Single()) {
+          GenerateSourceForAction(i, altSymb, sb);
+          if (!(altSymb is SemanticSymbol)) i++;
+        }
+      }
+      sb.Append("}").EndBlock();
+    }
+
+    private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
+      sb.Append("switch(_state.PeekNextAlternative()) {").BeginBlock();
+      // generate a case for each alternative
+      int i = 0;
+      foreach (var alt in alts) {
+        sb.AppendFormat("case {0}: {{ ", i).BeginBlock();
+
+        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
+        // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
+        Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
+        foreach (var altSymb in alt) {
+          GenerateSourceForAction(0, altSymb, sb); // index is always 0 because of the assertion above
+        }
+        i++;
+        sb.AppendLine("break;").Append("}").EndBlock();
+      }
+      sb.AppendLine("default: throw new System.InvalidOperationException();").Append("}").EndBlock();
+    }
+
+    // helper for generating calls to other symbol methods
+    private void GenerateSourceForAction(int idx, ISymbol s, SourceBuilder sb) {
+      var action = s as SemanticSymbol;
+      if (action != null)
+        sb.Append(action.Code + ";");
+      else if (!s.Attributes.Any())
+        sb.AppendFormat("_state.Follow({0}); {1}(_state); _state.Unwind();", idx, s.Name);
+      else sb.AppendFormat("_state.Follow({0}); {1}(_state, {2}); _state.Unwind();", idx, s.Name, s.GetAttributeString());
+      sb.AppendLine();
+    }
+
+    private string GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
+      // if the terminal symbol has attributes then we must samples values for these attributes
+      if (!s.Attributes.Any())
+        sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
+      else
+        sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
+
+      // each field must match a formal parameter, assign a value for each parameter
+      int i = 0;
+      foreach (var element in s.Attributes) {
+        sb.AppendFormat("_state.Follow({0});", i++).AppendLine();
+        sb.AppendFormat("{0} = Get{1}_{0}(_state);", element.Name, s.Name).AppendLine();
+        sb.AppendFormat("_state.Unwind();").AppendLine();
+      }
+      sb.Append("}").EndBlock();
+      return sb.ToString();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs	(revision 10099)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs	(revision 10100)
@@ -2,74 +2,159 @@
 using System.Collections.Generic;
 using System.Diagnostics;
-using System.IO;
 using System.Linq;
-using System.Text;
 using HeuristicLab.Grammars;
-using Attribute = HeuristicLab.Grammars.Attribute;
 
 namespace CodeGenerator {
   public class RandomSearchCodeGen {
-
-    private string usings = @"
-using System.Collections.Generic;
-using System.Linq;
-using System;
-";
 
     private string solverTemplate = @"
 namespace ?PROBLEMNAME? {
   public sealed class ?IDENT?Solver {
-    public sealed class SolverState {
-      private int currentSeed;
-      public Random random;
+    private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
+    private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
+    
+    public sealed class SolverState : ISolverState {
+      private class Tree {
+        public int altIdx;
+        // public string symbol; // for debugging
+        public List<Tree> subtrees;
+        public Tree(int state, int altIdx) {
+          subtrees = new List<Tree>(subtreeCount[state]);
+          this.altIdx = altIdx;
+        }
+      }
+      public int curDepth;
+      public int steps;
       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;
+      private readonly Stack<Tree> nodes;
+      private readonly IGpdlProblem problem;
+
+      private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
+?TRANSITIONTABLE?
+      };
+      private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
+         { -1, 0 }, // terminals
+?SUBTREECOUNTTABLE?
+      };
+      private static string[] symb = new string[] { ?SYMBOLNAMES? };
+
+      public SolverState(IGpdlProblem problem, int seed) {
+        this.problem = problem;
+        this.nodes = new Stack<Tree>();
+        
+        // create a random tree
+        var tree = SampleTree(new Random(seed), 0, -1);  // state 0 is the state for the start symbol
+        nodes.Push(tree);
+      }
+
+      public void Reset() {
+        // stack must contain only the root of the tree
+        System.Diagnostics.Debug.Assert(nodes.Count == 1);
+      }
+
+      private Tree SampleTree(Random random, int state, int altIdx) {
+        // Console.Write(state + "" "");        
+        curDepth += 1;
+        steps += 1;
+        depth = Math.Max(depth, curDepth);
+        var t = new Tree(state, altIdx);
+        // t.symbol = symb.Length > state ? symb[state] : ""TERM"";
+        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
+        if(subtreeCount[state] == 1) {
+          var targetStates = transition[state];
+          var i = SampleAlternative(random, state);
+          if(targetStates.Length == 0) {
+            //terminal
+            t.subtrees.Add(SampleTree(random, -1, i));
+          } else {
+            t.subtrees.Add(SampleTree(random, targetStates[i], i));
+          }
+        } else {
+          // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
+          for(int i = 0; i < subtreeCount[state]; i++) {
+            t.subtrees.Add(SampleTree(random, transition[state][i], i));
+          }
+        }
+        curDepth -=1;
+        return t;
+      }
+
+      public int PeekNextAlternative() {
+        // this must only be called nodes that contain alternatives and therefore must only have single-symbols alternatives
+        System.Diagnostics.Debug.Assert(nodes.Peek().subtrees.Count == 1);
+        return nodes.Peek().subtrees[0].altIdx;
+      }
+
+      public void Follow(int idx) {
+        nodes.Push(nodes.Peek().subtrees[idx]);
+      }
+
+      public void Unwind() {
+        nodes.Pop();
+      }
+
+      private int SampleAlternative(Random random, int state) {
+        switch(state) {
+
+?SAMPLEALTERNATIVECODE?
+
+          default: throw new InvalidOperationException();
+        }
+      }
+
+      private double TerminalProbForDepth(int depth) {
+        return baseTerminalProbability + depth * terminalProbabilityInc;
       }
     }
 
     public static void Main(string[] args) {
-      var solver = new ?IDENT?Solver();
+      if(args.Length >= 1) ParseArguments(args);
+
+      var problem = new ?IDENT?Problem();
+      var solver = new ?IDENT?Solver(problem);
       solver.Start();
     }
-
-    public ?IDENT?Solver() { 
-      Initialize();
-    }    
-
-    private void Initialize() {
-      ?INITCODE?
-    }
-
-    private bool IsBetter(double a, double b) { 
-      return ?MAXIMIZATION? ? a > b : a < b;
-    }
-
-    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 static void ParseArguments(string[] args) {
+      var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)"");
+      var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)"");
+      var helpRegex = new Regex(@""--help|/\?"");
+      
+      foreach(var arg in args) {
+        var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg);
+        var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg);
+        var helpMatch = helpRegex.Match(arg);
+        if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); }
+        else if(baseTerminalProbabilityMatch.Success) {
+          baseTerminalProbability = double.Parse(baseTerminalProbabilityMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+          if(baseTerminalProbability < 0.0 || baseTerminalProbability > 1.0) throw new ArgumentException(""base terminal probability must lie in range [0.0 ... 1.0]"");
+        } else if(terminalProbabilityIncMatch.Success) {
+           terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+           if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]"");
+        } else {
+           Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); 
+        }
+      }
+    }
+    private static void PrintUsage() {
+      Console.WriteLine(""Find a solution using random tree search."");
+      Console.WriteLine();
+      Console.WriteLine(""Parameters:"");
+      Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]"");
+      Console.WriteLine(""\t--terminalProbInc=<prob>\tSets the increment for the probability of sampling a terminal alternative for each level in the syntax tree [Default: 0.05]"");
+    }
+
+
+    private readonly ?IDENT?Problem problem;
+    public ?IDENT?Solver(?IDENT?Problem problem) {
+      this.problem = problem;
+    }
+
     private void Start() {
       var seedRandom = new Random();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
+      long sumDepth = 0;
+      long sumSize = 0;
+      var sumF = 0.0;
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
@@ -79,17 +164,25 @@
         // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
         
-        _state = new SolverState(seedRandom.Next());
-
-        var f = Calculate();
-
+        var _state = new SolverState(problem, seedRandom.Next());
+
+        var f = problem.Evaluate(_state);
+ 
         n++;
+        sumSize += _state.steps;
+        sumDepth += _state.depth;
+        sumF += f;
         if (IsBetter(f, bestF)) {
+          // evaluate again with tracing to console
+          // problem.Evaluate(new SolverState(_state.seed, true));
           bestF = f;
-          Console.WriteLine(""{0}\t{1}\t(depth={2})"", n, bestF, _state.maxDepth);
+          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
         }
         if (n % 1000 == 0) {
           sw.Stop();
-          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 1000.0 / sw.ElapsedMilliseconds);
+          Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
           sw.Reset();
+          sumSize = 0;
+          sumDepth = 0;
+          sumF = 0.0;
           sw.Start();
         }
@@ -97,265 +190,153 @@
     }
 
-    public double Calculate() {
-      ?FITNESSFUNCTION?
-    }
-
-    ?ADDITIONALCODE?
-
-    ?INTERPRETERSOURCE?
-
-    ?CONSTRAINTSSOURCE?
+    private bool IsBetter(double a, double b) { 
+      return ?MAXIMIZATION? ? a > b : a < b;
+    }
   }
 }";
 
-
-    /// <summary>
-    /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
-    /// </summary>
-    /// <param name="ast">An abstract syntax tree for a GPDL file</param>
-    public void Generate(GPDefNode ast) {
-      var problemSourceCode = new StringBuilder();
-      problemSourceCode.AppendLine(usings);
-
-      GenerateProblem(ast, problemSourceCode);
-
-      problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
-
-      // write the source file to disk
-      using (var stream = new StreamWriter(ast.Name + ".cs")) {
-        stream.WriteLine(problemSourceCode.ToString());
-      }
-    }
-
-    private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
-      var grammar = CreateGrammarFromAst(ast);
-      var problemClassCode =
-        solverTemplate
-          .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
-          .Replace("?IDENT?", ast.Name)
-          .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
-          .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
-          .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
-          .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
-          .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
-          ;
-
-      problemSourceCode.AppendLine(problemClassCode).AppendLine();
-    }
-
-    #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;
-
-      // create startSymbol
-      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) {
-        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
-        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
-          g.AddProductionRule(ntSymbol, alt);
-        }
-        // local initialization code
-        if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
-      }
-      return g;
-    }
-
-    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
-      return (from fieldDef in Util.ExtractParameters(formalParameters)
-              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
-        ToList();
-    }
-
-    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
-      foreach (var alt in altNode.Alternatives) {
-        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>();
-      foreach (var node in sequence) {
-        var callSymbolNode = node as CallSymbolNode;
-        var actionNode = node as RuleActionNode;
-        if (callSymbolNode != null) {
-          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));
-        }
-      }
-      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) {
-      var sb = new StringBuilder();
-      var terminals = symbols.OfType<TerminalNode>();
-      foreach (var t in terminals) {
-        sb.AppendLine(GenerateConstraintMethods(t));
+    public void Generate(IGrammar grammar, bool maximization, IEnumerable<SymbolNode> terminalSymbols, SourceBuilder problemSourceCode) {
+      var solverSourceCode = new SourceBuilder();
+      solverSourceCode.Append(solverTemplate)
+        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
+        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
+        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
+        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
+        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
+      ;
+
+      problemSourceCode.Append(solverSourceCode.ToString());
+    }
+
+
+
+    private string GenerateTransitionTable(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+
+      // state idx = idx of the corresponding symbol in the grammar
+      var allSymbols = grammar.Symbols.ToList();
+      var attributes = new List<string>();
+      foreach (var s in grammar.Symbols) {
+        var targetStates = new List<int>();
+        if (grammar.IsTerminal(s)) {
+          foreach (var att in s.Attributes) {
+            targetStates.Add(allSymbols.Count + attributes.Count);
+            attributes.Add(s.Name + "_" + att);
+          }
+        } else {
+          if (grammar.NumberOfAlternatives(s) > 1) {
+            foreach (var alt in grammar.GetAlternatives(s)) {
+              // only single-symbol alternatives are supported
+              Debug.Assert(alt.Count() == 1);
+              targetStates.Add(allSymbols.IndexOf(alt.Single()));
+            }
+          } else {
+            // rule is a sequence of symbols
+            var seq = grammar.GetAlternatives(s).Single();
+            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
+          }
+        }
+
+        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
+
+        var idxOfSourceState = allSymbols.IndexOf(s);
+        sb.AppendFormat("// {0}", s).AppendLine();
+        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
+      }
+      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
+        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
+        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
       }
       return sb.ToString();
     }
-
-    // generates helper methods for the attributes of a given terminal node
-    private string GenerateConstraintMethods(TerminalNode t) {
-      var sb = new StringBuilder();
-      foreach (var c in t.Constraints) {
-        var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
-        if (c.Type == ConstraintNodeType.Range) {
-          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();
-          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();
-        }
+    private string GenerateSubtreeCountTable(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+
+      // state idx = idx of the corresponding symbol in the grammar
+      var allSymbols = grammar.Symbols.ToList();
+      var attributes = new List<string>();
+      foreach (var s in grammar.Symbols) {
+        int subtreeCount;
+        if (grammar.IsTerminal(s)) {
+          subtreeCount = s.Attributes.Count();
+          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
+        } else {
+          if (grammar.NumberOfAlternatives(s) > 1) {
+            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
+            subtreeCount = 1;
+          } else {
+            subtreeCount = grammar.GetAlternative(s, 0).Count();
+          }
+        }
+
+        sb.AppendFormat("// {0}", s).AppendLine();
+        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
+      }
+
+      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
+        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
+        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
       }
       return sb.ToString();
     }
-    #endregion
-
-    private string GenerateInterpreterSource(AttributedGrammar grammar) {
-      var sb = new StringBuilder();
-
-      // generate methods for all nonterminals and terminals using the grammar instance
-      foreach (var s in grammar.NonTerminalSymbols) {
-        sb.AppendLine(GenerateInterpreterMethod(grammar, s));
-      }
-      foreach (var s in grammar.TerminalSymbols) {
-        sb.AppendLine(GenerateTerminalInterpreterMethod(s));
+
+    private string GenerateSampleAlternativeSource(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+      int stateCount = 0;
+      var attributes = new List<Tuple<string, string>>();
+      foreach (var s in grammar.Symbols) {
+        sb.AppendFormat("case {0}: ", stateCount++);
+        if (grammar.IsTerminal(s)) {
+          GenerateReturnStatement(s.Attributes.Count(), sb);
+          attributes.AddRange(s.Attributes.Select(att => Tuple.Create(s.Name, att.Name)));
+        } else {
+          var terminalAltIndexes = grammar.GetAlternatives(s)
+            .Select((alt, idx) => new { alt, idx })
+            .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
+            .Select(p => p.idx);
+          var nonTerminalAltIndexes = grammar.GetAlternatives(s)
+            .Select((alt, idx) => new { alt, idx })
+            .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
+            .Select(p => p.idx);
+          var hasTerminalAlts = terminalAltIndexes.Any();
+          var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
+          if (hasTerminalAlts && hasNonTerminalAlts) {
+            sb.Append("if(random.NextDouble() < TerminalProbForDepth(depth)) {").BeginBlock();
+            GenerateReturnStatement(terminalAltIndexes, sb);
+            sb.Append("} else {");
+            GenerateReturnStatement(nonTerminalAltIndexes, sb);
+            sb.Append("}").EndBlock();
+          } else {
+            GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
+          }
+        }
+      }
+      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
+        var terminalName = attributes[attIdx].Item1;
+        var attributeName = attributes[attIdx].Item2;
+        sb.AppendFormat("case {0}: return random.Next(problem.GetCardinality(\"{1}\", \"{2}\"));", attIdx + stateCount, terminalName, attributeName).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())
-          sb.AppendFormat("private void {0}() {{", s.Name);
-        else
-          sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString());
-
-        // get formal parameters of start symbol
-        var attr = g.StartSymbol.Attributes;
-
-        // actual parameter are the same as formalparameter only without type identifier
-        string actualParameter;
-        if (attr.Any())
-          actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
-        else
-          actualParameter = string.Empty;
-
-        sb.AppendFormat("{0}(_state.Prepare(), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
-        sb.AppendLine("}");
-      }
-
-      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());
-
-      // generate local definitions
-      sb.AppendLine(g.GetLocalDefinitions(s));
-
-
-      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
-      var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
-      var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
-      bool hasTerminalAlts = terminalAlts.Any();
-      bool hasNonTerminalAlts = nonTerminalAlts.Any();
-
-      if (altsWithSemActions.Length > 1) {
-        // here we need to bias the selection of alternatives (non-terminal vs terminal alternatives) to make sure that
-        // terminals are selected with a certain probability to make sure that:
-        // 1) we don't create the same small trees all the time (terminals have high probability to be selected)
-        // 2) we don't create very big trees by recursing to deep (leads to stack-overflow) (terminals have a low probability to be selected)
-        // so we first decide if we want to generate a terminal or non-terminal (50%, 50%) and then choose a symbol in the class randomly
-        // 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(_state.random.NextDouble() < TerminalProbForDepth(_state.depth)) {");
-          // terminals
-          sb.AppendLine("// terminals ");
-          GenerateSwitchStatement(sb, terminalAlts);
-          sb.AppendLine("} else {");
-          // non-terminals
-          sb.AppendLine("// non-terminals ");
-          GenerateSwitchStatement(sb, nonTerminalAlts);
-          sb.AppendLine("}");
-        } else if (hasTerminalAlts) {
-          sb.AppendLine("// terminals ");
-          GenerateSwitchStatement(sb, terminalAlts);
-        } else if (hasNonTerminalAlts) {
-          sb.AppendLine("// non-terminals ");
-          GenerateSwitchStatement(sb, nonTerminalAlts);
-        }
+    private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
+      if (idxs.Count() == 1) {
+        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
       } else {
-        foreach (var altSymb in altsWithSemActions.Single()) {
-          sb.AppendLine(GenerateSourceForAction(altSymb));
-        }
-      }
-      sb.AppendLine("}");
-      return sb.ToString();
-    }
-
-    private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
-      sb.AppendFormat("switch(_state.random.Next({0})) {{", alts.Count());
-      // generate a case for each alternative
-      int i = 0;
-      foreach (var alt in alts) {
-        sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-
-        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
-        // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
-        Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
-        foreach (var altSymb in alt) {
-          sb.AppendLine(GenerateSourceForAction(altSymb));
-        }
-        i++;
-        sb.AppendLine("break;").AppendLine("}");
-      }
-      sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
-
-    }
-
-    // helper for generating calls to other symbol methods
-    private string GenerateSourceForAction(ISymbol s) {
-      var action = s as SemanticSymbol;
-      if (action != null) {
-        return action.Code + ";";
+        var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
+        sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
+      }
+    }
+
+    private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
+      if (nAlts > 1) {
+        sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
+      } else if (nAlts == 1) {
+        sb.AppendLine("return 0; ");
       } else {
-        if (!s.Attributes.Any())
-          return string.Format("{0}(_state.IncDepth()); _state.depth--;", s.Name);
-        else
-          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();
+        sb.AppendLine("throw new InvalidProgramException();");
+      }
     }
   }
Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/SourceBuilder.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/SourceBuilder.cs	(revision 10100)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/SourceBuilder.cs	(revision 10100)
@@ -0,0 +1,51 @@
+﻿using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Grammars;
+using Attribute = HeuristicLab.Grammars.Attribute;
+
+namespace CodeGenerator {
+  public class SourceBuilder {
+    private readonly StringBuilder sb;
+    private int indent;
+    public SourceBuilder() {
+      sb = new StringBuilder();
+      indent = 0;
+    }
+
+    public SourceBuilder BeginBlock() {
+      indent += 2;
+      return AppendLine();
+    }
+    public SourceBuilder EndBlock() {
+      indent -= 2;
+      return AppendLine();
+    }
+    public SourceBuilder Append(string str) {
+      sb.Append(' ', indent).Append(str);
+      return this;
+    }
+    public SourceBuilder AppendFormat(string fmtString, params object[] args) {
+      sb.Append(' ', indent).AppendFormat(fmtString, args);
+      return this;
+    }
+    public SourceBuilder AppendLine() {
+      sb.AppendLine();
+      return this;
+    }
+    public SourceBuilder AppendLine(string str) {
+      sb.AppendLine(str);
+      return this;
+    }
+    public SourceBuilder Replace(string oldValue, string newValue) {
+      sb.Replace(oldValue, newValue);
+      return this;
+    }
+
+    public override string ToString() {
+      return sb.ToString();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GPDL/GpdlCompiler/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/GpdlCompiler/Program.cs	(revision 10099)
+++ /branches/HeuristicLab.Problems.GPDL/GpdlCompiler/Program.cs	(revision 10100)
@@ -32,5 +32,5 @@
       Parser parser = new Parser(scanner);
       parser.Parse();
-      var codeGen = new RandomSearchCodeGen();
+      var codeGen = new ProblemCodeGen();
 
       codeGen.Generate(parser.AbstractSyntaxTree);
