C Academy · 课时

计算语法树

Q: 「计算语法树」这节课中我会学到什么？

计算结果。 你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

计算结果。

计算语法树 是 CoddyKit 上的免费 C Academy 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 C Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 C Academy 课程共包含 4 节课。

遍历 AST

求值采用后序遍历：先计算子节点，再使用节点的运算符将它们组合起来。数字叶节点会直接返回自身的值。

这种树遍历解释器是解释器能够拥有的最简单后端。

eval 的签名

我们的求值器接收一个节点指针，并返回一个整数。由于语法树具有递归结构，该函数本身也具有递归结构。

对于浮点语言，您可以返回double或带标签的值。

int eval(Node *n);  /* returns the integer value of the subtree */

计算叶节点

基本情况会终止递归。当节点是数字时，它的值就是该子树的答案。

每次递归下降都必须到达基本情况，否则就永远不会终止。

int eval(Node *n) {
  if (n->kind == N_NUM) {
    return n->value;
  }
  /* ... handle N_BINOP below ... */
  return 0;
}

计算 BinOp

对于运算符节点，我们递归计算两个子节点，然后应用运算符。先计算左侧再计算右侧，就能得到通常的从左到右顺序。

根据运算符字符使用switch，可以让逻辑更清晰。

int eval(Node *n) {
  if (n->kind == N_NUM) return n->value;
  int l = eval(n->bin.left);
  int r = eval(n->bin.right);
  switch (n->bin.op) {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

防止除以零

在 C 中，整数除以零属于未定义行为，通常会导致进程崩溃。安全的解释器会先检查除数。

报告一个清晰的运行时错误，总好过让SIGFPE失控发生。

#include <stdio.h>
#include <stdlib.h>

static int safe_div(int a, int b) {
  if (b == 0) {
    fprintf(stderr, "runtime error: division by zero\n");
    exit(1);
  }
  return a / b;
}

端到端求值

这里会对手动构建的(2 + 3) * 4语法树求值，结果为 20。同一个eval也可以运行解析器生成的任何语法树。

运行它，确认后序遍历能够计算出正确答案。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int is_num; int value;
  char op; struct Node *l, *r;
} Node;

static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }

static int eval(Node *n){
  if (n->is_num) return n->value;
  int l = eval(n->l), r = eval(n->r);
  switch (n->op){
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/': return l / r;
  }
  return 0;
}

int main(void){
  Node *ast = B('*', B('+', N(2), N(3)), N(4));
  printf("%d\n", eval(ast));
  return 0;
}

栈深度

每个嵌套的运算符都会向 C 调用栈添加一个栈帧。像一千层括号这样的深度嵌套表达式可能会使调用栈溢出。

大多数实际表达式都不深，但稳健的解释器可以改用显式栈来确保安全。

折叠常量

由于求值和解析共享同一棵树，您可以对其进行优化。如果二元运算节点的两个子节点都是数字，就可以计算一次结果，并将该节点替换为叶节点。

这种常量折叠是经典的解释器优化方法。

/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
  if (n->kind == N_BINOP) {
    n->bin.left  = fold(n->bin.left);
    n->bin.right = fold(n->bin.right);
    if (n->bin.left->kind == N_NUM &&
        n->bin.right->kind == N_NUM)
      return num(eval(n));
  }
  return n;
}

释放语法树

在堆上分配的节点必须被释放。后序释放会先访问子节点，再访问父节点，与求值过程相对应。

忘记释放会导致解释器每运行一个表达式就泄漏内存。

void free_tree(Node *n) {
  if (n->kind == N_BINOP) {
    free_tree(n->bin.left);
    free_tree(n->bin.right);
  }
  free(n);
}

一元减号

需要处理-5这样的取负操作。一种选择是使用一元节点；另一种选择是在解析时将-x反糖化为0 - x。

无论采用哪种方式，求值都仍然只是简单的递归遍历。

/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
  bump();
  return binop('-', num(0), parse_factor());
}

为什么采用树遍历

树遍历解释器易于编写和调试，但会牺牲一些速度。早期的 Ruby 等语言曾采用这种模型，后来才转向字节码虚拟机。

接下来，我们将添加变量，让解释器能够记住值。

快速检查

思考 eval 访问各个节点的顺序。

回顾

您实现了一个递归求值器：包括叶节点基本情况、二元运算递归、除零保护，以及语法树释放和常量折叠。

现在，解释器可以计算任意算术 AST。下一步是添加变量。

常见问题解答

「计算语法树」课时是免费的吗？

是的 — 「计算语法树」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 C Academy 课程的其余内容，请升级到 CoddyKit PRO。 C Academy 课程共包含 4 节课。

「计算语法树」这节课中我会学到什么？

计算结果。你通过在浏览器中直接运行的动手代码来练习 C Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 C Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 C Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「计算语法树」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 C Academy 课中编写并运行代码吗？

能。每节 C Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 C Academy