在本文中，我們將繼續研究各種數學表達式解析方法，及其在 MQL 語言中的實現。 在第一部分里，我們研究了遞歸下降解析器。 這種解析器的主要優點在於用戶友好的結構，它與特定的表達式語法直接相關。 但是，在效率和技術功能方面，還有其他類型的解析器值得關注。

解析器采用運算符優先級

我們要研究的下一個解析器類型是優先級解析器。 它們具有更緊湊的實現，因為類方法並非基於語法規則創建的（在這種情況下，每個規則都轉換為單獨的方法），而是采用更通用的形式，僅考慮運算符的優先級。

在 EBNF 語法說明中，操作的優先級已經以隱式形式出現：其規則執行從低優先級操作到高優先級操作，直至終結實體 — 常量和變量。 這是因為在沒有顯式括號分組的情況下，優先級判定應是操作執行的順序。 例如，乘法運算的優先級高於加法的優先級。 但是一元減號優先於乘法。 語法樹元素越靠近根部（整個表達式），對其進行評估越靠後。

為了實現解析器，我們需要兩個表，每張表的數值與每個操作的優先級相對應。 值越高，優先級越高。

我們有兩張表，因為一元和二元運算會在算法中邏輯上分開。 實際上，我們不僅在討論操作，且在更廣泛地討論有關在表達式中如何找到可作為前綴和後綴的符號（Wikipedia 上有更多關於操作符類型的信息）。

顧名思義，前綴是操作數之前的符號（例如，“!var” 表達式中的 “!”），而中綴是操作數之間的字符（例如，表達式 ”a + b“ 中的 ‘+’）。 還有一些後綴（例如，增量運算符中的一對 “+”，在 MQL 中也可以用 — “i++”），但是我們在表達式中沒有用到它們，因此我們先不考慮它們。

除了一元運算符 '!'，'-'，'+' 外，前綴還可以是一個開始括號 '(' — 表示分組的開頭；字母或下劃線 — 表示標識符的開頭；以及數字或句點 “.” — 表示數字常數的開頭。

我們講述 ExpressionPrecedence 類中的表，它繼承自某些基於優先級的解析器類。 所有這些解析器將與 Promise 一起操作。

  class ExpressionPrecedence: public AbstractExpressionProcessor<Promise *>
  {
    protected:
      static uchar prefixes[128];
      static uchar infixes[128];
      
      static ExpressionPrecedence epinit;
      
      static void initPrecedence()
      {
        // 分組
        prefixes['('] = 9;
  
        // 一元運算符
        prefixes['+'] = 9;
        prefixes['-'] = 9;
        prefixes['!'] = 9;
        
        // 標識符
        prefixes['_'] = 9;
        for(uchar c = 'a'; c <= 'z'; c++)
        {
          prefixes[c] = 9;
        }
        
        // 數字
        prefixes['.'] = 9;
        for(uchar c = '0'; c <= '9'; c++)
        {
          prefixes[c] = 9;
        }
        
        // 運算符
        // infixes['('] = 9; // 此處不將括號用作“函數調用”運算符
        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; // 參數列表定界符
      }
  
      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);

優先級表則按“經濟”方式創建，利用 128 個元素的稀疏數組（這已足夠了，因為不支持來自其他範圍的代碼字符）。 在與符號代碼相對應的單元格中指定優先級。 因此，可按令牌代碼直接尋址來輕松訪問優先級。

子類中將使用兩個附加的輔助方法，從而可以檢查輸入字符串中的符號：_lookAhead 僅返回下一個標記（如同向前看）；_matchNext — 如果匹配則讀令牌，否則拋出錯誤。

  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);
        }
      }
      ...
  };

我們從第一個基於優先級的解析器開始：普拉特解析器。

普拉特解析器 (ExpressionPratt)

普拉特解析器是自上而下的，就像遞歸下降解析器一樣。 這意味着它可遞歸調用某些方法來分析表達式中的獨立構造，。 然而，這些方法很少見。

構造函數和主要的公開 “evaluate” 方法看起來很眼熟。

  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;
      }

新的 parseExpression 方法是普拉特算法的核心。 首先，開始要將當前優先級默認設置為 0，這意味着可以讀取任何信號。

      virtual Promise *parseExpression(const int precedence = 0)
      {
        if(_failed) return NULL; // 出錯時截斷子表達式
      
        _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;
      }

