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 | }
|
---|