Fulongのblog

编译原理

2021/03/25 Others 共 4026 字，约 12 分钟

编译原理

参考

预处理

最后简单描述一下预处理。预处理主要是处理一些宏定义，比如 #define、#include、#if 等。预处理的实现有很多种，有的编译器会在词法分析前先进行预处理，替换掉所有 # 开头的宏，而有的编译器则是在词法分析的过程中进行预处理。当分析到 # 开头的单词时才进行替换。虽然先预处理再词法分析比较符合直觉，但在实际使用中，GCC 使用的却是一边词法分析，一边预处理的方案。

词法分析

  • 输入：源代码
  • 输出：中间代码
  • 把源代码分割开，形成若干个单词。原理主要是状态机。处理之后，编译器就知道了每个单词

语法分析

  • 思路是模板匹配，把单词组合起来
  • 成功解析语法以后，我们会得到抽象语法树(AST: Abstract Syntax Tree)
int fun(int a, int b) {    int c = 0;    c = a + b;    return c;}

它的语法树如下:

img

生成中间代码

  • 意义：不同cpu的汇编语法不一致。因此需要生成和语言无关、也和cpu无关的中间代码，然后再生成各个cpu的汇编代码。可以理解为中间代码是一种非常抽象，又非常普适的代码。它客观中立的描述了代码要做的事情，如果用中文、英文来分别表示 C 和 Java 的话，中间码某种意义上可以被理解为世界语。
  • eg. 如gcc,
    • 语法树转高端gimple
      • 主要处理寄存器和栈，如c=a+b变成寄存器处理。
      • 函数调用则建栈
    • 高端gimple转低端gimple
      • 主要是把变量定义，语句执行和返回语句区分存储
        • 好处是容易计算一个函数需要多少栈空间
    • 低端gimple转中间代码
      • （略）

生成目标代码（生成汇编代码）

  • 主要的工作量在于兼容各种 CPU 以及填写模板。在最终生成的汇编代码中，不仅有汇编命令，也有一些对文件的说明。

汇编，生成二进制机器码

  • 把汇编代码转成 二进制的机器码，机器码可以直接被 CPU 识别并执行

  • 从目标代码可以猜出来，最终的目标文件(机器码)也是分段的，这主要有以下三个原因:

  1. 分段可以将数据和代码区分开。其中代码只读，数据可写，方便权限管理，避免指令被改写，提高安全性。
  2. 现代 CPU 一般有自己的数据缓存和指令缓存，区分存储有助于提高缓存命中率。
  3. 当多个进程同时运行时，他们的指令可以被共享，这样能节省内存。

对于一个目标文件来说，文件的最开头(也叫作 ELF 头)记录了目标文件的基本信息，程序入口地址，以及段表的位置，相当于是对文件的整体描述。接下来的重点是段表，它记录了每个段的段名，长度，偏移量。比较常用的段有:

  • .strtab 段: 字符串长度不定，分开存放浪费空间(因为需要内存对齐)，因此可以统一放到字符串表(也就是 .strtab 段)中进行管理。字符串之间用 \0 分割，所以凡是引用字符串的地方用一个数字就可以代表。
  • .symtab: 表示符号表。符号表统一管理所有符号，比如变量名，函数名。符号表可以理解为一个表格，每行都有符号名(数字)、符号类型和符号值(存储地址)
  • .rel 段: 它表示一系列重定位表。这个表主要在链接时用到，下面会详细解释。

编译 VS 解释

总结一下，对于 C 语言来说，从源码到运行结果大致上需要经历编译、汇编和链接三个步骤。编译器接收源代码，输出目标代码(也就是汇编代码)，汇编器接收汇编代码，输出由机器码组成的目标文件(二进制格式，.o 后缀)，最后链接器将各个目标文件链接起来，执行重定位，最终生成可执行文件。

解释型语言

  • 解释型语言：源代码 -> 解释器 -> 运行结果
  • 编译型语言：源代码 -> 中间代码 -> 目标代码 -> 运行结果

解释型语言和编译型语言的根本区别在于，对于用户来说，到底是直接从源码开始执行，还是从中间代码开始执行。以 C 语言为例，所有的可执行程序都是二进制文件。而对于传统意义的 Python 或者 JavaScript，用户并没有拿到中间代码，他们直接从源码开始执行。从这个角度来看， Java 不可能是解释型语言，虽然 Java 虚拟机会解释字节码，但是对于用户来说，他们是从编译好的 .class 文件开始执行，而非源代码。

解释程序和编译程序的根本区别：是否生成目标代码。有没有虚拟机，虚拟机是不是解释执行，会不会生成中间代码，这些都不重要，重要的是如果从中间代码开始执行，而且 AST 已经事先生成好，那就是编译型的语言。

运行时

运行时库的基本概念

以 C 语言为例，有非常多的操作最终都依赖于 glibc 这个动态链接库。包括但不限于字符串处理(strlen、strcpy)、信号处理、socket、线程、IO、动态内存分配(malloc)等等。这一点很好理解，如果回忆一下之前编译器的工作原理，我们会发现它仅仅是处理了语言的语法，比如变量定义，函数声明和调用等等。至于语言的功能， 比如内存管理，內建的类型，一些必要功能的实现等等。如果要对运行时库进行分类，大概有两类。一种是语言自身功能的实现，比如一些內建类型，内置的函数；另一种则是语言无关的基础功能，比如文件 IO，socket 等等。

