# My Parser Generator

**Repository Path**: zeege/my-parser-generator

## Basic Information

- **Project Name**: My Parser Generator
- **Description**: 通用可配置的，词法和LR(1)语法分析器-生成器 (compiler-compiler)
- **Primary Language**: C++
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2021-05-12
- **Last Updated**: 2022-06-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 🧾目录

[toc]

# 🛒快速开始

词法、LR(1)语法分析器生成器，**这只是一个玩具**，学编译原理的时候写的。用的C++17，如果无法编译，可以[点击这里](https://gitee.com/zeege/my-parser-generator/releases/)下载编译好的exe，双击运行里面的demo就好。`./demo`文件夹里的3个demo，**都可以直接运行**，注意运行的时候`cwd`是`./demo`，而不是项目根目录。

这三个demo从`./testcase`文件夹中读取词法、文法、AST的定义，将生成的程序写入到`./generated`文件夹中。在`./testcase`文件夹中同样有这三个语言的样例程序，这三个demo同时会把这三个程序的**分析结果写入到`./output`文件夹中**。

更详细的使用方法见后面的介绍。

> PS：生成Parser的算法复杂度好高QAQ，一个C语言结构体的文法大概要4秒生成

# 📌介绍

- 词法分析`MyLexer`：词法分析程序生成器，生成基于表格的词法分析器。支持的正则表达式包括形如这样的：
`()`、`[]`、`[^abc]`、`[a-zA-Z]`、`.*?+|`和转义`\.\*\+\?\|\(\)\[\]`，目前暂不支持`{}`、`^`、`$`、预查、元字符，不支持Unicode
- 语法分析`MyParser`：LR(1)语法分析程序生成器，生成基于表格的语法分析器。它不依赖于`MyLexer`，而是只依赖于`commons/token.hpp`中的`Token`类。

项目结构：

- `demo`：示例程序
- `jsonxx`：JSON和`fifo_map`依赖
- `src`
  - `commons`：lexer和parser的公共依赖
  - `lexer/lexercc.hpp`：词法分析生成器
  - `parser/parsercc.hpp`：语法分析生成器
  - `gen_lexer_and_parser.hpp`：一个生成词法和语法分析代码的函数，使用方法见后
  - `lexer_main.cpp`：包含一个main函数，请编译后在命令行中输入参数运行，使用方法见后
  - `parser_main.cpp`：包含一个main函数，请编译后在命令行中输入参数运行，使用方法见后
  - `lexer_demo.cpp`：一个简单的Lexer的demo
- `testcase`：测试用例，包括词法定义、文法定义、AST定义和一个待分析代码



# ⚡使用

## 词法定义

词法定义是一个普通的JSON文件，`Key-Value`表示`Token-Regex`，越先出现的token优先级越高，例如在下面的例子中，`INT`和`DOUBLE`的优先级高于`ID`的优先级，这样保证了关键字优先：

```json
// lexeme.json
{
    "INT": "int",
    "DOUBLE": "double",
    "PLUS": "+",
    "INT_VAL": "0|[1-9][0-9]*",
    "DOUBLE_VAL": "[0-9]*\\.[0-9]*",
    "ID": "[a-zA-Z_][a-zA-Z0-9_]*",
    "STRING": "\"([^\"]|\\\\[btnfr\\\\\"])*\"",
    "CHARACTER": "'[^']'"
}
```

## 文法定义

语法定义是一个CSV文件（为什么不也用JSON，因为懒QAQ，以后再补了它叭），有2列，第一列是产生式名字，第二列是产生式，单词之间用空格分割，**需要用扩展文法**，区分大小写：

```json
GS          , exp_elem
exp_elem    , add_exp
add_exp     , mul_exp
add_exp     , mul_exp PLUS add_exp
add_exp     , mul_exp MINUS add_exp
mul_exp     , VAL
mul_exp     , VAL TIMES mul_exp
mul_exp     , VAL DIV mul_exp
mul_exp     , VAL PERCENT mul_exp
```

## AST定义

这个可有可无，其实就是个语法制导翻译，参考了一下Charles N.Fischer等人的《编译器构造》，使用JSON定义。详细定义见`src/AST_schema.json`，包含4种操作
1. 重命名：对于非终结符，在`parseTreeToASTRules`的数组中重命名，需要注意的是，只有一个孩子的节点会被压缩，如果不想压缩掉，可以在`compressExclusions`中写
2. 重命名：对于终结符，在`terminalNamesMapping`的数组中重命名
3. 把某些孩子放到父节点的属性中，在`childToFields`中写，终结符默认都会放进去，如果不想放，参考第6点
4. 把递归的产生式节点（与自己同类型孩子）提升到邻居节点，在`childToSiblings`中写
5. 把邻居节点设置成父节点的孩子，在`mergeChilds`里写
6. 如果想直接忽略一些终结符（如分号、大括号等），可以在`ignoredTerminals`中写

## lexer_main

编译后命令行中运行`lexer_main.exe`，接收两个参数，一个是用json格式定义的词法文件路径，一个是输出的词法分析程序的路径。
例如，使用`testcase/midl_lex.json`中定义的词法，可以通过以下的方式在`./output`文件夹中找到输出的程序

```bash
./build> lexer_main.exe ./testcase/midl/midl_lex.json ./output/
```

## parser_main

编译后命令行中运行`parser_main.exe`，接收3~4个参数，含义如下：
1. 词法定义文件的路径
2. 文法定义文件的路径
3. 生成的词法和语法分析程序的文件夹路径
4. \[可选\] 输出的LR(1)分析表的路径，CSV格式

例如，使用`testcase/midl_syntax.txt`中定义的文法，可以通过下面的方式在`./output`文件夹中找到输出的程序和分析表

```bash
./build> parser_main.exe ./testcase/midl/midl.json ./testcase/midl/midl_syntax ./output/ ./output/parse_table.csv
```

如下面的例子

# 🔨API

## MyLexer

在`my_lexer.hpp`中包含核心的`MyLexer`类，它提供2种方法：
- `addRegex`：添加一个正则表达式，`priority`的值越小代表优先级越高
- `lex`：对输入字符串进行词法分析，支持从`std::istream`输入，也有一个从`string`输入的包装版

在`lexercc.hpp`中包含2个工厂方法：
- `buildLexer`：从文件流读取词法文件，并建立词法分析器
- `writeLexer`：将生成的词法分析器写入到指定路径的文件中

只需要用以上两个文件就好了，从JSON文件读取输入的详细示例见`lexer_main.cpp`。下面是一个从字符串读取输入的简单的例子：

```cpp
#include "./src/lexercc.hpp"

using namespace std;

int main(){
    MyLexer lexer;
    lexer.addRegex("int", "INT", 0);
    lexer.addRegex("double", "DOUBLE", 0);
    lexer.addRegex("0|[1-9][0-9]*", "INT_NUM", 0);
    lexer.addRegex("[0-9]*\\.[0-9]*", "DOUBLE_NUM", 0);
    lexer.addRegex("[a-zA-Z_][a-zA-Z0-9_]*", "ID", 1);
    lexer.addRegex("\"([^\"]|\\\\[btnfr\\\\\"])*\"", "STRING", 1);
    vector<Token> tokens = lexer.lex("double foo 1.2 int intt 1 \"abc#$+\\n\\t\"");
    for (auto i : tokens) {
        cout << i.tokenName << ": " << i.word << endl;
    }
    writeLexer(lexer, "./output/", "./src/lexer", true);
}
```

## MyParser

在`my_parser.hpp`中包含核心的`MyParser`类，它只依赖于`commons/Token.hpp`中的`Token`类作为输入，不依赖于`MyLexer`。它提供4个方法：

- `buildParserFromSyntaxDef`：工厂方法，从CSV格式的文法定义中建立语法分析器
- `buildParserFromCsvParseTable`：工厂方法，从CSV格式的LR(1)分析表中建立语法分析器
- `parse`：从`vector<Token>`中读取输入，返回分析树指针 `shared_ptr<MyParser::ParseTreeNode>`
- `printParseTable`：打印分析表到指定的输出流中
- `printParseTree`：打印分析树到指定的输出流中

在`parsercc.hpp`中包含一个方法：
- `writeParser`：将生成的语法分析器写入到指定路径的文件中

在`generate_lexer_and_parser.hpp`中包含一个方法：
- `generateLexerAndParser`：使用方法和前面的`parser_main.exe`的使用相同：[传送门](#parser_main)


# 🍀致谢

- 马老师！带我走进编译原理的世界
- `jsonxx` by [@Nomango](https://github.com/Nomango/jsonxx)
- `fifo_map` by [@Nlohmann](https://github.com/nlohmann/fifo_map)
- [@施工中请绕行](https://blog.csdn.net/xinghongduo/article/details/39455543)的博客
- LR(1) parse visualize by [@soroushj](https://github.com/soroushj/lr1-parser-vis)
- [LR(1) parser](http://jsmachines.sourceforge.net/machines/lr1.html)
- Toolbox by  [@CyberZHG](https://github.com/CyberZHG/toolbox)
- 某个要求我感谢ta的人[@Whuan](https://gitee.com/W-huan)