Luczy Compiler - 小辣稽编译器

小辣稽的编译原理大作业-简化的c语言编译器

项目概要

分6个部分，逐步实现一个基于简化的c的语言：SysY语言的编译器（将SysY编译到x86汇编）。SysY语言支持int，bool，string三种基本数据类型，支持if-else，for，while等基本流程控制语句。

在我的实现中，还支持指针、数组、函数调用，变量的内存分配在栈上进行。

项目分为六个部分

• Lab1 探索现有的GCC编译器，看看它干了些什么，了解一下接下来的工作大体内容

• lab2 自己动手翻译一个c写成的代码到汇编，并且和GCC产生的汇编对比

• lab3 利用词法分析工具Bison写一个简单的词法分析器，将一个计算式由中缀翻译为后缀

• lab4 实现SysY语言的词法分析器

• lab5 实现SysY语言的语法分析器，并与词法分析器结合，将源码翻译为AST语法树

• lab6 实现编译器前端 LSCC (Luczydoge Simplified C Compiler) 将c代码翻译到汇编代码

如何使用

请先参照本代码库根目录下的util.pdf安装配置环境，需要在Linux上使用，需要安装gcc(g++), flex, bison, qemu等工具

# 下载代码
git clone https://github.com/MilkyBoat/compilor_experiment.git
# 进入项目目录，lab6是最终成型的编译器前端
cd compilor_experiment/lab6
# 用gcc编译器编译编译器[\doge]
make
# main.out是得到的编译器，默认编译输出到命令行，使用>来重定向到汇编文件
./main.out c语言代码文件名 > result.s
# 得到的是32位AT&T格式的x86汇编，使用gcc进行后端编译的时候要加-m32选项
gcc result.s -m32 -o result.out
# 使用qemu模拟运行32位程序
qemu-i386 result.out

在./lab6/test目录下有大量的测试样例可供运行，lab6内置了由助教提供的测试程序，该测试程序代码库链接：https://github.com/gilsaia/lab6_test ，在lab6目录下使用make run指令可以查看所有测试样例的测试结果

编译器支持的语法说明

这个编译器支持如下的语法：

1. 类型

• 基本数据类型：int、char、bool、void。

  基本数据类型可以在变量声明与函数声明中使用，可以作为函数返回值或者函数参数类型。为简单起见，目前所有基本数据类型都占用4字节。

• 特殊数据类型：string、notype。

  特殊数据类型不可以被写入代码。

  string类型只会自动成为任何常量字符串（写入代码的）的数据类型，且string不能参与运算，不能被修改，目前唯一能够使用字符串的地方是基本输入输出语句（printf scanf）。

  void仅可以在函数类型中使用，虽然可以将其声明为变量类型，但是这会使得该变量不能被除基本输入输出语句（printf scanf）以外的任何函数或运算符使用。

  notype是所有statement语句的类型，仅在编译器内部使用

int a = 9;
char b = '\n';
bool c = true;
void func() {
    ;
}
printf("%d\n", a);

• 指针：任何基本数据类型可以通过在声明时加上*或&来使之成为指针型变量，该变量将一定只占用4字节。不过目前非int型指针不能进行加减等运算。

int *a = 0x0;
int *b = 0x4;
a++;
a == b; // 该表达式为真

• 数组：任意维度数组。

  声明时的类型可以为基本数据类型或基本类型指针，必须在声明时用字面常数指定每一个维度的尺寸，如int a[3][4][5]。声明时可以初始化，但是只能使用一维大括号顺序初始化，如果初始化值数量与数组定义不吻合，将优先从前向后赋值，局部变量中数组声明时，初始化值溢出的部分可能导致严重的运行时错误（此处未进行类型检查）。如int a[2][3] = {1, 2, 3, 4, 5, 6, 7}，如果是全局变量声明，7 将被舍弃，如果是局部变量声明，初始化值 7，将会溢出到内存堆栈原有内存空间的外部，可能产生未知错误。

  访问时可以使用任意int型表达式作为下标参与运算，但是，如果运算维度和定义维度不同，返回的将不是指针而是后续维度下标为0的数值，如对于三维数组 a，有 a[2][1] == a[2][1][0]。

