Berechnung mathematischer Ausdrücke (Teil 2). Parser nach Pratt und dem Shunting-yard-Algorithmus

In diesem Artikel untersuchen wir weiterhin verschiedene Parsing-Methoden für mathematische Ausdrücke und ihre Implementierung in der MQL-Sprache. Im ersten Teil besprachen wir Parser mit rekursivem Abstieg. Der Hauptvorteil solcher Parser ist ihre nutzerfreundliche Struktur, die direkt mit der spezifischen Grammatik von Ausdrücken zusammenhängt. Aber wenn es um Effizienz und technische Eigenschaften geht, gibt es noch andere Parsertypen, die Beachtung verdienen.

Parser mit Operator-Präzedenz

Der nächste Parsertyp, den wir in Betracht ziehen werden, ist der Präzedenz-Parser. Sie haben eine kompaktere Implementierung, da Klassenmethoden nicht auf grammatikalischen Regeln basieren (in diesem Fall wird jede Regel in eine separate Methode umgewandelt), sondern in einer verallgemeinerten Form erstellt werden, die nur den Vorrang der Operatoren berücksichtigt.

Der Vorrang der Operationen war bereits in impliziter Form in der EBNF-Grammatikbeschreibung vorhanden: Ihre Regeln werden von Operationen mit niedrigerer Priorität über Operationen mit höherer Priorität bis hin zu terminalen Entitäten — Konstanten und Variablen — ausgeführt. Der Grund dafür ist, dass der Vorrang die Reihenfolge bestimmt, in der die Operationen ausgeführt werden sollen, wenn es keine explizite Klammergruppierung gibt. Zum Beispiel ist der Vorrang der Multiplikationsoperation höher als der der Addition. Aber das unäre Minus hat Vorrang vor der Multiplikation. Je näher das Element des Syntaxbaums an der Wurzel (am gesamten Ausdruck) liegt, desto später wird es ausgewertet.

Um die Parser zu implementieren, benötigen wir zwei Tabellen mit numerischen Werten, die dem Vorrang jeder Operation entsprechen. Je höher der Wert, desto höher die Priorität.

Wir haben zwei Tabellen, weil unäre und binäre Operationen in Algorithmen logisch getrennt werden. Eigentlich sprechen wir nicht nur von Operationen, sondern ganz allgemein von den Symbolen, die sich in Ausdrücken als Präfixe und Infixe finden lassen (mehr Informationen über Arten von Operatoren in Wikipedia).

