https://github.com/zjhellofss/KuiperInfer 感謝大家點贊和PR, 這是對我最大的鼓勵, 謝謝.

表達式就是一個計算過程,類似于如下：

output_mid = input1 + input2
output = output_mid * input3 

用圖形來表達就是這樣的.

image-20230113160348886

但是在PNNX的Expession Layer中給出的是一種抽象表達式,會對計算過程進行折疊,消除中間變量. 并且將具體的輸入張量替換為抽象輸入@0,@1等.對于上面的計算過程,PNNX生成的抽象表達式是這樣的.

add(@0,mul(@1,@2)) 抽象的表達式重新變回到一個方便后端執行的計算過程（抽象語法樹來表達，在推理的時候我們會把它轉成逆波蘭式）。

其中add和mul表示我們上一節中說到的RuntimeOperator, @0和@1表示我們上一節課中說道的RuntimeOperand. 這個抽象表達式看起來比較簡單,但是實際上情況會非常復雜,我們給出一個復雜的例子：

add(add(mul(@0,@1),mul(@2,add(add(add(@0,@2),@3),@4))),@5)

這就要求我們需要一個魯棒的表達式解析和語法樹構建功能.

詞法解析的目的就是將add(@0,mul(@1,@2))拆分為多個token,token依次為add ( @0 , mul等.代碼如下：

enum class TokenType {
  TokenUnknown = -1,
  TokenInputNumber = 0,
  TokenComma = 1,
  TokenAdd = 2,
  TokenMul = 3,
  TokenLeftBracket = 4,
  TokenRightBracket = 5,
};

struct Token {
  TokenType token_type = TokenType::TokenUnknown;
  int32_t start_pos = 0; //詞語開始的位置
  int32_t end_pos = 0; // 詞語結束的位置
  Token(TokenType token_type, int32_t start_pos, int32_t end_pos): token_type(token_type), start_pos(start_pos), end_pos(end_pos) {

  }
};

我們在TokenType中規定了Token的類型,類型有輸入、加法、乘法以及左右括號等.Token類中記錄了類型以及Token在字符串的起始和結束位置.

如下的代碼是具體的解析過程,我們將輸入存放在statement_中,首先是判斷statement_是否為空, 隨后刪除表達式中的所有空格和制表符.

  if (!need_retoken && !this->tokens_.empty()) {
    return;
  }

  CHECK(!statement_.empty()) << "The input statement is empty!";
  statement_.erase(std::remove_if(statement_.begin(), statement_.end(), [](char c) {
    return std::isspace(c);
  }), statement_.end());
  CHECK(!statement_.empty()) << "The input statement is empty!";

下面的代碼中,我們先遍歷表達式輸入

 for (int32_t i = 0; i < statement_.size();) {
    char c = statement_.at(i);
    if (c == 'a') {
      CHECK(i + 1 < statement_.size() && statement_.at(i + 1) == 'd')
              << "Parse add token failed, illegal character: " << c;
      CHECK(i + 2 < statement_.size() && statement_.at(i + 2) == 'd')
              << "Parse add token failed, illegal character: " << c;
      Token token(TokenType::TokenAdd, i, i + 3);
      tokens_.push_back(token);
      std::string token_operation = std::string(statement_.begin() + i, statement_.begin() + i + 3);
      token_strs_.push_back(token_operation);
      i = i + 3;
    } 
 }

char c是當前的字符,當c等于字符a的時候,我們的詞法規定在token中以a作為開始的情況只有add. 所以我們判斷接下來的兩個字符必須是d和 d.如果不是的話就報錯,如果是i的話就初始化一個新的token并進行保存.

舉個簡單的例子只有可能是add,沒有可能是axc之類的組合.

else if (c == 'm') {
     CHECK(i + 1 < statement_.size() && statement_.at(i + 1) == 'u')
              << "Parse add token failed, illegal character: " << c;
      CHECK(i + 2 < statement_.size() && statement_.at(i + 2) == 'l')
              << "Parse add token failed, illegal character: " << c;
      Token token(TokenType::TokenMul, i, i + 3);
      tokens_.push_back(token);
      std::string token_operation = std::string(statement_.begin() + i, statement_.begin() + i + 3);
      token_strs_.push_back(token_operation);
      i = i + 3;
} 

同理當c等于字符m的時候,我們的語法規定token中以m作為開始的情況只有mul. 所以我們判斷接下來的兩個字必須是u和l. 如果不是的話,就報錯,是的話就初始化一個mul token進行保存.

   } else if (c == '@') {
      CHECK(i + 1 < statement_.size() && std::isdigit(statement_.at(i + 1)))
              << "Parse number token failed, illegal character: " << c;
      int32_t j = i + 1;
      for (; j < statement_.size(); ++j) {
        if (!std::isdigit(statement_.at(j))) {
          break;
        }
      }
      Token token(TokenType::TokenInputNumber, i, j);
      CHECK(token.start_pos < token.end_pos);
      tokens_.push_back(token);
      std::string token_input_number = std::string(statement_.begin() + i, statement_.begin() + j);
      token_strs_.push_back(token_input_number);
      i = j;
    } else if (c == ',') {
      Token token(TokenType::TokenComma, i, i + 1);
      tokens_.push_back(token);
      std::string token_comma = std::string(statement_.begin() + i, statement_.begin() + i + 1);
      token_strs_.push_back(token_comma);
      i += 1;
    }

當輸入為ant時候,我們對ant之后的所有數字進行讀取,如果其之后不是操作數,則報錯.當字符等于(或者,的時候就直接保存為對應的token,不需要對往后的字符進行探查, 直接保存為對應類型的Token.