// 正确的声明与使用
int a[2][3][4];
a[1][2][1] = 4;
int x = a[1][2][2];
// 以下代码会导致b被赋值为a[0][0][0]
int* b = a;
// 正确的声明时初始化
int c[2][3] = {1, 2, 3, 4, 5, 6};
// 以下的初始化会产生语法错误（不能使用多维初始化）
// int errArrayInit[2][3] = {{1, 2, 3}, {4, 5, 6}};
// 以下两句初始化语句等价（默认初始化到0）
int d[2][3] = {1, 2, 3};
int e[2][3] = {1, 2, 3, 0, 0, 0};
// 以下两句初始化语句等价（全局变量声明中过多的初始值会被丢弃）
int globalArray1[2][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int globalArray2[2][3] = {1, 2, 3, 4, 5, 6};
// 以下语句将会导致未知错误，且编译器无法检查出来
int main() {
    // 4 和 5将会溢出到栈上，修改附近内存值，直到产生segment fault
    int localArray[3] = {1, 2, 3, 4, 5};
    return 0;
}

• 函数：函数只能定义，不能声明。

// 正确的定义
int func1(int a, int* b) {
    return (a + *b);
}
// 不支持函数声明语句，这会产生语法错误
// int func2(int a);
int main() {
    int* a = 0x0;
    func1(1, a);
    int b = func3(3);
    return 0;
}
// 主函数之后定义的函数也能正常使用
int func3(int a) {
    return a + 1;
}

2. 运算符

这里列出了所有支持的运算符

运算符	名称	说明
+	加	[1]
+	正号	[1]
-	减	[1]
-	负号	[1]
*	乘	[1]
/	除	[1]
%	取模	[1]
=	赋值	[3]
+=	加等于	[1]
-=	减等于	[1]
*=	乘等于	[1]
/=	除等于	[1]
++	自增	[1]
--	自减	[1]
&&	逻辑与	[2]
||	逻辑或	[2]
!	逻辑非	[2]
==	判断相等	[3]
!=	不等于	[3]
>	大于	[1]
<	小于	[1]
>=	大于等于	[1]
<=	小于等于	[1]

• [1] 仅用于int类型或int指针之间
• [2] 仅用于bool类型或逻辑表达式之间
• [3] 任意类型，但是左右操作数类型必须一致

注意： 本编译器中，指针的&与*不是运算符，它们只能直接作用在标识符上而不能作用在表达式上，如

// 正确示例
int a = 9;
int* b = &a;
printf('%d\n', *b);

// 错误示例
int a = 9;
int* b = &(a + 1);
printf('%d\n', *b);

后者将会导致语法错误

3. 流程控制语句

以下为支持的流程控制语句

condition为逻辑表达式，也可以是数值表达式，编译器将自动强制类型转换（这是整个编译器唯一可以的强制类型转换）

block为语句块，可以是单个statement（不加大括号）

expression为表达式，可以是任何变量、常量、字面常量、运算语句，不限类型

• if (condition) block

• if (condition) block else block

• while (condition) block

• for (expression; condition; expression) block

• for (variable declaration; condition; expression) block

用到的工具与大致原理

1. 词法分析：lex，这里使用的是linux上的flex

   这一过程完成了单词token的提取。如果代码中有八进制或十六进制字面常量，这一步将全部转换到十进制

2. 语法分析：yacc，这里使用的是linux上的bison

   这一过程先使用bison构造LALR分析表，然后表驱动翻译c代码到抽象语法树。在./lab6/src/type.h中，解除第17行#define AST的注释，将能够在最终生成的汇编代码开头看到语法树的样子。

   此外，这一步还完成了标识符作用域的分析，将检查标识符重定义和未定义等错误。

3. 语义分析：./lab6/src/tree.cpp中的typecheck()函数

   主要是重新遍历语法树，进行类型检查和检查诸如break、continue是否处于循环体内部等语法分析难以检查的语法错误。

4. 中间代码生成：./lab6/src/tree.cpp中的genCode()函数

   这里递归的将语法树翻译到AT&T格式的32位x86架构汇编代码。

5. 机器码生成：gcc 🐶

   是的，这个项目只是前端，并没有完整的实现一个编译器，最后的机器码生成仍然需要GCC编译器。

6. 运行程序 qmue

   参见lab6的MakeFile，这个项目生成的可执行文件是32位的，不能直接在64位上运行，需要硬件模拟器qemu，使用时输入qemu-i386 ./main.out即可运行刚刚生成的可执行文件。