Wie der Name schon sagt, ist das Präfix das Symbol, das dem Operanden vorausgeht (z.B. '!' im Ausdruck "!var"), und das Infix ist das Zeichen zwischen den Operanden (z.B. '+' im Ausdruck "a + b"). Es gibt auch Postfixe (wie z.B. zwei '+' im Inkrementoperator, "i++2, den es auch in MQL gibt), aber sie werden in unseren Ausdrücken nicht verwendet und daher werden wir sie nicht berücksichtigen.

Zusätzlich zu den unären Operationen '!', '-', '+' können Präfixe eine offene Klammer sein '(' — der Beginn einer Gruppe, eines Buchstaben oder eines Unterstrichs — bezeichnet den Beginn eines Bezeichners, sowie eine Ziffer oder einen Punkt '.' — indiziert den Beginn einer numerischen Konstante.

Beschreiben wir die Tabellen in der Klasse ExpressionPrecedence, von denen bestimmte Parserklassen auf der Grundlage von Prioritäten abgeleitet werden. Alle diese Parser werden mit Promise arbeiten.

  class ExpressionPrecedence: public AbstractExpressionProcessor<Promise *>
  {
    protected:
      static uchar prefixes[128];
      static uchar infixes[128];
      
      static ExpressionPrecedence epinit;
      
      static void initPrecedence()
      {
        // grouping
        prefixes['('] = 9;
  
        // unary
        prefixes['+'] = 9;
        prefixes['-'] = 9;
        prefixes['!'] = 9;
        
        // identifiers
        prefixes['_'] = 9;
        for(uchar c = 'a'; c <= 'z'; c++)
        {
          prefixes[c] = 9;
        }
        
        // numbers
        prefixes['.'] = 9;
        for(uchar c = '0'; c <= '9'; c++)
        {
          prefixes[c] = 9;
        }
        
        // operators
        // infixes['('] = 9; // parenthesis is not used here as 'function call' operator
        infixes['*'] = 8;
        infixes['/'] = 8;
        infixes['%'] = 8;
        infixes['+'] = 7;
        infixes['-'] = 7;
        infixes['>'] = 6;
        infixes['<'] = 6;
        infixes['='] = 5;
        infixes['!'] = 5;
        infixes['&'] = 4;
        infixes['|'] = 4;
        infixes['?'] = 3;
        infixes[':'] = 2;
        infixes[','] = 1; // arg list delimiter
      }
  
      ExpressionPrecedence(const bool init)
      {
        initPrecedence();
      }
  
    public:
      ExpressionPrecedence(const string vars = NULL): AbstractExpressionProcessor(vars) {}
      ExpressionPrecedence(VariableTable &vt): AbstractExpressionProcessor(vt) {}
  };
  
  static uchar ExpressionPrecedence::prefixes[128] = {0};
  static uchar ExpressionPrecedence::infixes[128] = {0};
  static ExpressionPrecedence ExpressionPrecedence::epinit(true);

Präzedenz-Tabellen werden auf "sparsame" Weise erstellt, indem schlanke Arrays mit 128 Elementen verwendet werden (dies ist ausreichend, da Zeichen mit Codes aus anderen Bereichen nicht unterstützt werden). Die Präzedenz wird in Zellen angegeben, die den Symbolcodes entsprechen. Auf diese Weise kann die Präzedenz leicht durch direkte Adressierung über den Token-Code erreicht werden.

In Unterklassen werden zwei zusätzliche Hilfsmethoden verwendet, die es erlauben, die in der Eingabezeichenkette folgenden Symbole zu überprüfen: _lookAhead gibt einfach das nächste Token zurück (als ob es einen Schritt vorwärts schaut), _matchNext liest das Token, wenn es passt oder wirft andernfalls einen Fehler aus.

  class ExpressionPrecedence: public AbstractExpressionProcessor<Promise *>
  {
    protected:
      ...
      ushort _lookAhead()
      {
        int i = 1;
        while(_index + i < _length && isspace(_expression[_index + i])) i++;
        if(_index + i < _length)
        {
          return _expression[_index + i];
        }
        return 0;
      }
      
      void _matchNext(ushort c, string message, string context = NULL)
      {
        if(_lookAhead() == c)
        {
          _nextToken();
        }
        else if(!_failed) // prevent chained errors
        {
          error(message, context);
        }
      }
      ...
  };

Beginnen wir mit dem ersten auf Präzedenz basierenden Parser: dem Pratt-Parser.

Pratt-Parser (ExpressionPratt)

Der Pratt-Parser arbeiten von oben nach unten, genau wie der Parser mit rekursivem Abstieg. Das bedeutet, dass es auch rekursive Aufrufe einiger Methoden geben wird, die einzelne Konstrukte in den Ausdrücken analysieren. Es wird jedoch viel weniger dieser Methoden geben.

Die Konstrukteure und die wichtigste öffentliche "Bewertungsmethode" scheinen bekannt zu sein.

  class ExpressionPratt: public ExpressionPrecedence
  {
    public:
      ExpressionPratt(const string vars = NULL): ExpressionPrecedence(vars) { helper = new ExpressionHelperPromise(&this); }
      ExpressionPratt(VariableTable &vt): ExpressionPrecedence(vt) { helper = new ExpressionHelperPromise(&this); }
  
      virtual Promise *evaluate(const string expression) override
      {
        Promise::environment(&this);
        AbstractExpressionProcessor<Promise *>::evaluate(expression);
        if(_length > 0)
        {
          return parseExpression();
        }
        return NULL;
      }

Die neue Methode ParseExpression ist das Herzstück des Pratt-Algorithmus. Sie beginnt damit, dass die aktuelle Priorität standardmäßig auf 0 gesetzt wird, was bedeutet, dass jedes Signal gelesen werden kann.

      virtual Promise *parseExpression(const int precedence = 0)
      {
        if(_failed) return NULL; // cut off subexpressions in case of errors
      
        _nextToken();
        if(prefixes[(uchar)_token] == 0)
        {
          this.error("Can't parse " + ShortToString(_token), __FUNCTION__);
          return NULL;
        }
        
        Promise *left = _parsePrefix();
        
        while((precedence < infixes[_token]) && !_failed)
        {
          left = _parseInfix(left, infixes[(uchar)_token]);
        }
        
        return left;
      }

Die Idee der Methode ist einfach: Beginnen Sie das Parsen des Ausdrucks, indem Sie das nächste Symbol lesen, das ein Präfix sein muss (sonst ist es ein Fehler), und übergeben Sie die Kontrolle an die Methode _parsePrefix, die jedes Präfixkonstrukt als Ganzes lesen kann. Danach übergeben Sie die Kontrolle an die Methode _parseInfix, die jedes beliebige Präfixkonstrukt als Ganzes lesen kann, solange die Präzedenz des nächsten Symbols höher ist als die aktuelle Präzedenz. Der gesamte Parser besteht also nur aus drei Methoden. In gewisser Weise stellt der Pratt-Parser einen Ausdruck als eine Hierarchie von Präfix- und Infix-Konstrukten dar.

Beachten Sie, dass, wenn das aktuelle _token nicht in der Infix-Tabelle gefunden wird, sein Vorrang Null ist und die 'while'-Schleife stoppt (oder gar nicht erst beginnt).

Die Besonderheit der Methode _parseInfix besteht darin, dass das aktuelle Promise-Objekt (links) im ersten Parameter als Teil des Unterausdrucks übergeben wird, während die zulässige minimale Präzedenz der Operationen, die die Methode lesen darf, im zweiten Parameter als Präzedenz des aktuellen Infix-Tokens festgelegt wird. Die Methode gibt das neue Promise-Objekt für den gesamten Unterausdruck zurück. Dieses Objekt wird in der gleichen Variablen gespeichert (und die vorherige Referenz auf Promise wird irgendwie durch Referenzfelder des neuen Objekts verfügbar sein).

Betrachten wir die Methoden _parsePrefix und _parseInfix im Detail.

Die Methode _parsePrefix erwartet das aktuelle Token von erlaubten Präfixen und behandelt es mit 'switch'. Die bereits bekannte Methode parseExpression wird für die öffnende Klammer '(' aufgerufen, um den geschachtelten Ausdruck zu berechnen. Der Präzedenz-Parameter wird weggelassen, was bedeutet, dass von der niedrigsten Null-Präzedenz aus geparst wird (weil es wie ein separater Ausdruck in Klammern ist). Ein Hilfsobjekt, 'helper', wird für '!' verwendet, um eine logische Negation vom nächsten Fragment zu erhalten. Es wird von der Methode parseExpression gelesen, aber diesmal wird die Präzedenz des aktuellen Tokens in das Objekt übergeben. Das bedeutet, dass das zu negierende Fragment vor dem ersten Symbol mit einem Vorrang kleiner als '!' endet. Wenn der Ausdruck beispielsweise "!a*b" hat, dann wird der ParseAusdruck nach dem Lesen der Variablen 'a' beendet, weil die Multiplikation '*' eine niedrigere Priorität hat als die Negation '!'. Unäre '+' und '-' werden auf ähnliche Weise verarbeitet, aber der 'helper' wird in diesem Fall nicht verwendet. Für '+' müssen wir nur den Unterausdruck in parseExpression lesen. Für '-' rufen wir das überschriebene 'Minus' für das empfangene Ergebnis auf (wie Sie sich erinnern, sind die Ergebnisse Promise-Objekte).

Die Methode _parsePrefix sortiert alle anderen Symbole nach ihrer Zugehörigkeit zur Kategorie 'isalpha'. Es wird angenommen, dass ein Buchstabe der Anfang eines Bezeichners und eine Ziffer oder ein Punkt der Anfang einer Zahl ist. In allen anderen Fällen gibt die Methode NULL zurück.

      Promise *_parsePrefix()
      {
        Promise *result = NULL;
        switch(_token)
        {
          case '(':
            result = parseExpression();
            _match(')', ") expected!", __FUNCTION__);
            break;
          case '!':
            result = helper._negate(parseExpression(prefixes[_token]));
            break;
          case '+':
            result = parseExpression(prefixes[_token]);
            break;
          case '-':
            result = -parseExpression(prefixes[_token]);
            break;
          default:
            if(isalpha(_token))
            {
              string variable;
            
              while(isalnum(_token))
              {
                variable += ShortToString(_token);
                _nextToken();
              }
              
              if(_token == '(')
              {
                const string name = variable;
                const int index = _functionTable.index(name);
                if(index == -1)
                {
                  error("Function undefined: " + name, __FUNCTION__);
                  return NULL;
                }
                
                const int arity = _functionTable[index].arity();
                if(arity > 0 && _lookAhead() == ')')
                {
                  error("Missing arguments for " + name + ", " + (string)arity + " required!", __FUNCTION__);
                  return NULL;
                }
                
                Promise *params[];
                ArrayResize(params, arity);
                for(int i = 0; i < arity; i++)
                {
                  params[i] = parseExpression(infixes[',']);
                  if(i < arity - 1)
                  {
                    if(_token != ',')
                    {
                      _match(',', ", expected (param-list)!", __FUNCTION__);
                      break;
                    }
                  }
                }
              
                _match(')', ") expected after " + (string)arity + " arguments!", __FUNCTION__);
                
                result = helper._call(index, params);
              }
              else
              {
                return helper._variable(variable); // get index and if not found - optionally reserve the name with nan
              }
            }
            else // digits are implied, must be a number 
            {
              string number;
              if(_readNumber(number))
              {
                return helper._literal(number);
              }
            }
        }
        return result;
      }

Ein Bezeichner, gefolgt von einer Klammer '(', wird als Funktionsaufruf interpretiert. Wir parsen dafür zusätzlich eine Liste von Argumenten (entsprechend der Funktions-Arität), getrennt durch Kommata. Jedes Argument wird durch Aufruf von parseExpression mit dem Komma ',' Vorrang erhalten. Das Promise-Objekt für die Funktion wird mit helper._call() erzeugt. Wenn nach der Klammer kein Bezeichner steht, wird ein Promise-Objekt für die Variable helper._variable() erzeugt.

Wenn das erste Token kein Buchstabe ist, versucht die Methode _parsePrefix mit _readNumber eine Zahl zu lesen und erzeugt durch den Aufruf von helper._literal() ein Promise-Objekt für diese Zahl.

Die Methode _parseInfix erwartet, dass das aktuelle Token eines der erlaubten Infixe ist. Außerdem erhält sie im ersten Parameter den linken Operanden, der bereits in das Promise *left-Objekt eingelesen wurde. Der zweite Parameter gibt die minimale Präzedenz der zu parsenden Token an. Sobald etwas mit einer niedrigeren Priorität angetroffen wird, gilt der Unterausdruck als beendet. Der Zweck von _parseInfix ist der Aufruf von parseExpression mit 'Präzedenz', um den richtigen Operanden zu lesen, wonach wir ein Promise-Objekt für eine binäre Operation erzeugen können, die dem Infix entspricht.

      Promise *_parseInfix(Promise *left, const int precedence = 0)
      {
        Promise *result = NULL;
        const ushort _previous = _token;
        switch(_previous)
        {
          case '*':
          case '/':
          case '%':
          case '+':
          case '-':
            result = new Promise((uchar)_previous, left, parseExpression(precedence));
            break;
          case '>':
          case '<':
            if(_lookAhead() == '=')
            {
              _nextToken();
              result = new Promise((uchar)(_previous == '<' ? '{' : '}'), left, parseExpression(precedence));
            }
            else
            {
              result = new Promise((uchar)_previous, left, parseExpression(precedence));
            }
            break;
          case '=':
          case '!':
            _matchNext('=', "= expected after " + ShortToString(_previous), __FUNCTION__);
            result = helper._isEqual(left, parseExpression(precedence), _previous == '=');
            break;
          case '&':
          case '|':
            _matchNext(_previous, ShortToString(_previous) + " expected after " + ShortToString(_previous), __FUNCTION__);
            result = new Promise((uchar)_previous, left, parseExpression(precedence));
            break;
          case '?':
            {
              Promise *truly = parseExpression(infixes[':']);
              if(_token != ':')
              {
                _match(':', ": expected", __FUNCTION__);
              }
              else
              {
                Promise *falsy = parseExpression(infixes[':']);
                if(truly != NULL && falsy != NULL)
                {
                  result = helper._ternary(left, truly, falsy);
                }
              }
            }
          case ':':
          case ',': // just skip
            break;
          default:
            error("Can't process infix token " + ShortToString(_previous));
          
        }
        return result;
      }

Es ist wichtig, dass das aktuelle Infix-Token am Anfang der Methode in der Variablen _vorherigen gespeichert wird. Dies geschieht, weil der Aufruf von parseExpression im Erfolgsfall die Position in der Zeichenkette auf ein anderes Token, eine beliebige Anzahl von Symbolen, nach rechts verschiebt.

Wir haben nur 3 Methoden betrachtet, von denen jede eine ziemlich transparente Struktur hat, und das ist der gesamte Pratt-Parser als Ganzes.

Seine Anwendung ist ähnlich wie beim Parser ExpressionCompiler: Erstellen Sie das ExpressionPratt-Objekt, setzen Sie eine Tabelle mit Variablen, starten Sie die Methode 'evaluate' für den Ausdruck String und empfangen Sie Promise mit einem Syntaxbaum, der mittels resolve() berechnet werden kann.

Natürlich ist die Verwendung eines Syntaxbaums nicht die einzige Methode für eine faule Auswertung. Der nächste Parsertyp, den wir betrachten werden, läuft ohne Verwendung eines Baumes, während er den Auswertungsalgorithmus in den sogenannten Bytecode schreibt. Lassen Sie uns also zunächst sehen, wie ein Bytecode funktioniert.

Generieren des Bytecodes

Bytecode ist eine Folge von Befehlen, die den gesamten Berechnungsalgorithmus in einer "schnellen" Binärdarstellung beschreibt. Das Erzeugen eines Bytecodes ähnelt einer echten Kompilierung; das Ergebnis enthält jedoch nicht die Prozessorbefehle, sondern Variablen oder Strukturen der verwendeten Sprache, die eine bestimmte Rechenklasse steuern. In unserem Fall ist die Ausführungseinheit die folgende ByteCode-Struktur:

  struct ByteCode
  {
      uchar code;
      double value;
      int index;
  
      ByteCode(): code(0), value(0.0), index(-1) {}
      ByteCode(const uchar c): code(c), value(0.0), index(-1) {}
      ByteCode(const double d): code('n'), value(d), index(-1) {}
      ByteCode(const uchar c, const int i): code(c), value(0.0), index(i) {}
      
      string toString() const
      {
        return StringFormat("%s %f %d", CharToString(code), value, index);
      }
  };

Ihre Felder wiederholen die Felder der Promise-Objekte — nicht alle, sondern nur einige von ihnen, die einen für Streaming-Berechnungen erforderlichen Mindestsatz darstellen. Die Berechnungen sind fortlaufend, weil die Befehle nacheinander von links nach rechts gelesen und ausgeführt werden, ohne zwischen hierarchischen Strukturen zu wechseln.

Das Feld 'code' enthält das Wesen des Befehls (der Wert entspricht den Promise-Codes), das Feld 'value' enthält eine Zahl (Konstante), und das Feld 'index' enthält den Index einer Variablen/Funktion in der Tabelle der Variablen/Funktionen.

Eine der Methoden zum Schreiben von Rechenanweisungen ist die Umgekehrte polnische Notation (kurz RPN), auch bekannt als Postfixnotation. Die Idee dieser Notation besteht darin, dass Operatoren ihren Operanden folgen. Zum Beispiel wird die übliche Infix-Notation "a + b" zum Postfix "a b +", und ein komplexerer Fall von "a + b * sqrt(c)" wird zu "a b c 'sqrt' * +".

RPN eignet sich gut für Bytecode, da es eine einfache Implementierung der Berechnung unter Verwendung des Stacks ermöglicht. Wenn ein Programm eine Ziffer oder eine variable Referenz im Eingabestrom "sieht", schiebt es diesen Wert auf den Stack. Wenn ein Operator oder eine Funktion im Eingabestrom angetroffen wird, schiebt das Programm die erforderliche Anzahl von Werten vom Stapel, führt die angegebene Operation mit den Werten aus und schiebt das Ergebnis zurück auf den Stapel. Am Ende des Prozesses bleibt das Ergebnis der Ausdrucksauswertung die einzige Zahl auf dem Stapel.

Da RPN eine alternative Beschreibung der gleichen Ausdrücke liefert, für die wir Syntaxbäume erstellen, können diese beiden Darstellungen ineinander konvertiert werden. Versuchen wir, auf der Grundlage eines Promise-Baums einen Bytecode zu generieren. Dazu fügen wir der Promise-Klasse die Methode exportToByteCode hinzu.

  class Promise
  {
    ...
    public:
      void exportToByteCode(ByteCode &codes[])
      {
        if(left) left.exportToByteCode(codes);
        const int truly = ArraySize(codes);
        
        if(code == '?')
        {
          ArrayResize(codes, truly + 1);
          codes[truly].code = code;
        }
        
        if(right) right.exportToByteCode(codes);
        const int falsy = ArraySize(codes);
        if(last) last.exportToByteCode(codes);
        const int n = ArraySize(codes);
        
        if(code != '?')
        {
          ArrayResize(codes, n + 1);
          codes[n].code = code;
          codes[n].value = value;
          codes[n].index = index;
        }
        else // (code == '?')
        {
          codes[truly].index = falsy; // jump over true branch
          codes[truly].value = n;     // jump over both branches
        }
      }
      ...
  };

Die Methode erhält als Parameter ein Array von ByteCode-Strukturen, in das sie den Inhalt des aktuellen Promise-Objekts speichern soll. Zuerst analysiert sie alle untergeordneten Knoten, für die die Methode rekursiv für die Zeiger 'left', 'right' und 'last' aufgerufen wird, wenn es Zeiger ungleich Null gibt. Danach, wenn alle Operanden gespeichert worden sind, werden die Eigenschaften des Promise-Objekts in den Bytecode geschrieben.

Da die Ausdrucksgrammatik über einen Bedingungsoperator verfügt, merkt sich die Methode zusätzlich die Größe des Bytecode-Arrays an den Stellen, an denen der Wahr- und der Falsch-Befehlszweig beginnen, sowie das Ende des bedingten Ausdrucks. Dies erlaubt es, in die Bytecode-Struktur des Bedingungsoperators den Offset im Array zu schreiben, zu dem es während der Berechnungen springen soll, wenn die Bedingung wahr oder falsch ist. Der Befehlszweig für die wahre Bedingung beginnt unmittelbar nach dem Bytecode '?'. Nach der Ausführung der Befehle sollten wir um einen Offset zum Feld 'value' springen. Der Instruktionszweig für eine falsche Bedingung beginnt um den Offset im Feld 'index', unmittelbar nach dem Feld der "wahren" Instruktionen.

Bitte beachten Sie, dass, wenn wir den Ausdruck im Interpretationsmodus oder durch den Syntaxbaum auswerten, beide Zweige des Bedingungsoperators berechnet werden, bevor je nach Bedingung einer ihrer Werte ausgewählt wird, was bedeutet, dass einer der Zweige sinnlos berechnet wird. Im Bytecode überspringen wir die unnötige Zweigberechnung.

Um den gesamten Ausdrucksbaum in Bytecode zu konvertieren, rufen wir exportToByteCode für ein Wurzelobjekt auf, das von 'evaluate' zurückgegeben wird. Hier ist ein Beispiel für den Pratt-Parser:

    ExpressionPratt e(vars);
    Promise *p = e.evaluate(expr);
  
    ByteCode codes[];
    p.exportToByteCode(codes);
  
    for(int i = 0; i < ArraySize(codes); i++)
    {
      Print(i, "] ", codes[i].toString());
    }

Jetzt müssen wir eine Funktion schreiben, die auf der Grundlage des Bytecodes Berechnungen durchführt. Fügen wir sie derselben Klasse Promise hinzu, denn Bytecode verwendet Variablen- und Funktionsindizes, und Promise hat standardmäßig Links zu diesen Tabellen.

  #define STACK_SIZE 100
  
  // stack imitation
  #define push(S,V,N) S[N++] = V
  #define pop(S,N) S[--N]
  #define top(S,N) S[N-1]
  
  class Promise
  {
    ...
    public:
      static double execute(const ByteCode &codes[], VariableTable *vt = NULL, FunctionTable *ft = NULL)
      {
        if(vt) variableTable = vt;
        if(ft) functionTable = ft;
  
        double stack[]; int ssize = 0; ArrayResize(stack, STACK_SIZE);
        int jumps[]; int jsize = 0; ArrayResize(jumps, STACK_SIZE / 2);
        const int n = ArraySize(codes);
        for(int i = 0; i < n; i++)
        {
          if(jsize && top(jumps, jsize) == i)
          {
            --jsize; // fast "pop & drop"
            i = pop(jumps, jsize);
            continue;

          }
          switch(codes[i].code)
          {
            case 'n': push(stack, codes[i].value, ssize); break;
            case 'v': push(stack, variableTable[codes[i].index], ssize); break;
            case 'f':
              {
                IFunctor *ptr = functionTable[codes[i].index];
                double params[]; ArrayResize(params, ptr.arity()); int psize = 0;
                for(int j = 0; j < ptr.arity(); j++)
                {
                  push(params, pop(stack, ssize), psize);
                }
                ArrayReverse(params);
                push(stack, ptr.execute(params), ssize);
              }
              break;
            case '+': push(stack, pop(stack, ssize) + pop(stack, ssize), ssize); break;
            case '-': push(stack, -pop(stack, ssize) + pop(stack, ssize), ssize); break;
            case '*': push(stack, pop(stack, ssize) * pop(stack, ssize), ssize); break;
            case '/': push(stack, Promise::safeDivide(1, pop(stack, ssize)) * pop(stack, ssize), ssize); break;
            case '%':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, fmod(first, second), ssize);
              }
              break;
            case '!': push(stack, (double)(!pop(stack, ssize)), ssize); break;
            case '~': push(stack, (double)(-pop(stack, ssize)), ssize); break;
            case '<':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, (double)(first < second), ssize);
              }
              break;
            case '>':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, (double)(first > second), ssize);
              }
              break;
            case '{':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, (double)(first <= second), ssize);
              }
              break;
            case '}':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, (double)(first >= second), ssize);
              }
              break;
            case '&': push(stack, (double)(pop(stack, ssize) && pop(stack, ssize)), ssize); break;
            case '|':
              {
                const double second = pop(stack, ssize);
                const double first = pop(stack, ssize);
                push(stack, (double)(first || second), ssize); // order is important
              }
              break;
            case '`': push(stack, _precision < fabs(pop(stack, ssize) - pop(stack, ssize)), ssize); break;
            case '=': push(stack, _precision > fabs(pop(stack, ssize) - pop(stack, ssize)), ssize); break;
            case '?':
              {
                const double first = pop(stack, ssize);
                if(first) // true
                {
                  push(jumps, (int)codes[i].value, jsize); // to where the entire if ends
                  push(jumps, codes[i].index, jsize);      // we jump from where true ends
                }
                else // false
                {
                  i = codes[i].index - 1; // -1 is needed because of forthcoming ++
                }
              }
              break;
            default:
              Print("Unknown byte code ", CharToString(codes[i].code));
          }
        }
        return pop(stack, ssize);
      }
      ...
  };

