构建一个微型 C 编译器：词法分析器、解析器、AST

目标：编译像 4 + 3 * 2 这样的算术表达式。三个阶段：

1. 词法分析器（Lexer） — 源文本 → token 流
2. 解析器（Parser） — token 流 → AST
3. 代码生成（Codegen） — AST → 汇编（或直接求值）

1. 词法分析器

词法分析器逐字符读取像 "5 + 3" 这样的字符串，产出一串 token —— 带类型、有意义的代码单元。

token 类型，用 enum 表示：

typedef enum {
    TOKEN_NUMBER,
    TOKEN_PLUS,
    TOKEN_MINUS,
    TOKEN_STAR,
    TOKEN_SLASH,
    TOKEN_LPAREN,
    TOKEN_RPAREN,
    TOKEN_EOF
} TokenType;

每个 token 携带其类型以及一个数值（仅对数字有效）：

typedef struct {
    TokenType type;
    int value; // 当 type == TOKEN_NUMBER 时有效
} Token;

示例："42 + 7" → NUMBER(42), PLUS, NUMBER(7), EOF。

扫描是对游标（const char **）的一次遍历，因此词法分析器状态会随着 token 被消费而向前推进：

int is_digit(char c) { return c >= '0' && c <= '9'; }

Token get_next_token(const char **src) {
    // 1. 跳过空白字符
    while (**src == ' ' || **src == '\t' || **src == '\n') (*src)++;

    // 2. 输入结束
    if (**src == '\0') return (Token){ TOKEN_EOF, 0 };

    // 3. 多位数字
    if (is_digit(**src)) {
        int val = 0;
        while (is_digit(**src)) {
            val = val * 10 + (**src - '0');
            (*src)++;
        }
        return (Token){ TOKEN_NUMBER, val };
    }

    // 4. 单字符运算符
    char c = **src;
    (*src)++;
    switch (c) {
        case '+': return (Token){ TOKEN_PLUS, 0 };
        case '-': return (Token){ TOKEN_MINUS, 0 };
        case '*': return (Token){ TOKEN_STAR, 0 };
        case '/': return (Token){ TOKEN_SLASH, 0 };
        case '(': return (Token){ TOKEN_LPAREN, 0 };
        case ')': return (Token){ TOKEN_RPAREN, 0 };
        default:
            fprintf(stderr, "Error: unknown character '%c'\n", c);
            exit(1);
    }
}

驱动循环：

int main(void) {
    const char *src = "432 + 2 * 10";
    Token tok;

    do {
        tok = get_next_token(&src);
        printf("type=%d value=%d\n", tok.type, tok.value);
    } while (tok.type != TOKEN_EOF);
}

2. 解析器

解析器把扁平的 token 流转换成一棵 抽象语法树（AST），用来表示程序的结构。

AST 节点

一个表达式要么是一个 数字（叶子节点），要么是一个 二元运算（运算符 + 左/右子树）。用递归 struct 和 union 建模：

typedef enum { AST_NUMBER, AST_BINARY_OP } ASTNodeType;

typedef struct ASTNode {
    ASTNodeType type;
    union {
        int number_val; // AST_NUMBER
        struct {        // AST_BINARY_OP
            TokenType op;
            struct ASTNode *left, *right;
        } binary_op;
    };
} ASTNode;

堆分配的构造函数：

ASTNode *create_num_node(int val) {
    ASTNode *node = malloc(sizeof(ASTNode));
    node->type = AST_NUMBER;
    node->number_val = val;
    return node;
}

ASTNode *create_binop_node(TokenType op, ASTNode *left, ASTNode *right) {
    ASTNode *node = malloc(sizeof(ASTNode));
    node->type = AST_BINARY_OP;
    node->binary_op.op = op;
    node->binary_op.left = left;
    node->binary_op.right = right;
    return node;
}

通过递归下降实现优先级

4 + 3 * 2 必须解析成 4 + (3 * 2)，而不是 (4 + 3) * 2。解决方案：递归下降 —— 每一个优先级层级对应一个函数：

parse_expression  (+, -)
  └─ parse_term   (*, /)
       └─ parse_factor  (数字、括号)

优先级更高的运算符位于调用链的更深层，所以它们绑定得更紧。

解析器状态 —— 当前 token 加上一个指向源的游标：

static Token current_token;
static const char *src_ptr;

void advance(void) {
    current_token = get_next_token(&src_ptr);
}

parse_factor —— 原子单元

处理构建块：数字和带括号的表达式。

ASTNode *parse_factor(void) {
    if (current_token.type == TOKEN_NUMBER) {
        ASTNode *node = create_num_node(current_token.value);
        advance();
        return node;
    }

    if (current_token.type == TOKEN_LPAREN) { // '(' expr ')'
        advance();
        ASTNode *node = parse_expression(); // 括号内是完整表达式
        if (current_token.type != TOKEN_RPAREN) {
            fprintf(stderr, "Syntax Error: expected ')'\n");
            exit(1);
        }
        advance();
        return node;
    }

    fprintf(stderr, "Syntax Error: expected number or '('\n");
    exit(1);
}

括号属于 parse_factor，因为带括号的表达式是一个原子单元，就像数字一样。对 parse_expression 的递归调用处理像 ((1 + 2) * 3) 这样的嵌套。

parse_term 和 parse_expression

两个层级采用相同模式：先解析左操作数，然后只要当前运算符匹配本层级，就循环构建一棵左结合的树。

ASTNode *parse_term(void) {
    ASTNode *left = parse_factor();

    while (current_token.type == TOKEN_STAR || current_token.type == TOKEN_SLASH) {
        TokenType op = current_token.type;
        advance();
        left = create_binop_node(op, left, parse_factor());
    }
    return left;
}

ASTNode *parse_expression(void) {
    ASTNode *left = parse_term();

    while (current_token.type == TOKEN_PLUS || current_token.type == TOKEN_MINUS) {
        TokenType op = current_token.type;
        advance();
        left = create_binop_node(op, left, parse_term());
    }
    return left;
}

跟踪：4 + 3 * 2

1. parse_expression → parse_term → parse_factor 读入 4。
2. 回到 parse_expression：看到 +，调用 parse_term 解析右侧。
3. parse_term 读入 3，看到 *，读入 2，构建子树 (3 * 2)。
4. parse_expression 连接成 4 + (3 * 2)。

最终 AST：

    (+)
    / \
  (4) (*)
      / \
    (3) (2)

3. 下一步：求值或代码生成

AST 构建完成后，有两条路径：

• 解释器：递归遍历这棵树，直接在 C 中计算整数结果。
• 编译器：遍历这棵树生成 x86-64 指令（mov、add、imul），用 GCC 汇编链接，原生运行。