# Compiler

**Repository Path**: sethan/Compiler

## Basic Information

- **Project Name**: Compiler
- **Description**: 一个用于教学语言SysY（类似c语言）的编译器
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2024-10-13
- **Last Updated**: 2025-03-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Compiler, Java

## README



# SysYCompiler - 一个SysY语言的完整编译器实现

![Java](https://img.shields.io/badge/Java-17%2B-007396?logo=java)
![License](https://img.shields.io/badge/License-MIT-green)

本项目是一个完整的SysY语言编译器实现，支持从词法分析到目标代码生成的全流程，并包含多层次的优化策略。参考`javac`设计思想，实现了模块化的编译流程和高效的中间代码优化。

`README.md` 中简要介绍了相关的技术实现，具体实现可以参见 [详细技术实现文档](./docs/README.md) 以及 [优化文档](./docs/Optimizer.md)。

## 目录
- [SysYCompiler - 一个SysY语言的完整编译器实现](#sysycompiler---一个sysy语言的完整编译器实现)
  - [目录](#目录)
  - [功能特性](#功能特性)
    - [前端](#前端)
    - [中端](#中端)
    - [后端](#后端)
  - [技术栈](#技术栈)
  - [快速开始](#快速开始)
    - [环境要求](#环境要求)
    - [构建与运行](#构建与运行)
  - [使用示例](#使用示例)
    - [1. 解析SysY程序](#1-解析sysy程序)
    - [2. 生成LLVM IR](#2-生成llvm-ir)
    - [3. 生成MIPS汇编](#3-生成mips汇编)
  - [许可证](#许可证)

---

## 功能特性

### 前端
- **词法分析**：基于有限状态机实现，支持保留字、标识符、常量等Token解析
- **语法分析**：递归下降法构建AST，支持复杂文法嵌套（如`if-else`、`for`循环）
- **语义分析**：符号表栈式管理，支持作用域嵌套，实现12类语义错误检测（如类型不匹配、未定义符号）

### 中端
- **中间代码生成**：生成LLVM IR，支持函数调用、数组访问、控制流指令
- **机器无关优化**：
  - **常量折叠**：在IR生成阶段直接计算可折叠表达式
  - **乘除模优化**：将乘2^n转换为移位指令，除法转换为乘法优化
  - **窥孔优化**：合并条件跳转指令，删除冗余计算

### 后端
- **目标代码生成**：生成MIPS汇编指令，支持寄存器分配和函数调用约定
- **机器相关优化**：
  - **除法优化**：基于《Division by Invariant Integers using Multiplication》算法实现
  - **寄存器释放策略**：动态跟踪寄存器使用情况，及时回收空闲寄存器

---

## 技术栈
| 模块     | 关键技术                                    |
| -------- | ------------------------------------------- |
| 前端     | 递归下降解析、符号表栈式管理                |
| 中间表示 | LLVM IR                                     |
| 目标代码 | MIPS32指令集，支持syscall调用（如输入输出） |
| 优化     | 常量折叠、窥孔优化、指令替换                |

---

## 快速开始

### 环境要求
- JDK 17+
- MARS MIPS模拟器（用于运行生成的汇编代码）

### 构建与运行
1. **克隆仓库**

   ```sh
   git clone git@gitee.com:sethan/Compiler.git
   cd SysYCompiler
   ```

2. **创建测试文件**

   ```sh
   echo "int main() { return 0; }" > testfile.txt
   # 引号内是需要输入的sysY代码
   ```

3. **运行java项目**

4. **生成文件** 运行成功后，将在当前目录下生成：

   - `lexer.txt`（词法分析结果）
   - `parser.txt`（语法分析结果）
   - `symbol.txt`（符号表）
   - `llvm_ir.txt`（LLVM IR）
   - `mips.txt`（MIPS汇编代码）
   - `error.txt`（错误日志）

你可以根据需要修改 `testfile.txt` 以测试不同的 SysY 代码。

---

## 使用示例

### 1. 解析SysY程序
```sysy
// demo.sy
int main() {
    int a = 10;
    int b = a * 2 + 5;
    return b;
}
```

### 2. 生成LLVM IR
```llvm

declare i32 @getint()
declare i32 @getchar()
declare void @putint(i32)
declare void @putch(i32)
declare void @putstr(i8*)

define dso_local i32 @main() {
cyx0:
  %cyx1 = alloca i32
  store i32 10, i32* %cyx1
  %cyx2 = alloca i32
  %cyx3 = load i32, i32* %cyx1
  %cyx4 = shl i32 %cyx3, 1
  %cyx5 = add i32 %cyx4, 5
  store i32 %cyx5, i32* %cyx2
  %cyx6 = load i32, i32* %cyx2
  ret i32 %cyx6
}

```

### 3. 生成MIPS汇编
```mips
.data
.text
main:
addi $sp, $sp, -84
sw $ra, 80($sp)

main_cyx0:
li $t0, 10
sw $t0, 0($sp)
lw $t1, 0($sp)
sll $t2, $t1, 1
addiu $t3, $t2, 5
sw $t3, 4($sp)
lw $t4, 4($sp)
li $v0, 10
syscall
```

## 许可证
[MIT License](https://opensource.org/licenses/MIT) © 2024 Chen Yanxiang