# toyc_compiler

**Repository Path**: ganrl/toyc_compiler

## Basic Information

- **Project Name**: toyc_compiler
- **Description**: 武汉大学编译原理课程实践的一部分，旨在实现一个简化版 C 语言 —— ToyC 的编译器。
- **Primary Language**: OCaml
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-07-02
- **Last Updated**: 2025-08-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# ToyC Compiler

本项目是武汉大学编译原理课程实践的一部分，旨在实现一个简化版 C 语言 —— **ToyC** 的编译器。编译器以 ToyC 源文件（`.tc`）为输入，经过词法分析、语法分析、语义分析与代码生成等阶段，输出可在 RISC-V32 架构上运行的汇编代码（`.s` 文件）。

## 项目目标

- 使用 **OCaml (版本 5.3.0)** 开发完整的 ToyC 编译器
- 支持从 ToyC 源代码生成有效、正确、规范的 RISC-V 汇编代码
- 满足课程提供的所有测试用例的语义与语法约束
- 尽可能实现中间代码与汇编优化，提高程序运行性能

## ToyC 语言特性

ToyC 是 C 语言的子集，具有以下特性：

- 支持函数定义、变量声明与赋值、控制流（if-else、while）、break、continue、return 等语句
- 支持 void 函数的汇编
- 支持变量的块作用域隐藏；支持多参数的函数调用
- 表达式支持基本的算术、关系、逻辑运算，运算规则与优先级同 C 语言
- 不支持函数的前向声明
- 不支持数组、指针、结构体、I/O、多文件等高级特性
- 每个程序必须包含一个 `int main()` 入口函数

详细文法和语义规则见课程任务书。

## 编译器结构

编译器实现分为如下几个阶段：

1. **词法分析**：将源文件解析为标记流（token stream）
2. **语法分析**：根据文法规则构建抽象语法树（AST）
3. **语义分析**：进行类型检查、作用域检查、控制流合法性分析等
4. **中间表示生成**：生成适合进一步优化与代码生成的中间表示
5. **优化阶段**：如常量传播、死代码消除等
6. **代码生成**：生成 RISC-V32 汇编代码

## 项目结构

```plain
├── bin/                   # 可执行文件目录
│   ├── dune              
│   └── main.ml           # 编译器主入口（参数解析/流程控制）
│
└── lib/                   # 核心编译逻辑
    ├── ast.ml            # 抽象语法树定义
    ├── astToIR.ml        # AST→IR 转换, 和 IR 优化
    ├── optimazation.ml   # 活跃变量分析
    ├── cfg.ml            # 控制流图构建及常量传播
    ├── regAllocation.ml  # 寄存器分配策略，使用线性扫描分配
    ├── lexer.mll         # 词法规则
    ├── parser.mly        # 语法规则
    ├── print_ast.ml      # AST 打印器
    ├── print_ir.ml       # IR 打印器
    ├── irToAsm.ml        # IR→RISC-V 汇编生成，提供两套汇编方法
    └── dune             
```

## 使用方法

本编译器从标准输入流（stdin）中读取源程序代码，最终向标准输出流（stdout）中写入汇编程序代码。

`dune exec toyc_compiler -- [-print_ast] [-print_ir] [-opt] [-print_live] [-print_alloc] `

`-opt` 选项用于启用优化的编译策略。

为了方便，你可以重定向标准输入输出流，用文件读写的方式来输入输出。

## 实现的功能

- 正确的语义翻译和汇编；

- 简单的寄存器分配策略（线性扫描寄存器分配）和 Spill 策略;

- 标准的函数栈帧分配策略和寄存器保护策略;

- 强度缩减、常量折叠、常量传播、死代码移除、尾递归优化、拷贝传播、公共子表达式消除、循环消除和循环不变量外提等优化策略;

## 仍然存在的问题

- 寄存器分配策略在极端情况下会出现交叠，且分配性能不够优、寄存器复用性不强;

- 只对明显有收益的算术指令做强度缩减; 只对最简单的情况做了循环消除(循环变量自增);

- 只在过程块级别做了公共子表达式消除;