Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/18/17 12:17:13 (8 years ago)
Author:
gkronber
Message:

#2650 infix formatter also produces factor variable weights, infix parser supports reading of factor variable weights

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/symbreg-factors-2650/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs

    r14351 r14761  
    3939  ///
    4040  ///
    41   /// S       = Expr EOF
    42   /// Expr    = ['-' | '+'] Term { '+' Term | '-' Term }
    43   /// Term    = Fact { '*' Fact | '/' Fact }
    44   /// Fact    = '(' Expr ')' | funcId '(' Expr ')' | VarExpr | number
    45   /// VarExpr = varId [ '=' varVal]
    46   /// varId   =  ident | ' ident ' | " ident "
    47   /// varVal  =  ident | ' ident ' | " ident "
    48   /// ident   =  '_' | letter { '_' | letter | digit }
     41  /// S             = Expr EOF
     42  /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
     43  /// Term          = Fact { '*' Fact | '/' Fact }
     44  /// Fact          = '(' Expr ')'
     45  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
     46  ///                 | funcId '(' ArgList ')'
     47  ///                 | VarExpr | number
     48  /// ArgList       = Expr { ',' Expr }
     49  /// VarExpr       = varId OptFactorPart
     50  /// OptFactorPart = [ ('=' varVal | '[' number {',' number } ']' ) ]
     51  /// varId         =  ident | ' ident ' | " ident "
     52  /// varVal        =  ident | ' ident ' | " ident "
     53  /// ident         =  '_' | letter { '_' | letter | digit }
    4954  /// </summary>
    5055  public sealed class InfixExpressionParser {
    51     private enum TokenType { Operator, Identifier, Number, LeftPar, RightPar, Comma, Eq, End, NA };
     56    private enum TokenType { Operator, Identifier, Number, LeftPar, RightPar, LeftBracket, RightBracket, Comma, Eq, End, NA };
    5257    private class Token {
    5358      internal double doubleVal;
    … …  
    7782    private Variable variable = new Variable();
    7883    private BinaryFactorVariable binaryFactorVar = new BinaryFactorVariable();
     84    private FactorVariable factorVar = new FactorVariable();
    7985
    8086    private ProgramRootSymbol programRootSymbol = new ProgramRootSymbol();
    … …  
    126132
    127133
    128       foreach (var kvp in dict) {
     134      foreach(var kvp in dict) {
    129135        knownSymbols.Add(kvp.Key, kvp.Value);
    130136      }
    … …  
    145151    private IEnumerable<Token> GetAllTokens(string str) {
    146152      int pos = 0;
    147       while (true) {
    148         while (pos < str.Length && Char.IsWhiteSpace(str[pos])) pos++;
    149         if (pos >= str.Length) {
     153      while(true) {
     154        while(pos < str.Length && Char.IsWhiteSpace(str[pos])) pos++;
     155        if(pos >= str.Length) {
    150156          yield return new Token { TokenType = TokenType.End, strVal = "" };
    151157          yield break;
    152158        }
    153         if (char.IsDigit(str[pos])) {
     159        if(char.IsDigit(str[pos])) {
    154160          // read number (=> read until white space or operator or comma)
    155161          var sb = new StringBuilder();
    156162          sb.Append(str[pos]);
    157163          pos++;
    158           while (pos < str.Length && !char.IsWhiteSpace(str[pos])
     164          while(pos < str.Length && !char.IsWhiteSpace(str[pos])
    159165            && (str[pos] != '+' || str[pos - 1] == 'e' || str[pos - 1] == 'E')     // continue reading exponents
    160166            && (str[pos] != '-' || str[pos - 1] == 'e' || str[pos - 1] == 'E')
    … …  
    162168            && str[pos] != '/'
    163169            && str[pos] != ')'
     170            && str[pos] != ']'
    164171            && str[pos] != ',') {
    165172            sb.Append(str[pos]);
    … …  
    167174          }
    168175          double dblVal;
    169           if (double.TryParse(sb.ToString(), NumberStyles.Float, CultureInfo.InvariantCulture, out dblVal))
     176          if(double.TryParse(sb.ToString(), NumberStyles.Float, CultureInfo.InvariantCulture, out dblVal))
    170177            yield return new Token { TokenType = TokenType.Number, strVal = sb.ToString(), doubleVal = dblVal };
    171178          else yield return new Token { TokenType = TokenType.NA, strVal = sb.ToString() };
    172         } else if (char.IsLetter(str[pos]) || str[pos] == '_') {
     179        } else if(char.IsLetter(str[pos]) || str[pos] == '_') {
    173180          // read ident
    174181          var sb = new StringBuilder();
    175182          sb.Append(str[pos]);
    176183          pos++;
    177           while (pos < str.Length &&
     184          while(pos < str.Length &&
    178185            (char.IsLetter(str[pos]) || str[pos] == '_' || char.IsDigit(str[pos]))) {
    179186            sb.Append(str[pos]);
    … …  
    181188          }
    182189          yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
    183         } else if (str[pos] == '"') {
     190        } else if(str[pos] == '"') {
    184191          // read to next "
    185192          pos++;
    186193          var sb = new StringBuilder();
    187           while (pos < str.Length && str[pos] != '"') {
     194          while(pos < str.Length && str[pos] != '"') {
    188195            sb.Append(str[pos]);
    189196            pos++;
    190197          }
    191           if (pos < str.Length && str[pos] == '"') {
     198          if(pos < str.Length && str[pos] == '"') {
    192199            pos++; // skip "
    193200            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
    … …  
    195202            yield return new Token { TokenType = TokenType.NA };
    196203
    197         } else if (str[pos] == '\'') {
     204        } else if(str[pos] == '\'') {
    198205          // read to next '
    199206          pos++;
    200207          var sb = new StringBuilder();
    201           while (pos < str.Length && str[pos] != '\'') {
     208          while(pos < str.Length && str[pos] != '\'') {
    202209            sb.Append(str[pos]);
    203210            pos++;
    204211          }
    205           if (pos < str.Length && str[pos] == '\'') {
     212          if(pos < str.Length && str[pos] == '\'') {
    206213            pos++; // skip '
    207214            yield return new Token { TokenType = TokenType.Identifier, strVal = sb.ToString() };
    208215          } else
    209216            yield return new Token { TokenType = TokenType.NA };
    210         } else if (str[pos] == '+') {
     217        } else if(str[pos] == '+') {
    211218          pos++;
    212219          yield return new Token { TokenType = TokenType.Operator, strVal = "+" };
    213         } else if (str[pos] == '-') {
     220        } else if(str[pos] == '-') {
    214221          pos++;
    215222          yield return new Token { TokenType = TokenType.Operator, strVal = "-" };
    216         } else if (str[pos] == '/') {
     223        } else if(str[pos] == '/') {
    217224          pos++;
    218225          yield return new Token { TokenType = TokenType.Operator, strVal = "/" };
    219         } else if (str[pos] == '*') {
     226        } else if(str[pos] == '*') {
    220227          pos++;
    221228          yield return new Token { TokenType = TokenType.Operator, strVal = "*" };
    222         } else if (str[pos] == '(') {
     229        } else if(str[pos] == '(') {
    223230          pos++;
    224231          yield return new Token { TokenType = TokenType.LeftPar, strVal = "(" };
    225         } else if (str[pos] == ')') {
     232        } else if(str[pos] == ')') {
    226233          pos++;
    227234          yield return new Token { TokenType = TokenType.RightPar, strVal = ")" };
    228         } else if (str[pos] == '=') {
     235        } else if(str[pos] == '[') {
     236          pos++;
     237          yield return new Token { TokenType = TokenType.LeftBracket, strVal = "[" };
     238        } else if(str[pos] == ']') {
     239          pos++;
     240          yield return new Token { TokenType = TokenType.RightBracket, strVal = "]" };
     241        } else if(str[pos] == '=') {
    229242          pos++;
    230243          yield return new Token { TokenType = TokenType.Eq, strVal = "=" };
    231         } else if (str[pos] == ',') {
     244        } else if(str[pos] == ',') {
    232245          pos++;
    233246          yield return new Token { TokenType = TokenType.Comma, strVal = "," };
    … …  
    237250      }
    238251    }
    239 
    240     // S       = Expr EOF
    241     // Expr    = ['-' | '+'] Term { '+' Term | '-' Term }
    242     // Term    = Fact { '*' Fact | '/' Fact }
    243     // Fact    = '(' Expr ')' | funcId '(' ArgList ')' | varId | number
    244     // ArgList = Expr { ',' Expr }
     252    /// S             = Expr EOF
    245253    private ISymbolicExpressionTreeNode ParseS(Queue<Token> tokens) {
    246254      var expr = ParseExpr(tokens);
    247255
    248256      var endTok = tokens.Dequeue();
    249       if (endTok.TokenType != TokenType.End)
     257      if(endTok.TokenType != TokenType.End)
    250258        throw new ArgumentException(string.Format("Expected end of expression (got {0})", endTok.strVal));
    251259
    252260      return expr;
    253261    }
     262
     263    /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
    254264    private ISymbolicExpressionTreeNode ParseExpr(Queue<Token> tokens) {
    255265      var next = tokens.Peek();
    … …  
    257267      var negTerms = new List<ISymbolicExpressionTreeNode>();
    258268      bool negateFirstTerm = false;
    259       if (next.TokenType == TokenType.Operator && (next.strVal == "+" || next.strVal == "-")) {
     269      if(next.TokenType == TokenType.Operator && (next.strVal == "+" || next.strVal == "-")) {
    260270        tokens.Dequeue();
    261         if (next.strVal == "-")
     271        if(next.strVal == "-")
    262272          negateFirstTerm = true;
    263273      }
    264274      var t = ParseTerm(tokens);
    265       if (negateFirstTerm) negTerms.Add(t);
     275      if(negateFirstTerm) negTerms.Add(t);
    266276      else posTerms.Add(t);
    267277
    268278      next = tokens.Peek();
    269       while (next.strVal == "+" || next.strVal == "-") {
    270         switch (next.strVal) {
     279      while(next.strVal == "+" || next.strVal == "-") {
     280        switch(next.strVal) {
    271281          case "+": {
    272282              tokens.Dequeue();
    … …  
    286296
    287297      var sum = GetSymbol("+").CreateTreeNode();
    288       foreach (var posTerm in posTerms) sum.AddSubtree(posTerm);
    289       if (negTerms.Any()) {
    290         if (negTerms.Count == 1) {
     298      foreach(var posTerm in posTerms) sum.AddSubtree(posTerm);
     299      if(negTerms.Any()) {
     300        if(negTerms.Count == 1) {
    291301          var sub = GetSymbol("-").CreateTreeNode();
    292302          sub.AddSubtree(negTerms.Single());
    … …  
    294304        } else {
    295305          var sumNeg = GetSymbol("+").CreateTreeNode();
    296           foreach (var negTerm in negTerms) sumNeg.AddSubtree(negTerm);
     306          foreach(var negTerm in negTerms) sumNeg.AddSubtree(negTerm);
    297307
    298308          var constNode = (ConstantTreeNode)constant.CreateTreeNode();
    … …  
    305315        }
    306316      }
    307       if (sum.SubtreeCount == 1) return sum.Subtrees.First();
     317      if(sum.SubtreeCount == 1) return sum.Subtrees.First();
    308318      else return sum;
    309319    }
    … …  
    311321    private ISymbol GetSymbol(string tok) {
    312322      var symb = knownSymbols.GetByFirst(tok).FirstOrDefault();
    313       if (symb == null) throw new ArgumentException(string.Format("Unknown token {0} found.", tok));
     323      if(symb == null) throw new ArgumentException(string.Format("Unknown token {0} found.", tok));
    314324      return symb;
    315325    }
    316326
    317     // Term = Fact { '*' Fact | '/' Fact }
     327    /// Term          = Fact { '*' Fact | '/' Fact }
    318328    private ISymbolicExpressionTreeNode ParseTerm(Queue<Token> tokens) {
    319329      var factors = new List<ISymbolicExpressionTreeNode>();
    … …  
    322332
    323333      var next = tokens.Peek();
    324       while (next.strVal == "*" || next.strVal == "/") {
    325         switch (next.strVal) {
     334      while(next.strVal == "*" || next.strVal == "/") {
     335        switch(next.strVal) {
    326336          case "*": {
    327337              tokens.Dequeue();
    … …  
    342352        next = tokens.Peek();
    343353      }
    344       if (factors.Count == 1) return factors.First();
     354      if(factors.Count == 1) return factors.First();
    345355      else {
    346356        var prod = GetSymbol("*").CreateTreeNode();
    347         foreach (var f in factors) prod.AddSubtree(f);
     357        foreach(var f in factors) prod.AddSubtree(f);
    348358        return prod;
    349359      }
    350360    }
    351361
    352     // Fact = '(' Expr ')' | 'LAG' '(' varId ',' ['+' | '-' ] number ')' | funcId '(' Expr ')' | varId [ = valId ] | number
     362    /// Fact          = '(' Expr ')'
     363    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
     364    ///                 | funcId '(' ArgList ')'
     365    ///                 | VarExpr | number
     366    /// ArgList       = Expr { ',' Expr }
     367    /// VarExpr       = varId OptFactorPart
     368    /// OptFactorPart = [ ('=' varVal | '[' number {',' number } ']' ) ]
     369    /// varId         =  ident | ' ident ' | " ident "
     370    /// varVal        =  ident | ' ident ' | " ident "
     371    /// ident         =  '_' | letter { '_' | letter | digit }
    353372    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
    354373      var next = tokens.Peek();
    355       if (next.TokenType == TokenType.LeftPar) {
     374      if(next.TokenType == TokenType.LeftPar) {
    356375        tokens.Dequeue();
    357376        var expr = ParseExpr(tokens);
    358377        var rPar = tokens.Dequeue();
    359         if (rPar.TokenType != TokenType.RightPar)
     378        if(rPar.TokenType != TokenType.RightPar)
    360379          throw new ArgumentException("expected )");
    361380        return expr;
    362       } else if (next.TokenType == TokenType.Identifier) {
     381      } else if(next.TokenType == TokenType.Identifier) {
    363382        var idTok = tokens.Dequeue();
    364         if (tokens.Peek().TokenType == TokenType.LeftPar) {
    365           // function identifier
     383        if(tokens.Peek().TokenType == TokenType.LeftPar) {
     384          // function identifier or LAG
    366385          var funcId = idTok.strVal.ToUpperInvariant();
    367386
    368387          var funcNode = GetSymbol(funcId).CreateTreeNode();
    369388          var lPar = tokens.Dequeue();
    370           if (lPar.TokenType != TokenType.LeftPar)
     389          if(lPar.TokenType != TokenType.LeftPar)
    371390            throw new ArgumentException("expected (");
    372391
    373392          // handle 'lag' specifically
    374           if (funcNode.Symbol is LaggedVariable) {
     393          if(funcNode.Symbol is LaggedVariable) {
    375394            var varId = tokens.Dequeue();
    376             if (varId.TokenType != TokenType.Identifier) throw new ArgumentException("Identifier expected. Format for lagged variables: \"lag(x, -1)\"");
     395            if(varId.TokenType != TokenType.Identifier) throw new ArgumentException("Identifier expected. Format for lagged variables: \"lag(x, -1)\"");
    377396            var comma = tokens.Dequeue();
    378             if (comma.TokenType != TokenType.Comma) throw new ArgumentException("',' expected, Format for lagged variables: \"lag(x, -1)\"");
     397            if(comma.TokenType != TokenType.Comma) throw new ArgumentException("',' expected, Format for lagged variables: \"lag(x, -1)\"");
    379398            double sign = 1.0;
    380             if (tokens.Peek().strVal == "+" || tokens.Peek().strVal == "-") {
     399            if(tokens.Peek().strVal == "+" || tokens.Peek().strVal == "-") {
    381400              // read sign
    382401              var signTok = tokens.Dequeue();
    383               if (signTok.strVal == "-") sign = -1.0;
     402              if(signTok.strVal == "-") sign = -1.0;
    384403            }
    385404            var lagToken = tokens.Dequeue();
    386             if (lagToken.TokenType != TokenType.Number) throw new ArgumentException("Number expected, Format for lagged variables: \"lag(x, -1)\"");
    387             if (!lagToken.doubleVal.IsAlmost(Math.Round(lagToken.doubleVal)))
     405            if(lagToken.TokenType != TokenType.Number) throw new ArgumentException("Number expected, Format for lagged variables: \"lag(x, -1)\"");
     406            if(!lagToken.doubleVal.IsAlmost(Math.Round(lagToken.doubleVal)))
    388407              throw new ArgumentException("Time lags must be integer values");
    389408            var laggedVarNode = funcNode as LaggedVariableTreeNode;
    … …  
    395414            var args = ParseArgList(tokens);
    396415            // check number of arguments
    397             if (funcNode.Symbol.MinimumArity > args.Length || funcNode.Symbol.MaximumArity < args.Length) {
     416            if(funcNode.Symbol.MinimumArity > args.Length || funcNode.Symbol.MaximumArity < args.Length) {
    398417              throw new ArgumentException(string.Format("Symbol {0} requires between {1} and  {2} arguments.", funcId,
    399418                funcNode.Symbol.MinimumArity, funcNode.Symbol.MaximumArity));
    400419            }
    401             foreach (var arg in args) funcNode.AddSubtree(arg);
     420            foreach(var arg in args) funcNode.AddSubtree(arg);
    402421          }
    403422
    404423          var rPar = tokens.Dequeue();
    405           if (rPar.TokenType != TokenType.RightPar)
     424          if(rPar.TokenType != TokenType.RightPar)
    406425            throw new ArgumentException("expected )");
    407426
    … …  
    409428        } else {
    410429          // variable
    411           if (tokens.Peek().TokenType == TokenType.Eq) {
     430          if(tokens.Peek().TokenType == TokenType.Eq) {
    412431            // binary factor
    413432            tokens.Dequeue(); // skip Eq
    414433            var valTok = tokens.Dequeue();
    415             if (valTok.TokenType != TokenType.Identifier) throw new ArgumentException("expected identifier");
     434            if(valTok.TokenType != TokenType.Identifier) throw new ArgumentException("expected identifier");
    416435            var binFactorNode = (BinaryFactorVariableTreeNode)binaryFactorVar.CreateTreeNode();
    417436            binFactorNode.Weight = 1.0;
    … …  
    419438            binFactorNode.VariableValue = valTok.strVal;
    420439            return binFactorNode;
     440          } else if(tokens.Peek().TokenType == TokenType.LeftBracket) {
     441            // factor variable
     442            var factorVariableNode = (FactorVariableTreeNode) factorVar.CreateTreeNode();
     443            factorVariableNode.VariableName = idTok.strVal;
     444
     445            tokens.Dequeue(); // skip [
     446            var weights = new List<double>();
     447            // at least one weight is necessary
     448            if(tokens.Peek().TokenType != TokenType.Number) throw new ArgumentException("number expected");
     449            var weightTok = tokens.Dequeue();
     450            weights.Add(weightTok.doubleVal);
     451            while(tokens.Peek().TokenType == TokenType.Comma) {
     452              // skip comma
     453              tokens.Dequeue();
     454              weightTok = tokens.Dequeue();
     455              if(weightTok.TokenType != TokenType.Number) throw new ArgumentException("number expected");
     456              weights.Add(weightTok.doubleVal);
     457            }
     458            var rightBracketToken = tokens.Dequeue();
     459            if(rightBracketToken.TokenType != TokenType.RightBracket) throw new ArgumentException("closing bracket ] expected");
     460            factorVariableNode.Weights = weights.ToArray();
     461            return factorVariableNode;
    421462          } else {
    422463            // variable
    … …  
    427468          }
    428469        }
    429       } else if (next.TokenType == TokenType.Number) {
     470      } else if(next.TokenType == TokenType.Number) {
    430471        var numTok = tokens.Dequeue();
    431472        var constNode = (ConstantTreeNode)constant.CreateTreeNode();
    … …  
    441482      var exprList = new List<ISymbolicExpressionTreeNode>();
    442483      exprList.Add(ParseExpr(tokens));
    443       while (tokens.Peek().TokenType != TokenType.RightPar) {
     484      while(tokens.Peek().TokenType != TokenType.RightPar) {
    444485        var comma = tokens.Dequeue();
    445         if (comma.TokenType != TokenType.Comma) throw new ArgumentException("expected ',' ");
     486        if(comma.TokenType != TokenType.Comma) throw new ArgumentException("expected ',' ");
    446487        exprList.Add(ParseExpr(tokens));
    447488      }
Note: See TracChangeset for help on using the changeset viewer.