引论

发表于 Waline： 阅读次数： 本文字数： 3k 阅读时长 ≈ 11 分钟

什么是编译器？

编译器（Compiler）本质上是一个程序，它的工作是将用某种源语言（Source Language）编写的程序，翻译成一个与之等价的、用另一种目标语言（Target Language）编写的程序。

编译器的核心任务

源程序（Source Program）→\to 编译器（Compiler）→\to 目标程序（Target Program）

  • 源语言：通常是像 C, C++, Java 这样的高级程序设计语言。
  • 目标语言：可以是另一种高级语言、特定机器的汇编语言，或者更常见的机器代码。
  • 等价性：指目标程序在执行时，其行为和结果应与源程序保持一致。
  • 错误报告：在翻译过程中，如果编译器发现源程序不符合源语言的语法或语义规则，它会报告错误，这是编译器的基本职责之一。

编译器 vs. 解释器

编译器和解释器是实现高级语言的两种主要方式，它们在工作原理上有本质区别。

特性 编译器（Compiler） 解释器（Interpreter）
工作方式 一次性翻译：先将整个源程序完整翻译成目标程序，然后执行目标程序。 逐行解释：读一句，解释一句，立即执行，不生成独立的目标文件。
产出物 独立的可执行目标程序（如 .exe, .o 文件）。 无独立目标程序，执行依赖于解释器。
执行效率 高。程序只需编译一次，之后可以多次快速运行目标代码。 低。每次执行都需要重新解释源代码，开销较大。
错误诊断 在编译阶段一次性报告所有语法错误，但错误定位可能不如解释器精确。 好。遇到错误立即停止，并报告出错位置，调试方便。
典型语言 C, C++, Go, Rust Python, JavaScript, Ruby, Shell

混合模式：Java 的启示

现代语言常常结合编译器和解释器的优点。以 Java 为例：

  1. javac 编译器首先将 .java 源文件编译成平台无关的字节码（Bytecode）文件（.class）。
  2. Java 虚拟机（JVM）充当一个解释器，解释执行字节码。
  3. 为了提升性能，JVM 内部还包含了即时编译器（Just-in-Time Compiler, JIT），它会在运行时将频繁执行的「热点」字节码编译成高效的本地机器码。
  4. 此外，还有提前编译器（Ahead-of-Time Compiler, AOT）技术，可以直接将字节码或源代码在运行前编译成本地机器码。

一个典型的编译过程

将一个 C 语言源文件（例如 hello.c）变成一个可执行程序，并不仅仅是编译器一个程序的功劳，而是由一个工具链（Toolchain）协同完成的。

graph LR
    subgraph 编译系统
        A_Source[源程序 main.c] -->|预处理器| B_Preprocessed[预处理的源程序 main.i];
        B_Preprocessed -->|编译器| C_Assembly[目标汇编程序 main.s];
        C_Assembly -->|汇编器| D_Relocatable[可重定位目标文件 main.o];
        E_Library[库文件 libc.a] --- F_LinkHidden:::hidden;
        D_Relocatable --- F_LinkHidden;
        F_LinkHidden -->|链接器| G_Executable[可执行目标文件 main];
    end
  
    G_Executable --> |加载器| H_MemoryImage[内存中的程序映像];
    H_MemoryImage --> I_ProcessExecution[进程执行];

    classDef hidden display: none;

    %% 节点样式
    classDef nodeStyle fill:#e0f7fa,stroke:#00796b,stroke-width:2px,rx:8px,ry:8px,color:#263238;
    class A_Source,B_Preprocessed,C_Assembly,D_Relocatable,E_Library,G_Executable,H_MemoryImage,I_ProcessExecution nodeStyle;

    %% 强调关键节点
    style A_Source fill:#ffecb3,stroke:#ffa000,stroke-width:2px,color:#263238;
    style G_Executable fill:#bbdefb,stroke:#1976d2,stroke-width:2px,color:#263238;
    style I_ProcessExecution fill:#c8e6c9,stroke:#388e3c,stroke-width:2px,color:#263238;

    %% 子图样式
    subgraph 编译系统
        style 编译系统 fill:#f0f4c3,stroke:#afb42b,stroke-width:2px,rx:10px,ry:10px;
    end
  1. 预处理器（Preprocessor）：处理源代码中以 # 开头的指令，如 #include（插入头文件内容）、#define（宏替换）等。它本质上是一个文本替换工具。
  2. 编译器（Compiler）：这是核心环节，将预处理后的 C 代码翻译成等价的汇编代码。这个过程包含了后续将深入学习的词法分析、语法分析、语义分析、优化等步骤。
  3. 汇编器（Assembler）：将汇编代码翻译成机器可以理解的二进制指令，生成可重定位目标文件（Relocatable Object File），在 Linux 中通常是 .o 文件。
  4. 链接器（Linker）：程序通常会调用库函数（如 printf）。链接器负责将我们自己生成的 .o 文件与所需的库文件链接在一起，解决符号引用问题，最终生成一个完整的可执行文件。
  5. 加载器（Loader）：当执行程序时，操作系统中的加载器负责将可执行文件从磁盘加载到内存，并准备好执行环境，程序开始运行。