該方法的思路很簡單：開始解析表達式時，先讀取下一個符號，必須是前綴（否則出錯），然後將控制權傳遞給 _parsePrefix 方法，該方法可以讀取任何前綴的整體構造。 在此之後，只要下一個符號的優先級高於當前優先級，就將控制權傳遞給 _parseInfix 方法，該方法可以讀取任何 infix 的整體構造。 如此，整個解析器僅包含三個方法。 從某種意義上說，普拉特解析器將表達式表述為由前綴和中綴構造的層次結構。

請注意，如果在中綴表中找不到當前的 _token，則其優先級為零，且 'while' 循環將終止（或根本不會啟動）。

_parseInfix 方法的特定功能是，當前的 Promise (left) 對象會在第一個參數中被傳遞到內部，成為子表達式的一部分，而在該方法的第二個參數里設置允許的最小操作優先級，作為當前中綴令牌的優先級。 該方法返回依據整個子表達式生成的新 Promise 對象。 該對象保存在相同的變量中（之前的 Promise 引用，則會通過新對象的引用字段以某種方式提供）。

我們來研究方法 _parsePrefix 和 _parseInfix 詳情。

_parsePrefix 方法期待來自許可前綴的當前令牌，並利用 “switch” 進行處理。 對於開頭的括號 '('，調用已熟知的方法 parseExpression 來計算嵌套表達式。 優先級參數則被省略，這意味着從最低的零優先級進行解析（因為它就像方括號中的單獨表達式一樣）。 一個 “helper” 對象用於 “!”，以便接收邏輯非得下一個片段。 它由 parseExpression 方法讀取，但這次會將當前令牌的優先級傳遞給它。 這意味着取非的片段將在第一個符號之前以低於 “!” 的優先級結束。 例如，如果表達式為 “!a*b”，則 parseExpression 將在讀取 “a” 變量後停止，因為乘法 “*” 的優先級低於取非 “!” 的優先級。 一元 '+' 和 '-' 以類似的方式處理，但在這種情況下不使用 “helper”。 對於 “+”，我們只需要讓 parseExpression 讀取子表達式。 對於 '-'，調用覆蓋方法 “minus” 接收結果（您應當記得，結果是 Promise 對象）。

_parsePrefix 方法根據它們是否屬於 “isalpha” 類別為所有其他符號排序。 假定字母是標識符的開頭，數字或句點是數字的開頭。 在所有其他情況下，該方法將返回 NULL。

      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); // 獲取索引（如果找不到）- 選擇使用 nan 保留名稱
              }
            }
            else // 暗示數字，必須為數字 
            {
              string number;
              if(_readNumber(number))
              {
                return helper._literal(number);
              }
            }
        }
        return result;
      }

標識符後跟括號“(”，解釋為函數調用。 我們為其解析時還創建了一個參數列表（根據函數 Arity），並用逗號分隔。 調用 parseExpression，根據逗號 “,” 優先級獲取每個參數。 該函數的 Promise 對象是利用 helper._call() 生成的。 如果括號後沒有標識符，則會為 helper._variable() 變量創建 Promise 對象。

當第一個標記不是字母時，_parsePrefix 方法嘗試調用 _readNumber 讀取數字，並調用 helper._literal() 為其創建 Promise。

_parseInfix 方法期望當前令牌是允許的中綴之一。 甚至，在第一個參數中，它接收已被讀入 Promise *left 對象的左側操作數。 第二個參數指定所要解析令牌的最小優先級。 一旦遇到優先級較低的內容，該子表達式即被視為結束。 _parseInfix 的目的是采用 'precedence' 調用 parseExpression，以便讀取正確的操作數，然後，我們可以為二元操作相應的中綴創建 Promise 對象。

      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 ',': // 跳過
            break;
          default:
            error("Can't process infix token " + ShortToString(_previous));
          
        }
        return result;
      }

重要的是，必須在 _previous 變量中記住方法開頭的當前中綴令牌。 這樣做是因為，若在成功的情況下，parseExpression 調用會將字符串中的位置移至其他令牌，即右移任意數量的符號。

我們只研究了 3 個方法，每個方法都擁有相當透明的結構，這便是普拉特解析器的整體。

其應用類似於 ExpressionCompiler 解析器：創建 ExpressionPratt 對象，設置變量表，啟動表達式字符串的 “evaluate” 方法，並調用 resolve() 計算所接收 Promise 內的語法樹。

