從零自制深度學習推理框架: 計算圖中的表達式講解（3）

我們提出這個例子是為了讓同學更加透徹的理解Expression Layer, 我們舉一個復雜點的例子：

add(mul(@0,@1),@2),我們將以人工分析的方式去還原詞法和語法分析的過程.

我們將以上的這個輸入劃分為多個token,多個token分別為

add | left bracket|  |mul|left bracket|@0|comma|@1|right bracket| @2 |right bracket

在ExpressionParser::Generate_函數對例子add(mul(@0,@1),@2),如下的列表為token 數組.

• add
• (
• mul
• (
• @0
• ,
• @1
• )
• ,
• @2
• )

1. index = 0, 當前遇到的token為add, 調用層為1

2. index = 1, 根據以上的流程,我們期待add token之后的token為left bracket, 否則就報錯. 調用層為1

3. **開始遞歸調用,構建add的左子樹.**從層1進入層2

4. index = 2, 遇到了mul token. 調用層為2.

5. index = 3, 根據以上的流程,我們期待mul token之后的token是第二個left bracket. 調用層為2.

6. 開始遞歸調用用來構建mul token的左子樹.

7. index = 4, 遇到@0,進入遞歸調用,進入層3, 但是因為操作數都是葉子節點,構建好之后就直接返回了,得到mul token的左子節點.放在mul token的left 指針上.

8. index = 5, 我們希望遇到一個逗號,否則就報錯mul(@0,@1)中中間的逗號.調用層為2.

9. index = 6, 遇到@2,進入遞歸調用,進入層3, 但是因為操作數是葉子節點, 構建好之后就直接返回到2,得到mul token的右子節點.

10. index = 7, 我們希望遇到一個右括號,就是mul(@1,@2)中的右括號.調用層為2.

11. 到現在為止mul token已經構建完畢,返回形成add token的左子節點,add token的left指針指向構建完畢的mul樹. 返回到調用層1.

    ...

12. add token開始構建right token,但是因為@2是一個輸入操作數,所以直接遞歸就返回了,至此得到add的右子樹,并用right指針指向.

所以構建好的抽象語法樹如圖：

需要完成test/tet_expression.cpp下的expression3函數

TEST(test_expression, expression3) {
  using namespace kuiper_infer;
  const std::string &statement = "add(@0,div(@1,@2))";
  ExpressionParser parser(statement);
  const auto &node_tokens = parser.Generate();
  ShowNodes(node_tokens);
}

static void ShowNodes(const std::shared_ptr<kuiper_infer::TokenNode> &node) {
  if (!node) {
    return;
  }
  ShowNodes(node->left);
  if (node->num_index < 0) {
    if (node->num_index == -int(kuiper_infer::TokenType::TokenAdd)) {
      LOG(INFO) << "ADD";
    } else if (node->num_index == -int(kuiper_infer::TokenType::TokenMul)) {
      LOG(INFO) << "MUL";
    }
  } else {
    LOG(INFO) << "NUM: " << node->num_index;
  }
  ShowNodes(node->right);
}

TEST(test_expression, expression1) {
  using namespace kuiper_infer;
  const std::string &statement = "add(mul(@0,@1),@2)";
  ExpressionParser parser(statement);
  const auto &node_tokens = parser.Generate();
  ShowNodes(node_tokens);
}

最后會打印抽象語法樹的中序遍歷：

Could not create logging file: No such file or directory
COULD NOT CREATE A LOGGINGFILE 20230115-223854.21496!I20230115 22:38:54.863226 21496 test_main.cpp:13] Start test...
I20230115 22:38:54.863480 21496 test_expression.cpp:23] NUM: 0
I20230115 22:38:54.863488 21496 test_expression.cpp:20] MUL
I20230115 22:38:54.863492 21496 test_expression.cpp:23] NUM: 1
I20230115 22:38:54.863497 21496 test_expression.cpp:18] ADD
I20230115 22:38:54.863502 21496 test_expression.cpp:23] NUM: 2

如果語句是一個更復雜的表達式 add(mul(@0,@1),mul(@2,@3))

image-20230115224350088

我們的單元測試輸出為:

I20230115 22:48:22.086627 23767 test_expression.cpp:23] NUM: 0
I20230115 22:48:22.086635 23767 test_expression.cpp:20] MUL
I20230115 22:48:22.086639 23767 test_expression.cpp:23] NUM: 1
I20230115 22:48:22.086644 23767 test_expression.cpp:18] ADD
I20230115 22:48:22.086649 23767 test_expression.cpp:23] NUM: 2
I20230115 22:48:22.086653 23767 test_expression.cpp:20] MUL
I20230115 22:48:22.086658 23767 test_expression.cpp:23] NUM: 3