实验框架¶
实验框架介绍¶
考虑到较低年级同学的代码经验以及《形式语言与自动机》与前置课程的联系，本实验项目采用 C++ 语言编写，实现的功能类似于std::regex_match。在<regex>库中，字符类型是模板参数，这是因为实际字符串中的字符类型并不一定是char，这种设计可以增强库函数的泛用性，例如把字符类型分别取为char和wchar的情况可以复用同一套代码：
typedef basic_regex<char> regex;
typedef basic_regex<wchar_t> wregex;
在本实验中，我们也令字符类型是模板参数，如果同学们正确完成了所有实验，就可以得到一个高效的、适用于各种字符类型的测试正规表达式匹配的模板库。
标准库的性能问题
实际上，C++ 标准库的std::regex性能比较糟糕，要明显低于 python、PHP 的 regex 性能，而且因为 ABI 兼容的问题没法改正。同学们在实验中写出的正则库应该会比<regex>库的性能高，如果使用自己生成的测例进行测试，本实验写的库能通过而标准库用时过长甚至爆栈是可能出现的。
实验框架大致可以划分为五个部分，分别放在五个文件夹中，依次介绍如下
model¶
model中的代码定义了本实验中的各种模型，包括自动机DFA，ε-NFA，语法分析树parse-tree，上下文无关文法CFG，字符类型COE(character or epsilon)，以及各种字符类型下用来表示特殊符号的常量。建议同学们在进行实验之前首先了解各种类型的定义，以便于操作其数据结构。
homework¶
homework中包含同学们需要补全的函数，其中的子文件夹（除了DFA-accept）实现下述阶段中的一个转换
正规表达式 => 语法分析树 => ε-NFA => DFA => 最小化的DFA
CNF 及其句子 => 语法分析树
整个homework构成一个模板库，可以实现正规语言表示形式之间的转换。
lib_char¶
为了便于同学们独立评测每个小实验，lib_char提供了模板参数为char情况下的静态链接库，例如仅完成“正规表达式 => 语法分析树”后，可以静态链接基于char类型的“语法分析树 => ε-NFA => DFA => 最小化的DFA”库，组合成一个完整的测试正规表达式是否与字符串相匹配的程序，然后与std::regex_match<char>对拍，以检查自己的实现是否存在问题。
tests¶
tests中包含用于测试的程序头文件和源文件。按照本实验的链接顺序，g++-14会优先在主程序代码中寻找符号，找不到才会再去静态库中查找，因此只需去除homework/lib_char.h中的相应注释，测试程序就会使用你在homework中完成的函数。test.cpp（对应 CMake 目标 regex_lab_test）从输入中读取一个正规表达式和数字n，然后测试n次该正规表达式是否匹配输入的字符串。std_test_all.cpp（对应 CMake 目标 regex_lab_std_test）以testcases/input.txt为输入，将本实验的库与std::regex_match<char>比较，若结果出现不同则给出提示。
testcases¶
testcases包含了一份标准测例input.txt和一个简易的测例生成器make_cases.py。然而std::regex_match使用了 DFS 而不是先完全转化为 DFA 再匹配，这使得自己生成的测例有一定可能在 C++ 标准正则库上消耗极长时间。如果你对testcases和tests中的内容有所修改，请务必在提交到 GitLab 前将这两个文件夹恢复原状，以免过多占用评测机计算资源。
任务¶
阅读model/DFA.h，根据 DFA 接受输入符号串的过程，完成homework/DFA-accept/accept.h中的TODO（仅修改homework/DFA-accept/accept.h文件），使项目通过CI/CD。