# myCompiler **Repository Path**: sduwmj/my-compiler ## Basic Information - **Project Name**: myCompiler - **Description**: 模仿chibicc制作一个简单的玩具编译器，源语言为C，目标语言为汇编语言 - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 2 - **Forks**: 0 - **Created**: 2025-10-31 - **Last Updated**: 2025-11-30 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # myCompiler ## 介绍 模仿chibicc制作一个简单的玩具编译器，源语言为C，目标语言为汇编语言。 本项目是用C语言编写的，从最简单的编译一个数字开始，逐步模拟C语言的编译。因此这是一个自我托管的编译器。 这个项目的目的是促进开发者本人对编译原理的学习。 ## 安装教程 在Ubuntu 22.04 -LTS x86背景下，确保编译工具链完整并有正确的makefile。 直接使用make指令编译源代码，将会得到编译器的可执行文件，其路径为./compiler，这个可执行文件就是本项目所编写的编译器。 本项目有测试脚本，用户可以在测试脚本中测试编译结果是否正确 ## C语言编译器开发学习笔记 这里附上在开发项目过程中，开发者学习到的各种知识 ### 基础准备 熟悉这个编译器的工作流程。本编译器的源语言为C语言，目标语言为汇编语言。 在测试脚本中用断言assert来测试编译结果。参数（为一个字符串，内容为一个语句）给出后，编译器编译得到的汇编程序写入tmp.s这个汇编文件中。然后根据汇编文件生成可执行文件。最终得到运行结果。 ### 编译原理相关知识 主要介绍语法分析和代码生成的内容，学会将构建好的token流构造成一棵正确的AST，然后根据AST做语义分析和中间代码生成。 我们这里先不考虑代码优化，只考虑简单的语法解析和代码生成。 #### AST 如果表达式中只有加法和减法或者其他优先级相同的运算符，那么其实可以将这个表达式做线性处理，而不需要按照层次结构做处理。 但是实际上的表达式往往包含了多种优先级不同的运算符，这时候就不能简单地做线性处理了。因此就需要使用表达式的语法描述和语法分析，来为表达式构建一个可以被计算机正确理解和执行的数据结构。 在编程语言的解析（也就是语法分析 parse）器实现中，输入通常是一个扁平的token序列，而输出是表示嵌套结构的树（AST，抽象语法树） AST是一棵能够正确反映表达式语法结构，由token节点组成的树状结构。 对于表达式，一般具有多种优先级，因此使用树状结构表示是比较自然的事情。而对于函数这种顺序执行指令的结构，则使用线性结构表示比较好，可以用一个节点表示函数，节点内部包含函数的执行序列。 #### 生成规则文法 编程语言的语法是使用生成规则定义的，而生成规则实际上是递归定义语法的规则。 可以这样理解生成文法： 1. 一个句子可以按照某种规则由多个不同的成分构成 2. 每个成分又可以按照自己的规则，由不同成分构成 3. 如此递归下去，组成了规则集合。按照这个规则集合，对每个层次的成分做生成，最终可以形成若干个句子 #### BNF范式 我们使用BNF范式描述文法规则。 每一个文法规则可以区分出两种类型的符号：终结符和非终结符 1. 终结符是指不能被进一步拆分的符号 2. 非终结符是指可以按照文法规则进一步拆分的符号 非终结符可以匹配多种文法规则，生成多种结果。 文法规则的右端可以是空字符串，用epsilon表示。 字符串要用双引号表示，终结符一般用字符串表示。 在BNF中引入一些可以表示复杂文法规则的简单符号，就形成了EBNF。EBNF常用的表示如表格所示： | 符号 | 含义 | | ---- | ----------------- | | () | 为符号分组 | | A* | 表示零个或者多个A | | A\|B | A或者B | | A？ | A或者空串 | **本项目用到的简单文法示例**： expr -> mul ( "+" mul | "-" mul )* mul -> primary ( "\*" primary | "/" primary )\* primary -> num | "(" expr ")" #### 递归下降语法分析 递归下降语法分析的基本策略是将生成文法规则中的非终结符映射成函数。 将单个生成规则映射到单个函数的语法分析技术称为"递归下降语法解析"。 运算符左结合的意思是当前节点的左侧分支更深一些，也就是把符号放在当前节点的左子树上。 在处理字符流序列时，我们预先处理一个序列元素，根据这个元素选择要调用的函数。这种每次处理只预读一个序列元素的方法是LL(1)文法 #### 如何实现递归下降语法分析？ 当然是借助系统栈，只需要递归地处理抽象语法树，将终结符（目前只可能是数字）压栈，回溯的时候按照父节点类型（四则运算）做操作即可。递归处理AST的顺序为： 1. 递归处理左子树，如果左子树非空 2. 递归处理右子树，如果右子树非空 3. 回溯父节点，从第一部开始重复，知道节点全部处理完毕 递归处理左右子树时，得到的结果会依次压栈，操作符可以根据栈中的元素做相应运算。 在X86-64指令集下实现递归下降语法分析，可以如是安排指令顺序： 1. 如果当前节点是数字，就压栈 2. 依次递归处理左子树和右子树 3. 依次将栈顶元素弹出到rdi和rax两个寄存器 4. 根据节点指示的运算类型计算结果（采取对应的运算指令） 5. 将运算结果压入栈中。 ### 汇编基础知识 由C语言翻译成的汇编语言，同样存在函数的概念。函数是一个由标签指向的汇编指令序列。在汇编语言的开端，将会为各个函数指定作用域。我们用一段简单的C语言程序及其对应的汇编程序来解释汇编语言 C语言程序如下： ```c int add(int a,int b){ return a+b; } int main(){ return add(3,4); } ``` 这段程序中，main函数以参数3和4调用了一个全局函数add，实现了3和4相加的逻辑。 对应的汇编程序如下： ``` .globl add,main add: add %rsi,%rdi mov %rax,%rsi ret main: mov %rdi,3 mov %rsi,4 call add ret ``` 这段汇编程序反应了汇编指令，一般情况下汇编程序做什么，以及汇编程序中函数是什么样子的。 #### 汇编指令 汇编指令有运算指令，访存指令，跳转指令和访寄存器指令。这段汇编程序中的add指令是运算指令，mov指令是寄存器指令（也是访存指令），call是函数调用指令，ret则是返回指令。我们详细介绍一下这几类指令 上面展现的指令除了call和ret之外都是两操作数的，前一个操作数叫做目的操作数，后一个叫做源操作数，操作数可以是寄存器也可以是内存。 **访存（寄存器）指令**，以mov a,b为例，这条指令的意思是将b中的值存入a中，也就是说项目环境下的汇编指令是从右到左的执行顺序。 类似的访存指令和访寄存器指令还有load和store指令。load指令是将指定内存位置的内容取出来，装进指定的寄存器。store指令则是将内容存进指定的内存位置。 **运算指令**：比如add a,b，这条指令的意思是将a中的数和b中的数相加，结果放在a中，一般指定a和b是寄存器。 **堆栈指令**：即pop指令和push指令。 1. 在x86-64指令集中，push指令没有参数，隐式地将rax寄存器中的内容存放在栈中，然后向下移动栈指针寄存器，因此需要汇编程序员提前将内容mov/load进寄存器rax中。有的版本push指令有参数，参数是一个寄存器 2. pop指令则需要指定栈顶元素存放在哪里，一般是存放在指定的寄存器中。 **call指令**：可以根据给定的名字，调用对应的函数。需要先将当前函数的位置保存在栈中，然后跳转到参数所指定的位置。 **ret指令**：类似于return，先从栈中弹出调用函数时压入栈中的地址，然后根据这个地址跳转回调用者。 #### 汇编语言中的函数 观感上，汇编语言的函数与C语言中的函数相近：有一个标签，指示了一定范围，这个范围内有一系列按序执行的汇编指令。 在汇编程序最顶部，需要指定这个程序所遵循的格式，然后声明各个标签的“作用域”，比如上面程序中add函数和main函数都是global域的，即这两个函数全局可见。 函数栈帧分配和局部变量分配，以及很重要的内存对齐，在后面支持编译函数与函数调用时再介绍。 ### C基础知识 此前没有C语言的开发经验，这次开发学到了不少C的系统编程知识。基本上都是些以前没用过的函数。 比较内存区域的方法： ``` int memcmp(const char* p1,const char* p2,size_t n); p1和p2分别指定两块内存区域的指针，同时也是这两块区域的首地址 n表示从首地址开始要比对的字节数 ``` 字符串-数字相关方法 ``` long long int strtol(const char* str,char **endptr,int base) 处理字符串时会根据指定的基数（进制）来解析数值，并返回转换后的长整型数值。如果字符串中包含无法转换为数字的字符，strtoll 会停止转换并返回已转换的部分数值。位置用endptr给定 unsigned long int strtoul(const char* str,char** endptr,int base) 给定一个字符串，根据给定base做无符号长整数转换。转换过程中会更新指针endptr，最后的endptr会指向非数字的第一个字符 ``` C语言中的布尔类型需要引包#`include` #### 自定义异常处理 这个项目的异常处理要求有，可以接受格式语句和可变参数。 使用C语言的可变列表方法做异常处理。使用可变列表接收参数，然后打印到标准错误流中，最后退出程序 ```c //异常处理，处理可变参数 static void error(char* fmt,...) { va_list ap; va_start(ap,fmt); vfprintf(stderr,fmt,ap); fprintf(stderr, "\n"); exit(1); } ``` ### 词法分析 词法分析实际上是一个扫描字符串的过程。将程序字符流输入给词法分析器，词法分析器将原来语句中的每个词语翻译为词素，词素的组成如下： ``` ``` 词法分析器的输出为翻译后的词素组成的字符流。 需要为词法分析器设计token类型，在C语言中可以用枚举来设计。 ``` typedef enum{ ... }TokenKind ``` 需要为词法分析器涉及一个token结构体，最终输出的字符流是token结构体组成的链表。token结构体需要具备如下成员： ``` typedef struct Token Token; struct Token{ TokenKind kind;//token类型 Token *next;//指针域 int val;//token为数字时，需要有一个值 char *loc;//token所在的内存位置 int len;//token的长度 } ``` 词法分析的步骤，用文字表示 ``` 1, 构建一个空的token列表head{} 2. 用一个token指针指向列表头cur=head->next 3. 开始扫描字符串 3.1 对每一个扫描到的元素做分支判断，判断条件是匹配一种token类型 3.2 对每一个匹配的元素，使用token构造方法构造相应类型的token 3.3 更新字符串指针， 3.1' 如果没有匹配到就报错 4. 返回token列表 head->next ``` ### 语法分析 引入乘除法之后，简单的线性token流无法满足需要。由于乘除法和加减法具有不同的优先级，优先级越高与数字（在算术表达式中，数字是终结符）越接近，并且计算机处理运算时相当于一个递归层次，我们引入AST（抽象语法树）来表示一个语句。 四则运算和括号的文法为： ``` expr->expr+mul|expr-mul|mul mul->mul*primary|mul/primary|primary primary->(expr)|num ``` `expr`为含有加减法的表达式，`mul`表示含有乘除法的表达式，primary则是基本运算包含括号和新的`expr` 我们发现这个文法的前两个产生式是左递归的，需要运用公式消除左递归如下： ``` expr->mul(+mul|-mul)expr' mul->primary(*primary|/primary)mul' ``` 由于选择了最左推导，在创建新的AST节点时，左子树为当前节点，右子树为新推导的产生式 #### 一元运算符 一元运算符（一元加和一元减）是右结合的，优先级高于乘除法和加减法 对文法规则的改变是： 1. 加入unary层级 2. 改造mul层级对下一层级的调用 改造后的文法为： ``` expr->mul(+mul|-mul)expr' mul->unary(*unary|/unary)mul' unary->(+|-)unary primary->(expr)|num ``` 根据文法设计的语法分析，可以自然的编译多个连续一元运算的特殊情况。 #### 关系运算符 关系运算符是双目运算符，因此作为节点应当有两个子节点。本项目只添加了等于、不等于、小于和小于等于。大于等于和大于可以通过改变小于和小于等于运算中两个数的位置，即让小于和小于等于的左右子树调换来实现。 关系运算符的运算优先级低于加减运算，即需要将左右两个子树的值计算完成以后才能进行比较。引入关系运算符后的文法表示如下（已经消除左递归）： ``` expr->equality equality->relational(==relational|!=relational)equality* relational->add(add|>=add)relational* add->mul(+mul|-mul)add* 后续未改变 ``` 需要注意关系运算符相关的汇编指令 1. sete：判断两个数是否相等 2. setne：判断两个数是否不相同 3. setl：判断左边是否小于右边 4. setle：判断左边是否小于等于右边 上面四条指令都是针对寄存器的标志位的 **汇编视角下**：需要先用cmp指令比较两个寄存器的内容，将比较结果放在rax寄存器中。执行上面四条指令之一改变ZF标志位，存放在al寄存器中。然后将al的标志位移动到rax寄存器中，作为输出结果 #### 分号 C语言中每个语句都要以分号结束。为了模拟C语言编译，本项目有如下考虑为： 1. 我们将项目拆分为词法分析、语法分析和代码生成三部分。语法分析的结果将以parse方法的返回值形式返回给main函数。这样就需要一个调用的起点，我们用stmt方法为构造AST的起点，便于我们后面调用语法分析功能。 2. stmt调用的下一层级为expr-stmt，这个层级负责分析作为整体的语句。C语言中每个语句都以分号结束，因此本层级的文法为：expr-stmt -> expr";" 3. 本项目将分号视作一个单目运算符，头文件中将语句stmt作为一个节点定义。stmt的左子树是表达式expr，右子树是分号";" 4. 后面的层级文法构造不变。 ### 真正的语句 C语言中的真正语句应当包括一个变量（左值）、赋值号=、右值表达式，形如 ``` var = stmt; ``` 因此需要为AST添加赋值号和变量节点。 1. 赋值号节点的左子树应当是一个左值（变量），右子树是一个表达式。在处理赋值号节点时，用到了后序遍历AST生成代码时的非递归栈模拟递归的思路：即先处理右子树，将右子树的值压入栈保存，然后处理左子树。处理过程中使用到rdi和rax两个寄存器 2. 变量节点由于变量是一个终结符，所以变量没有子树 由于增加了终结符变量（暂时将变量名定为只有一个字符），需要修改文法中直接与终结符打交道的primary层级，修改比较简单就不再展示 此外重要的是，我们这里涉及到了函数调用。在函数调用时，需要先为保存函数栈帧的基指针，然后为函数调用所需要的可能的局部变量开辟空间。函数栈帧底部位置存放在基指针寄存器rbp中，在调用函数时需要保存这个寄存器的内容以便于函数体执行完毕后继续执行下面的内容。 涉及到的汇编语句是 ``` push %rbp move %rsp,%rbp sub [局部变量空间大小],%rsp 执行函数体结束后，恢复环境 mov %rbp,%rsp pop %rbp ``` #### 变量名、偏移量和函数栈帧大小 变量名以字母或者下划线开头，非首字母除此之外可以包含数字 偏移量是指变量与基指针寄存器指定值的偏移值 函数栈帧大小则是局部变量偏移量之和对其之后的数值 C语言在内存中存放变量时，遵循边界对齐的原则：边界对齐要求每个变量的地址紧邻，并且首地址要能够整除align 实现边界对齐的编码是： ``` (n+align-1)/align*align n为原来的值，align为基数，一般为n所属变量类型的大小 这样设计避免了浮点运算，同时实现了向上对齐 ``` #### 关键字 在词法分析时，关键字与变量标识符都被认为是一个字符串。在生成词素序列之后，再将本应该是关键字的词素类型改正为关键字 在构建文法时，第一次添加的关键字return是最后被处理的，修改文法如下： ``` 最开始的层级stmt->return expr;|expr_stmt ``` 增加关键字的通用流程为： 1. 在词法分析的关键字列表中增加关键字（可能还有辅助函数） 2. 在语法分析对应的产生式中增加这个关键字的语法分析。一般是在stmt层级，因为关键字一般都是最后执行的 3. 在代码生成部分的gen_stmt函数中增加关键字的汇编打印 #### 函数体block 函数体block即大括号{}，标定了一段函数。 每一句语句都是定义在函数体block之内的，具有自己的局部变量、AST和词素序列 将函数体block作为一个层级，改造文法，增加了compound_stmt层级，即复合语句。改造文法如下： ``` stmt={compound_stmt compound_stmt=stmt*} ``` 函数体语法分析和词法分析都在对应的compound_stmt层级里实现。 #### 空语句 C语言支持支持空语句，允许一个语句直接以分号结束 上面我们定义函数体时，在函数体compound_stmt层级中创建AST节点时，实际上是创建一个语句列表，将每条语句逐个创建节点，然后加入到语句列表中。 如果没有语句的话就会直接结束，返回一个空列表。这样就是空语句，直接进入到分号终结符。 #### if-else分支结构 主要描述if-else分支结构的控制流： 0. 生成唯一标签 1. 计算cond的expr，结果存放在寄存器rax中 2. 将rax中的值与0作比较，等于0就错，不不等于0就真 3. 根据第二步的结果跳转 1. 如果第二步为假，跳转到else 2. 如果第二步为真，就继续执行语句 4. 如果else分支语句不为空，就执行else分支语句 5. 结束 控制流的第零步是考虑到可能会有嵌套if-else结构，为了防止混乱，需要为每一个if分支结构分配唯一标识符 if-else结构的文法比较简单，直接把if-else的常见形式转译即可 说明一下实现if-else结构需要用到的汇编语句 ``` printf(" cmp $0,%%rax\n"); //将if中expr的计算结果与0作比较，如果结果为0就是假，反之则为真 printf(" je .L.else.%d\n", c); // 条件为假时跳转到else分支 printf(" jmp .L.end.%d\n", c); // 跳过else分支 printf(".L.else.%d:\n", c); // else分支标签 ``` #### for结构 for结构的控制流很简单。for结构包含初始化、条件和变量自增三条语句，不过这些语句都是可选的。for结构的控制流如下所示： 1. 执行初始化语句 2. 开始循环 3. 执行条件语句，如果有的话 1. 如果结果为真，就继续执行循环体 2. 如果结果为假，就跳出循环 4. 执行自增语句，如果有的话 5. 退出循环 for循环结构的文法也很简单。注意for括号里的语句都是可以不写的，直接用分号表示这是空语句 ``` for ( expr_stmt expr? ; expr? ) stmt ``` #### while结构 while结构和for结构非常相像。它们的区别在于while循环一定没有初始化语句。我们考虑将while和for合并为一个AST节点，并且共用编译器 while循环的实现比较简单，这里就不再赘述 #### 解引用和取地址 众所周知C语言支持指针。这里增加了本项目对解引用运算符和取地址运算符的支持。用这两个单目运算符可以创建指针变量和引用变量。 取地址运算符&，直接返回变量的绝对地址。 解引用运算符*，将变量所指的地址中存放的东西返回。 指针的算术运算：指针算术运算需要重载为指针向下一个位置移动，即将ptr+数字重载为ptr+数字*sizeof(变量) 指针算术运算分为加法和减法，而这两种情况并不完全相同，两种运算的相通之处在于： 1. 指针加/减数字：即将指针向下移动数字个单位，如果指针不在左操作数位置上，需要调换位置 2. 数字加/减数字：这种运算不需要重载 对于左操作数和右操作数都是指针的情况，加法和减法的处理有所不同： 1. 加法：这种运算是非法的 2. 减法：会将从左指针到右指针这个范围内的元素数量返回 #### 变量声明 C语言变量声明形式如： ``` Type varName (= expr) ; ``` 因此变量声明的检查需要分为两部分 1. 检查声明类型 2. 处理 varName(=expr)这个语句。如果是赋值语句的话，需要处理赋值语句 **检查声明类型** 1. 解析基础类型，即不包括指针和引用的基础类型 2. 处理特殊类型，即处理指针、引用等。 在检查声明类型时，强制要求程序给出变量名。 处理特殊类型时候，可以递归处理指针类型。 **处理语句** 首先解析基础类型，即解析最基本的声明。如int、double。这同时也强制要求程序给出声明符 然后准备开始构造节点，构造头节点，节点链表。 在处理声明语句时，需要注意C语言支持同一条语句可以声明多个变量，变量用逗号隔开。 在处理声明语句时，首先获得声明的类型，然后根据类型创建左值变量 赋值语句的节点类型是ND_ASSIGN，它的左子树是左值变量，右子树是赋值语句 声明语句节点则实际上是一个语句体类型节点，包含了上面过程构建的节点列表 **修改文法** 复合语句可能产生stmt层级，也可能产生声明层级。 #### 函数调用 函数调用需要有如下步骤： 1. 调用方保存参数 2. 调用方保存返回地址 3. 开辟栈帧，分配空间 4. 进入被调用函数，执行被调用函数 5. 调用函数将返回结果保存 6. 根据返回地址恢复调用方现场 在编译时，我们将函数调用作为一个AST节点考察，在代码生成阶段，会根据函数调用节点类型生成对应的汇编语句 函数调用需要提供函数名，因此在node中增加function_name这个字段 函数调用需要提供参数，参数一般是一个基本表达式，因此我们需要在primary这个层级上修改文法。 由于函数调用实际上是用一个标识符去调用，如何与普通标识符做区分呢，我们考察函数名的下一个token，如果下一个token是左括号(，那么下面将要编译的就是一个函数体。 **如何提供参数** 我们需要为函数调用增加一个文法层级，专门处理参数列表。 参数列表的长度限于常用通用寄存器的数量，一共6个寄存器：rdi，rsi，rdx，rcx，r8，r9 函数参数需要先被压入栈中，并记录参数个数。然后再将栈中的参数依次弹入寄存器中 函数调用的文法如下： ``` funccall->identifier "(" ( "," assign)* ")" ``` 由此得到的语法解析部分流程为： 1. 解析函数名称，函数名称是一个辨识符 2. 略过左括号 3. 构造参数列表 4. 构造函数调用节点，函数调用节点的参数字段args赋值为参数列表 #### 函数定义 引入函数定义之后，语法解析变为以函数为单位的解析，即返回结果是一个函数列表 函数定义的语法可以归纳如下： ``` function_definition = declspec declarator compound_statement ``` #### 数组 计算机中的数组是指一系列连续存储的相同类型元素构成的数据结构。在底层表示数组时，是通过首元素地址和偏移量实现的。 数组初始化时通过指定首元素地址和数组长度实现。本项目依据C语言对数组和指针的二义性表示，将数组和指针用同一个对象表示。 用索引获取数组元素，实际上是利用前面定义的指针算术运算，对指向首元素的指针做向后偏移操作。 ### 代码生成 chibicc的编译过程是工业编译器的简化版本，流程如下： ``` 词法分析->语法分析->中间代码生成->代码生成 ``` 在这个项目中，代码生成用到了两个寄存器和堆栈 ``` rax：用于保存左操作数和返回结果 rdi：用于保存右操作数 堆栈：用于保存中间结果 ``` 在本项目中，代码生成实际上就是后序遍历AST，然后得到对应的汇编指令。后序遍历即左右中的顺序遍历AST。原因是AST中，节点层次越深优先级越高，后序遍历首先遍历最左子树的最左节点，而这个特点符合算术表达式的要求。 实现后序遍历的关键代码如下： ``` //先递归处理右子树 gen_code(node->rchild); //右子树结果入栈 push(); //再递归左子树 gen_code(node->lchild); //将右子树结果恢复，弹出到rdi中 pop("%rdi"); ``` 在这个过程中，将右子树的处理结果作为中间结果存放在栈中，等到左子树的处理结果压入rax寄存器后，再从栈中恢复元素弹入rdi寄存器。 由于代码生成涉及到堆栈的操作，需要用一个栈深度计数器来记录栈的深度，最终代码生成结束后，应当保证计数器的值为0。栈的相关数据结构和方法如下： ``` //栈深度计数器 static int depth; //入栈指令，将rax寄存器中的值压入到堆栈中 static void push(void) { printf(" push %%rax\n"); depth++; } //出栈指令，将堆栈栈顶元素弹出到指定寄存器（rdi）中 static void pop(char* source) { printf(" pop %s\n",source); depth--; } ``` 代码生成部分相对简单，只需要掌握对AST的后序遍历即可。 ### 优化 目前来看，本项目的优化可以从两方面入手： 1. 编译器运行效率；即编译器完成词法分析、语法分析并生成代码的过程可以得到优化。最典型的优化是为递归树剪枝 2. 输出更加友善：编译器输出的信息应当便于开发者阅读，并根据此调试修改自己的代码 2025，11，7的优化中，我们为每个AST节点引入了代表性token这个概念，为的是利用先前编写过的`error_tk`这个函数，让语法错误的信息更加完善。