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

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Problems.DataAnalysis;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
  public enum GrammarRule {
    MultipleTerms,
    MultipleFactors,
    InverseTerm,
    Logarithm,
    Exponentiation,
    Sine
  }

  public class Grammar {

    public Symbol StartSymbol { get; }

    public Hasher<int> Hasher { get; }

    #region Symbols

    public IReadOnlyDictionary<Symbol, IReadOnlyList<Production>> Productions { get; }

    public NonterminalSymbol Var;
    public IReadOnlyList<VariableTerminalSymbol> VarTerminals;

    public NonterminalSymbol Expr;
    public NonterminalSymbol Term;
    public NonterminalSymbol Factor;
    public NonterminalSymbol LogFactor;
    public NonterminalSymbol ExpFactor;
    public NonterminalSymbol SinFactor;

    public NonterminalSymbol SimpleExpr;
    public NonterminalSymbol SimpleTerm;

    public NonterminalSymbol InvExpr;
    public NonterminalSymbol InvTerm;

    public TerminalSymbol Addition;
    public TerminalSymbol Multiplication;
    public TerminalSymbol Log;
    public TerminalSymbol Exp;
    public TerminalSymbol Sin;
    public TerminalSymbol Inv;

    public TerminalSymbol Const;

    #endregion

    #region HL Symbols for Parsing ExpressionTrees

    private ISymbol constSy;
    private ISymbol varSy;

    private ISymbol addSy;
    private ISymbol mulSy;
    private ISymbol logSy;
    private ISymbol expSy;
    private ISymbol divSy;
    private ISymbol sinSy;

    private ISymbol rootSy;
    private ISymbol startSy;

    private InfixExpressionFormatter infixExpressionFormatter;
    #endregion

    public Grammar(string[] variables) : this(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>()) { }

    public Grammar(string[] variables, IEnumerable<GrammarRule> includedRules) {
      #region Define Symbols
      Var = new NonterminalSymbol("Var");

      Expr = new NonterminalSymbol("Expr");
      Term = new NonterminalSymbol("Term");
      Factor = new NonterminalSymbol("Factor");
      LogFactor = new NonterminalSymbol("LogFactor");
      ExpFactor = new NonterminalSymbol("ExpFactor");
      SinFactor = new NonterminalSymbol("SinFactor");

      SimpleExpr = new NonterminalSymbol("SimpleExpr");
      SimpleTerm = new NonterminalSymbol("SimpleTerm");

      InvExpr = new NonterminalSymbol("InvExpr");
      InvTerm = new NonterminalSymbol("InvTerm");

      Addition = new TerminalSymbol("+");
      Multiplication = new TerminalSymbol("*");
      Log = new TerminalSymbol("log");
      Exp = new TerminalSymbol("exp");
      Sin = new TerminalSymbol("sin");
      Inv = new TerminalSymbol("inv");

      Const = new TerminalSymbol("c");
      #endregion

      #region Production rules
      StartSymbol = Expr;

      Dictionary<Symbol, IReadOnlyList<Production>> productions = new Dictionary<Symbol, IReadOnlyList<Production>>();

      // Map each variable to a separate production rule of the "Var" nonterminal symbol.
      VarTerminals = variables.Select(v => new VariableTerminalSymbol(v)).ToArray();
      productions[Var] = VarTerminals.Select(v => new Production(v)).ToArray();

      // Expression Grammar Rules
      var exprProductions = new List<Production>();
      if (includedRules.Contains(GrammarRule.MultipleTerms))
        exprProductions.Add(new Production(Const, Term, Multiplication, Expr, Addition));

      exprProductions.Add(new Production(Const, Term, Multiplication, Const, Addition));
      productions[Expr] = exprProductions.ToArray();

      // Term Grammar Rules
      var termProductions = new List<Production>();
      if (includedRules.Contains(GrammarRule.MultipleFactors))
        termProductions.Add(new Production(Factor, Term, Multiplication));
      if (includedRules.Contains(GrammarRule.InverseTerm))
        termProductions.Add(new Production(InvExpr, Inv));
      termProductions.Add(new Production(Factor));
      productions[Term] = termProductions.ToArray();

      // Factor Grammar Rules
      var factorProductions = new List<Production>();
      factorProductions.Add(new Production(Var));
      if (includedRules.Contains(GrammarRule.Logarithm))
        factorProductions.Add(new Production(LogFactor));
      if (includedRules.Contains(GrammarRule.Exponentiation))
        factorProductions.Add(new Production(ExpFactor));
      if (includedRules.Contains(GrammarRule.Sine))
        factorProductions.Add(new Production(SinFactor));
      productions[Factor] = factorProductions.ToArray();

      productions[LogFactor] = new[] { new Production(SimpleExpr, Log) };
      productions[ExpFactor] = new[] { new Production(Const, SimpleTerm, Multiplication, Exp) };
      productions[SinFactor] = new[] { new Production(SimpleExpr, Sin) };

      productions[SimpleExpr] = new[] {
        new Production(Const, SimpleTerm, Multiplication, SimpleExpr, Addition),
        new Production(Const, SimpleTerm, Multiplication, Const, Addition)
      };

      productions[SimpleTerm] = new[] {
        new Production(Var, SimpleTerm, Multiplication),
        new Production(Var)
      };

      productions[InvExpr] = new[] {
        new Production(Const, InvTerm, Multiplication, InvExpr, Addition),
        new Production(Const, InvTerm, Multiplication, Const, Addition)
      };

      productions[InvTerm] = new[] {
        new Production(Factor, InvTerm, Multiplication),
        new Production(Factor)
      };

      Productions = productions;
      #endregion

      #region Parsing to SymbolicExpressionTree
      var symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();
      symbolicExpressionGrammar.ConfigureAsDefaultRegressionGrammar();

      constSy = symbolicExpressionGrammar.Symbols.OfType<Constant>().First();
      varSy = symbolicExpressionGrammar.Symbols.OfType<Variable>().First();
      addSy = symbolicExpressionGrammar.Symbols.OfType<Addition>().First();
      mulSy = symbolicExpressionGrammar.Symbols.OfType<Multiplication>().First();
      logSy = symbolicExpressionGrammar.Symbols.OfType<Logarithm>().First();
      expSy = symbolicExpressionGrammar.Symbols.OfType<Exponential>().First();
      divSy = symbolicExpressionGrammar.Symbols.OfType<Division>().First();
      sinSy = symbolicExpressionGrammar.Symbols.OfType<Sine>().First();

      rootSy = symbolicExpressionGrammar.Symbols.OfType<ProgramRootSymbol>().First();
      startSy = symbolicExpressionGrammar.Symbols.OfType<StartSymbol>().First();

      infixExpressionFormatter = new InfixExpressionFormatter();
      #endregion

      Hasher = new IntHasher(this);
    }

    public int GetComplexity(SymbolString s) {
      int c = 0;
      int length = s.Count();
      for (int i = 0; i < length; i++) {
        if (s[i] is NonterminalSymbol || s[i] is VariableTerminalSymbol) c++;
      }
      return c;
    }

    public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
      SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);

      double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);

      return r2;
    }

    #region Parse to SymbolicExpressionTree

    public string ToInfixString(SymbolString sentence) {
      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");

      return infixExpressionFormatter.Format(ParseSymbolicExpressionTree(sentence));
    }

    public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {
      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");

      var rootNode = rootSy.CreateTreeNode();
      var startNode = startSy.CreateTreeNode();
      rootNode.AddSubtree(startNode);

      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
      startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));

      return new SymbolicExpressionTree(rootNode);
    }

    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<Symbol> parseStack) {
      Symbol currentSymbol = parseStack.Pop();

      ISymbolicExpressionTreeNode parsedSubTree = null;

      if (currentSymbol == Addition) {
        parsedSubTree = addSy.CreateTreeNode();
        ISymbolicExpressionTreeNode rightSubtree = ParseSymbolicExpressionTree(parseStack);
        if (rightSubtree is ConstantTreeNode) {
          ((ConstantTreeNode)rightSubtree).Value = 0.0;
        }
        parsedSubTree.AddSubtree(rightSubtree); // left part

        ISymbolicExpressionTreeNode leftSubtree = ParseSymbolicExpressionTree(parseStack);
        if (leftSubtree is ConstantTreeNode) {
          ((ConstantTreeNode)leftSubtree).Value = 0.0;
        }
        parsedSubTree.AddSubtree(leftSubtree); // right part

      } else if (currentSymbol == Multiplication) {
        parsedSubTree = mulSy.CreateTreeNode();
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // left part
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // right part

      } else if (currentSymbol == Log) {
        parsedSubTree = logSy.CreateTreeNode();
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));

      } else if (currentSymbol == Exp) {
        parsedSubTree = expSy.CreateTreeNode();
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));

      } else if (currentSymbol == Sin) {
        parsedSubTree = sinSy.CreateTreeNode();
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));

      } else if (currentSymbol == Inv) {
        parsedSubTree = divSy.CreateTreeNode();
        ConstantTreeNode dividend = (ConstantTreeNode)constSy.CreateTreeNode();
        dividend.Value = 1.0;
        parsedSubTree.AddSubtree(dividend);
        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));

      } else if (currentSymbol == Const) {
        ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();
        constNode.Value = 1.0;
        parsedSubTree = constNode;

      } else if (currentSymbol is VariableTerminalSymbol) {
        VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();
        varNode.Weight = 1.0;
        varNode.VariableName = currentSymbol.StringRepresentation;
        parsedSubTree = varNode;

      } else if (currentSymbol is NonterminalSymbol) {
        ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();
        constNode.Value = 0.0;
        parsedSubTree = constNode;
      }

      Debug.Assert(parsedSubTree != null);
      return parsedSubTree;
    }
    #endregion
  }
}