由于每个程序都依赖于运行时库，这些库一般都是动态链接的，比如 C 语言的 (g)libc。这样一来，运行时库可以存储在操作系统中，节省内存占用空间和应用程序大小。

对于 Java 语言来说，它的垃圾回收功能，文件 IO 等都是在虚拟机中实现，并提供给 Java 层调用。从这个角度来看，虚拟机/解释器也可以被看做语言的运行时环境(库)。

链接和装入

链接

在一个目标文件中，不可能所有变量和函数都定义在文件内部。比如 strlen 函数就是一个被调用的外部函数，此时就需要把 main.o 这个目标文件和包含了 strlen 函数实现的目标文件链接起来。我们知道函数调用对应到汇编其实是 jump 指令，后面写上被调用函数的地址，但在生成 main.o 的过程中，strlen() 函数的地址并不知道，所以只能先用 0 来代替，直到最后链接时，才会修改成真实的地址。

链接器就是靠着重定位表来知道哪些地方需要被重定位的。每个可能存在重定位的段都会有对应的重定位表。在链接阶段，链接器会根据重定位表中，需要重定位的内容，去别的目标文件中找到地址并进行重定位。

链接是将多个目标文件（.o 文件）和库文件（.a / .so）合并为一个可执行文件的过程。

编译后是否已经完成链接，取决于链接方式

  • 静态链接：编译完成 = 链接完成，可独立运行
  • 动态链接：编译完成 ≠ 链接完成，运行时仍需加载 .so 库

装入（Loading）

装入是指操作系统将程序从磁盘加载到内存，并准备运行的过程。

装入的三种方式

  1. 绝对装入（Absolute Loading）
    • 代码只能装入到固定的内存地址（如嵌入式设备）
    • 缺点：不同机器或不同进程可能导致冲突
  2. 可重定位装入（Relocatable Loading）
    • 常见于现代操作系统，程序可装入任意空闲地址
    • 需要重定位表（Relocation Table），装入时修改地址引用
  3. 动态装入（Dynamic Loading）
    • 按需装入程序或库，如 dlopen() 方式
    • 常用于共享库、插件系统，如 Python 的 import 机制

Go 的编译、链接、装入概览

阶段作用执行者输出
编译（Compilation）源代码 → 汇编/机器码go build（调用 cmd/compile）.o 目标文件
链接（Linking）目标文件 + 库 → 可执行文件cmd/link可执行文件
装入（Loading）加载可执行文件到内存并执行OS Loader进程

编译步骤


go build -o myapp main.go

内部执行流程

  1. 词法分析（Lexical Analysis）：将 Go 代码转换为 Token。
  2. 语法分析（Parsing）：生成 AST（抽象语法树）。
  3. 类型检查（Type Checking）：检查变量、函数、结构体等是否正确。
  4. 优化（Optimization）：移除无用代码（dead code elimination）、内联（inlining）等。
  5. 代码生成（Code Generation）：生成中间代码（SSA）。
  6. 寄存器分配（Register Allocation）：为变量分配 CPU 寄存器。
  7. 机器码生成（Machine Code Generation）：最终生成 .o 目标文件。

中间文件


go build -gcflags="-m" main.go
  • -m 选项会显示编译优化情况。
  • 可以用 -S 选项查看 Go 生成的汇编代码。

QA

  • .o 文件包含机器码，不同架构（如 x86_64 vs. ARM）无法通用
  • .o 文件是 机器代码（Machine Code），但包含符号表和重定位信息，不能直接执行。
  • 汇编代码（.s） 是 人类可读的中间代码，需要汇编器转换成 .o 文件。
  • 在 Go 语言中，.a 文件是静态库（Archive Library），它包含已经编译好的 Go 代码（机器码），但尚未链接成最终的可执行文件。在 go build 过程中，Go 编译器会先编译 .go 源文件为 .o 目标文件，再将多个 .o 文件打包成 .a 静态库。最终，链接器（cmd/link）会将 .a 库与其他依赖合并，生成可执行文件。
文件类型内容能否执行作用
.o（目标文件）单个编译单元的机器码❌ 不能直接执行用于链接
.a（静态库）多个 .o 目标文件的集合❌ 不能直接执行提供复用的静态库
可执行文件完整的机器码✅ 可以执行运行程序

Go 默认静态链接

Go 默认使用 静态链接（Static Linking），不会依赖外部动态库（除非使用 CGO）。

静态链接过程

  1. 合并所有目标文件（.o）

  2. 链接 Go 标准库（runtime）

  3. 生成完整可执行文件

       
go build -o myapp main.go

    生成的

    myapp

    不依赖 任何外部库。

Go 的装入过程

（1）装入流程

当运行 ./myapp 时，OS 执行以下步骤：

  1. 加载 ELF 文件（Linux）或 Mach-O 文件（macOS）。
  2. 解析 Go 运行时（Go runtime）。
  3. 初始化全局变量。
  4. 调用 main.main() 并开始执行。

（2）Go 运行时（Runtime）

  • 垃圾回收（GC）：Go 运行时自带 GC，不依赖外部库。
  • goroutine 调度：Go 运行时管理协程调度，而非 OS 线程调度。
  • 系统调用（Syscall）：Go 通过 runtime 处理系统调用。

Search

    Table of Contents

    Popular Posts