# compilor_experiment

**Repository Path**: luczydoge/compilor_experiment

## Basic Information

- **Project Name**: compilor_experiment
- **Description**: 简化的c语言（SysY）编译器
- **Primary Language**: C++
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 16
- **Forks**: 3
- **Created**: 2021-04-30
- **Last Updated**: 2025-04-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 编译器, flex, Bison, SysY

## README

# 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等工具

```bash
# 下载代码
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](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语句的类型，仅在编译器内部使用

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

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

```c
// 正确的声明与使用
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;
}
```

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

```c
// 正确的定义
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] 任意类型，但是左右操作数类型必须一致

 注意： 本编译器中，指针的`&`与`*`不是运算符，它们只能直接作用在标识符上而不能作用在表达式上，如
``` c
// 正确示例
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` :dog:

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

6. 运行程序 `qmue`

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