Die Arbeit mit dem Stack wird durch Makros auf dem 'Stack'-Array implementiert, in dem eine bestimmte Anzahl von Elementen STACK_SIZE im Voraus zugewiesen wird. Dies geschieht, um die Ausführung zu beschleunigen, indem ArrayResize-Aufrufe während Push- und Pop-Operationen vermieden werden. STACK_SIZE gleich 100 scheint für die meisten echten einzeiligen Ausdrücke ausreichend zu sein. Andernfalls kommt es zu einem Stapelüberlauf.

Um die Ausführung von verschachtelbaren Bedingungsoperatoren zu kontrollieren, müssen wir einen zusätzlichen 'Sprung'-Stapel verwenden.

All diese Operationen sind bereits aus den obigen Parser-Codes Promise und Pratt bekannt. Der einzige Unterschied besteht in der weit verbreiteten Verwendung des Stapels als Quelle von Operanden und als Ort zur Speicherung eines Zwischenergebnisses. Der Bytecode wird in einer Schleife, in einem einzigen Methodenaufruf, ohne Rekursion ausgeführt.

Diese Funktionalität ermöglicht uns die Berechnung von Ausdrücken unter Verwendung von Bytecode, der durch den Export von Syntaxbäumen vom Pratt-Parser oder vom ExpressionCompiler empfangen wird.

    ExpressionPratt e(vars);
    Promise *p = e.evaluate(expr);
  
    ByteCode codes[];
    p.exportToByteCode(codes);
    double r = Promise::execute(codes);

