我们提出这个例子是为了让同学更加透彻的理解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

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。