Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/14/14 12:40:26 (10 years ago)
Author:
gkronber
Message:

#2026 worked on code generator for random search (work in progress commit)

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r10086 r10335  
    22using System.Collections.Generic;
    33using System.Diagnostics;
    4 using System.IO;
    54using System.Linq;
    6 using System.Text;
    75using HeuristicLab.Grammars;
    8 using Attribute = HeuristicLab.Grammars.Attribute;
    96
    107namespace CodeGenerator {
    118  public class BruteForceCodeGen {
    12 
    13     private string usings = @"
    14 using System.Collections.Generic;
    15 using System.Linq;
    16 using System;
    17 ";
    18 
    199    private string solverTemplate = @"
    2010namespace ?PROBLEMNAME? {
    2111  public sealed class ?IDENT?Solver {
    2212
     13    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
     14?TRANSITIONTABLE?
     15    };
     16    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
     17       { -1, 0 }, // terminals
     18?SUBTREECOUNTTABLE?
     19    };
     20
     21    private static string[] symb = new string[] { ?SYMBOLNAMES? };
     22    private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? };
     23    private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? };
     24
     25   
     26    public sealed class SolverState : ISolverState {
     27      private class Node {
     28        public int state;
     29        public int count;
     30        public List<Node> nodes;
     31        public bool done;
     32        private int nextAlt;
     33        public Node(int state) {
     34          this.state = state;
     35          nodes = new List<Node>(transition[state].Length);
     36          if (!hasAlternatives[state]) {
     37            foreach (var t in transition[state]) { nodes.Add(new Node(t)); }
     38          }
     39        }
     40
     41        public int GetNextAlternative() {
     42          System.Diagnostics.Debug.Assert(hasAlternatives[state]);
     43          if(nodes.Count == 0 && !isTerminal[state]) {
     44            foreach(var targetState in transition[state]) nodes.Add(new Node(targetState));
     45            nextAlt = 0;
     46            // begin with a terminal if possible
     47            if(!isTerminal[nodes[nextAlt].state])
     48              do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]);
     49          }
     50
     51          throw new NotImplementedException(); // TODO: handle terminal classes correctly
     52          return nextAlt;
     53        }
     54
     55        public void Update() {
     56          count++;
     57          if(hasAlternatives[state] && !isTerminal[state]) {
     58            nodes[GetNextAlternative()].Update();
     59            // check if all nodes done and set this node to done
     60            if(nodes.All(n=>n.done)) {
     61              this.done = true;
     62            } else {
     63              // must not walk nodes that are done
     64              do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done);
     65            }
     66          } else {
     67            if(isTerminal[state]) {
     68              throw new NotImplementedException(); // TODO: handle terminal classes correctly
     69              done = (nextAlt + 1) >= GetAlternativesCount(symb[state]);
     70            } else {
     71              // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one
     72              Node minNode = nodes.First();
     73              foreach(var node in nodes.Skip(1)) {
     74                if(node.count < minNode.count) {
     75                  minNode = node;
     76                }
     77              }
     78              minNode.Update();
     79              if(nodes.All(n=>n.done)) this.done = true;
     80            }
     81          }
     82        }
     83      }
     84
     85
     86      ?ALTERNATIVESCOUNTMETHOD?
     87
     88
     89      public int curDepth;
     90      public int steps;
     91      public int depth;
     92      private readonly Stack<Node> nodes;
     93      private readonly IGpdlProblem problem;
     94      private readonly Node searchTree;
     95
     96      public SolverState(IGpdlProblem problem) {
     97        this.problem = problem;
     98        nodes = new Stack<Node>();
     99        searchTree = new Node(0);
     100        nodes.Push(searchTree);
     101      }
     102
     103      public void Reset() {
     104        System.Diagnostics.Debug.Assert(nodes.Count == 1);
     105        steps = 0;
     106        depth = 0;
     107        curDepth = 0;
     108      }
     109
     110      public int PeekNextAlternative() {
     111        var curNode = nodes.Peek();
     112        System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]);
     113        return curNode.GetNextAlternative();
     114      }
     115
     116      public void Follow(int idx) {
     117        steps++;
     118        curDepth++;
     119        depth = Math.Max(depth, curDepth);
     120        var curNode = nodes.Peek();
     121        if(hasAlternatives[curNode.state]) {
     122          nodes.Push(curNode.nodes[curNode.GetNextAlternative()]);
     123        } else {
     124          nodes.Push(curNode.nodes[idx]);
     125        }
     126      }
     127
     128      public void Unwind() {
     129        nodes.Pop();
     130        curDepth--;
     131      }
     132
     133      public void Update() {
     134        searchTree.Update();
     135      }
     136    }
     137
    23138    public static void Main(string[] args) {
    24       var solver = new ?IDENT?Solver();
     139      var problem = new ?IDENT?Problem();
     140      var solver = new ?IDENT?Solver(problem);
    25141      solver.Start();
    26142    }
    27 
    28     public ?IDENT?Solver() {
    29       Initialize();
    30     }   
    31 
    32     private void Initialize() {
    33       ?INITCODE?
     143   
     144    private readonly ?IDENT?Problem problem;
     145    public ?IDENT?Solver(?IDENT?Problem problem) {
     146      this.problem = problem;
     147    }
     148
     149    private void Start() {
     150      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
     151      int n = 0;
     152      long sumDepth = 0;
     153      long sumSize = 0;
     154      var sumF = 0.0;
     155      var sw = new System.Diagnostics.Stopwatch();
     156      sw.Start();
     157      var _state = new SolverState(problem);
     158      while (true) {
     159
     160        var f = problem.Evaluate(_state);
     161        _state.Update();
     162
     163        n++;
     164        sumSize += _state.steps;
     165        sumDepth += _state.depth;
     166        sumF += f;
     167        if (IsBetter(f, bestF)) {
     168          // evaluate again with tracing to console
     169          // problem.Evaluate(new SolverState(_state.seed, true));
     170          bestF = f;
     171          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
     172        }
     173        if (n % 1000 == 0) {
     174          sw.Stop();
     175          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);
     176          sw.Reset();
     177          sumSize = 0;
     178          sumDepth = 0;
     179          sumF = 0.0;
     180          sw.Start();
     181        }
     182      }
    34183    }
    35184
    … …  
    37186      return ?MAXIMIZATION? ? a > b : a < b;
    38187    }
    39 
    40     private class SearchTree {
    41       private SearchTree[] subTrees;
    42       public bool Done { get; private set; }
    43       private int nextAlternative;
    44 
    45       public SearchTree() {
    46         Done = false;
    47       }
    48 
    49       public SearchTree GetSubtree(int i) {
    50         // if (subTrees[i] == null) subTrees[i] = new SearchTree();
    51         return subTrees[i];
    52       }
    53 
    54       public int GetNextAlternative() {
    55         System.Diagnostics.Debug.Assert(IsAlternativeNode);
    56         return nextAlternative;
    57       }
    58 
    59       public bool IsUninitialized {
    60         get { return subTrees == null; }
    61       }
    62 
    63       public void SetNumberOfSubtrees(int n) {
    64         this.subTrees = new SearchTree[n];
    65         for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
    66         nextAlternative = 0;
    67       }
    68 
    69       public void UpdatePath() {
    70         System.Diagnostics.Debug.Assert(!Done);
    71         if (IsUninitialized) { return; }
    72         Count++;
    73         if (subTrees.Length == 0) {
    74           Done = true;
    75         }
    76         if (IsAlternativeNode) {
    77           // update only the active alternative and calculate a new alternative
    78           subTrees[nextAlternative].UpdatePath();
    79 
    80           do {
    81             nextAlternative = (nextAlternative + 1) % subTrees.Length;
    82           } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
    83         } else {
    84           // for sequenceNodes update all sub-trees
    85           foreach (var t in subTrees) t.UpdatePath();
    86         }
    87         // set node to done if all nodes are non-null and done
    88         this.Done = true;
    89         foreach(var t in subTrees) {
    90           if(t == null || !t.Done)
    91             { this.Done = false; break; }
    92         }       
    93       }
    94 
    95       public bool IsAlternativeNode { get; set; }
    96       public bool IsSequenceNode { get; set; }
    97       public int Count { get; private set; }
    98     }
    99 
    100     private SearchTree tree;
    101     private void Start() {
    102       // start with empty tree
    103       tree = new SearchTree();
    104       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    105       int n = 0;
    106       var sw = new System.Diagnostics.Stopwatch();
    107       sw.Start();
    108       while (!tree.Done) {
    109 
    110         var f = Calculate();
    111         // do one more run through the tree to update the path
    112         tree.UpdatePath();
    113 
    114         n++;
    115         if (IsBetter(f, bestF)) bestF = f;
    116         if (n % 100 == 0) {
    117           sw.Stop();
    118           Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
    119           sw.Reset();
    120           sw.Start();
    121         }
    122       }
    123     }
    124 
    125     public double Calculate() {
    126       ?FITNESSFUNCTION?
    127     }
    128 
    129     ?ADDITIONALCODE?
    130 
    131     ?INTERPRETERSOURCE?
    132 
    133     ?CONSTRAINTSSOURCE?
    134188  }
    135189}";
    136190
    137191
    138     /// <summary>
    139     /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
    140     /// </summary>
    141     /// <param name="ast">An abstract syntax tree for a GPDL file</param>
    142     public void Generate(GPDefNode ast) {
    143       var problemSourceCode = new StringBuilder();
    144       problemSourceCode.AppendLine(usings);
    145 
    146       GenerateProblem(ast, problemSourceCode);
    147 
    148       problemSourceCode.Replace("?PROBLEMNAME?", ast.Name);
    149 
    150       // write the source file to disk
    151       using (var stream = new StreamWriter(ast.Name + ".cs")) {
    152         stream.WriteLine(problemSourceCode.ToString());
    153       }
    154     }
    155 
    156     private void GenerateProblem(GPDefNode ast, StringBuilder problemSourceCode) {
    157       var grammar = CreateGrammarFromAst(ast);
    158       var problemClassCode =
    159         solverTemplate
    160           .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
    161           .Replace("?IDENT?", ast.Name)
    162           .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
    163           .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
    164           .Replace("?INITCODE?", ast.InitCodeNode.SrcCode)
    165           .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
    166           .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
    167           ;
    168 
    169       problemSourceCode.AppendLine(problemClassCode).AppendLine();
    170     }
    171 
    172     private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
    173 
    174       var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
    175       var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
    176       string startSymbolName = ast.Rules.First().NtSymbol;
    177 
    178       // create startSymbol
    179       var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
    180       var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
    181 
    182       // add all production rules
    183       foreach (var rule in ast.Rules) {
    184         var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
    185         foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
    186           g.AddProductionRule(ntSymbol, alt);
    187         }
    188         // local initialization code
    189         if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
    190       }
    191       return g;
    192     }
    193 
    194     private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
    195       return (from fieldDef in Util.ExtractParameters(formalParameters)
    196               select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
    197         ToList();
    198     }
    199 
    200     private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
    201       foreach (var alt in altNode.Alternatives) {
    202         yield return GetSequence(alt.Sequence, allSymbols);
    203       }
    204     }
    205 
    206     private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
    207       Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
    208       var l = new List<ISymbol>();
    209       foreach (var node in sequence) {
    210         var callSymbolNode = node as CallSymbolNode;
    211         var actionNode = node as RuleActionNode;
    212         if (callSymbolNode != null) {
    213           Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
    214           // create a new symbol with actual parameters
    215           l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
    216         } else if (actionNode != null) {
    217           l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
    218         }
    219       }
    220       return new Sequence(l);
    221     }
    222 
    223     // produces helper methods for the attributes of all terminal nodes
    224     private string GenerateConstraintMethods(List<SymbolNode> symbols) {
    225       var sb = new StringBuilder();
    226       var terminals = symbols.OfType<TerminalNode>();
    227       foreach (var t in terminals) {
    228         sb.AppendLine(GenerateConstraintMethods(t));
     192    public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) {
     193      var solverSourceCode = new SourceBuilder();
     194      solverSourceCode.Append(solverTemplate)
     195        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
     196        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
     197        .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
     198        .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
     199        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
     200        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
     201        .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar))
     202      ;
     203
     204      problemSourceCode.Append(solverSourceCode.ToString());
     205    }
     206
     207    #region same as random search
     208    private string GenerateTransitionTable(IGrammar grammar) {
     209      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     210      var sb = new SourceBuilder();
     211
     212      // state idx = idx of the corresponding symbol in the grammar
     213      var allSymbols = grammar.Symbols.ToList();
     214      var attributes = new List<string>();
     215      foreach (var s in grammar.Symbols) {
     216        var targetStates = new List<int>();
     217        if (grammar.IsTerminal(s)) {
     218          foreach (var att in s.Attributes) {
     219            targetStates.Add(allSymbols.Count + attributes.Count);
     220            attributes.Add(s.Name + "_" + att);
     221          }
     222        } else {
     223          if (grammar.NumberOfAlternatives(s) > 1) {
     224            foreach (var alt in grammar.GetAlternatives(s)) {
     225              // only single-symbol alternatives are supported
     226              Debug.Assert(alt.Count() == 1);
     227              targetStates.Add(allSymbols.IndexOf(alt.Single()));
     228            }
     229          } else {
     230            // rule is a sequence of symbols
     231            var seq = grammar.GetAlternatives(s).Single();
     232            targetStates.AddRange(seq.Select(symb => allSymbols.IndexOf(symb)));
     233          }
     234        }
     235
     236        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
     237
     238        var idxOfSourceState = allSymbols.IndexOf(s);
     239        sb.AppendFormat("// {0}", s).AppendLine();
     240        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
     241      }
     242      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
     243        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
     244        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
    229245      }
    230246      return sb.ToString();
    231247    }
    232 
    233     // generates helper methods for the attributes of a given terminal node
    234     private string GenerateConstraintMethods(TerminalNode t) {
    235       var sb = new StringBuilder();
    236       foreach (var c in t.Constraints) {
    237         var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
    238         if (c.Type == ConstraintNodeType.Range) {
    239           sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
    240           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
    241         } else if (c.Type == ConstraintNodeType.Set) {
    242           sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
    243         }
    244         sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
     248    private string GenerateSubtreeCountTable(IGrammar grammar) {
     249      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     250      var sb = new SourceBuilder();
     251
     252      // state idx = idx of the corresponding symbol in the grammar
     253      var allSymbols = grammar.Symbols.ToList();
     254      var attributes = new List<string>();
     255      foreach (var s in grammar.Symbols) {
     256        int subtreeCount;
     257        if (grammar.IsTerminal(s)) {
     258          subtreeCount = s.Attributes.Count();
     259          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
     260        } else {
     261          if (grammar.NumberOfAlternatives(s) > 1) {
     262            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
     263            subtreeCount = 1;
     264          } else {
     265            subtreeCount = grammar.GetAlternative(s, 0).Count();
     266          }
     267        }
     268
     269        sb.AppendFormat("// {0}", s).AppendLine();
     270        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
     271      }
     272
     273      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
     274        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
     275        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
    245276      }
    246277      return sb.ToString();
    247278    }
    248 
    249     private string GenerateInterpreterSource(AttributedGrammar grammar) {
    250       var sb = new StringBuilder();
    251 
    252 
    253       // get formal parameters of start symbol
    254       var attr = grammar.StartSymbol.Attributes;
    255 
    256       var formalParameter = grammar.StartSymbol.GetAttributeString();
    257       // actual parameter are the same as formalparameter only without type identifier
    258       string actualParameter;
    259       if (attr.Any())
    260         actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
    261       else
    262         actualParameter = string.Empty;
    263 
    264       // generate entry method for evaluation. This is called from the min/max function
    265       // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
    266       sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
    267       sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
    268       sb.AppendLine("}");
    269 
    270       // generate methods for all nonterminals and terminals using the grammar instance
    271       foreach (var s in grammar.NonTerminalSymbols) {
    272         sb.AppendLine(GenerateInterpreterMethod(grammar, s));
    273       }
    274       foreach (var s in grammar.TerminalSymbols) {
    275         sb.AppendLine(GenerateTerminalInterpreterMethod(s));
    276       }
     279    #endregion
     280    private string GenerateAlternativesCountMethod(IGrammar grammar) {
     281      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
     282      var sb = new SourceBuilder();
     283      sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock();
     284      sb.AppendLine("switch(symbol) {");
     285      foreach (var s in grammar.Symbols) {
     286        sb.AppendFormat("case \"{0}\":", s.Name).AppendLine();
     287        int altCount;
     288        if (grammar.IsTerminal(s)) {
     289          if (s.Attributes.Any()) {
     290            sb.Append("switch(attribute) {").BeginBlock();
     291            foreach (var att in s.Attributes) {
     292              sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine();
     293            }
     294            sb.Append("} // switch").EndBlock();
     295          } else {
     296            sb.AppendLine("return 0;");
     297          }
     298        } else {
     299          sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine();
     300        }
     301
     302
     303      }
     304      sb.AppendLine("} // switch");
     305      sb.Append("}").EndBlock();
    277306      return sb.ToString();
    278     }
    279 
    280     private string GenerateTerminalInterpreterMethod(ISymbol s) {
    281       var sb = new StringBuilder();
    282       // if the terminal symbol has attributes then we must create values for these attributes
    283       if (!s.Attributes.Any())
    284         sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
    285       else
    286         sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
    287 
    288       sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
    289       // each field must match a formal parameter, assign a value for each parameter
    290       int i = 0;
    291       foreach (var element in s.Attributes) {
    292         // read next symbol
    293         sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
    294         sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
    295       }
    296       sb.AppendLine("}");
    297       return sb.ToString();
    298     }
    299 
    300     private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
    301       var sb = new StringBuilder();
    302       if (!s.Attributes.Any())
    303         sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
    304       else
    305         sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
    306 
    307       // generate local definitions
    308       sb.AppendLine(g.GetLocalDefinitions(s));
    309 
    310 
    311 
    312       // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
    313       var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
    314         .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
    315 
    316       if (altsWithSemActions.Length > 1) {
    317         sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
    318 
    319         int i = 0;
    320         sb.AppendLine("switch(tree.GetNextAlternative()) {");
    321         // generate a case for each alternative
    322         foreach (var alt in altsWithSemActions) {
    323           sb.AppendFormat("case {0}: {{ ", i).AppendLine();
    324           sb.AppendLine("SearchTree subtree = null; ");
    325 
    326           // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
    327           // handling multiple non-terminals here would require a change in the structure of the search tree
    328           // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
    329           Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
    330           foreach (var altSymb in alt) {
    331             if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
    332             sb.AppendLine(GenerateSourceForAction(altSymb));
    333           }
    334           i++;
    335           sb.AppendLine("break;").AppendLine("}");
    336         }
    337         sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
    338       } else {
    339         sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
    340         int j = 0;
    341         sb.AppendLine("SearchTree subtree = null; ");
    342         foreach (var altSymb in altsWithSemActions.Single()) {
    343           if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
    344           sb.AppendLine(GenerateSourceForAction(altSymb));
    345         }
    346       }
    347       sb.AppendLine("}");
    348       return sb.ToString();
    349     }
    350 
    351     // helper for generating calls to other symbol methods
    352     private string GenerateSourceForAction(ISymbol s) {
    353       var action = s as SemanticSymbol;
    354       if (action != null) {
    355         return action.Code + ";";
    356       } else {
    357         if (!s.Attributes.Any())
    358           return string.Format("{0}(subtree);", s.Name);
    359         else
    360           return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
    361       }
    362307    }
    363308  }
Note: See TracChangeset for help on using the changeset viewer.