• Windows 10
• C++17
• CMake 3.18
• MinGW

LexAnaGen
	|--build/*				cmake编译生成文件
	|--include				源码头文件
	|--src					源码cpp文件
	|--static				项目静态资源文件
	|--target				目标文件

static 文件夹中包括 RE.txt、Chars.txt(可选，字符表，默认为 ASCII码 可打印字符)。

target 文件夹中包含项目执行结束后生成的词法分析器 cpp 文件。

* 具体文件作用在后文说明。

./> mkdir build
./> cd build
./build> cmake -G "MinGW Makefiles" ..
./build> mingw32-make
./build> LexicalAnalyzer.exe

项目将目标分析器生成后，保存在 target 文件夹下，命名为 analyzer.cpp，该文件夹下还保存一个用于测试分析器的测试文件 test.cpp，可参照如下命令，运行测试：

./> cd target
./target> g++ analyzer.cpp -o a.exe
./target> a.exe test.cpp

1. main() 从 RE.txt 文件中，读取词法种类以及对应的正则表达式；
2. GNFA 将一系列正则表达式转变成对应的 NFA (Thompson 算法)；
3. 将所有 NFA 合并成一个 NFA (一个开始节点，多个结束节点)；
4. GDFA 将得到的 NFA 确定化为 DFA (ε-Closure 算法)；
5. 最小化 DFA (Equivalence Partitioning 算法)；
6. 再由 GLexA 将 DFA 转换成 switch case 的写法，写入目标词法生成器的代码中；
7. 程序结束，同时打印执行进度与步骤执行结果。

RE.txt 文件中，第一行包含一个整数 n，表示词法种类个数，接下来 n 行表示词法种类名称（不能包含字符 空格）；接着符号 % 用于分隔于测试便利；接下来若干行，每行两个字符串，由空格隔开，分别表示词法种类（与上述种类必须对应），对应正则表达式（可以包含空格），如：

2
STRING
ID
%
ID [_a-zA-Z]+[0-9a-zA-Z]*
STRING "[\*&\(\)\\!@ 0-9a-zA-Z]*"
STRING main 

特殊字符需要使用 \ 进行转义。

在自定义词法时，需注意并不包含所有正则表达式语法，如：?! 否定式向前查找，因此正则表达式间存在包含关系，则包含类型将覆盖被包含类型，在本项目中，程序内算法不会处理此种情况，而需设计者主动避免。项目实例中将在被包含式后增加一个包含式中不存在的字符，以打破包含关系，如上述 main 后添加一个空格 main_。

此部分简单描述项目中将会使用的数据结构、以及主要算法的过程描述。更多细节可直接查看源码。其中 GNFA.h/GNFA.cpp 为 NFA 相关算法的声明与实现，GDFA.h/GDFA.cpp 为 DFA 相关算法的声明与实现，GLexA.h/GLexA.cpp 为生成程序的实现，Data.h/Data.cpp 为全局数据的声明与通用函数的声明与实现，config.h 为方便测试的部分宏定义。

字符表：std::string；

自动机状态：state 即 std::shared_ptr<NodeElem>，其中 NodeElem 为节点类，继承该类的类型有 StartElem 和 EndElem 分别表示自动机的开始和结束节点，使用指针表示，方便后续的多态操作（实际上使用编号加字符的结构也可以实现后续算法，不过本项目中，我更倾向于使用多态） ；

自动机转换路径：path 即 std::pair<state, std::string>，表示一个状态接收一个字符；

转换图的存储：

• NFA：std::multimap<path, state>，表示由路径 path 到达下一个 state
• DFA：std::map<path, state>，表示由路径 path 到达下一个 state，DFA 同一个路径不可达到不同状态

更多细节可参考头文件中命名空间中的声明。

算法基本操作如上图所示；

在实现过程中，如果使用输入的正则表达式直接构造，则需要递归地解析正则表达式的子表达式；在本实验中，先将正则表达式转换成二叉树，再使用后缀式形式存储，如：(a|b)(c|d)* 转换成如下形式，对应的后缀式为 ab|cd|*。

图片来源：https://www.cnblogs.com/jerry-fuyi/p/12832989.html

算法过程：

1. 取开始节点的 ε 闭包，加入队列；
2. 取出队列首元素，分别对字符表中的字符判断是否可接收，如果可接收，则将下一个节点即下一个节点的 ε 闭包加入到新的集合中，如果新集合的之前未出现过，则加入队列，否则跳过；
3. 判断队列是否为空，如果为空则结束，反之到步骤2。

DFA 最小化过程：

1. 将原先的 DFA 节点划分为两类，一类是结束节点集合，一类是非结束节点集合；
2. 对每个类别使用字符表中的字符检查，以是否可接收，以及接收到达的状态是否一致进一步划分类别；
3. 判断步骤 2 是否新增类别，如果有新增则继续执行步骤 2，反之结束。

实际上，为了最小化节点后，仍然可以区分不同种类的结束节点，因此对步骤 1 进行改动，初始将每个结束节点都归为单独一类。（另外，在步骤 2 中判断，如果到达节点为结束状态，且路径接收字符不同时，也可归为一类，应该可以进一步减少节点数量，不过本项目中未实现，在此给出思路）

• 水平有限，可能仍然存在未发现的 bug；
• 仍然存在一些细节问题没有很好的解决，如正则表达式的包含关系，给定 RE.txt 文件中 ID 的正则表达式包含了 KEYWORD 的正则表达式的表达范围，而 ID 中不包括空格，因此我在 KEYWORD 后增加了一个空格，以区分这两类，如：int 表示 KEYWORD int，而 int 只能识别出 ID int。