Später, wenn wir alle Parser testen, werden wir die Leistungsgeschwindigkeit der Berechnungen anhand eines Baumes und eines Bytecodes vergleichen.

Der Hauptzweck der Einführung eines Bytecodes bestand jedoch darin, die Implementierung eines anderen Parsertyps, des Shunting-yard-Algorithmus (auf Deutsch "Rangierbahnhof"), zu ermöglichen.

Shunting-yard Parser (ExpressionShuntingYard)

Der Parsername Shunting-yard rührt von der Methode her, mit der der Strom von Eingabe-Token in solche unterteilt wird, die sofort an die Ausgabe übergeben werden können, und solche, die auf einen speziellen Stapel geschoben werden sollen, von dem die Token nach bestimmten Regeln bezüglich der Kombination von Token-Prioritäten (die des Tokens im Stapel und des nächsten Tokens im Eingabestrom) abgerufen werden. Der Parser konvertiert einen Eingabeausdruck zurück in RPN (Reverse Polish Notation). Dies ist für uns praktisch, weil wir sofort Bytecode erzeugen können, ohne einen Syntaxbaum. Wie aus der allgemeinen Beschreibung ersichtlich ist, basiert das "Rangierverfahren" auf dem Vorrang der Operatoren, weshalb dieser Parser mit dem Pratt-Parser verwandt ist. Daher wird er als eine von ExpressionPrecedence abgeleitete Klasse implementiert.

