# My_Compiler

**Repository Path**: LabMem-No004/my_-compiler

## Basic Information

- **Project Name**: My_Compiler
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-12-02
- **Last Updated**: 2025-12-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# LL(1)语法分析器

## 项目简介

本项目实现了一个完整的LL(1)语法分析器，包括：
- 消除左递归的文法改写
- FIRST集和FOLLOW集的计算
- LL(1)预测分析表的构造
- 基于栈的预测分析算法
- 语法错误识别和处理

## 编译方法

### Windows
```bash
.\build.bat
```

### Linux/Mac
```bash
make
```

## 使用方法

### 1. 从文件分析
```bash
.\parser.exe tests\test1.sy
```

### 2. 交互式模式
```bash
.\parser.exe
```
然后选择：
- 1: 从文件分析
- 2: 从键盘输入分析
- 3: 显示FIRST/FOLLOW集和预测分析表

### 3. 从键盘输入
在交互模式中选择2，然后输入源代码，以单独一行`END`结束输入。

## 输出格式

预测分析过程输出格式：
```
序号    栈顶符号#面临输入符号    执行动作
```

执行动作包括：
- `move`: 匹配终结符并前进
- `reduction (产生式X: A -> α)`: 使用产生式X进行推导
- `accept`: 接受，分析成功
- `error`: 错误，分析失败

## 文法说明

本分析器实现的是C语言子集的LL(1)文法，消除了原文法中的左递归。主要特点：
- 支持变量声明、函数定义
- 支持算术表达式、关系表达式、逻辑表达式
- 支持if-else语句、return语句
- 支持函数调用

### 消除左递归的方法

对于形如 `A -> A α | β` 的左递归，改写为：
```
A -> β A'
A' -> α A' | ε
```

### dangling else问题的处理

对于else的归约-移进冲突，采用"最近匹配"策略，即优先选择shift(else)。

## 测试用例

项目包含三个测试用例：
- `tests/test1.sy`: 包含变量声明、算术运算、if-else语句
- `tests/test2.sy`: 更复杂的测试用例
- `tests/test3.sy`: 综合测试用例
- `tests/test_simple.sy`: 简单测试用例

## 项目结构

```
code/
├── include/          # 头文件
│   ├── parser.h     # 语法分析器头文件
│   ├── lexer.h      # 词法分析器头文件
│   └── tokens.h     # Token定义
├── src/             # 源文件
│   ├── parser.c     # 语法分析器实现
│   ├── main.c       # 主程序
│   └── ...          # 其他源文件
├── tests/           # 测试用例
├── build.bat        # Windows编译脚本
├── Makefile         # Linux/Mac编译脚本
└── README.md        # 本文件
```

## 技术要点

### 1. FIRST集计算
对于产生式 `A -> α`：
- 如果α第一个符号是终结符，FIRST(A)包含该终结符
- 如果α第一个符号是非终结符B，FIRST(A)包含FIRST(B)-{ε}
- 如果B可以推导出ε，继续考察α的下一个符号
- 迭代直到不再变化

### 2. FOLLOW集计算
对于产生式 `A -> αBβ`：
- FOLLOW(B)包含FIRST(β)-{ε}
- 如果β可以推导出ε或β为空，FOLLOW(B)包含FOLLOW(A)
- 开始符号的FOLLOW集包含EOF
- 迭代直到不再变化

### 3. 预测分析表构造
对于产生式 `A -> α`：
- 对FIRST(α)中的每个终结符a，M[A,a] = 产生式
- 如果ε∈FIRST(α)，对FOLLOW(A)中的每个终结符b，M[A,b] = 产生式
- 对于冲突，优先选择非ε产生式（处理dangling else）

### 4. 预测分析算法
使用栈结构：
1. 初始化：栈中压入结束符和开始符号
2. 循环：
   - 如果栈顶是终结符，匹配并弹出
   - 如果栈顶是非终结符，查表获取产生式，弹出并逆序压入产生式右部
   - 如果栈顶是$END且输入是EOF，接受
   - 其他情况报错
3. 直到栈空或出错

## 作者

实验六 - LL(1)语法分析器