- 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
- main() 从 RE.txt 文件中,读取词法种类以及对应的正则表达式;
- GNFA 将一系列正则表达式转变成对应的 NFA (Thompson 算法);
- 将所有 NFA 合并成一个 NFA (一个开始节点,多个结束节点);
- GDFA 将得到的 NFA 确定化为 DFA (ε-Closure 算法);
- 最小化 DFA (Equivalence Partitioning 算法);
- 再由 GLexA 将 DFA 转换成 switch case 的写法,写入目标词法生成器的代码中;
- 程序结束,同时打印执行进度与步骤执行结果。
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
算法过程:
- 取开始节点的 ε 闭包,加入队列;
- 取出队列首元素,分别对字符表中的字符判断是否可接收,如果可接收,则将下一个节点即下一个节点的 ε 闭包加入到新的集合中,如果新集合的之前未出现过,则加入队列,否则跳过;
- 判断队列是否为空,如果为空则结束,反之到步骤2。
DFA 最小化过程:
- 将原先的 DFA 节点划分为两类,一类是结束节点集合,一类是非结束节点集合;
- 对每个类别使用字符表中的字符检查,以是否可接收,以及接收到达的状态是否一致进一步划分类别;
- 判断步骤 2 是否新增类别,如果有新增则继续执行步骤 2,反之结束。
实际上,为了最小化节点后,仍然可以区分不同种类的结束节点,因此对步骤 1 进行改动,初始将每个结束节点都归为单独一类。(另外,在步骤 2 中判断,如果到达节点为结束状态,且路径接收字符不同时,也可归为一类,应该可以进一步减少节点数量,不过本项目中未实现,在此给出思路)
- 水平有限,可能仍然存在未发现的 bug;
- 仍然存在一些细节问题没有很好的解决,如正则表达式的包含关系,给定 RE.txt 文件中 ID 的正则表达式包含了 KEYWORD 的正则表达式的表达范围,而 ID 中不包括空格,因此我在 KEYWORD 后增加了一个空格,以区分这两类,如:
int
表示 KEYWORD int,而int
只能识别出 IDint
。