第二章 编译器前端基础：词法分析与语法分析入门、抽象语法树（AST）的构建、符号表与作用域管理

好，咱们正式开始啃编译器前端这块硬骨头。

很多人一听到「词法分析」「语法分析」就觉得头大，觉得这是编译原理课上的理论活儿。但说实话，做 GPU Shader 编译器优化，前端基础是绕不开的。你想想看，连代码都解析不对，后面的优化就是空中楼阁。

我个人习惯把编译器前端比作「翻译官」——它把人类写的 GLSL 或 HLSL 代码，翻译成编译器后端能理解的结构化数据。今天我们就来拆解这个翻译过程。

2.1 词法分析：把字符流变成 Token 流

词法分析，说白了就是「分词」。

你写了一句 float4 color = texture2D(tex, uv);，编译器看到的是一个个字符：f、l、o、a、t…… 但编译器没法直接处理这些零散的字符。它需要先把它们组合成有意义的「单词」——也就是 Token。

Token 是什么？

Token 是词法分析的最小单元。每个 Token 包含两部分：类型（比如关键字、标识符、运算符）和值（比如 "float4"、"color"）。

举个例子，对于 float4 color = texture2D(tex, uv);，词法分析器会生成这样的 Token 序列：

Token(TYPE, "float4")
Token(IDENTIFIER, "color")
Token(OPERATOR, "=")
Token(IDENTIFIER, "texture2D")
Token(LEFT_PAREN, "(")
Token(IDENTIFIER, "tex")
Token(COMMA, ",")
Token(IDENTIFIER, "uv")
Token(RIGHT_PAREN, ")")
Token(SEMICOLON, ";")

我在项目中遇到过一个问题：某个 Shader 在编译时总是报「unexpected token」错误。查了半天，发现是词法分析器把 texture2D 当成了两个 Token——texture 和 2D。嗯，这是因为词法规则里没把 texture2D 注册为内置函数名。所以你看，词法分析看似简单，但规则定义必须严谨。

小技巧：写词法分析器时，我建议用「最长匹配」原则。比如遇到 >>=，应该匹配成 >>=（右移赋值），而不是 > 和 >=。否则后面语法分析会出大问题。

2.2 语法分析：从 Token 流到语法树

词法分析完了，我们得到了一堆 Token。但 Token 只是单词，不是句子。语法分析的任务，就是把这些单词按照语法规则组合成「句子」——也就是语法树。

语法分析有两种主流方式：自顶向下（递归下降）和自底向上（LR 分析）。做 Shader 编译器，我个人更偏爱递归下降。为什么？因为 Shader 的语法相对简单，递归下降写起来直观，调试也方便。

举个例子，对于赋值语句 color = tex2D(uv);，语法分析器会构建出这样的结构：

AssignmentStmt
├── LHS: Variable("color")
└── RHS: FunctionCall("tex2D")
    └── Argument: Variable("uv")

你可能会问：「这不就是 AST 吗？」对，语法分析的结果就是抽象语法树。但注意，语法分析阶段生成的树，还带着很多「语法糖」——比如括号、分号这些。后面我们会去掉这些冗余信息，得到真正的 AST。

我曾经踩过的坑：在写递归下降解析器时，左递归是个大麻烦。比如表达式 a + b + c，如果规则写成 expr ::= expr '+' term，就会无限递归。解决办法是改成右递归，或者用循环代替递归。嗯，这个坑我至少掉进去三次。

2.3 抽象语法树（AST）的构建

AST 是编译器前端的核心产出。它去掉了语法分析树中的「噪音」——比如括号、分号、逗号这些只为了辅助解析的东西，只保留程序的结构和语义。

拿一个简单的 Shader 函数来说：

float4 main(float2 uv : TEXCOORD0) : SV_Target {
    return tex2D(tex, uv);
}

对应的 AST 大概是这样的：

FunctionDef
├── ReturnType: float4
├── Name: "main"
├── Parameters
│   └── Parameter
│       ├── Type: float2
│       ├── Name: "uv"
│       └── Semantic: "TEXCOORD0"
├── Semantic: "SV_Target"
└── Body: Block
    └── ReturnStmt
        └── CallExpr
            ├── Function: "tex2D"
            └── Arguments
                ├── Variable: "tex"
                └── Variable: "uv"

你看，AST 里没有分号、没有括号，只有纯粹的语义结构。这就是编译器后端做优化的基础。

我个人习惯用 Visitor 模式来遍历 AST。每个节点都有一个 accept 方法，接受一个 Visitor 对象。这样，添加新的优化 pass 时，只需要写一个新的 Visitor，不用修改 AST 节点本身。

核心要点：AST 的节点类型要设计得「不多不少」。太少，语义信息丢失；太多，遍历效率低下。我一般控制在 20-30 种节点类型，覆盖变量、表达式、语句、函数、类型声明等。

2.4 符号表与作用域管理

AST 建好了，但还有一个关键问题：我怎么知道 tex 是什么？是 uniform？是局部变量？还是函数参数？

这就需要符号表了。

符号表，说白了就是一个「字典」，记录了每个标识符的类型、作用域、存储类别等信息。而作用域管理，就是决定这个字典在什么时候生效、什么时候失效。

Shader 的作用域规则和 C 语言很像：

  • 全局作用域：uniform、attribute、varying 等声明
  • 函数作用域：函数参数、函数内局部变量
  • 块作用域：{} 内的局部变量

举个例子：

uniform float4 color;  // 全局作用域

float4 main() {
    float4 result = color;  // 查找全局符号表
    {
        float4 color = float4(1,0,0,1);  // 块作用域，遮蔽全局 color
        result = color;  // 查找块作用域，找到局部 color
    }
    return result;  // 块作用域结束，局部 color 失效
}

符号表的设计，我建议用「栈」结构。每进入一个作用域，就压入一个新表；退出时弹出。查找时从栈顶往下找，这样自然实现了「内层遮蔽外层」的语义。

避坑指南：我曾经在实现符号表时，忘了处理「前向引用」。比如在 GLSL 中，你可以先调用一个函数，再定义它。这时候符号表里还没有这个函数的信息。解决办法是分两遍扫描：第一遍收集所有声明，第二遍才做类型检查和代码生成。

2.5 三者如何协同工作？

词法分析、语法分析、AST 构建、符号表管理，这四个步骤不是孤立的。它们在实际编译器中是这样配合的：

  1. 词法分析器逐个读取字符，吐出 Token
  2. 语法分析器消费 Token，一边构建 AST 节点，一边调用符号表接口
  3. 遇到变量声明时，语法分析器通知符号表：「嘿，我声明了一个叫 color 的变量，类型是 float4」
  4. 遇到变量使用时，语法分析器查询符号表：「这个 color 是什么？在哪定义的？」
  5. AST 构建完成后，符号表里已经记录了所有标识符的信息

你想想看，如果没有符号表，AST 里的 Variable("color") 节点就是个空壳子，编译器根本不知道它是什么类型、在哪定义的。后面的类型检查、常量折叠、死代码消除，全都无从谈起。

总结一下：

  • 词法分析：字符 → Token
  • 语法分析：Token → AST（带语法糖）
  • AST 构建：去语法糖，保留语义结构
  • 符号表：记录标识符的「身份信息」
  • 作用域管理：控制符号表的生命周期

好了，这一章的内容就到这里。下一章我们会深入 AST 的遍历和变换，看看编译器是如何在 AST 上做各种优化的。到时候我会分享一些实际项目中用到的技巧，比如如何用 AST 做常量折叠、如何检测死代码。嗯，敬请期待。

← 上一章 📖 返回目录 下一章 →