编译器的逻辑结构

一个现代编译器在逻辑上通常被划分为两个主要部分：前端和后端。

  • 分析部分（前端, Front End）：负责理解源程序。它对源程序进行词法、语法和语义的分析，检查错误，并生成一种与具体机器无关的中间表示（Intermediate Representation, IR）。前端主要与源语言的特性相关。
  • 综合部分（后端, Back End）：负责生成目标程序。它接收前端生成的中间表示，进行优化，并最终生成特定目标机器的代码。后端主要与目标机器的体系结构相关。

这种划分带来了极大的好处：

  • 模块化：可以为 M 种语言和 N 种机器架构，只开发 M 个前端和 N 个后端，就能组合出 M ×\times N 个编译器。
  • 关注点分离：前端开发者专注于语言本身，后端开发者专注于目标硬件的优化。

编译器的主要阶段（Phases）

让我们通过一个简单的例子 position = initial + rate * 60 来追踪源程序在编译器前端和后端经历的旅程。

词法分析（Lexical Analysis）

  • 任务：读取源程序的字符流，将它们组合成有意义的词素（lexeme），并为每个词素生成一个词法单元（token）。
  • 输出：一个 token 流。token 通常表示为 <token-name, attribute-value> 的形式。
  • 示例：
    • 源字符串：position = initial + rate * 60
    • 生成的 Token 流：
      • position → <id, 1>（1 是其在符号表中的条目指针）
      • = → <assign_op>
      • initial → <id, 2>
      • + → <add_op>
      • rate → <id, 3>
      • * → <mul_op>
      • 60 → <number, 60>

语法分析（Syntax Analysis/Parsing）

  • 任务：接收词法分析器生成的 token 流，根据语言的语法规则，将它们组织成一个树状的中间表示，通常是抽象语法树（Abstract Syntax Tree, AST）。AST 清晰地展示了程序的层次结构和运算的优先级。
  • 输出：一棵抽象语法树。
  • 示例： 
    graph TD
    A[=] --> B(id, position);
    A --> C(\+);
    C --> D(id, initial);
    C --> E(\*);
    E --> F(id, rate);
    E --> G(number, 60);

语义分析（Semantic Analysis）

  • 任务：使用语法树和符号表中的信息，检查源程序是否符合语言的语义规则。主要工作是类型检查，确保操作符的操作数类型匹配。如果类型不匹配，它会尝试进行类型转换（Type Coercion）。
  • 输出：一棵经过类型检查和注解的 AST。
  • 示例：假设 position, initial, rate 都是 float 类型，而 60 是一个 int。语义分析器会发现 * 运算符的一个操作数是 float，另一个是 int。它会插入一个隐式的类型转换节点，将 60 转换为浮点数。 
    graph TD
    A[=] --> B(id, position);
    A --> C(\+);
    C --> D(id, initial);
    C --> E(\*);
    E --> F(id, rate);
    E --> H(int_to_float);
    H --> G(number, 60);

中间代码生成（Intermediate Code Generation）

  • 任务：将 AST 翻译成一种更接近机器语言但又与具体机器无关的中间表示（IR）。三地址代码（Three-Address Code）是一种常见的 IR，其特点是每个指令最多有三个操作数。
  • 输出：中间代码序列。
  • 示例： 
    1
    2
    3
    4
    t1 = int_to_float(60)
    t2 = id3 * t1          ; id3 对应 rate
    t3 = id2 + t2          ; id2 对应 initial
    id1 = t3               ; id1 对应 position

代码优化（Code Optimization）

  • 任务：分析中间代码，对其进行改进，以生成更快、更小或更节能的目标代码。这是一个非常复杂的阶段，包含多种优化技术。
  • 输出：优化后的中间代码。
  • 示例：一个简单的优化是常量折叠（Constant Folding）。编译器可以在编译时就计算出 int_to_float(60) 的结果是 60.0。 
    1
    2
    t1 = id3 * 60.0
    id1 = id2 + t1