當然，利用語法樹並不是惰性評估的唯一方法。 下一款我們將要研究的解析器類型會運行在沒有語法樹的情況下，且其將評估算法寫入所謂的字節碼當中。 因此，我們先看看字節碼是如何工作的。

字節碼生成

字節碼是一系列命令，以“快速”二進制表現形式描述整個計算算法。 字節碼的創建類似於實際的編譯。 但是，結果不包含處理器指令，而是包含控制某個計算器類的應用語言變量或結構。 在我們的例子中，執行單元是以下字節碼結構：

  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);
      }
  };

它的字段重複 Promise 對象的字段 — 不是全部，而是僅重複其中的一些，它們表示流計算所需的最小集合。 計算之所以繁瑣，是因為命令會從左到右依次讀取和執行，而無需在層次結構之間進行切換。

“code” 字段包含命令的本質（該值對應於 Promise 代碼），“value” 字段包含一個數字（常量），而 “index” 字段包含在變量/函數表中的索引。

編寫計算指令的方法之一是反向波蘭語表示法，也稱為後綴表示法。 這種表示法的思路是，運算符後隨其操作數。 例如，通常的後綴符號 “a + b” 變為後綴 “a b +”，而更複雜的情況 “a + b * sqrt(c)” 變為 “a b c 'sqrt' * +”。

RPN 非常適合字節碼，因為它能用堆棧輕松實現計算。 當程序在輸入流中“看到”數字或變量引用時，它會把該值壓入堆棧。 如果在輸入流中遇到運算符或函數，則程序會從堆棧中彈出所需數量的值，用這些值執行指定的操作，然後將結果壓回堆棧之中。 在該過程結束時，表達式評估結果會是堆棧上保留得唯一數字。

由於 RPN 為我們提供了構建相同表達式的語法樹的替代方案，因此這兩種表示形式可以相互轉換。 我們來嘗試基於 Promise 樹生成一個字節碼。 為了這樣做，將 exportToByteCode 方法添加到 Promise 類中。

  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; // 跳過 true 分支
          codes[truly].value = n;     // 跳過兩個分支
        }
      }
      ...
  };

該方法接收一個字節碼結構數組作為參數，它應該保存當前 Promise 對象的內容。 首先，它分析所有的從屬節點，如果存在非零值，則遞歸調用該方法的 'left'，'right' 和 'last' 指針。 在此之後，當保存了所有操作數之後，Promise 對象的屬性將寫入字節碼。

由於表達式的語法含有條件運算符，因此該方法還可以記住字節碼數組在 true 和 false 指令分支開始處，以及條件表達式結尾處的大小。 這允許將條件數組中的偏移量寫入條件運算符字節碼結構，如果條件為真或假，則在計算過程中應跳過轉該偏移量。 條件為真的指令分支在字節碼 “?” 之後立即開始。 指令執行完畢後，我們應該根據 “value” 字段的偏移量跳轉。 錯誤條件的指令分支則按 “index” 字段中的偏移量開始，緊接着是 “true” 指令字段中的偏移量。

請注意，當我們以解釋或語法樹模式評估表達式時，在二選一之前，會依據條件計算條件運算符的全部兩個分支，這意味着計算分支其一毫無意義。 在字節碼中，我們跳過不必要的分支計算。

為了將整個表達式語法樹轉換為字節碼，需要針對 “evaluate” 返回的根對象調用 exportToByteCode。 這是普拉特解析器的示例：

    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());
    }

現在，我們需要編寫函數，基於字節碼執行計算。 我們將其添加到同一 Promise 類中，因為字節碼會用到變量和函數索引，且 Promise 默認情況下含有指向這些表的鏈接。

  #define STACK_SIZE 100
  
  // 堆棧模仿
  #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; // 快速 "彈 & 壓 （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); // 順序很重要
              }
              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); // 直至結束所在
                  push(jumps, codes[i].index, jsize);      // 我們從真實的終點跳躍
                }
                else // false
                {
                  i = codes[i].index - 1; // 由於即將出現 ++，因此需要 -1
                }
              }
              break;
            default:
              Print("Unknown byte code ", CharToString(codes[i].code));
          }
        }
        return pop(stack, ssize);
      }
      ...
  };

