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; \
- 1
- 2
前往页