[10100] | 1 | using System.Collections.Generic;
|
---|
| 2 | using System.Diagnostics;
|
---|
| 3 | using System.IO;
|
---|
| 4 | using System.Linq;
|
---|
| 5 | using HeuristicLab.Grammars;
|
---|
| 6 | using Attribute = HeuristicLab.Grammars.Attribute;
|
---|
| 7 |
|
---|
| 8 | namespace CodeGenerator {
|
---|
| 9 | // code generator for problem class
|
---|
| 10 | public class ProblemCodeGen {
|
---|
| 11 | private const string usings = @"
|
---|
| 12 | using System.Collections.Generic;
|
---|
| 13 | using System.Linq;
|
---|
| 14 | using System;
|
---|
| 15 | using System.Text.RegularExpressions;
|
---|
| 16 | ";
|
---|
| 17 |
|
---|
| 18 | private const string problemTemplate = @"
|
---|
| 19 | namespace ?PROBLEMNAME? {
|
---|
| 20 | public interface IGpdlProblem {
|
---|
| 21 | int GetCardinality(string terminalSymbol, string attribute);
|
---|
| 22 | }
|
---|
| 23 | public interface ISolverState {
|
---|
| 24 | void Reset();
|
---|
| 25 | int PeekNextAlternative();
|
---|
| 26 | void Follow(int idx);
|
---|
| 27 | void Unwind();
|
---|
| 28 | }
|
---|
| 29 |
|
---|
| 30 | public sealed class ?IDENT?Problem : IGpdlProblem {
|
---|
| 31 |
|
---|
| 32 | private readonly Dictionary<string, Dictionary<string, int>> cardinalities = new Dictionary<string, Dictionary<string, int>>();
|
---|
| 33 | public ?IDENT?Problem() {
|
---|
| 34 | Initialize();
|
---|
| 35 |
|
---|
| 36 | ?CONSTRUCTORSOURCE?
|
---|
| 37 |
|
---|
| 38 | }
|
---|
| 39 |
|
---|
| 40 | private void Initialize() {
|
---|
| 41 | ?INITSOURCE?
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | private ISolverState _state;
|
---|
| 45 | public double Evaluate(ISolverState _state) {
|
---|
| 46 | this._state = _state;
|
---|
| 47 | ?FITNESSFUNCTION?
|
---|
| 48 | }
|
---|
| 49 |
|
---|
| 50 | ?ADDITIONALCODE?
|
---|
| 51 |
|
---|
| 52 | ?INTERPRETERSOURCE?
|
---|
| 53 |
|
---|
| 54 | ?CONSTRAINTSSOURCE?
|
---|
| 55 |
|
---|
| 56 | public int GetCardinality(string terminal, string attribute) {
|
---|
| 57 | return cardinalities[terminal][attribute];
|
---|
| 58 | }
|
---|
| 59 | }
|
---|
| 60 | }";
|
---|
| 61 |
|
---|
| 62 |
|
---|
| 63 | /// <summary>
|
---|
| 64 | /// Generates the source code for a brute force searcher that can be compiled with a C# compiler
|
---|
| 65 | /// </summary>
|
---|
| 66 | /// <param name="ast">An abstract syntax tree for a GPDL file</param>
|
---|
| 67 | public void Generate(GPDefNode ast) {
|
---|
| 68 | var problemSourceCode = new SourceBuilder();
|
---|
| 69 | problemSourceCode.AppendLine(usings);
|
---|
| 70 |
|
---|
| 71 | GenerateProblemSource(ast, problemSourceCode);
|
---|
| 72 | GenerateSolvers(ast, problemSourceCode);
|
---|
| 73 |
|
---|
| 74 | problemSourceCode
|
---|
| 75 | .Replace("?PROBLEMNAME?", ast.Name)
|
---|
| 76 | .Replace("?IDENT?", ast.Name);
|
---|
| 77 |
|
---|
| 78 |
|
---|
| 79 | // write the source file to disk
|
---|
| 80 | using (var stream = new StreamWriter(ast.Name + ".cs")) {
|
---|
| 81 | stream.WriteLine(problemSourceCode.ToString());
|
---|
| 82 | }
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 | private void GenerateProblemSource(GPDefNode ast, SourceBuilder problemSourceCode) {
|
---|
| 86 | var grammar = CreateGrammarFromAst(ast);
|
---|
| 87 | problemSourceCode
|
---|
| 88 | .AppendLine(problemTemplate)
|
---|
| 89 | .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
|
---|
| 90 | .Replace("?CONSTRUCTORSOURCE?", GenerateConstructorSource(ast))
|
---|
| 91 | .Replace("?INITSOURCE?", ast.InitCodeNode.SrcCode)
|
---|
| 92 | .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
|
---|
| 93 | .Replace("?INTERPRETERSOURCE?", GenerateInterpreterSource(grammar))
|
---|
| 94 | .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
|
---|
| 95 | ;
|
---|
| 96 | }
|
---|
| 97 |
|
---|
| 98 | private void GenerateSolvers(GPDefNode ast, SourceBuilder solverSourceCode) {
|
---|
| 99 | var grammar = CreateGrammarFromAst(ast);
|
---|
| 100 | var randomSearchCodeGen = new RandomSearchCodeGen();
|
---|
| 101 | randomSearchCodeGen.Generate(grammar, ast.FitnessFunctionNode.Maximization, ast.Terminals, solverSourceCode);
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | #region create grammar instance from AST
|
---|
| 105 | private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
|
---|
| 106 |
|
---|
| 107 | var nonTerminals = ast.NonTerminals
|
---|
| 108 | .Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters)))
|
---|
| 109 | .ToArray();
|
---|
| 110 | var terminals = ast.Terminals
|
---|
| 111 | .Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters)))
|
---|
| 112 | .ToArray();
|
---|
| 113 | string startSymbolName = ast.Rules.First().NtSymbol;
|
---|
| 114 |
|
---|
| 115 | // create startSymbol
|
---|
| 116 | var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
|
---|
| 117 | var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
|
---|
| 118 |
|
---|
| 119 | // add all production rules
|
---|
| 120 | foreach (var rule in ast.Rules) {
|
---|
| 121 | var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
|
---|
| 122 | foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
|
---|
| 123 | g.AddProductionRule(ntSymbol, alt);
|
---|
| 124 | }
|
---|
| 125 | // local initialization code
|
---|
| 126 | if (!string.IsNullOrEmpty(rule.LocalCode)) g.AddLocalDefinitions(ntSymbol, rule.LocalCode);
|
---|
| 127 | }
|
---|
| 128 | return g;
|
---|
| 129 | }
|
---|
| 130 |
|
---|
| 131 | private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
|
---|
| 132 | return (from fieldDef in Util.ExtractParameters(formalParameters)
|
---|
| 133 | select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
|
---|
| 134 | ToList();
|
---|
| 135 | }
|
---|
| 136 |
|
---|
| 137 | private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
|
---|
| 138 | foreach (var alt in altNode.Alternatives) {
|
---|
| 139 | yield return GetSequence(alt.Sequence, allSymbols);
|
---|
| 140 | }
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 | private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
|
---|
| 144 | Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
|
---|
| 145 | var l = new List<ISymbol>();
|
---|
| 146 | foreach (var node in sequence) {
|
---|
| 147 | var callSymbolNode = node as CallSymbolNode;
|
---|
| 148 | var actionNode = node as RuleActionNode;
|
---|
| 149 | if (callSymbolNode != null) {
|
---|
| 150 | Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
|
---|
| 151 | // create a new symbol with actual parameters
|
---|
| 152 | l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
|
---|
| 153 | } else if (actionNode != null) {
|
---|
| 154 | l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
|
---|
| 155 | }
|
---|
| 156 | }
|
---|
| 157 | return new Sequence(l);
|
---|
| 158 | }
|
---|
| 159 | #endregion
|
---|
| 160 |
|
---|
| 161 | #region helper methods for terminal symbols
|
---|
| 162 | // produces helper methods for the attributes of all terminal nodes
|
---|
| 163 | private string GenerateConstraintMethods(IEnumerable<SymbolNode> symbols) {
|
---|
| 164 | var sb = new SourceBuilder();
|
---|
| 165 | var terminals = symbols.OfType<TerminalNode>();
|
---|
| 166 | foreach (var t in terminals) {
|
---|
| 167 | GenerateConstraintMethods(t, sb);
|
---|
| 168 | }
|
---|
| 169 | return sb.ToString();
|
---|
| 170 | }
|
---|
| 171 |
|
---|
| 172 |
|
---|
| 173 | // generates helper methods for the attributes of a given terminal node
|
---|
| 174 | private void GenerateConstraintMethods(TerminalNode t, SourceBuilder sb) {
|
---|
| 175 | foreach (var c in t.Constraints) {
|
---|
| 176 | var fieldType = t.FieldDefinitions.First(d => d.Identifier == c.Ident).Type;
|
---|
| 177 | if (c.Type == ConstraintNodeType.Range) {
|
---|
| 178 | sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
|
---|
| 179 | sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
|
---|
| 180 | // 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();
|
---|
| 181 | 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();
|
---|
| 182 | } else if (c.Type == ConstraintNodeType.Set) {
|
---|
| 183 | sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
|
---|
| 184 | sb.AppendFormat("private readonly {0}[] values_{1}_{2};", fieldType, t.Ident, c.Ident).AppendLine();
|
---|
| 185 | sb.AppendFormat("public {0} Get{1}_{2}(ISolverState _state) {{ return values_{1}_{2}[_state.PeekNextAlternative()]; }}", fieldType, t.Ident, c.Ident).AppendLine();
|
---|
| 186 | }
|
---|
| 187 | }
|
---|
| 188 | }
|
---|
| 189 | private string GenerateConstructorSource(GPDefNode ast) {
|
---|
| 190 | var sb = new SourceBuilder();
|
---|
| 191 | // generate code to initialize the tables for terminals
|
---|
| 192 | foreach (var t in ast.Terminals.OfType<TerminalNode>()) {
|
---|
| 193 | if (t.Constraints.Any()) {
|
---|
| 194 | foreach (var constraint in t.Constraints) {
|
---|
| 195 | sb.AppendFormat("values_{0}_{1} = GetAllowed{0}_{1}().ToArray();", t.Ident, constraint.Ident);
|
---|
| 196 | }
|
---|
| 197 | sb.AppendFormat("cardinalities[\"{0}\"] = new Dictionary<string, int>() {{ ", t.Ident);
|
---|
| 198 | foreach (var constraint in t.Constraints) {
|
---|
| 199 | sb.AppendFormat("{{ \"{1}\", values_{0}_{1}.Length }}, ", t.Ident, constraint.Ident);
|
---|
| 200 | }
|
---|
| 201 | sb.Append("};").AppendLine();
|
---|
| 202 | }
|
---|
| 203 | }
|
---|
| 204 | return sb.ToString();
|
---|
| 205 | }
|
---|
| 206 |
|
---|
| 207 |
|
---|
| 208 | #endregion
|
---|
| 209 |
|
---|
| 210 | private string GenerateInterpreterSource(AttributedGrammar grammar) {
|
---|
| 211 | var sb = new SourceBuilder();
|
---|
| 212 |
|
---|
| 213 | // generate methods for all nonterminals and terminals using the grammar instance
|
---|
| 214 | foreach (var s in grammar.NonTerminalSymbols) {
|
---|
| 215 | GenerateInterpreterMethod(grammar, s, sb);
|
---|
| 216 | }
|
---|
| 217 | foreach (var s in grammar.TerminalSymbols) {
|
---|
| 218 | GenerateTerminalInterpreterMethod(s, sb);
|
---|
| 219 | }
|
---|
| 220 | return sb.ToString();
|
---|
| 221 | }
|
---|
| 222 |
|
---|
| 223 | private void GenerateInterpreterMethod(AttributedGrammar g, ISymbol s, SourceBuilder sb) {
|
---|
| 224 | // if this is the start symbol we additionally have to create the method which can be called from the fitness function
|
---|
| 225 | if (g.StartSymbol.Equals(s)) {
|
---|
| 226 | if (!s.Attributes.Any())
|
---|
| 227 | sb.AppendFormat("private void {0}() {{", s.Name).BeginBlock();
|
---|
| 228 | else
|
---|
| 229 | sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
|
---|
| 230 |
|
---|
| 231 | // get formal parameters of start symbol
|
---|
| 232 | var attr = g.StartSymbol.Attributes;
|
---|
| 233 |
|
---|
| 234 | // actual parameter are the same as formalparameter only without type identifier
|
---|
| 235 | string actualParameter;
|
---|
| 236 | if (attr.Any())
|
---|
| 237 | actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
|
---|
| 238 | else
|
---|
| 239 | actualParameter = string.Empty;
|
---|
| 240 | sb.AppendLine("_state.Reset();");
|
---|
| 241 | sb.AppendFormat("{0}(_state, {1});", g.StartSymbol.Name, actualParameter).AppendLine();
|
---|
| 242 | sb.AppendLine("}").EndBlock();
|
---|
| 243 | }
|
---|
| 244 |
|
---|
| 245 | if (!s.Attributes.Any())
|
---|
| 246 | sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
|
---|
| 247 | else
|
---|
| 248 | sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
|
---|
| 249 |
|
---|
| 250 | // generate local definitions
|
---|
| 251 | sb.AppendLine(g.GetLocalDefinitions(s));
|
---|
| 252 |
|
---|
| 253 | var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
|
---|
| 254 |
|
---|
| 255 | if (altsWithSemActions.Length > 1) {
|
---|
| 256 | GenerateSwitchStatement(altsWithSemActions, sb);
|
---|
| 257 | } else {
|
---|
| 258 | int i = 0;
|
---|
| 259 | foreach (var altSymb in altsWithSemActions.Single()) {
|
---|
| 260 | GenerateSourceForAction(i, altSymb, sb);
|
---|
| 261 | if (!(altSymb is SemanticSymbol)) i++;
|
---|
| 262 | }
|
---|
| 263 | }
|
---|
| 264 | sb.Append("}").EndBlock();
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | private void GenerateSwitchStatement(IEnumerable<Sequence> alts, SourceBuilder sb) {
|
---|
| 268 | sb.Append("switch(_state.PeekNextAlternative()) {").BeginBlock();
|
---|
| 269 | // generate a case for each alternative
|
---|
| 270 | int i = 0;
|
---|
| 271 | foreach (var alt in alts) {
|
---|
| 272 | sb.AppendFormat("case {0}: {{ ", i).BeginBlock();
|
---|
| 273 |
|
---|
| 274 | // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
|
---|
| 275 | // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
|
---|
| 276 | Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
|
---|
| 277 | foreach (var altSymb in alt) {
|
---|
| 278 | GenerateSourceForAction(0, altSymb, sb); // index is always 0 because of the assertion above
|
---|
| 279 | }
|
---|
| 280 | i++;
|
---|
| 281 | sb.AppendLine("break;").Append("}").EndBlock();
|
---|
| 282 | }
|
---|
| 283 | sb.AppendLine("default: throw new System.InvalidOperationException();").Append("}").EndBlock();
|
---|
| 284 | }
|
---|
| 285 |
|
---|
| 286 | // helper for generating calls to other symbol methods
|
---|
| 287 | private void GenerateSourceForAction(int idx, ISymbol s, SourceBuilder sb) {
|
---|
| 288 | var action = s as SemanticSymbol;
|
---|
| 289 | if (action != null)
|
---|
| 290 | sb.Append(action.Code + ";");
|
---|
| 291 | else if (!s.Attributes.Any())
|
---|
| 292 | sb.AppendFormat("_state.Follow({0}); {1}(_state); _state.Unwind();", idx, s.Name);
|
---|
| 293 | else sb.AppendFormat("_state.Follow({0}); {1}(_state, {2}); _state.Unwind();", idx, s.Name, s.GetAttributeString());
|
---|
| 294 | sb.AppendLine();
|
---|
| 295 | }
|
---|
| 296 |
|
---|
| 297 | private string GenerateTerminalInterpreterMethod(ISymbol s, SourceBuilder sb) {
|
---|
| 298 | // if the terminal symbol has attributes then we must samples values for these attributes
|
---|
| 299 | if (!s.Attributes.Any())
|
---|
| 300 | sb.AppendFormat("private void {0}(ISolverState _state) {{", s.Name).BeginBlock();
|
---|
| 301 | else
|
---|
| 302 | sb.AppendFormat("private void {0}(ISolverState _state, {1}) {{", s.Name, s.GetAttributeString()).BeginBlock();
|
---|
| 303 |
|
---|
| 304 | // each field must match a formal parameter, assign a value for each parameter
|
---|
| 305 | int i = 0;
|
---|
| 306 | foreach (var element in s.Attributes) {
|
---|
| 307 | sb.AppendFormat("_state.Follow({0});", i++).AppendLine();
|
---|
| 308 | sb.AppendFormat("{0} = Get{1}_{0}(_state);", element.Name, s.Name).AppendLine();
|
---|
| 309 | sb.AppendFormat("_state.Unwind();").AppendLine();
|
---|
| 310 | }
|
---|
| 311 | sb.Append("}").EndBlock();
|
---|
| 312 | return sb.ToString();
|
---|
| 313 | }
|
---|
| 314 | }
|
---|
| 315 | }
|
---|