堆棧操控通過 'stack' 數組上的宏來實現，其中預先分配了一定數量 STACK_SIZE 的元素。 在壓入和彈出操作期間，避免調用 ArrayResize 來加快執行速度。 STACK_SIZE 等於 100 看似對於大多數實際的單行表達式來說足夠了。 否則我們就會遇到堆棧溢出。

為了控制可嵌套條件運算符的執行，我們需要使用額外的“跳轉”堆棧。

從上面的 Promise 和普拉特解析器代碼中我們已經熟悉了所有這些操作。 唯一的區別是堆棧作為操作數源，和存儲中間結果的地方被廣泛運用。 字節碼在一個循環中執行，在單一方法中調用，沒有遞歸。

此功能令我們能夠從普拉特解析器或 ExpressionCompiler 導出語法樹，並依據轉換接收的字節碼來計算表達式。

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

稍後，在測試所有解析器時，我們將比較樹形和字節碼在計算時的性能速度。

但是引入字節碼的主要目的是實現另一種解析器類型，“分流場”解析器。

分流場解析器 (ExpressionShuntingYard)

分流場解析器名稱源於一種方法，該方法將輸入令牌流切分成可立即傳遞到輸出的令牌流，並應當推送到一個特殊堆棧上，從中可由有關令牌優先權組合的特殊規則提取令牌（堆棧中的令牌和輸入流中的下一個令牌）。 解析器將輸入表達式轉換回 RPN（反向波蘭表示法）。 對於我們來說這樣很方便，因為我們可以立即生成字節碼，無需語法樹。 從一般描述中可以看出，分流方法是基於運算符的優先級的，這便是為什麼這個解析器與普拉特解析器相關。 因此，它將作為 ExpressionPrecedence 子類實現。

這個解析器屬於自下而上的類別。

一般來說，算法如下（我們此處省略了我們還不曾擁有的右關聯性細節，以及與三元條件運算符相關的複雜性）：

  在循環中讀取表達式的下一個標記（直到表達式結束）
    如果令牌是一元操作，則將其保存在堆棧中
    如果是一個數字，則將其寫入字節碼
    如果是一個變量，則將其索引寫入字節碼
    如果它是一個函數標識符，則將其索引保存在堆棧上
    如果令牌是中綴運算符
      只要 “(” 不在堆棧頂部，且堆棧頂部的運算符優先級 >= 當前運算符優先級，或函數位於頂部
        將堆棧頂部推入輸出字節碼
      將運算符保存到堆棧上
    如果令牌是 “(”，則將其保存在堆棧中
    如果令牌是 ')'
      只要堆棧頂不是 '('
        將堆棧頂部推入輸出字節碼
      如果堆棧頂是 '('，刪除並廢棄
  如果堆棧上還有遺留標記，則按順序將它們移動到輸出字節碼中

顯然，這個解析器的實現只需要一個方法。

整個 ExpressionShuntingYard 類如下所示。 主體公開方法 convertToByteCode 開始解析，執行則在 exportToByteCode 當中。 由於我們的表達式支持條件運算符，所以遞歸調用 exportToByteCode 來解析它們的子表達式。

  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)) // 如果讀取了一個數字，則 _token 已更改
          {
            _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 // 變量名
            {
              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) // 運算符，包括最低有效值 '?'
          {
            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); // 子表達式為真，_token 已經改變了
                if(_token != ':')
                {
                  error("Colon expected, given: " + ShortToString(_token), __FUNCTION__);
                  break;
                }
                output[start].index = ArraySize(output);
                exportToByteCode(output); // 子表達式為假，_token 已經改變了
                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 == '(') // 除非是子表達式，否則必須為 true（那麼 “c” 可以為 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 != ':';
      }
  };

分流場解析器的用法不同於以前的類型。 我們在此跳過調用 “evaluate” 接收語法樹的步驟。 取而代之，convertToByteCode 方法立即返回所傳遞表達式的字節碼。

  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);
  }

不同類型的解析器的概覽至此完畢。 類示意圖如下所示：

解析器類示意圖

為了測試和比較不同的解析器，我們稍後將創建一個測試腳本。

鑒於最終的應用領域是交易，我們來看看如何用技術指標來擴展標準函數列表。

在表達式中嵌入指標作為函數

在計算表達式時，交易者也許需要一些特殊的信息，如餘額、持倉數量、指標讀數、等等。 通過擴展函數列表，所有這些都可在表達式當使用。 為了展示這種方法，我們將移動平均指標添加到函數集合之中。

