source: branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs @ 15861

Last change on this file since 15861 was 15861, checked in by lkammere, 3 years ago

#2886: Make constant optimization toggleable in algorithm.

File size: 9.5 KB
Line 
1using System.Collections.Generic;
2using System.Diagnostics;
3using System.Linq;
4using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
5using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
6using HeuristicLab.Problems.DataAnalysis.Symbolic;
7
8namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
9  public class Grammar {
10
11    public Symbol StartSymbol { get; }
12
13    public Hasher<int> Hasher { get; }
14
15    #region Symbols
16
17    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }
18
19    public NonterminalSymbol Var;
20    public IReadOnlyList<VariableTerminalSymbol> VarTerminals;
21
22    public NonterminalSymbol Expr;
23    public NonterminalSymbol Term;
24    public NonterminalSymbol Factor;
25    public NonterminalSymbol LogFactor;
26    public NonterminalSymbol ExpFactor;
27    public NonterminalSymbol SinFactor;
28
29    public NonterminalSymbol SimpleExpr;
30    public NonterminalSymbol SimpleTerm;
31
32    public NonterminalSymbol InvExpr;
33    public NonterminalSymbol InvTerm;
34
35    public TerminalSymbol Addition;
36    public TerminalSymbol Multiplication;
37    public TerminalSymbol Log;
38    public TerminalSymbol Exp;
39    public TerminalSymbol Sin;
40    public TerminalSymbol Inv;
41
42    public TerminalSymbol Const;
43
44    #endregion
45
46    #region HL Symbols for Parsing ExpressionTrees
47
48    private ISymbol constSy;
49    private ISymbol varSy;
50
51    private ISymbol addSy;
52    private ISymbol mulSy;
53    private ISymbol logSy;
54    private ISymbol expSy;
55    private ISymbol divSy;
56    private ISymbol sinSy;
57
58    private ISymbol rootSy;
59    private ISymbol startSy;
60
61    private InfixExpressionFormatter infixExpressionFormatter;
62    #endregion
63
64    public Grammar(string[] variables) {
65      #region Define Symbols
66      Var = new NonterminalSymbol("Var");
67
68      Expr = new NonterminalSymbol("Expr");
69      Term = new NonterminalSymbol("Term");
70      Factor = new NonterminalSymbol("Factor");
71      LogFactor = new NonterminalSymbol("LogFactor");
72      ExpFactor = new NonterminalSymbol("ExpFactor");
73      SinFactor = new NonterminalSymbol("SinFactor");
74
75      SimpleExpr = new NonterminalSymbol("SimpleExpr");
76      SimpleTerm = new NonterminalSymbol("SimpleTerm");
77
78      InvExpr = new NonterminalSymbol("InvExpr");
79      InvTerm = new NonterminalSymbol("InvTerm");
80
81      Addition = new TerminalSymbol("+");
82      Multiplication = new TerminalSymbol("*");
83      Log = new TerminalSymbol("log");
84      Exp = new TerminalSymbol("exp");
85      Sin = new TerminalSymbol("sin");
86      Inv = new TerminalSymbol("inv");
87
88      Const = new TerminalSymbol("c");
89      #endregion
90
91      #region Production rules
92      StartSymbol = Expr;
93
94      Dictionary<Symbol, IReadOnlyList<Production>> productions = new Dictionary<Symbol, IReadOnlyList<Production>>();
95
96      // Map each variable to a separate production rule of the "Var" nonterminal symbol.
97      VarTerminals = variables.Select(v => new VariableTerminalSymbol(v)).ToArray();
98      productions[Var] = VarTerminals.Select(v => new Production(v)).ToArray();
99
100      productions[Expr] = new[] {
101        new Production(Const, Term, Multiplication, Expr, Addition),
102        new Production(Const, Term, Multiplication, Const, Addition)
103      };
104
105      productions[Term] = new[] {
106        new Production(Factor, Term, Multiplication),
107        new Production(Factor),
108        new Production(InvExpr, Inv)
109      };
110
111      productions[Factor] = new[] {
112        new Production(Var),
113        new Production(LogFactor),
114        new Production(ExpFactor),
115        new Production(SinFactor),
116      };
117
118      productions[LogFactor] = new[] { new Production(SimpleExpr, Log) };
119      productions[ExpFactor] = new[] { new Production(Const, SimpleTerm, Multiplication, Exp) };
120      productions[SinFactor] = new[] { new Production(SimpleExpr, Sin) };
121
122      productions[SimpleExpr] = new[] {
123        new Production(Const, SimpleTerm, Multiplication, SimpleExpr, Addition),
124        new Production(Const, SimpleTerm, Multiplication, Const, Addition)
125      };
126
127      productions[SimpleTerm] = new[] {
128        new Production(Var, SimpleTerm, Multiplication),
129        new Production(Var)
130      };
131
132      productions[InvExpr] = new[] {
133        new Production(Const, InvTerm, Multiplication, InvExpr, Addition),
134        new Production(Const, InvTerm, Multiplication, Const, Addition)
135      };
136
137      productions[InvTerm] = new[] {
138        new Production(Factor, InvTerm, Multiplication),
139        new Production(Factor)
140      };
141
142      Productions = productions;
143      #endregion
144
145      #region Parsing to SymbolicExpressionTree
146      var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();
147      symbolicExpressionGrammar.ConfigureAsDefaultRegressionGrammar();
148
149      constSy = symbolicExpressionGrammar.Symbols.OfType<Constant>().First();
150      varSy = symbolicExpressionGrammar.Symbols.OfType<Variable>().First();
151      addSy = symbolicExpressionGrammar.Symbols.OfType<Addition>().First();
152      mulSy = symbolicExpressionGrammar.Symbols.OfType<Multiplication>().First();
153      logSy = symbolicExpressionGrammar.Symbols.OfType<Logarithm>().First();
154      expSy = symbolicExpressionGrammar.Symbols.OfType<Exponential>().First();
155      divSy = symbolicExpressionGrammar.Symbols.OfType<Division>().First();
156      sinSy = symbolicExpressionGrammar.Symbols.OfType<Sine>().First();
157
158      rootSy = symbolicExpressionGrammar.Symbols.OfType<ProgramRootSymbol>().First();
159      startSy = symbolicExpressionGrammar.Symbols.OfType<StartSymbol>().First();
160
161      infixExpressionFormatter = new InfixExpressionFormatter();
162      #endregion
163
164      Hasher = new IntHasher(this);
165    }
166
167    public int GetComplexity(SymbolString s) {
168      int c = 0;
169      int length = s.Count();
170      for (int i = 0; i < length; i++) {
171        if (s[i] is NonterminalSymbol || s[i] is VariableTerminalSymbol) c++;
172      }
173      return c;
174    }
175
176    #region Parse to SymbolicExpressionTree
177
178    public string ToInfixString(SymbolString sentence) {
179      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
180      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
181
182      return infixExpressionFormatter.Format(ParseSymbolicExpressionTree(sentence));
183    }
184
185    public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {
186      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
187      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
188
189      var rootNode = rootSy.CreateTreeNode();
190      var startNode = startSy.CreateTreeNode();
191      rootNode.AddSubtree(startNode);
192
193      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
194      startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));
195
196      return new SymbolicExpressionTree(rootNode);
197    }
198
199    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<TerminalSymbol> parseStack) {
200      TerminalSymbol currentSymbol = parseStack.Pop();
201
202      ISymbolicExpressionTreeNode parsedSubTree = null;
203
204      if (currentSymbol == Addition) {
205        parsedSubTree = addSy.CreateTreeNode();
206        ISymbolicExpressionTreeNode rightSubtree = ParseSymbolicExpressionTree(parseStack);
207        if (rightSubtree is ConstantTreeNode) {
208          ((ConstantTreeNode)rightSubtree).Value = 0.0;
209        }
210        parsedSubTree.AddSubtree(rightSubtree); // left part
211
212        ISymbolicExpressionTreeNode leftSubtree = ParseSymbolicExpressionTree(parseStack);
213        if (leftSubtree is ConstantTreeNode) {
214          ((ConstantTreeNode)leftSubtree).Value = 0.0;
215        }
216        parsedSubTree.AddSubtree(leftSubtree); // right part
217
218      } else if (currentSymbol == Multiplication) {
219        parsedSubTree = mulSy.CreateTreeNode();
220        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // left part
221        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // right part
222
223      } else if (currentSymbol == Log) {
224        parsedSubTree = logSy.CreateTreeNode();
225        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
226
227      } else if (currentSymbol == Exp) {
228        parsedSubTree = expSy.CreateTreeNode();
229        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
230
231      } else if (currentSymbol == Sin) {
232        parsedSubTree = sinSy.CreateTreeNode();
233        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
234
235      } else if (currentSymbol == Inv) {
236        parsedSubTree = divSy.CreateTreeNode();
237        ConstantTreeNode dividend = (ConstantTreeNode)constSy.CreateTreeNode();
238        dividend.Value = 1.0;
239        parsedSubTree.AddSubtree(dividend);
240        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
241
242      } else if (currentSymbol == Const) {
243        ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();
244        constNode.Value = 1.0;
245        parsedSubTree = constNode;
246
247      } else if (currentSymbol is VariableTerminalSymbol) {
248        VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();
249        varNode.Weight = 1.0;
250        varNode.VariableName = currentSymbol.StringRepresentation;
251        parsedSubTree = varNode;
252      }
253
254      Debug.Assert(parsedSubTree != null);
255      return parsedSubTree;
256    }
257    #endregion
258  }
259}
Note: See TracBrowser for help on using the repository browser.