作为一个起点，你可以将“程序的形式”简单理解为“程序文件的格式”。例如，将以下代码保存为 ret0.c 文件，然后使用 clang ret0.c -o ret0.exe 编译它：
int main() {
return 0;
}现在，你的电脑（不管是 Linux 还是 Windows）里有了两个文件：ret0.c 和 ret0.exe。尽管人们通常意义上只会把 ret0.exe 当作程序，但你不能否认 ret0.c 其实也是一个程序文件，只不过它不能由你的操作系统直接运行而已。换言之，运行 ret0.c 的方式就是“先编译，再运行”。
到这里就已经出现了两种程序格式了：源代码文件和可执行文件。前者同时也是一个文本文件，它的内容就是上面的代码；后者则更加神秘一些，你一般不会关注它的内容，但有一些方法可以让你查看它。
在 Linux 等类 UNIX 操作系统上，可执行文件格式被命名为“可执行与可链接格式”（ELF，Executable and Linkable Format）；Windows 采用的格式与之不同，并被称为“可执行可链接格式”（PE，Portable Executable）。
这里我们以 Linux 的 ELF 格式为例，给你建立一个对可执行文件的感性认知：
你可以看到，ELF 文件的结构是非常复杂的，而且都直接基于位与字节来定义。实践中，我们可以使用 readelf 命令来查看一个 ELF 文件的结构，例如 readelf -s ret0.exe 会输出程序里所有的符号：
Symbol table '.dynsym' contains 6 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FUNC GLOBAL DEFAULT UND _[...]@GLIBC_2.34 (2)
2: 0000000000000000 0 NOTYPE WEAK DEFAULT UND _ITM_deregisterT[...]
3: 0000000000000000 0 NOTYPE WEAK DEFAULT UND __gmon_start__
4: 0000000000000000 0 NOTYPE WEAK DEFAULT UND _ITM_registerTMC[...]
5: 0000000000000000 0 FUNC WEAK DEFAULT UND [...]@GLIBC_2.2.5 (3)
Symbol table '.symtab' contains 35 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 FILE LOCAL DEFAULT ABS Scrt1.o
2: 000000000000037c 32 OBJECT LOCAL DEFAULT 4 __abi_tag
3: 0000000000000000 0 FILE LOCAL DEFAULT ABS crtstuff.c
4: 0000000000001070 0 FUNC LOCAL DEFAULT 14 deregister_tm_clones
5: 00000000000010a0 0 FUNC LOCAL DEFAULT 14 register_tm_clones
6: 00000000000010e0 0 FUNC LOCAL DEFAULT 14 __do_global_dtors_aux
7: 0000000000004028 1 OBJECT LOCAL DEFAULT 25 completed.0
8: 0000000000003e20 0 OBJECT LOCAL DEFAULT 20 __do_global_dtor[...]
9: 0000000000001120 0 FUNC LOCAL DEFAULT 14 frame_dummy
10: 0000000000003e18 0 OBJECT LOCAL DEFAULT 19 __frame_dummy_in[...]
11: 0000000000000000 0 FILE LOCAL DEFAULT ABS ret0.c
12: 0000000000000000 0 FILE LOCAL DEFAULT ABS crtstuff.c
13: 00000000000020c0 0 OBJECT LOCAL DEFAULT 18 __FRAME_END__
14: 0000000000000000 0 FILE LOCAL DEFAULT ABS
15: 0000000000003e28 0 OBJECT LOCAL DEFAULT 21 _DYNAMIC
16: 0000000000002004 0 NOTYPE LOCAL DEFAULT 17 __GNU_EH_FRAME_HDR
17: 0000000000004000 0 OBJECT LOCAL DEFAULT 23 _GLOBAL_OFFSET_TABLE_
18: 0000000000000000 0 FUNC GLOBAL DEFAULT UND __libc_start_mai[...]
19: 0000000000000000 0 NOTYPE WEAK DEFAULT UND _ITM_deregisterT[...]
20: 0000000000004018 0 NOTYPE WEAK DEFAULT 24 data_start
21: 0000000000004028 0 NOTYPE GLOBAL DEFAULT 24 _edata
22: 0000000000001140 0 FUNC GLOBAL HIDDEN 15 _fini
23: 0000000000004018 0 NOTYPE GLOBAL DEFAULT 24 __data_start
24: 0000000000000000 0 NOTYPE WEAK DEFAULT UND __gmon_start__
25: 0000000000004020 0 OBJECT GLOBAL HIDDEN 24 __dso_handle
26: 0000000000002000 4 OBJECT GLOBAL DEFAULT 16 _IO_stdin_used
27: 0000000000004030 0 NOTYPE GLOBAL DEFAULT 25 _end
28: 0000000000001040 38 FUNC GLOBAL DEFAULT 14 _start
29: 0000000000004028 0 NOTYPE GLOBAL DEFAULT 25 __bss_start
30: 0000000000001130 15 FUNC GLOBAL DEFAULT 14 main
31: 0000000000004028 0 OBJECT GLOBAL HIDDEN 24 __TMC_END__
32: 0000000000000000 0 NOTYPE WEAK DEFAULT UND _ITM_registerTMC[...]
33: 0000000000000000 0 FUNC WEAK DEFAULT UND __cxa_finalize@G[...]
34: 0000000000001000 0 FUNC GLOBAL HIDDEN 11 _init
你可以看到我们源代码里的 main 函数就出现在 .symtab 的第 30 项。本次实验的并不要求你实现 ELF 文件或者 PE 文件的生成，这已经超出了编译技术的核心内容，显得过于具体和琐碎，因此我不会在这里进一步对 ELF 文件格式作出更多阐释了。
另一方面，你可能会“错误地”认为 ret0.c 的文件格式比 ret0.exe 简单得多。如果你把 ret0.c 的内容看作寻常的文本文件，那么确实如此；然而，要明白，不是所有的文件文件都能通过 Clang 的编译，生成一个可执行文件的：如果将这些限制都考虑在内，那么源代码文件其实并不比可执行文件更简单。
源代码到这两种可执行文件格式通常被认为是编译的起点和终点。现在，再让我们来看看这个过程中的所有可能程序形式。
源代码是文本文件，文本文件是由字符组成的序列。编译器的词法分析将这个字符序列切分、组合为一个个词法单元，这时的程序形式就是一个词法单元序列。你可以使用 clang -cc1 -dump-tokens ret0.c 来查看编译器在词法分析阶段生成的词法单元流：
int 'int' [StartOfLine] Loc=<ret0.c:1:1>
identifier 'main' [LeadingSpace] Loc=<ret0.c:1:5>
l_paren '(' Loc=<ret0.c:1:9>
r_paren ')' Loc=<ret0.c:1:10>
l_brace '{' [LeadingSpace] Loc=<ret0.c:1:12>
return 'return' [StartOfLine] [LeadingSpace] Loc=<ret0.c:2:5>
numeric_constant '0' [LeadingSpace] Loc=<ret0.c:2:12>
semi ';' Loc=<ret0.c:2:13>
r_brace '}' [StartOfLine] Loc=<ret0.c:3:1>
eof '' Loc=<ret0.c:3:2>
每个词法单元以一行来表示，可以看到，这个输出要比源代码长得多，但却更规整。它将那些含义相近的字符组合在一起，形成了一个个词法单元，例如 return 原本是一个由 r e t u r n 六个字符组成的字符串，但在词法分析阶段，它被组合为单个 return 关键字，并在一行打印出来；{ 只有一个字符，但它也被识别为一个独立的词法单元，表明它和 return 同样地重要，而不论其长度。
简单的工作到这里就结束了，接下来的程序形式都要复杂得多。
词法分析后是语法分析，在这个环节，程序会被转换为一种树形结构。你可以使用 clang -cc1 -ast-dump ret0.c 来查看编译器在语法分析阶段生成的语法树：
TranslationUnitDecl 0x1a7b408 <<invalid sloc>> <invalid sloc>
| <<<此处省略一些无关输出>>>
`-FunctionDecl 0x1ae0e10 <ret0.c:1:1, line:3:1> line:1:5 main 'int ()'
`-CompoundStmt 0x1ae0f28 <col:12, line:3:1>
`-ReturnStmt 0x1ae0f18 <line:2:5, col:12>
`-IntegerLiteral 0x1ae0ef8 <col:12> 'int' 0
一些无关的输出被隐藏了，你可以看到，语法树的结构是一种树形结构，它的根节点是 TranslationUnitDecl，表示整个翻译单元；根节点里面有一个 FunctionDecl，表示一个函数，名字叫 main，类型为 int ()；函数里面有一个 CompoundStmt，表示一个复合语句；复合语句里面是一个 ReturnStmt，表示一个返回语句；返回什么呢？一个 IntegerLiteral，整数字面量，它的值是 0。
我们的实验要求学生以 JSON 格式输出语法树并进行评测，即 clang -cc1 -ast-dump=json ret0.c：
{
"id": "0xeb3408",
"kind": "TranslationUnitDecl",
"loc": {},
"range": {
"begin": {},
"end": {}
},
"inner": [
// 此处省略一些无关输出
{
"id": "0xf18e10",
"kind": "FunctionDecl",
"loc": {
"offset": 4,
"file": "ret0.c",
"line": 1,
"col": 5,
"tokLen": 4
},
"range": {
"begin": {
"offset": 0,
"col": 1,
"tokLen": 3
},
"end": {
"offset": 27,
"line": 3,
"col": 1,
"tokLen": 1
}
},
"name": "main",
"mangledName": "main",
"type": {
"qualType": "int ()"
},
"inner": [
{
"id": "0xf18f28",
"kind": "CompoundStmt",
"range": {
"begin": {
"offset": 11,
"line": 1,
"col": 12,
"tokLen": 1
},
"end": {
"offset": 27,
"line": 3,
"col": 1,
"tokLen": 1
}
},
"inner": [
{
"id": "0xf18f18",
"kind": "ReturnStmt",
"range": {
"begin": {
"offset": 17,
"line": 2,
"col": 5,
"tokLen": 6
},
"end": {
"offset": 24,
"col": 12,
"tokLen": 1
}
},
"inner": [
{
"id": "0xf18ef8",
"kind": "IntegerLiteral",
"range": {
"begin": {
"offset": 24,
"col": 12,
"tokLen": 1
},
"end": {
"offset": 24,
"col": 12,
"tokLen": 1
}
},
"type": {
"qualType": "int"
},
"valueCategory": "prvalue",
"value": "0"
}
]
}
]
}
]
}
]
}这个 JSON 格式的语法树和前面的文本输出是等价的，只是它更加结构化，更加容易处理。
必须讲清楚的是，虽然表达完全相同的含义，但文本和 JSON 是不同的程序形式。编译就是要在形式之间转换，区分不同的形式十分必要，而绝不能搅浑水。
此前，我们介绍的所有程序形式都是以文件的方式存在的，它们可以存储在硬盘（外存）上或者打印到终端上。但在目前的计算机体系结构中，执行编译程序的 CPU 并不是直接操作硬盘中的数据，而是先将数据加载到内存中，然后在处理好之后再写回硬盘。由于编译程序执行一会就终止了，所以在内存中的程序形式是暂态的，因而极其容易被大家忽略，但它对于编译器开发人员而言却是至关重要的。
那么，程序应该怎么在内存中表示呢？是类似源码的字符串、类似词法单元的序列、JSON、还是什么其它东西？答案是，全都有。由于外存中的数据都是在内存中操作的，所以有一种外存形式，就一定至少有一种内存形式。
为什么要有这么多形式？原因很简单，不同形式有不同的约束，适合不同的操作，比如文本形式就支持单个字符的插入和删除，而 JSON 形式则支持树的遍历和修改。
在所有这些内存形式中，最重要的就是抽象语法树（Abstract Syntax Tree，AST），或者，我更愿称之为抽象语义图（Abstract Semantic Graph，ASG）。这是一种对源语言语法/语义结构的抽象，方便我们在语法/语义的层面对代码进行操作，例如“替换掉一个表达式”、“在一个函数调用前插入一个语句”等等。
AST/ASG 的设计是整个编译器前端设计的核心，也是我此前《实验攻略》的首要内容。一个好的 AST/ASG 设计可以大大简化编译器代码的编写，提高编译器的可维护性和可扩展性。
AST/ASG 的设计是一个很大的话题，我会在后续的文档中详细介绍，在这里你只需要记住它非常重要。
在本实验中，学生需要完成从源代码出发，将 C 语言（的子集）翻译为等价的 LLVM IR，这是一个完整的编译器前端实现工作，之后的 ELF 文件生成等则交由 LLVM 框架来做。
与其说 LLVM IR 是一种适合编程操作与编译优化的程序形式，不如说 LLVM IR 就是为编程而设计的编程语言（这里是它的语言参考手册）。LLVM IR 介于源代码和机器码之间，它与两者都有点相似，但都有很大不同，我们相信选择这样一种形式作为实验的最终目标足以在展示编译技术的核心内容，同时避免底层特定于机器的、过于琐碎的细节。
值得一提的是 LLVM IR 实际上有三种形式：文本形式（.ll文件）、二进制形式（.bc文件）和内存形式。在完成本实验后，学生至少会入门其中的文本形式和内存形式。
在设计上，本实验全流程所涉及到的程序形式变换可以用下图来表示：
flowchart LR
A[源代码]
.->|task0| B[预处理后\n的源代码]
-->|task1| C[词法单元\n序列]
-->|task2| D[AST/ASG]
.-> E[Clang的\nJSON语法树]
.-> F[AST/ASG]
-->|task3| G[LLVM IR]
-->|task4| H[优化的\nLLVM IR]
.-> I[可执行文件\nELF/PE]
图中虚线部分由框架实现，实线部分需要学生自行完成（框架提供基础代码，学生完成补全工作）。