將指標嵌入表達式的機制基於前面所研究的函子，由此，可從 AbstractFunc 類派生來實現。 正如我們已知，所有 AbstractFunc 族類實例都會自動注冊到 AbstractFunctStorage 當中，並在函數表中可用。

  class IndicatorFunc: public AbstractFunc
  {
    public:
      IndicatorFunc(const string n, const int a = 1): AbstractFunc(n, a)
      {
        // 單參數是柱線數量，
        // 兩個參數是柱線數量和緩衝區索引
      }
      static IndicatorFunc *create(const string name);
  };

Metatrader 5 中指標的具體特點是，它們還需要兩個應用階段：首先我們需要創建指標（為了獲取其描述），然後從中請求數據。 在表達式處理的上下文中，第一步應該在解析期間執行，第二步應該在求值期間執行。 由於創建指標時需要指定所有參數，因此它們必須以名稱實現，取代通過函數參數中傳遞。 例如，如果我們采用參數（period，method，price_type）創建 “iMA” 函數，那麼在解析階段我們只會收到它的名稱，而參數的定義會推遲到執行階段，這時創建指標已經太晚了（因為我們在這個階段應該從指標中讀取數據）。

作為解決方案，我們可以為移動平均指標保留一組名稱。 名稱按照以下規則組成：method_price_period。 此處，'method' 是 ENUM_MA_METHOD 枚舉里有意義的單詞之一 (SMA, EMA, SMMA, LWMA); 'price' 是 ENUM_APPLIED_PRICE 枚舉中的價格類型之一 (CLOSE, OPEN, HIGH, LOW, MEDIAN, TYPICAL, WEIGHTED); 'period' 是一個整數。 因此，運用 “SMA_OPEN_10” 函數應基於開盤價創建一個簡單移動平均線，周期為 10。

指標函數參數個數默認等於 1。 唯一的參數用於傳遞柱線數量。 如果參數個數設置為 2，則第二個參數表示緩衝區數量。 移動平均線不需要它。

MAIndicatorFunc 類依據參數所需的相應名稱創建指標實例。

  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];
      }
  };

“create” 工廠方法解析傳遞給它的名稱，從名稱中提取參數，並使用 “handle” 創建一個指標。 指標值是通過標準函子方法獲得 — execute。

由於將來可將其他指標添加到函數當中，IndicatorFunc 類為任何指標的請求提供一個單一的入口點，即 “create” 方法。 截至目前，它只包含一個轉發 MAIndicatorFunc::create() 的調用：

  static IndicatorFunc *IndicatorFunc::create(const string name)
  {
    // TODO:支持更多指標類型，根據名稱調度調用
    return MAIndicatorFunc::create(name);
  }

該方法必須從函數表調用，因此請將所需代碼添加到 FunctionTable 類中。

  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
  };

如果在內置的 25 個函數列表中找不到傳遞來的名稱，新版本的 “index” 方法將嘗試查找合適的指標。 為了連接這個附加功能，我們需要定義 INDICATOR_FUNCTORS 宏。

啟用此選項後，我們可以計算以下表達式："EMA_OPEN_10(0)/EMA_OPEN_21(0)"。

實際上，所調用指標的參數通常在設置中提供。 這意味着它們必須以某種方式動態插入到表達式行中。 為了簡化此任務，AbstractExpressionProcessor 類支持一個特殊的表達式預處理選項。 為了簡潔起見，本文省略了對它的闡述。 啟用預處理由 “evaluate” 方法的第二個可選參數管理（默認情況下等於 false，即禁用預處理）。

該選項的操作如下。 在表達式中，我們可以用大括號指定一個變量名，在解析之前它會被替換為變量值。 例如，如果表達式等於 “EMA_TYPICAL_{Period}(0)”，若變量表包含 Period 變量且值為 11，那麼將分析成 “EMA_TYPICAL_11(0)”。

為了測試指標函數，我們稍後將創建一個智能交易系統，根據評估的表達式生成交易信號，包括移動平均值。

但我們首先需要確保解析器能工作正常。

測試腳本（ExpressParser）

測試腳本 ExpresSParserS.mq5 包括一套功能測試，和 4 種解析器類型計算速度的測量，以及各種模式的演示，語法樹和字節碼的記錄，把指標作為內置函數的運用。

