C Academy · 课时

解析表达式

Q: 「解析表达式」这节课中我会学到什么？

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

构建解析树。

第 2 / 4 课13 个步骤

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

从 Token 到树

语法分析会将扁平的 Token 流转换成结构化的抽象语法树（AST）。这棵树会编码原始 Token 仅仅暗示出的优先级和分组关系。

对于 3 + 4 * 2，AST 会将乘法嵌套在加法之下，因此结果是 11，而不是 14。

AST Node 的形状

每个 Node 要么是数字叶子，要么是带有两个子 Node 的二元运算。使用带标签的结构体和联合体可以节省内存。

运算符字符会在运行时区分 +、-、* 和 /。

typedef struct Node {
  enum { N_NUM, N_BINOP } kind;
  union {
    int value;                 /* N_NUM */
    struct {                   /* N_BINOP */
      char op;
      struct Node *left, *right;
    } bin;
  };
} Node;

分配 Node

两个小型构造函数会在堆上分配 Node。自底向上构建树意味着先创建叶子，然后再将它们包装进运算符 Node。

在生产环境的解释器中，您还需要跟踪这些分配，以便稍后释放它们。

#include <stdlib.h>

static Node *num(int v) {
  Node *n = malloc(sizeof *n);
  n->kind = N_NUM; n->value = v;
  return n;
}

static Node *binop(char op, Node *l, Node *r) {
  Node *n = malloc(sizeof *n);
  n->kind = N_BINOP;
  n->bin.op = op; n->bin.left = l; n->bin.right = r;
  return n;
}

语法

我们使用经典的优先级语法。expr处理加法和减法，term处理乘法和除法，factor处理数字和括号。

由于优先级更高的规则位于更深层，乘法会自动比加法结合得更紧。

/* Grammar (EBNF):
   expr   = term   { ('+' | '-') term } ;
   term   = factor { ('*' | '/') factor } ;
   factor = NUMBER | '(' expr ')' ; */

匹配令牌

expect辅助函数会消耗指定类型的令牌；如果类型不符，就会中止。它是解析器与词法分析器之间的契约。

我们复用词法分析课程中的cur和bump前瞻辅助函数。

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

static void expect(TokKind k) {
  if (cur().kind != k) {
    fprintf(stderr, "parse error: unexpected token\n");
    exit(1);
  }
  bump();
}

解析因子

因子是语法中的原子：它要么是字面量数字，要么是带括号的子表达式。括号会递归调用parse_expr。

正是这种递归赋予了递归下降解析器这个名称。

static Node *parse_expr(void);

static Node *parse_factor(void) {
  if (cur().kind == TOK_NUM) {
    int v = cur().value; bump();
    return num(v);
  }
  expect(TOK_LPAREN);
  Node *e = parse_expr();
  expect(TOK_RPAREN);
  return e;
}

解析项

项先解析一个因子，然后在遇到*或/时循环，将每个运算折叠到一个左结合的二元运算节点中。

左结合意味着8 / 4 / 2会解析为(8 / 4) / 2 = 1。

static Node *parse_term(void) {
  Node *left = parse_factor();
  while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
    char op = (cur().kind == TOK_STAR) ? '*' : '/';
    bump();
    left = binop(op, left, parse_factor());
  }
  return left;
}

解析表达式

顶层规则与parse_term相似，但处理加法和减法。每一层都会调用优先级更高的下一条规则，因此生成的树会正确嵌套。

这三个函数组成的结构是解析器的核心。

static Node *parse_expr(void) {
  Node *left = parse_term();
  while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
    char op = (cur().kind == TOK_PLUS) ? '+' : '-';
    bump();
    left = binop(op, left, parse_term());
  }
  return left;
}

检查语法树

这个程序会解析一个表达式，并以完整括号化的形式将其打印出来，从而展示优先级是如何解析的。

美化打印器会递归遍历解析器构建的同一套节点结构。

#include <stdio.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 void show(Node *n){
  if (n->is_num){ printf("%d", n->value); return; }
  printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}

int main(void){
  /* 3 + 4 * 2  ->  (3 + (4 * 2)) */
  Node *ast = B('+', N(3), B('*', N(4), N(2)));
  show(ast); printf("\n");
  return 0;
}

避免左递归

像expr = expr '+' term这样的朴素语法会让parse_expr永远调用自身。递归下降解析器无法处理直接左递归。

将规则改写为围绕{ '+' term }的while循环，就能彻底避开无限递归。

为什么需要 AST

AST将语法与执行分离开来。同一棵树可以被求值、优化，或编译为字节码，而无需重新解析。

接下来，我们将遍历这棵树来计算它的值。

快速检查

思考一下语法的分层是如何强制实现优先级的。

在交互式课程中回答

回顾

您编写了一个递归下降解析器：包括 AST 节点结构体、构造函数，以及用于编码优先级和左结合性的表达式、项、因子函数。

生成的语法树已经可以进行求值。

免费开始

用 AI 导师学习 C — 免费

在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。

课程: 39
课程: 144

免费开始学习查看完整课程

常见问题解答

「解析表达式」课时是免费的吗？

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

「解析表达式」这节课中我会学到什么？

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

学习 C Academy 需要有经验吗？

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

「解析表达式」课时需要多长时间？

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

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

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

此课程中的所有课时

← 返回 C Academy