第26章指针与编译器原理

课程目录第26章指针与编译器原理

第26章：指针与编译器原理：抽象语法树的指针表示、符号表的指针操作、中间代码生成的指针应用

说实话，很多C语言程序员写了好几年代码，对指针的理解还停留在“int *p”这个层面。但如果你真想成为高手，就得钻进编译器的肚子里看看——指针在编译器内部是怎么玩的？

我个人习惯把编译器比作一个翻译官。它把你的C代码读进去，拆成一颗树（抽象语法树），然后查字典（符号表），最后生成中间语言。这三个环节，处处离不开指针。今天我就带你走一遍这个流程。

26.1 抽象语法树的指针表示

抽象语法树，简称AST。说白了，就是把你的代码变成一棵树。每个节点是一个结构体，节点之间用指针连接。

我在项目中遇到过一个问题：一个表达式解析器，递归深度太深导致栈溢出。后来改成用指针构建AST，问题就解决了。为什么？因为树结构天然适合递归，而指针就是树的“关节”。

26.1.1 节点结构设计

每个AST节点，本质上就是一个结构体。里面存着节点类型、子节点指针、一些附加信息。比如一个二元表达式节点：

typedef struct ASTNode {
    int nodeType;           // 节点类型：加法、减法、赋值...
    struct ASTNode *left;   // 左子节点
    struct ASTNode *right;  // 右子节点
    union {
        int intVal;         // 如果是常量节点
        char *varName;      // 如果是变量节点
        // 其他类型...
    } data;
} ASTNode;

你看，left和right就是指针。它们指向子节点。整个表达式树就是靠这些指针串起来的。

核心思想：AST的指针表示，本质上是把线性代码“立起来”变成树。每个指针就是一个“边”，连接父节点和子节点。

26.1.2 树的构建过程

编译器解析代码时，遇到一个表达式就创建一个节点。比如解析“a + b * 3”：

先解析“b * 3”，创建一个乘法节点，left指向变量b，right指向常量3
再解析“a + (结果)”，创建一个加法节点，left指向变量a，right指向乘法节点

整个过程就是不断malloc新节点，然后设置指针。嗯，这里要注意：指针必须正确初始化。我曾经见过一个同事，malloc之后忘了给left和right赋NULL，结果遍历树时野指针崩溃。

我的习惯：每次创建节点后，立即把所有指针字段初始化为NULL。这叫“防御性编程”。

26.2 符号表的指针操作

符号表是什么？就是编译器用来记录变量、函数、类型信息的“字典”。每个符号对应一个条目，条目之间用指针组织起来。

你想想看，一个C程序里可能有几百个变量。怎么快速找到某个变量的类型信息？用数组？太慢了。用链表？查找是O(n)。所以编译器通常用哈希表或树，而这些数据结构都离不开指针。

26.2.1 符号表条目结构

typedef struct Symbol {
    char *name;             // 变量名
    int type;               // 类型：int、float、指针...
    int scopeLevel;         // 作用域层级
    struct Symbol *next;    // 哈希表链指针
    struct Symbol *parent;  // 作用域嵌套指针
    // 其他属性...
} Symbol;

这里有两个指针：next用于哈希表冲突链，parent用于作用域嵌套。我建议你仔细理解parent指针——它实现了作用域的“洋葱模型”。

26.2.2 作用域嵌套的指针实现

C语言的作用域是嵌套的。比如：

int x = 1;
void func() {
    int x = 2;  // 内层x覆盖外层x
    {
        int x = 3;  // 更内层
    }
}

编译器怎么知道每个x对应哪个声明？靠的就是符号表里的parent指针。每个作用域是一个链表，内层作用域的符号通过parent指向上层。查找时，先查当前层，找不到就顺着parent往上找。

我曾经踩过的坑：实现作用域退出时，忘了释放内层符号表的内存。结果内存泄漏，跑大型程序时内存暴涨。记住：退出作用域时，要遍历链表free所有节点。

26.3 中间代码生成的指针应用

AST和符号表都准备好了，下一步就是生成中间代码。中间代码是一种介于源码和机器码之间的表示，比如三地址码。

生成中间代码的过程，就是遍历AST，把每个节点翻译成一条或多条中间指令。这个遍历过程，本质上就是指针的“旅行”。

26.3.1 三地址码的指针表示

三地址码的每条指令，通常包含一个操作符和三个地址（两个操作数，一个结果）。地址可以是变量、常量、临时变量。这些地址怎么表示？用指针！

typedef struct TACInsn {
    int op;                 // 操作码：ADD、SUB、LOAD、STORE...
    struct TACAddr *arg1;   // 第一个操作数
    struct TACAddr *arg2;   // 第二个操作数
    struct TACAddr *result; // 结果
    struct TACInsn *next;   // 下一条指令
} TACInsn;

typedef struct TACAddr {
    int kind;               // 地址类型：变量、常量、临时变量
    union {
        Symbol *sym;        // 如果是变量，指向符号表条目
        int constVal;       // 如果是常量
        int tempId;         // 如果是临时变量
    } data;
} TACAddr;

你看，TACAddr里的sym指针直接指向符号表条目。这样，中间代码和符号表就关联起来了。生成代码时，只需要顺着AST的指针遍历，每遇到一个节点就生成一条TACInsn，然后用next指针串成链表。

26.3.2 遍历AST生成中间代码

生成中间代码的核心函数，就是一个递归遍历：

TACInsn* generateCode(ASTNode *node) {
    if (node == NULL) return NULL;
    
    switch (node->nodeType) {
        case NODE_BINARY_ADD: {
            // 先生成左右子树的代码
            TACInsn *leftCode = generateCode(node->left);
            TACInsn *rightCode = generateCode(node->right);
            
            // 创建新的临时变量
            TACAddr *temp = newTempAddr();
            
            // 创建加法指令
            TACInsn *addInsn = newTACInsn(OP_ADD, 
                leftCode->result, rightCode->result, temp);
            
            // 把指令串起来
            TACInsn *last = leftCode;
            while (last->next) last = last->next;
            last->next = rightCode;
            while (last->next) last = last->next;
            last->next = addInsn;
            
            return leftCode;
        }
        // 其他节点类型...
    }
}

这个函数返回的是一个指令链表。每个子树的代码生成后，通过next指针连接起来。最后整个函数返回的就是一个完整的指令序列。

关键点：中间代码生成，本质上是把树形结构（AST）转换成线性结构（指令链表）。指针在这个过程中扮演了“转换器”的角色。

26.4 知识体系总览

为了让你更直观地理解这三者的关系，我画了一张图：

从这张图你可以看到：源码经过分析变成AST，AST的节点通过指针连接成树。符号表通过指针实现快速查找和作用域嵌套。最后，遍历AST并查询符号表，生成中间代码——中间代码本身也是用指针串成的链表。

说白了，整个编译器就是一个“指针的狂欢”。每个阶段都在创建、修改、遍历指针连接的数据结构。你如果能把指针玩转，理解编译器内部机制就轻松多了。

我的建议：如果你想深入理解，可以自己动手写一个微型编译器。不需要太复杂，能解析“a = b + c”这种表达式就行。你会惊讶地发现，指针操作占了代码量的一半以上。

好了，这一章的内容就到这里。指针在编译器中的应用，远不止我今天讲的这些。但掌握了AST、符号表、中间代码这三个核心环节，你就抓住了编译器设计的“牛鼻子”。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录