UCC 内部实现
UCC内部实现 ..................................................................................................................................1
第一节 体系结构...............................................................................................................3
第二节 内存管理...............................................................................................................4
2.1 数据结构....................................................................................................................4
2.2 接口............................................................................................................................5
第三节 类型子系统...........................................................................................................5
3.1 数据结构....................................................................................................................5
3.2 接口............................................................................................................................7
第四节 词法分析...............................................................................................................7
4.1 输入处理....................................................................................................................8
4.2 接口............................................................................................................................8
4.3 标识符和字符串........................................................................................................8
第五节 语法分析...............................................................................................................8
5.1 数据结构....................................................................................................................9
5.2 C语言语法................................................................................................................10
第六节 语义分析.............................................................................................................11
6.1 break, case和continue语句 .......................................................................................11
6.2 标号..........................................................................................................................11
6.3 声明中的类型推导..................................................................................................12
6.4 变量初始化..............................................................................................................13
第七节 中间代码生成.....................................................................................................13
7.1 数据结构..................................................................................................................14
7.2 中间语言语法..........................................................................................................15
第八节 中间代码优化.....................................................................................................15
8.1 代数简化..................................................................................................................15
8.2 值-编号 ....................................................................................................................15
8.3 无用代码消除..........................................................................................................16
8.4 窥孔优化..................................................................................................................16
8.5 控制流简化..............................................................................................................16
第九节 目标代码生成.....................................................................................................16
9.1 指令模板..................................................................................................................16
9.2 寄存器分配..............................................................................................................17
9.3 调用规范..................................................................................................................17
ucc 是一个遵从 ANSI C 标准的 C 编译器，在 ucc 的设计和实现过程中，代码结构的清晰性，
可扩展性和效率被放在了同等重要的位置。本文档主要讲解 ucc 的实现，帮助开发者更好的
掌握源码。
第一节 体系结构
语
法
分
析
器
语
义
检
查
语
法
树
输
出
中
间
代
码
生
成
中
间
代
码
优
化
中
间
代
码
输
出
内存管理
类型子系统
符号表管理
目
标
代
码
生
成
词
法
分
析
器
图 1 ucc体系结构
对于一个给定的经过预处理的 C 程序，ucc 完成以下几个阶段的处理：
(1) 语法分析：语法分析和词法分析不是两个独立的阶段，在语法分析器的运行过程中，直
接调用词法分析器，语法分析的结果是生成语法树。
(2) 语义检查：语义检查直接对语法树进行操作，检查程序语义的正确性。
(3) 语法树输出：图中该阶段使用的是虚线，表明这是一个用户可选的功能。
(4) 中间代码生成：将语法树翻译成中间代码，ucc 使用三地址码。
(5) 中间代码优化：消除中间代码中不必要的部分或者冗余的计算等。
(6) 中间代码输出：与语法树输出一样，这也是一个用户可选的功能。
(7) 目标代码生成：生成目标平台的汇编码。
以上 7 个阶段需要依赖于几个基础模块，其中从下往上依次是内存管理，类型子系统和符号
表管理。以上的各个阶段和模块会在以下的章节中详细阐述。
下面按字母顺序列出每个 C 文件的功能：
alloc.c： 内存管理
ast.c ： 语法分析公用函数
decl.c： C语言声明语法分析
declchk.c： C语言声明语义检查
dumpast.c： 输出语法树
emit.c： 目标代码生成
error.c： 错误报告
expr.c： C语言表达式语法分析
flow.c： 中间代码控制流优化
fold.c： 常量折叠
gen.c： 中间代码生成
input.c： 输入处理
lex.c： 词法分析器
output.c： 文件输出
reg.c： 寄存器分配
simp.c： 中间代码简化
stmt.c： C语言语句语法分析
stmtchk.c： C语言语句语义检查
str.c： 字符串和标识符处理
symbol.c： 符号表
tranexpr.c： C语言表达式翻译
transtmt.c： C语言语句翻译
type.c： 类型子系统
ucl.c： 程序主入口点
uildasm.c： 中间代码输出
vector.c： 动态数组
x86.c： Linux 和 Windows 共有的汇编码生成
x86linux.c： Linux 平台汇编码生成
x86win32.c： Windows 平台汇编码生成
第二节 内存管理
内存管理对于一个编译器的高效运行是非常重要的，ucc 不是简单的使用 malloc 和 free 来完
成对内存的分配和释放。由编译器所分配的很多数据结构具有非常重要的一个特性，就是生
命期。比如说对于语法树，当释放根节点的时候，相应的子结点也要被释放。因此 ucc 采取
了一个基于堆的分配策略。堆是一个可以动态增长的内存块列表。不同于 free 操作，对于
堆的释放并不真的释放内存，系统中会维护一个空闲内存块列表，当释放堆时，就将堆中的
所有内存块放入空闲内存块列表中。
2.1 数据结构
struct mblock
{
struct mblock *next;
char *begin;
char *avail;
char *end;
};
每一个内存块的头部是一个 mblock 结构，它用以描述一个内存块，ucc 在分配内存时，会
预先分配较大的内存块以满足后续的内存分配需求。
z next： 指向堆中下一个内存块的指针
z begin： 内存块的起始
z end： 内存块的结束
z avail： 当前可用的内存
typedef struct heap
{
struct mblock *last;
struct mblock head;
} *Heap;
heap 用以描述一个堆。
z last： 指向堆中最后一个内存块
z head： 内存块列表的头部。
2.2 接口
void InitHeap(Heap hp)
初始化堆的内存块列表为空列表。
void* HeapAllocate(Heap hp, int size)
从堆中分配 size 大小的内存，如果堆中最后一个内存块不能满足要求，则从空闲内存块列
表中寻找一个能满足要求的内存块，如果找不到，则分配一个新的内存块。
void FreeHeap(Heap hp)
将堆中所有的内存块回收到空闲内存块列表 FreeBlocks
第三节 类型子系统
C 语言是一个强类型语言，类型子系统实现了 C 语言的所有类型相关操作。
3.1 数据结构
#define TYPE_COMMON \
int categ : 8; \
int qual : 8; \
int align: 16; \
int size; \
