# SyntaxAnalyzer

**Repository Path**: CodexploRe/syntax-analyzer

## Basic Information

- **Project Name**: SyntaxAnalyzer
- **Description**: syntax-analyzer是基于LR(1)/LALR(1)分析算法的语法分析器。可以根据输入的文法求解各非终结符的First、Follow集合，生成文法对应的LR(1)/LALR(1)的DFA图，并据此对源代码的分词文件进行语法分析，生成语法树。编译原理基础。
- **Primary Language**: Unknown
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-06-02
- **Last Updated**: 2025-03-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 编译原理项目：语法分析器



## 简介

本项目是一个语法分析器，用于编译原理课程的实践。它能够读取分词器输出的标记流，根据给定的文法规则，分析源代码的语法结构，生成语法树或进行错误检查。



## 功能

- 支持上下文无关文法（Context-Free Grammar, CFG）。
- 能够识别和构建抽象语法树（Abstract Syntax Tree, AST）。
- 语法错误检测和报告。
- 支持LR分析解析算法。



## 使用方法

1. 确保已经使用分词器已经生成了**标记流文件**（推荐结合我编写的[分词器程序](https://gitee.com/CodexploRe/lexical-analyzer)使用），文件内容参考[tiny-token-text.txt](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/tiny-token-test.txt)文件。

2. 准备代码的**文法规则文件**，文法中的终结符号与标记流文件中的token类型对应，注意空格的书写，参考[tiny-prod.txt](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/tiny-prod.txt)文件。

   - 如果文法规则中涉及到`空`，请参考[mini_c-prod.txt](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/mini_c-prod.txt)文件，该文件中的`@`字符即代表`空`，如需更换为其他字符，可修改[global.h](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/global.h)文件中的`NULL_CHARACTER`宏的定义。

3. 准备文法规则文件对应的**语法树构建类型配置文件**，为文法规则文件中的每个文法语句的右侧符号列表标记建点类型，这决定了执行规约时构建语法树节点的具体操作。建点类型的宏定义位于[global.h](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/global.h)文件中，当前配置为：

   - -1：舍弃的语法树节点。规约该文法时，忽略此终结符/非终结符对应的语法树节点，即该语法树节点不会出现在最后的语法树中。
   - 0：作为选定的根节点的子节点。规约该文法时，将此终结符/非终结符对应的语法树节点添加到选定的根节点的子节点列表中。
   - 1：作为根节点。规约该文法时，不创建新的语法树节点作为根节点，而是使用此终结符/非终结符对应的语法树节点作为根节点。

   构建语法树节点的逻辑如下：

   1. 当右侧类型列表中存在且仅存在一个根节点类型时，构建方法为：使用该根节点类型对应的语法树节点作为根节点，连接所有标记的子节点。
   2. 除此之外，都将执行下面的构建方法：创建一个新的语法树节点作为根节点，节点名为左侧的非终结符名，连接所有标记的子节点。

   标记文件中仅需编写每个文法语句右侧的符号对应的建点类型，内容参考[tiny-prod-build-type.txt](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/tiny-prod-build-type.txt)文件，该示例文件与其对应的文法语句文件的对照图如下，供参考：

   ![Clip_2024-12-02_16-55-49](README.assets/Clip_2024-12-02_16-55-49.png)

4. 修改[main.cpp](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/main.cpp)文件的主程序，参考如下代码，所有路径使用**绝对路径**：

   ```c++
   int main(int argc, char* argv[]) {
       // 初始化分词结果数据
       buffs = initBuffs("Path:/to/your/tokens.txt"); // todo
       const auto tokenManager = TokenManager(buffs);
       
       // 初始化文法语句
       auto productionBuffs = initBuffs("Path:/to/your/prod.txt"); // todo
       auto prodBuildTypeBuffs = initBuffs("Path:/to/your/prod-build-type.txt") // todo
       const auto productionManager = ProductionManager(productionBuffs, prodBuildTypeBuffs);
   
       // 建立LR(1)/LALR(1)分析表
       const auto lrMap = LRMap(productionManager.productions, productionManager.nameToCharacter,
                                productionManager.nameToProductions, true); // true建立LALR(1)分析表，false建立LR(1)分析表
       lrMap.showMap();
       lrMap.showTable();
   
       // 对分词结果进行语法分析
       auto parser = Parser(lrMap.productions, lrMap.tableMap, lrMap.allEndCharNames, tokenManager.tokens);
       parser.parse();
   }
   ```

5. 检查[CMakeLists.txt](https://gitee.com/CodexploRe/lexical-analyzer/blob/master/CMakeLists.txt)文件配置正确后，编译运行代码，即可在终端中查看输出日志，日志实例参考[out.txt](https://gitee.com/CodexploRe/syntax-analyzer/blob/master/out.txt)文件（该文件内容是同时测试tiny和mini_c两种代码的日志输出）。




## 许可证

本项目遵循 [AGPL-3.0](https://www.gnu.org/licenses/agpl-3.0.zh-cn.html) 开源许可协议，请确保遵守AGPL-3.0的所有条款和条件。