Dieser Parser gehört zur Kategorie bottom-up.

Im Allgemeinen sieht der Algorithmus wie folgt aus (wir lassen hier die Besonderheiten der Rechtsassoziativität weg, die wir nicht haben, sowie die Komplikationen, die mit dem ternären Bedingungsoperator zusammenhängen):

  Wir lesen das nächste Token aus dem Ausdruck in einer Schleife (bis zum Ende des Ausdrucks)
    wenn das Token eine einheitliche Operation ist, speichern wir ihn auf dem Stapel
    wenn es eine Zahl ist, schreiben wir sie in den Bytecode
    wenn es eine Variable ist, schreiben wir ihren Index in Bytecode
    wenn es sich um einen Funktionsbezeichner handelt, speichern wir seinen Index auf dem Stapel
    wenn das Token ein Infix-Operator ist
      solange '(' nicht oben auf dem Stapel steht und ((der Vorrang des Operators am Stapelanfang >= aktueller Operator-Vorrang) oder eine Funktion oben steht)
        schieben wir den oberen Teil des Stapels in den Ausgabe-Bytecode
      sichern wir der Operator auf dem Stapel
    wenn das Token '(' ist, speichern wir es auf dem Stapel
    wenn das Token ')' ist
      solange das obere Ende des Stapels nicht '('
        schieben wir den oberen Teil des Stapels in den Ausgabe-Bytecode
      wenn sich '(' oben auf dem Stapel befindet, entfernen und verwerfen es
  falls noch Token auf dem Stapel vorhanden sind, schieben wir diese nacheinander in den Ausgabe-Bytecode

Offensichtlich ist für die Implementierung dieses Parsers nur eine Methode erforderlich.

Im Folgenden wird die gesamte Klasse ExpressionShuntingYard vorgestellt. Die 'public' Hauptmethode convertToByteCode startet den Parser, der in exportToByteCode ausgeführt wird. Da unsere Ausdrücke Bedingungsoperatoren unterstützen, wird ein rekursiver Aufruf von exportToByteCode verwendet, um ihre Unterausdrücke zu parsen.

  class ExpressionShuntingYard: public ExpressionPrecedence
  {
    public:
      ExpressionShuntingYard(const string vars = NULL): ExpressionPrecedence(vars) { }
      ExpressionShuntingYard(VariableTable &vt): ExpressionPrecedence(vt) { }
  
      bool convertToByteCode(const string expression, ByteCode &codes[])
      {
        Promise::environment(&this);
        AbstractExpressionProcessor<Promise *>::evaluate(expression);
        if(_length > 0)
        {
          exportToByteCode(codes);
        }
        return !_failed;
      }
  
    protected:
      template<typename T>
      static void _push(T &stack[], T &value)
      {
        const int n = ArraySize(stack);
        ArrayResize(stack, n + 1, STACK_SIZE);
        stack[n] = value;
      }
  
      void exportToByteCode(ByteCode &output[])
      {
        ByteCode stack[];
        int ssize = 0;
        string number;
        uchar c;
        
        ArrayResize(stack, STACK_SIZE);
        
        const int previous = ArraySize(output);
        
        while(_nextToken() && !_failed)
        {
          if(_token == '+' || _token == '-' || _token == '!')
          {
            if(_token == '-')
            {
              _push(output, ByteCode(-1.0));
              push(stack, ByteCode('*'), ssize);
            }
            else if(_token == '!')
            {
              push(stack, ByteCode('!'), ssize);
            }
            continue;
          }
          
          number = "";
          if(_readNumber(number)) // if a number was read, _token has changed
          {
            _push(output, ByteCode(StringToDouble(number)));
          }
          
          if(isalpha(_token))
          {
            string variable;
            while(isalnum(_token))
            {
              variable += ShortToString(_token);
              _nextToken();
            }
            if(_token == '(')
            {
              push(stack, ByteCode('f', _functionTable.index(variable)), ssize);
            }
            else // variable name
            {
              int index = -1;
              if(CheckPointer(_variableTable) != POINTER_INVALID)
              {
                index = _variableTable.index(variable);
                if(index == -1)
                {
                  if(_variableTable.adhocAllocation())
                  {
                    index = _variableTable.add(variable, nan);
                    _push(output, ByteCode('v', index));
                    error("Unknown variable is NaN: " + variable, __FUNCTION__, true);
                  }
                  else
                  {
                    error("Unknown variable : " + variable, __FUNCTION__);
                  }
                }
                else
                {
                  _push(output, ByteCode('v', index));
                }
              }
            }
          }
          
          if(infixes[_token] > 0) // operator, including least significant '?'
          {
            while(ssize > 0 && isTop2Pop(top(stack, ssize).code))
            {
              _push(output, pop(stack, ssize));
            }
            
            if(_token == '?' || _token == ':')
            {
              if(_token == '?')
              {
                const int start = ArraySize(output);
                _push(output, ByteCode((uchar)_token));
                exportToByteCode(output); // subexpression truly, _token has changed
                if(_token != ':')
                {
                  error("Colon expected, given: " + ShortToString(_token), __FUNCTION__);
                  break;
                }
                output[start].index = ArraySize(output);
                exportToByteCode(output); // subexpression falsy, _token has changed
                output[start].value = ArraySize(output);
                if(_token == ':')
                {
                  break;
                }
              }
              else
              {
                break;
              }
            }
            else
            {
              if(_token == '>' || _token == '<')
              {
                if(_lookAhead() == '=')
                {
                  push(stack, ByteCode((uchar)(_token == '<' ? '{' : '}')), ssize);
                  _nextToken();
                }
                else
                {
                  push(stack, ByteCode((uchar)_token), ssize);
                }
              }
              else if(_token == '=' || _token == '!')
              {
                if(_lookAhead() == '=')
                {
                  push(stack, ByteCode((uchar)(_token == '!' ? '`' : '=')), ssize);
                  _nextToken();
                }
              }
              else if(_token == '&' || _token == '|')
              {
                _matchNext(_token, ShortToString(_token) + " expected after " + ShortToString(_token), __FUNCTION__);
                push(stack, ByteCode((uchar)_token), ssize);
              }
              else if(_token != ',')
              {
                push(stack, ByteCode((uchar)_token), ssize);
              }
            }
          }
          
          if(_token == '(')
          {
            push(stack, ByteCode('('), ssize);
          }
          else if(_token == ')')
          {
            while(ssize > 0 && (c = top(stack, ssize).code) != '(')
            {
              _push(output, pop(stack, ssize));
            }
            if(c == '(') // must be true unless it's a subexpression (then 'c' can be 0)
            {
              ByteCode disable_warning = pop(stack, ssize);
            }
            else
            {
              if(previous == 0)
              {
                error("Closing parenthesis is missing", __FUNCTION__);
              }
              return;
            }
          }
        }
        
        while(ssize > 0)
        {
          _push(output, pop(stack, ssize));
        }
      }
      
      bool isTop2Pop(const uchar c)
      {
        return (c == 'f' || infixes[c] >= infixes[_token]) && c != '(' && c != ':';
      }
  };

