|
|
# SysY 编译器课程实验（Rust）
|
|
|
|
|
|
本仓库为“并行编译课程实验”提供一个 SysY 编译器的最小可运行示例，实验按 Lab1 至 Lab6 逐步完成：
|
|
|
从前端（词法/语法分析与语法树处理）到中端（IR 生成、基本标量优化），再到后端（ARM64/AArch64 汇编生成、寄存器分配与后端优化），最后进行循环/并行相关优化。目前仓库提供了面向 AArch64 的后端实现，未提供 RISC-V 后端代码；但从 SysY 源程序到中端生成的实现与机器无关，Lab1 至 Lab4 的内容对 RISC-V 同样具有参考价值，二者在后端指令集与寄存器方面存在差异，但实现思路是共通的。
|
|
|
|
|
|
---
|
|
|
|
|
|
## 1、实验内容
|
|
|
|
|
|
| 实验 | 名称 | 任务/目标 |
|
|
|
| :--- | :------------------- | :---------------------------------------------------------- |
|
|
|
| Lab1 | 语法树构建 | 基于 SysY 源程序完成语法分析与语法树构建，并按约定输出语法树 |
|
|
|
| Lab2 | 中间表示生成 | 将语法树翻译为 LLVM 风格的中间表示（IR），并输出 IR |
|
|
|
| Lab3 | 指令选择与汇编生成 | 将 IR 翻译为目标平台汇编代码（本项目以 ARM64/AArch64 为主） |
|
|
|
| Lab4 | 基本标量优化 | 实现常量传播、死代码删除、简化控制流图等标量优化 |
|
|
|
| Lab5 | 寄存器分配与后端优化 | 为虚拟寄存器分配物理寄存器，完成溢出/重载、冗余指令消除与局部优化 |
|
|
|
| Lab6 | 并行与循环优化 | 面向循环的优化（循环变换/并行化等），进一步提升程序性能 |
|
|
|
|
|
|
---
|
|
|
## 2. 参考资料
|
|
|
|
|
|
本仓库提供的示例代码和实验文档只是参考。我们非常鼓励大家在阅读当前仓库实现的同时，也结合自己的理解重新设计框架并完成实现，而不是机械照搬。
|
|
|
|
|
|
如果希望进一步参考编译相关项目和往届优秀实现，可以查看编译比赛官网的技术支持栏目：<https://compiler.educg.net/#/index?TYPE=26COM>。其中的“备赛推荐”整理了一些编译相关项目，也能看到往届优秀作品的开源实现，这些内容都很值得参考。
|
|
|
|
|
|
## 3. 头歌平台协作流程
|
|
|
|
|
|
头歌平台的代码托管方式与 GitHub/Gitee 类似。如果你希望基于当前仓库快速开始协作，可以参考下面这套流程。
|
|
|
|
|
|
### 3.1 组长 fork 课程仓库
|
|
|
|
|
|
组长打开课程仓库页面，点击右上角的 `Fork`，创建你们小组自己的仓库副本。后续组内开发统一基于这个 fork 后的仓库进行。
|
|
|
|
|
|
|
|
|
|
|
|
### 3.2 组长邀请组员加入仓库
|
|
|
|
|
|
fork 完成后，组长进入自己的仓库页面，在右侧可以看到邀请码。把邀请码发给组员即可，组员不需要再 fork 课程仓库。
|
|
|
|
|
|
|
|
|
|
|
|
### 3.3 组员申请加入，组长审批通过
|
|
|
|
|
|
组员拿到邀请码后，可以在页面右上角的 `+` 菜单里选择 `加入项目`，然后提交加入申请。
|
|
|
|
|
|
|
|
|
|
|
|
申请发出后，组长到个人主页的待办事项中审批成员申请，同意后组员就可以正常参与仓库协作。
|
|
|
|
|
|
|
|
|
|
|
|
### 3.4 在本地克隆小组仓库并配置远端
|
|
|
|
|
|
组长和组员在成功加入小组仓库后，就可以从仓库页面复制 HTTPS 地址，在本地克隆代码：
|
|
|
|
|
|
|
|
|
|
|
|
下面示例使用 HTTPS 方式：
|
|
|
|
|
|
```bash
|
|
|
git clone <仓库 HTTPS 地址>
|
|
|
cd nudt-compiler-cpp
|
|
|
```
|
|
|
|
|
|
如果希望后续同步课程仓库更新，可以额外把课程主仓库配置为 `upstream`：
|
|
|
|
|
|
```bash
|
|
|
git remote add upstream https://bdgit.educoder.net/NUDT-compiler/nudt-compiler-rust.git
|
|
|
git remote -v
|
|
|
```
|
|
|
|
|
|
配置完成后，常见的远端分工如下：
|
|
|
|
|
|
- `origin`：你们小组 fork 后的仓库，日常提交代码、推送分支都使用这个远端。
|
|
|
- `upstream`：课程主仓库，通常用于查看或同步课程团队发布的更新。
|
|
|
|
|
|
如果后续需要同步主仓库更新，可以先抓取远端信息：
|
|
|
|
|
|
```bash
|
|
|
git fetch upstream
|
|
|
```
|
|
|
|
|
|
### 3.5 提交与协作建议
|
|
|
|
|
|
借助 Git 进行协作开发，是当前软件开发中非常常见的一种工作方式，也是这门课程里需要大家掌握的基本能力。如果你对 Git 还不太熟悉，可以先看一下网络上的 Git 教程，例如：<https://liaoxuefeng.com/books/git/introduction/index.html>。
|
|
|
|
|
|
当然也没有必要一开始学得特别深入，只需要记住常见操作即可，例如 `clone`、`status`、`add`、`commit`、`pull`、`push`、分支切换与合并。遇到具体报错或不会处理的冲突时，可以把现象和命令发给大模型帮你分析。
|
|
|
|
|
|
Git Commit 提交的信息建议尽量写清楚，推荐使用下面的格式：
|
|
|
|
|
|
```text
|
|
|
<type>(<scope>): <subject>
|
|
|
```
|
|
|
|
|
|
常见的 `type` 有：
|
|
|
|
|
|
- `feat`：新增功能
|
|
|
- `fix`：修复 bug
|
|
|
- `refactor`：重构但不改变外部行为
|
|
|
- `docs`：文档修改
|
|
|
- `test`：测试相关
|
|
|
- `chore`：杂项维护
|
|
|
|
|
|
`scope` 用来说明改动的大致范围，例如 `frontend`、`irgen`、`backend`、`test`、`doc`。
|
|
|
|
|
|
`subject` 用一句简短的话说明“这次改了什么”。
|
|
|
|
|
|
例如：
|
|
|
|
|
|
```text
|
|
|
feat(irgen): 支持一元表达式生成
|
|
|
fix(frontend): 修复空语句解析错误
|
|
|
docs(doc): 补充实验环境配置说明
|
|
|
```
|
|
|
|
|
|
除了提交代码本身，也推荐大家把头歌平台上的协作功能真正用起来：
|
|
|
|
|
|
- `Issue` 适合用来拆分任务、记录 bug、整理讨论结果和跟踪待办。
|
|
|
- `PR` / `Merge Request` 适合用来做分支合并和代码评审。比较推荐的流程是：每个人在自己的分支上开发，完成一个相对独立的小功能后提交 PR，再由组内其他同学帮忙检查实现思路、代码质量和测试结果。
|
|
|
|
|
|
## 4、关于 Rust
|
|
|
|
|
|
Rust 是一门由 Mozilla 开发的现代系统级编程语言，其特点在于能够在保证与 C/C++ 相媲美的性能（无垃圾收集和运行时）的同时，通过所有权系统和借用检查器，在编译期杜绝内存安全和并发安全方面的常见错误（如空指针、悬垂指针和数据竞争）。此外，Rust 还提供零成本抽象、模式匹配、包管理器 Cargo 以及友好的编译器错误提示。
|
|
|
|
|
|
结合编译比赛的实际经验，提供几点参考：
|
|
|
|
|
|
- Rust 学习曲线较 C/C++ 稍陡，但本实验所设计的编译器较为基础，未涉及过于复杂的 Rust 高级用法。网上存在许多可用参考资料：
|
|
|
- [菜鸟教程](https://www.runoob.com/rust/rust-tutorial.html)
|
|
|
- [Rust 程序设计语言](https://kaisery.github.io/trpl-zh-cn/)
|
|
|
- [Rust 语言圣经](https://course.rs/basic/intro.html)
|
|
|
- 此外，[南开大学编译系统原理](https://junimay.github.io/nku-compiler-2024-rs/intro.html#)的实验文档同时提供了 C++ 和 Rust 的实现介绍。
|
|
|
- Rust 提供成熟的项目管理工具 Cargo，无需手写 Makefile，可一站式解决依赖、编译和运行问题。
|
|
|
- Rust 编译器检查严格，若实现逻辑正确且通过编译，通常可避免运行时的内存错误，调试时配合 VSCode 的 `CodeLLDB` 插件即可。
|
|
|
- Rust 并非面向对象语言，不存在类的概念，结构体之间的关系可能不如 C++ 直观，但枚举类型为语法树操作提供了便利。
|
|
|
- Rust 提供 `lalrpop` 等语法解析工具，便于实现语法分析器和灵活的 AST 操作。
|
|
|
- Rust 生态系统丰富，许多库可直接使用，相关资源可访问 [Rust 官方学习页面](https://rust-lang.org/zh-CN/learn/)。
|
|
|
|
|
|
---
|
|
|
|
|
|
## 5、实验环境配置
|
|
|
|
|
|
### 5.1 系统建议
|
|
|
|
|
|
建议使用 **Ubuntu 22.04** 或 **WSL（Ubuntu 22.04 环境）**。虽然 Rust 在 Windows 和 Linux 上均可方便配置，但后续可能使用 ARM 或 RISC-V 工具链，在 Linux 环境下配置更为便捷。
|
|
|
|
|
|
### 5.2 Rust 环境配置
|
|
|
|
|
|
在 Ubuntu 中安装 Rust 环境：
|
|
|
|
|
|
```bash
|
|
|
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
|
|
|
```
|
|
|
|
|
|
安装完成后，验证：
|
|
|
|
|
|
```bash
|
|
|
rustc --version
|
|
|
```
|
|
|
|
|
|
建议搭配 VSCode 使用，并安装插件 `rust-analyzer`。
|
|
|
|
|
|
### 5.3 安装 LLVM 工具链
|
|
|
|
|
|
LLVM 工具链可用于生成中间表示（IR），若输出的 IR 符合 LLVM-IR 语法，可在 IR 层验证中间代码生成和优化的正确性，便于与后端开发解耦。
|
|
|
|
|
|
```bash
|
|
|
sudo apt update
|
|
|
sudo apt install -y llvm clang
|
|
|
```
|
|
|
|
|
|
### 5.4 安装 ARM64 交叉编译工具链与 QEMU
|
|
|
|
|
|
后续实验将生成 ARM64/AArch64 汇编代码，并使用 ARM64 交叉编译工具链完成汇编与链接；通过 QEMU 用户态模拟器运行生成的 ARM 可执行文件。
|
|
|
|
|
|
```bash
|
|
|
# 安装 ARM64 交叉编译工具链
|
|
|
sudo apt update
|
|
|
sudo apt install gcc-aarch64-linux-gnu
|
|
|
|
|
|
# 安装 QEMU 用户模式模拟器
|
|
|
sudo apt install qemu-user
|
|
|
```
|
|
|
|
|
|
---
|
|
|
|
|
|
## 6、目录结构
|
|
|
|
|
|
```bash
|
|
|
.
|
|
|
├── doc
|
|
|
│ └── Git Commit Message 规范.md
|
|
|
├── src
|
|
|
│ ├── backend
|
|
|
│ │ ├── peephole
|
|
|
│ │ ├── schedule
|
|
|
│ │ ├── mir
|
|
|
│ │ ├── regalloc
|
|
|
│ │ ├── asm2string.rs
|
|
|
│ │ ├── mirgen.rs
|
|
|
│ │ └── mod.rs
|
|
|
│ ├── frontend
|
|
|
│ │ ├── ir
|
|
|
│ │ ├── lalrpop
|
|
|
│ │ ├── ir2string.rs
|
|
|
│ │ ├── irgen.rs
|
|
|
│ │ ├── mod.rs
|
|
|
│ │ ├── symboltable.rs
|
|
|
│ │ └── typecheck.rs
|
|
|
│ ├── passes
|
|
|
│ ├── utils
|
|
|
│ │ ├── linked_list.rs
|
|
|
│ │ ├── mod.rs
|
|
|
│ │ └── storage.rs
|
|
|
│ └── main.rs
|
|
|
├── test
|
|
|
│ ├── output
|
|
|
│ │ ├── test
|
|
|
│ │ ├── test.ll
|
|
|
│ │ └── test.s
|
|
|
│ └── test_case
|
|
|
│ ├── functional
|
|
|
│ ├── performance
|
|
|
│ └── test.sy
|
|
|
├── Cargo.lock
|
|
|
├── Cargo.toml
|
|
|
├── README.md
|
|
|
└── build.rs
|
|
|
```
|
|
|
|
|
|
---
|
|
|
|
|
|
## 7、编译与运行
|
|
|
|
|
|
### 7.1 编译编译器
|
|
|
|
|
|
使用以下命令编译生成可执行文件：
|
|
|
|
|
|
```bash
|
|
|
cargo build --release
|
|
|
```
|
|
|
|
|
|
编译生成的可执行文件 `compiler` 位于 `nudt-compiler-rust/target/release/` 中。
|
|
|
- `--release` 表示以发布模式编译，开启优化，生成的可执行文件运行速度快，但调试信息较少，适合最终测试。
|
|
|
- 若需调试，可去掉 `--release` 使用默认的 debug 模式，编译速度更快，包含完整调试信息。
|
|
|
|
|
|
### 7.2 运行编译器
|
|
|
|
|
|
- **基本用法**
|
|
|
|
|
|
```bash
|
|
|
compiler [选项] source_file
|
|
|
```
|
|
|
|
|
|
- **参数列表**
|
|
|
|
|
|
| 参数 | 类型 | 描述 | 示例 |
|
|
|
| :----------- | :--- | :----------------------------------------------------------- | :-------------------- |
|
|
|
| `-ast <file>` | 可选 | 将抽象语法树（AST）输出到指定文件 | `-ast ast.txt` |
|
|
|
| `-ir <file>` | 可选 | 将中间表示（IR）输出到指定文件 | `-ir ir.txt` |
|
|
|
| `-asm <file>` | 可选 | 将汇编代码输出到指定文件（优先级高于 `-S` 和 `-o`） | `-asm output.s` |
|
|
|
| `-S` | 标志 | 生成汇编代码，输出到 stdout 或通过 `-o` 指定的文件 | `-S` |
|
|
|
| `-o <file>` | 可选 | 指定汇编代码的输出文件（仅当同时使用 `-S` 时有效） | `-o output.s` |
|
|
|
| `-O1` | 标志 | 启用一级优化 | `-O1` |
|
|
|
| `-h` | 标志 | 显示帮助信息 | `-h` |
|
|
|
|
|
|
- **示例**
|
|
|
|
|
|
1. **生成中间文件**（用于调试）
|
|
|
```bash
|
|
|
compiler -ast test.ast -ir test.ll -asm test.s test.sy
|
|
|
```
|
|
|
|
|
|
2. **生成优化后的中间文件**
|
|
|
```bash
|
|
|
compiler -O1 -ast test.ast -ir test.ll -asm test.s test.sy
|
|
|
```
|
|
|
|
|
|
3. **仅生成汇编并输出到文件**（比赛功能用例的编译命令）
|
|
|
```bash
|
|
|
compiler -S -o test.s test.sy
|
|
|
```
|
|
|
|
|
|
4. **启用优化**（比赛性能用例的编译命令）
|
|
|
```bash
|
|
|
compiler -O1 -S -o test.s test.sy
|
|
|
```
|
|
|
|
|
|
**说明**：`-ast`、`-ir`、`-asm` 参数主要用于开发调试，比赛环境中仅使用上述 3、4 所示的命令格式。 |