功能測試包括正確的和故意設置錯誤的應用程序（未聲明的變量、零除、等等）。 測試的正確性取決於實際結果與預期結果的一致性，這意味着錯誤也可以是“正確的”。 例如，此處是普拉特t解析器測試日誌的樣子。

  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

如您所見，所有 19 個測試都成功完成。 在兩次測試中，我們收到了預期的錯誤。

僅在一個多次計算的循環中進行了速度測量。 當以解釋器運行時，這包括了表達式解析階段，因為它每次計算後都要馬上執行。 對於所有其他解析器類型，解析階段是在“外部”完成。 對於所有方法，表達式解析一次性花費的時間大致相等。 這是測量 10000 次循環的結果之一（微秒）。

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

正如預期的那樣，表達式預先“編譯”的計算速度比解釋型速度快若幹倍。 我們還可以得出結論，最快的計算是基於字節碼的計算。 在這種情況下，獲取字節碼的方法沒有實質性的區別，因此我們即可以使用普拉特解析器，或或分流場方法。 您可以根據您的個人參考，以及您對算法的理解程度來選擇解析器，或者選擇最適合您特定任務的解析器，例如語法擴展，或與現有程序的集成。

使用表達式來為智能交易系統設置信號（ExprBot）

表達式為交易機器人生成交易信號。 與簡單地更改參數相比，這樣做提供了更大的靈活性。 由於函數的可擴展列表，它提供了與 MQL 幾乎相同的功能，然而在此它不需要編譯。 此外，常規操作可以很容易地隱藏在現成的函子中。 這在產品設置靈活性和複雜性之間提供了平衡性。

我們已擁有了一套移動平均指標，因此我們的交易系統將以這些指標為基礎（盡管，我們可以在表達式中添加時間函數、風險管理、即時報價和其他數據）。

為了演示這個原理，我們來創建一個簡單的智能系統 ExprBot。 變量 SignalBuy 和 SignalSell 將包含執行買賣交易的條件表達式。 以下公式可在兩個基於均線交叉的策略里運用。

  #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;

閾值設置為常數，僅是為了演示隨機變量的輸入。 快速和慢速平均周期的參數在解析表達式之前應將其插入表達式，作為指標名稱的一部分。

由於有兩個信號，我們實例化了兩個遞歸下降解析器。 一般來講，我們只使用一個，但兩個表達式中的變量表可能存在潛在差異，在這種情況下，我們需要在每次計算之前切換上下文。

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

在 OnInit 處理程序中，將參數保存在變量表中，並構建語法樹。

  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;
  }

整個策略在 OnTick 處理程序中編寫（這里省略了輔助函數；還需要包括 MT4Orders 函數庫）。

  #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();
    }
  }

這兩個表達式由 “promises” p1 和 p2 計算。 結果則是，我們有兩個標誌“買入”和“賣出”，它們在相應的方向上開倉或平倉。 MQL 代碼保證一次只能有一筆持倉，因此，如果信號相反（如果您用了更複雜的表達式，或錯誤地設置了負閾值，則可能發生這種情況），則任何現有持倉都將平倉。 可以在解析器函數中以不同的方式編輯信號條件。

如果在策略測試器中啟動 EA，結果很可能不是很好。 然而，重要的是，交易現由解析器管理。 它們未提供現成的盈利系統，但提供了尋找策略的額外工具。

利用表達式計算信號進行交易的示例

結束語

在這兩篇文章中，我們研究了四種解析器類型，比較了它們的功能，以及可以嵌入到 MQL 程序中的實現類。 所有解析器使用相同的語法，最常用的數學運算，和 25 個函數。 如有必要，可以通過擴展支持的運算符列表、添加新的內置應用程序函數（指標、價格、貿易統計數據）和語法結構（特別是用於處理它們的數組和函數）來擴展語法。

該技術能夠更靈活地將設置和不可變的 MQL 代碼隔離。 對於最終用戶來說，通過編輯輸入參數中的表達式來定制算法的能力似乎更容易，且無需學習 MQL 編程的基礎知識；而這些基礎知識在查找所需代碼片段、按照規則編輯代碼片段，和處理潛在編譯錯誤所必需的。 從 MQL 程序開發人員的角度來看，表達式解析和評估支持還提供了其他優勢，例如，它可以轉換為“在 MQL 之上的腳本”的潛在能力，這能夠避免函數庫和 MQL 編譯器的版本控制。