Die Verwendung eines Shunting-yard-Parsers unterscheidet sich von vorherigen Typen. Wir überspringen hier den Schritt, in dem ein Baum durch Aufruf von 'evaluate' empfangen wird. Stattdessen gibt die Methode convertToByteCode sofort den Bytecode für den übergebenen Ausdruck zurück.

  ExpressionShuntingYard sh;
  sh.variableTable().adhocAllocation(true);
  
  ByteCode codes[];
  bool success = sh.convertToByteCode("x + y", codes);
  if(success)
  {
    sh.variableTable().assign("x=10;y=20");
    double r = Promise::execute(codes);
  }

Damit ist der Überblick über die verschiedenen Arten von Parsern abgeschlossen. Das Diagramm der Klassen sieht wie folgt aus:

Diagramm der Parser-KlasseDas Diagramm der Klassen sieht wie folgt aus:

Um verschiedene Parser zu testen und zu vergleichen, erstellen wir später ein Testskript.

Da das ultimative Anwendungsfeld der Handel ist, sehen wir uns an, wie die Liste der Standardfunktionen mit technischen Indikatoren erweitert werden kann.

Einbetten von Indikatoren in Ausdrücke als Funktionen

Bei der Berechnung von Ausdrücken benötigt der Händler möglicherweise einige spezifische Informationen, wie z. B. den Kontostand, die Anzahl der Positionen, Indikatorwerte usw. All dies kann in Ausdrücken verfügbar gemacht werden, indem die Liste der Funktionen erweitert wird. Um diesen Ansatz zu demonstrieren, fügen wir dem Funktionsumfang den Indikator Gleitender Durchschnitt hinzu.

Der Mechanismus zum Einbetten eines Indikators in Ausdrücke basiert auf den zuvor betrachteten Funktoren und wird daher als von AbstractFunc abgeleitete Klasse implementiert. Wie wir bereits wissen, werden alle Klasseninstanzen der AbstractFunc-Familie automatisch in AbstractFuncStorage registriert und in der Funktionstabelle verfügbar.

  class IndicatorFunc: public AbstractFunc
  {
    public:
      IndicatorFunc(const string n, const int a = 1): AbstractFunc(n, a)
      {
        // the single argument is the bar number,
        // two arguments are bar number and buffer index
      }
      static IndicatorFunc *create(const string name);
  };

Die Besonderheit der Indikatoren in MetaTrader 5 besteht darin, dass sie ebenfalls zwei Anwendungsphasen erfordern: Zuerst müssen wir den Indikator erstellen (um seine Beschreibung zu erhalten) und dann Daten von ihm anfordern. Im Zusammenhang mit der Verarbeitung von Ausdrücken sollte der erste Schritt während des Parsens und der zweite Schritt während der Auswertung durchgeführt werden. Da die Erstellung des Indikators die Angabe aller Parameter erfordert, müssen diese im Namen implementiert werden, anstatt in Funktionsparametern übergeben zu werden. Wenn wir zum Beispiel die Funktion "iMA" mit Parametern (Periode, Methode, Preis_Typ) erstellen würden, dann würden wir im Parsing-Stadium nur ihren Namen erhalten, während die Definition der Parameter bis zum Ausführungsstadium verschoben würde, wenn es für die Erstellung eines Indikators zu spät ist (da wir in diesem Stadium Daten aus dem Indikator lesen sollten).

Als Lösung können wir eine Reihe von Namen für den Indikator Gleitender Durchschnitt reservieren. Die Namen werden nach der folgenden Regel zusammengesetzt: method_price_period. Dabei ist 'method' eines der aussagekräftigen Wörter der Aufzählung ENUM_MA_METHOD (SMA, EMA, SMMA, LWMA), 'price' ist einer der Preistypen aus den Aufzählungen ENUM_APPLIED_PRICE (CLOSE, OPEN, HIGH, LOW, MEDIAN, TYPICAL, WEIGHTED), und 'period' ist eine ganze Zahl. Daher sollte die Verwendung der Funktion "SMA_OPEN_10" einen einfachen gleitenden Durchschnitt auf der Grundlage des offenen Preises mit einer Periode von 10 erzeugen.

Die Arität der Indikatorfunktion ist standardmäßig gleich 1. Es wird ein einziger Parameter verwendet, um die Balkenzahl zu übergeben. Wenn die Arität auf 2 gesetzt ist, dann kann der zweite Parameter zur Angabe der Puffernummer verwendet werden. Er wird für den gleitenden Durchschnitt nicht benötigt.

Die Klasse MAIndicatorFunc wird für die Erstellung von Indikatorinstanzen mit Parametern verwendet, die den angeforderten Namen entsprechen.

  class MAIndicatorFunc: public IndicatorFunc
  {
    protected:
      const int handle;
      
    public:
      MAIndicatorFunc(const string n, const int h): IndicatorFunc(n), handle(h) {}
      
      ~MAIndicatorFunc()
      {
        IndicatorRelease(handle);
      }
      
      static MAIndicatorFunc *create(const string name) // SMA_OPEN_10(0)
      {
        string parts[];
        if(StringSplit(name, '_', parts) != 3) return NULL;
        
        ENUM_MA_METHOD m = -1;
        ENUM_APPLIED_PRICE t = -1;
        
        static string methods[] = {"SMA", "EMA", "SMMA", "LWMA"};
        for(int i = 0; i < ArraySize(methods); i++)
        {
          if(parts[0] == methods[i])
          {
            m = (ENUM_MA_METHOD)i;
            break;
          }
        }
  
        static string types[] = {"NULL", "CLOSE", "OPEN", "HIGH", "LOW", "MEDIAN", "TYPICAL", "WEIGHTED"};
        for(int i = 1; i < ArraySize(types); i++)
        {
          if(parts[1] == types[i])
          {
            t = (ENUM_APPLIED_PRICE)i;
            break;
          }
        }
        
        if(m == -1 || t == -1) return NULL;
        
        int h = iMA(_Symbol, _Period, (int)StringToInteger(parts[2]), 0, m, t);
        if(h == INVALID_HANDLE) return NULL;
        
        return new MAIndicatorFunc(name, h);
      }
      
      double execute(const double &params[]) override
      {
        const int bar = (int)params[0];
        double result[1] = {0};
        if(CopyBuffer(handle, 0, bar, 1, result) != 1)
        {
          Print("CopyBuffer error: ", GetLastError());
        }
        return result[0];
      }
  };

Die Factory-Methode 'create' parst den ihr übergebenen Namen, extrahiert Parameter aus dem Namen und erzeugt einen Indikator mit 'handle'. Der Wert des Indikators wird in der Standardmethode des functors erhalten — execute.