目标代码生成（Code Generation）

  • 任务：将优化后的中间代码映射到目标机器的指令集上。这个阶段涉及指令选择、寄存器分配和内存管理。
  • 输出：目标语言程序（通常是汇编代码）。
  • 示例（假设使用一种简化的类 MIPS 汇编）： 
    1
    2
    3
    4
    5
    LDF  R2, rate       ; 将 rate 的值加载到浮点寄存器 R2
    MULF R2, R2, #60.0  ; R2 = R2 * 60.0
    LDF  R1, initial    ; 将 initial 的值加载到浮点寄存器 R1
    ADDF R1, R1, R2     ; R1 = R1 + R2
    STF  position, R1   ; 将 R1 的值存回 position 的内存位置

贯穿各阶段的工具

  • 符号表管理（Symbol Table Management）：符号表是一个核心数据结构，用于存储源程序中出现的标识符（如变量名、函数名）的各种信息，包括其类型、作用域、存储位置等。编译器的所有阶段都会查询或更新符号表。
  • 错误处理（Error Handling）：在编译的每个阶段都可能检测到错误。一个好的编译器应该能准确、清晰地报告错误，并尽可能从错误中恢复，以便继续检查程序的其余部分。

程序设计语言的核心概念

编译器的设计深受程序设计语言自身特性的影响。理解这些基本概念至关重要。

静态 vs. 动态

  • 静态（Static）：指在编译时就可以确定的特性或执行的动作。例如，在 C 语言中，变量的类型是静态的，编译器在编译时就知道 int x; 中的 x 是整数类型。
  • 动态（Dynamic）：指必须在运行时才能确定或执行的动作。例如，Python 中的变量类型是动态的，一个变量在程序的不同执行点可以指向不同类型的对象。

语言的静态特性越多，编译器能做的检查和优化就越多。

作用域（Scope）

作用域是一个标识符在程序文本中有效的区域。

  • 静态作用域（Static Scope），也称词法作用域（Lexical Scope）：作用域由标识符在源代码中的位置决定。一个变量引用的是其定义所在的代码块（或函数）中最近的那个声明。C/C++ 和 Java 等绝大多数现代语言都使用静态作用域。
    • 块作用域（Block Scope）：由 {} 定义。在块内声明的变量仅在该块及其子块中可见。
  • 动态作用域（Dynamic Scope）：作用域由程序的调用链决定。一个变量引用的是在程序执行路径上，最近一次调用且尚未返回的函数中对该变量的声明。一些早期的 Lisp 方言和 shell 脚本使用动态作用域。

参数传递机制（Parameter Passing）

  • 传值调用（Call by Value）：将实际参数的值复制一份传递给形式参数。在函数内对形式参数的修改不会影响到函数外的实际参数。这是 C, Java 等语言的默认方式。
  • 传引用调用（Call by Reference）：将实际参数的地址（或引用）传递给形式参数。形式参数成为实际参数的别名（Alias）。在函数内对形式参数的修改会直接影响到函数外的实际参数。C++ 的引用参数 & 和 Pascal 的 VAR 参数就是这种方式。

别名问题

别名（Aliasing）是指两个或多个不同的名字指向了同一块内存地址。这通常由指针或引用参数造成。别名会给代码优化带来巨大挑战，因为编译器很难判断对一个变量的修改是否会意外地改变另一个看似无关的变量的值。

编译技术的应用与发展

编译技术不仅仅用于构建传统语言的编译器，它的理论和方法在计算机科学的许多领域都有广泛应用：

  • 针对新硬件的优化：为多核处理器、GPU、FPGA 等专用硬件设计编译器，以充分利用其并行计算能力和特殊架构。
  • 程序翻译：
    • 二进制翻译：在一种平台上运行为另一种平台编译的程序（例如，苹果的 Rosetta 2）。
    • 硬件合成：将类 C 的硬件描述语言（如 SystemC）编译成电路布局。
  • 软件生产力工具：
    • 静态分析器：检查代码中的潜在 bug、安全漏洞和编码规范问题。
    • 内存管理工具：如 Valgrind，利用编译技术在程序中插入检查代码，以检测内存泄漏和越界访问。
  • 新兴领域：
    • 深度学习编译器：如 TVM, MLIR 等，它们将高级的深度学习模型（如 TensorFlow, PyTorch 图）编译成在不同硬件（CPU, GPU, TPU）上高效执行的代码。