source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs @ 12014

using System;
using System.Collections.Generic;
using System.Diagnostics.Eventing.Reader;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.Remoting.Messaging;
using System.Text;
using System.Threading.Tasks;
using AutoDiff;
using HeuristicLab.Common;

namespace HeuristicLab.Problems.GrammaticalOptimization {
  public class ExpressionCompiler {
    private string sentence;
    private int syIdx;
    // compiles sentences from L(G(Expr)) using AutoDiff
    // does not compile to IL it is only necessary to calculate gradients for parameter optimization
    // Expr -> Term { ('+' | '-' | '^' ) Term } 
    // Term -> Fact { ('*' | '%' | '/') Fact }
    // Fact -> '!' Expr | '(' Expr ')' | Var | const | one
    // Var -> 'a'..'z'
    // const -> '0' .. '9'
    // one -> |    // pipe symbol for constant one instead of ERC 1

    // constants are completely ignored, instead we introduce a multiplicative constant factor for each term and an additive constant term for each expression

    // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR

    public void Compile(string sentence, out Term f, Variable[] variables, out Variable[] constants) {
      InitLex(sentence);
      var constantsList = new List<Variable>();
      f = Expr(variables, constantsList);
      constants = constantsList.ToArray();
    }

    private void InitLex(string sentence) {
      this.sentence = sentence;
      this.syIdx = 0;
    }

    private char CurSy() {
      if (syIdx >= sentence.Length) return '\0';
      return sentence[syIdx];
    }
    private void NewSy() {
      if (syIdx < sentence.Length) syIdx++;
    }

    // helper for xor
    private Term Not(Term x) {
      return 1.0 - x;
    }

    private Term Expr(IList<Variable> variables, IList<Variable> constants) {
      var terms = new List<Term>();
      terms.Add(Term(variables, constants));
      var curSy = CurSy();
      while (curSy == '+' || curSy == '-' || curSy == '^') {
        if (curSy == '+') {
          NewSy();
          terms.Add(Term(variables, constants));
        } else if (curSy == '-') {
          NewSy();
          terms.Add(-Term(variables, constants)); // minus
        } else {
          NewSy();
          throw new NotImplementedException();
          // var e = Expr(variables, constants);
          // r = Not(r) * e + r * Not(e); // xor = (!x AND y) OR (x AND !y)
        }
        curSy = CurSy();
      }

      // at this point we might have multiple constants in the list of terms but we only need one of them
      var firstConstant = terms.OfType<Variable>().FirstOrDefault(); // if a term is only a variable then it must be a constant (otherwise (for real variables) it would be a product of two constants)
      if (firstConstant == null) {
        // no constant found => add a constant offset for each full expression
        var offset = new Variable();
        constants.Add(offset);
        terms.Add(offset);
      } else {
        // there is already a constant => remove all others if there are more
        var otherConsts = terms.OfType<Variable>().Where(t => t != firstConstant).ToArray();
        foreach (var otherConst in otherConsts) {
          terms.Remove(otherConst);
          constants.Remove(otherConst);
        }
      }
      return TermBuilder.Sum(terms);
    }

    private Term Term(IList<Variable> variables, IList<Variable> constants) {
      var factors = new List<Term>();
      var f = Fact(variables, constants);
      if (f != null) factors.Add(f);
      var curSy = CurSy();
      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
        if (curSy == '*') {
          NewSy();
          f = Fact(variables, constants); // fact might return null (for constants)
          if (f != null) factors.Add(f);
        } else {
          NewSy();
          f = Fact(variables, constants);
          if (f != null) factors.Add(1.0 / f); // cannot use protected division here
        }
        curSy = CurSy();
      }

      // generate a constant factor (scale) for each full term
      // since we ignore constants in the string it could be possible that factors is still empty at this point
      var scale = new Variable();
      constants.Add(scale);
      factors.Add(scale);

      if (factors.Count == 1) return factors[0];
      else if (factors.Count == 2) return factors[0] * factors[1];
      else return TermBuilder.Product(factors[0], factors[1], factors.Skip(2).ToArray());
    }

    private Term Fact(IList<Variable> variables, IList<Variable> constants) {
      Term r = null;
      var curSy = CurSy();
      if (curSy == '!') {
        NewSy();
        r = Not(Expr(variables, constants));
      } else if (curSy == '(') {
        NewSy();
        r = Expr(variables, constants);
        if (CurSy() != ')') throw new ArgumentException();
        NewSy();
      } else if (curSy >= 'a' && curSy <= 'z') {
        var varIdx = (byte)curSy - (byte)'a';
        if (varIdx >= variables.Count) throw new ArgumentException();
        r = variables[varIdx];
        NewSy();
      } else if (curSy == '|') {
        // pipe symbol is used in the expressionextender to represent constant one (|/x). 
        // this is necessary because we also use symbols 0..9 as indices for ERCs
        r = 1.0;
        NewSy();
      } else if (curSy >= '0' && curSy <= '9') {
        int o = (byte)curSy - (byte)'0';
        //int o = Convert.ToByte(CurSy()) - Convert.ToByte('a');
        if (o < 0 || o >= 10) throw new ArgumentException();

        // completely ignore existing constants

        // var newConst = new Variable();
        // constants.Add(newConst);
        // r = newConst;
        NewSy();
      } else throw new ArgumentException();
      return r;
    }

  }
}