Da der Funktion in Zukunft weitere Indikatoren hinzugefügt werden können, bietet die Klasse IndicatorFunc einen einzigen Einstiegspunkt für Anforderungen beliebiger Indikatoren, nämlich die Methode 'create'. Bislang enthält sie nur eine Umleitung zum Aufruf MAIndicatorFunc::create().

  static IndicatorFunc *IndicatorFunc::create(const string name)
  {
    // TODO: support more indicator types, dispatch calls based on the name
    return MAIndicatorFunc::create(name);
  }

Diese Methode muss aus der Funktionstabelle aufgerufen werden, fügen Sie also den erforderlichen Code zur Klasse FunctionTable hinzu.

  class FunctionTable: public Table<IFunctor *>
  {
    public:
      ...
      #ifdef INDICATOR_FUNCTORS
      virtual int index(const string name) override
      {
        int i = _table.getIndex(name);
        if(i == -1)
        {
          i = _table.getSize();
          IFunctor *f = IndicatorFunc::create(name);
          if(f)
          {
            Table<IFunctor *>::add(name, f);
            return i;
          }
          return -1;
        }
        return i;
      }
      #endif
  };

Die neue Version der Methode 'index' versucht, einen geeigneten Indikator zu finden, wenn der übergebene Name nicht in der Liste der eingebauten 25 Funktionen gefunden wird. Um diese zusätzliche Funktionalität zu verbinden, müssen wir das Makro INDICATOR_FUNCTORS definieren.

Wenn diese Option aktiviert ist, können wir zum Beispiel den folgenden Ausdruck berechnen: "EMA_OPEN_10(0)/EMA_OPEN_21(0)".

In der Praxis werden die Parameter der aufgerufenen Indikatoren oft in Einstellungen angegeben. Das bedeutet, dass sie irgendwie dynamisch in die Ausdruckszeile eingefügt werden müssen. Um diese Aufgabe zu vereinfachen, unterstützt die Klasse AbstractExpressionProcessor eine spezielle Option zur Vorverarbeitung von Ausdrücken. Ihre Beschreibung wird im Artikel der Kürze halber weggelassen. Die Aktivierung der Vorverarbeitung wird durch den optionalen zweiten Parameter der Methode 'evaluate' verwaltet (der standardmäßig gleich false ist, d.h. die Vorverarbeitung ist deaktiviert).

Die Option funktioniert wie folgt. In einem Ausdruck können wir in geschweiften Klammern einen Variablennamen angeben, der durch den Variablenwert von vor dem Parsen ersetzt wird. Wenn der Ausdruck zum Beispiel gleich "EMA_TYPICAL_{Periode}(0)" ist und die Variablentabelle die Variable Periode mit dem Wert 11 enthält, dann wird "EMA_TYPICAL_11(0)" analysiert.

Um die Indikatorfunktionen zu testen, werden wir später einen Expert Advisor erstellen, dessen Handelssignale auf der Grundlage der ausgewerteten Ausdrücke, einschließlich des gleitenden Durchschnitts, generiert werden.

Doch zuerst müssen wir sicherstellen, dass die Parser korrekt funktionieren.

Testskript (ExpresSParserS)

Das Testskript ExpresSParserS.mq5 enthält eine Reihe von Funktionstests und Messungen der Berechnungsgeschwindigkeit für 4 Parsertypen, sowie eine Demonstration verschiedener Modi, Protokollierung von Syntaxbaum und Bytecode, Verwendung von Indikatoren als eingebaute Funktionen.

Die Funktionstests umfassen sowohl richtige als auch absichtlich falsche Anwendungen (nicht deklarierte Variablen, Null-Division usw.). Die Korrektheit eines Tests wird durch die Übereinstimmung des tatsächlichen und des erwarteten Ergebnisses bestimmt, was bedeutet, dass auch Fehler "richtig" sein können. So sieht beispielsweise das Testprotokoll des Pratt-Parsers aus.

  Running 19 tests on ExpressionPratt* …
  1 passed, ok: a > b ? b > c ? 1 : 2 : 3 = 3.0; expected = 3.0
  2 passed, ok: 2 > 3 ? 2 : 3 > 4 ? 3 : 4 = 4.0; expected = 4.0
  3 passed, ok: 4 > 3 ? 2 > 4 ? 2 : 4 : 3 = 4.0; expected = 4.0
  4 passed, ok: (a + b) * sqrt(c) = 8.944271909999159; expected = 8.944271909999159
  5 passed, ok: (b == c) > (a != 1.5) = 0.0; expected = 0.0
  6 passed, ok: (b == c) >= (a != 1.5) = 1.0; expected = 1.0
  7 passed, ok: (a > b) || sqrt(c) = 1.0; expected = 1.0
  8 passed, ok: (!1 != !(b - c/2)) = 1.0; expected = 1.0
  9 passed, ok: -1 * c == -sqrt(-c * -c) = 1.0; expected = 1.0
  10 passed, ok: pow(2, 5) % 5 = 2.0; expected = 2.0
  11 passed, ok: min(max(a,b),c) = 2.5; expected = 2.5
  12 passed, ok: atan(sin(0.5)/cos(0.5)) = 0.5; expected = 0.5
  13 passed, ok: .2 * .3 + .1 = 0.16; expected = 0.16
  14 passed, ok: (a == b) + (b == c) = 0.0; expected = 0.0
  15 passed, ok: -(a + b) * !!sqrt(c) = -4.0; expected = -4.0
  16 passed, ok: sin ( max ( 2 * 1.5, 3 ) / 3 * 3.14159265359 ) = -2.068231111547469e-13; expected = 0.0
  lookUpVariable error: Variable is undefined: _1c @ 7: 1 / _1c^
  17 passed, er: 1 / _1c = nan; expected = nan
  safeDivide error: Error : Division by 0! @ 15: 1 / (2 * b - c)^
  18 passed, er: 1 / (2 * b - c) = inf; expected = inf
  19 passed, ok: sqrt(b-c) = -nan(ind); expected = -nan(ind)
  19 tests passed of 19
  17 for correct expressions, 2 for invalid expressions

Wie Sie sehen können, wurden alle 19 Tests erfolgreich abgeschlossen. Bei zwei Tests erhielten wir die erwarteten Fehler.

Die Geschwindigkeit wird nur bei mehreren Berechnungen in einem Zyklus gemessen. Bei der Arbeit mit dem Interpreter schließt dies die Phase des Parsens eines Ausdrucks ein, da sie für jede Auswertung durchgeführt wird. Bei allen anderen Parsertypen wird die Parsing-Phase "außerhalb" durchgeführt. Das Parsen einmaliger Ausdrücke nimmt für alle Methoden ungefähr die gleiche Zeit in Anspruch. Hier ist eines der Ergebnisse der Messung von 10.000 Zyklen (Mikrosekunden).

  >>> Performance tests (timing per method)
  Evaluation: 104572
  Compilation: 25011
  Pratt bytecode: 23738
  Pratt: 24967
  ShuntingYard: 23147

Wie erwartet, werden zuvor "kompilierte" Ausdrücke um ein Vielfaches schneller ausgewertet als interpretierte. Wir können auch feststellen, dass die schnellsten Berechnungen diejenigen sind, die auf einem Bytecode basieren. In diesem Fall macht die Methode zur Gewinnung des Bytecodes keinen wesentlichen Unterschied, so dass wir entweder den Pratt-Parser oder die Shunting-yard-Methode verwenden können. Sie können einen Parser je nach Ihrer persönlichen Referenz und je nachdem, wie gut Sie den Algorithmus verstehen, auswählen oder denjenigen wählen, der sich am besten für Ihre spezifischen Aufgaben, wie z.B. Syntaxerweiterung oder Integration mit bestehenden Programmen, eignet.

Die Verwendung von Ausdrücken zur Einrichtung von Signalen für einen Expert Advisor (ExprBot)

Ausdrücke können in Handelsrobotern verwendet werden, um Handelssignale zu erzeugen. Dies bietet eine größere Flexibilität im Vergleich zur einfachen Änderung von Parametern. Aufgrund der erweiterbaren Liste von Funktionen bietet dies praktisch die gleichen Möglichkeiten wie MQL, jedoch ist hier keine Kompilierung erforderlich. Darüber hinaus können Routineoperationen leicht in vorgefertigten Funktoren versteckt werden. Auf diese Weise wird ein Gleichgewicht zwischen Flexibilität und Komplexität der Produkteinrichtung geschaffen.

Wir verfügen über eine Reihe von Indikatoren für den gleitenden Durchschnitt, sodass unser Handelssystem auf diesen Indikatoren basieren wird (allerdings können wir den Ausdrücken Zeitfunktionen, Risikomanagement, Tick-Preise und andere Daten hinzufügen).

Um das Prinzip zu demonstrieren, erstellen wir einen einfachen Expert Advisor, ExprBot. Die Variablen SignalBuy und SignalSell werden Ausdrücke mit den Bedingungen für die Ausführung von Kauf- und Verkaufstransaktionen enthalten. Die folgenden Formeln können für eine Strategie verwendet werden, die auf der Schnittmenge von zwei MAs basiert.

  #define INDICATOR_FUNCTORS
  #include <ExpresSParserS/ExpressionCompiler.mqh>
  
  input string SignalBuy = "EMA_OPEN_{Fast}(0)/EMA_OPEN_{Slow}(0) > 1 + Threshold";
  input string SignalSell = "EMA_OPEN_{Fast}(0)/EMA_OPEN_{Slow}(0) < 1 - Threshold";
  input string Variables = "Threshold=0.01";
  input int Fast = 10;
  input int Slow = 21;

Der Schwellenwert wird nur als Konstante festgelegt, um die Eingabe von Zufallsvariablen zu demonstrieren. Parameter mit der schnellen und langsamen Mittelungsperiode werden als Teil des Indikatornamens in Ausdrücke eingefügt, bevor diese geparst werden.

Da es zwei Signale gibt, instantiieren wir zwei Parser mit rekursivem Abstieg. Eigentlich könnten wir einen verwenden, aber die Variablentabellen in zwei Ausdrücken können potenziell unterschiedlich sein. In diesem Fall müssten wir diesen Kontext vor jeder Berechnung wechseln.

  ExpressionCompiler ecb(Variables), ecs(Variables);
  Promise *p1, *p2;

Wir sichern in OnInit die Parameter in den Variablentabellen und bauen Syntaxbäume auf.

  int OnInit()
  {
    ecb.variableTable().set("Fast", Fast);
    ecb.variableTable().set("Slow", Slow);
    p1 = ecb.evaluate(SignalBuy, true);
    if(!ecb.success())
    {
      Print("Syntax error in Buy signal:");
      p1.print();
      return INIT_FAILED;
    }
    ecs.variableTable().set("Fast", Fast);
    ecs.variableTable().set("Slow", Slow);
    p2 = ecs.evaluate(SignalSell, true);
    if(!ecs.success())
    {
      Print("Syntax error in Sell signal:");
      p2.print();
      return INIT_FAILED;
    }
    
    return INIT_SUCCEEDED;
  }

Die gesamte Strategie ist in OnTick geschrieben (Hilfsfunktionen werden hier weggelassen; es ist auch notwendig, die Bibliothek MT4Orders einzubinden).

  #define _Ask SymbolInfoDouble(_Symbol, SYMBOL_ASK)
  #define _Bid SymbolInfoDouble(_Symbol, SYMBOL_BID)
  
  void OnTick()
  {
    if(!isNewBar()) return;
    
    bool buy = p1.resolve();
    bool sell = p2.resolve();
    
    if(buy && sell)
    {
      buy = false;
      sell = false;
    }
    
    if(buy)
    {
      OrdersCloseAll(_Symbol, OP_SELL);
      if(OrdersTotalByType(_Symbol, OP_BUY) == 0)
      {
        OrderSend(_Symbol, OP_BUY, Lot, _Ask, 100, 0, 0);
      }
    }
    else if(sell)
    {
      OrdersCloseAll(_Symbol, OP_BUY);
      if(OrdersTotalByType(_Symbol, OP_SELL) == 0)
      {
        OrderSend(_Symbol, OP_SELL, Lot, _Bid, 100, 0, 0);
      }
    }
    else
    {
      OrdersCloseAll();
    }
  }

Diese beiden Ausdrücke werden durch die "promises" p1 und p2 berechnet. Infolgedessen haben wir zwei Flags "Kauf" und "Verkauf", die die Eröffnung oder Schließung einer Position in den entsprechenden Richtungen einleiten. Der MQL-Code garantiert, dass es immer nur eine offene Position zur gleichen Zeit geben kann, und wenn also die Signale entgegengesetzt sind (dies kann passieren, wenn Sie komplexere Ausdrücke verwenden oder wenn versehentlich ein negativer Schwellenwert gesetzt wird), wird jede bestehende Position geschlossen. Signalbedingungen können innerhalb der Parserfunktionen auf verschiedene Weise bearbeitet werden.

Wenn Sie den EA im Strategy Tester starten, wird das Ergebnis höchstwahrscheinlich nicht sehr gut sein. Wichtig ist jedoch, dass der EA-Handel und der Handel von den Parsern verwaltet wird. Sie geben keine fertigen, profitablen Systeme, sondern bieten ein zusätzliches Werkzeug, um Strategien zu finden.

Ein Beispiel für den Handel mit Signalen, die durch Ausdrücke ermittelt werden

Schlussfolgerung

In diesen beiden Artikeln untersuchten wir vier Parsertypen, verglichen ihre Fähigkeiten und implementierten Klassen, die in MQL-Programme eingebettet werden können. Alle Parser verwendeten die gleiche Grammatik mit den am häufigsten verwendeten mathematischen Operationen und 25 Funktionen. Bei Bedarf kann die Grammatik erweitert werden, indem die Liste der unterstützten Operatoren erweitert wird, indem neue eingebaute Anwendungsfunktionen (Indikatoren, Preise, Handelsstatistik) und Syntaxstrukturen (insbesondere Arrays und Funktionen für deren Verarbeitung) hinzugefügt werden.

Die Technologie ermöglicht eine flexiblere Trennung von Einstellungen und unveränderlichem MQL-Code. Die Möglichkeit, Algorithmen durch die Bearbeitung von Ausdrücken in Eingabeparametern anzupassen, scheint für den Endbenutzer einfacher zu sein, da es nicht notwendig ist, die Grundlagen der MQL-Programmierung zu erlernen, die erforderlich sind, um das gewünschte Codefragment zu finden, es nach Regeln zu bearbeiten und mit möglichen Kompilierungsfehlern umzugehen. Aus der Sicht der Entwickler von MQL-Programmen bietet die Unterstützung von Parsing und Ausdrucksauswertung weitere Vorteile, wie z.B. die potentielle Möglichkeit, in ein "Skript über MQL" umgewandelt zu werden, wodurch die Verwendung von Bibliotheken und die Versionierung des MQL-Compilers vermieden werden könnte.