# 正则表达式转DFA **Repository Path**: RaidenLumine/regular-to-dfa ## Basic Information - **Project Name**: 正则表达式转DFA - **Description**: No description available - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-10-02 - **Last Updated**: 2026-10-20 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 正则表达式转换为 DFA 图（编译原理实验2） 把一条或多条正则表达式走完 **正则 → NFA → DFA → 最小化 DFA → 词法分析源程序** 的整条流水线，界面上同时给出状态转换表和状态图。 ## 目录 ``` src/ 核心算法，对 Qt 一无所知，没装 Qt 也能单独编 gui/ Qt Widgets 界面：上面写正则，下面左边表格、右边状态图 CMakeSettings.json Visual Studio“打开文件夹”的 Debug/Release 配置 ``` ## 架构 ``` [两个入口] gui/main.cpp: main() ├─ 带 --batch → runBatch() ────────────────┐ └─ 不带 → QApplication → MainWindow │ ├─ 编辑框 textChanged │ │ → 防抖 QTimer(400ms) │ │ → analyze() │ └─ analyze() ─────────────────┤ ▼ rtd::runPipeline(const std::string &text) ← 唯一算法入口 │ ┌───────────────┬───────────────┬───┴───────────┬──────────────┐ ▼ ▼ ▼ ▼ ▼ 1 parseProgram 2 buildAlphabet 3 buildNfa 4 subsetConstruct 5 minimizeDfa 6 emitLexer (RegexParser) (Alphabet) (Nfa) (Dfa) (Dfa) (LexerEmitter) │ │ │ │ │ │ └───────────────┴───────────────┴───────► PipelineResult ◄────┴─────────────┘ │ ┌────────────────────────────────┴───────────────┐ ▼ ▼ renderReport()（批处理打印） MainWindow::applyResult()（界面） ├─ TableModel::setTable → QTableView ├─ graphFromDfa/Nfa → GraphView::setGraph └─ codeView->setPlainText ``` ## 依赖 | | | |---|---| | 编译器 | 支持 C++20 的 GCC 11+ / MSVC 19.3+ | | 构建工具 | CMake 3.16+ | | 图形界面 | Qt 6（Widgets）。**不装也能编**，只是没有界面，只剩批处理 | ## 输入语法 每行一条，四种写法： ``` digit=[0-9] 命名定义（宏），不进自动机 ID-101=letter(letter|digit)* 规则，编码 101 Symbol-200C= \+ | - | \* 规则，候选项按书写顺序从 200 开始依次编码 e-5=$ 编码 5，$ 表示空串 ``` 运算符：转义 `\`、连接、选择 `|`、闭包 `*`、正闭包 `+`、范围 `[ ]`（含 `^` 取反、`a-z` 区间）、可选 `?`、括号 `( )`。 几条约定： - 只有写了编码的规则（`名字-编码=`）才算单词规则；没写编码的是命名定义， 会被展开到用到它的规则里。 - 多条带编码的规则之间是"或"的关系，合并成一台自动机。 - 没定义过的名字按字面字符处理（所以 `cat-22=cat` 直接写就行），同时会在 诊断里提示一句。 - 字母表按**字符类**划分：`[A-Za-z]`、`[0-9]` 各占表格的一列，和演示范例 里的 `letter`、`digit` 一致，而不是拆成 62 列。 ## 构建示例 ### Linux ```bash cmake -B build -DCMAKE_BUILD_TYPE=Release cmake --build build --parallel ``` 产物在 `build/bin/RegularToDfa`。装的是发行版的 Qt6 就行；没装 Qt6 的话 CMake 会跳过界面，只编出能跑 `--batch` 的程序。 ### Windows（MSVC + 官方 Qt） 本次实际验证过的环境： | | | |---|---| | Visual Studio | 2026 Community，MSVC 19.51 | | Qt | 6.11.2，套件 `msvc2022_64` | | CMake | 4.4.3（VS 自带的也可以） | Qt 必须选 **MSVC 2022 64-bit** 套件，不要混用 `mingw_64`。如果 Qt 安装在别的目录，改 `CMakeSettings.json` 里的 `CMAKE_PREFIX_PATH` 和 下面命令里的路径即可。 #### Visual Studio 2026（打开文件夹） 1. `文件 → 打开 → 文件夹`，选择项目根目录，不要直接打开 `.sln`。 2. 顶部配置选 `msvc-qt-release`，调试时选 `msvc-qt-debug`。 3. 点“生成”。 4. 运行 `build\msvc-qt-release\bin\RegularToDfa.exe`。 `CMakeSettings.json` 使用 VS 的 CMake 文件夹模式，生成器是 `Visual Studio 18 2026`（x64），`buildCommandArgs` 是 `--target deploy`。 因此 VS 里的“生成”会自动构建程序并执行 `windeployqt`，Qt 运行库会直接 放到 exe 旁边，不需要再手动复制 DLL。 这里没有用 Ninja，是因为你机器 PATH 里的 MSYS2 `c++` 排在 `cl.exe` 前面； VS 的 Ninja 配置如果不强制 `CMAKE_CXX_COMPILER=cl.exe`，很容易误选 GCC， 然后拿 MinGW 编译器去链 MSVC 版 Qt。直接用 VS 生成器可以避开这个问题。 #### 命令行 ```powershell # 如果 build 目录之前用别的生成器配过，先删掉再重新 configure cmake -E remove_directory build cmake -S . -B build -G "Visual Studio 18 2026" -A x64 ` -DCMAKE_PREFIX_PATH=C:\Qt\6.11.2\msvc2022_64 cmake --build build --config Release --target deploy --parallel .\build\bin\RegularToDfa.exe ``` 这里显式指定 `-G "Visual Studio 18 2026"` 很重要：机器上 `PATH` 里的 `cmake` 可能来自 MSYS2，默认生成器是 Ninja；不指定生成器时容易用 MinGW/GCC 去配 MSVC 版 Qt，出现找不到 Qt 或链接失败。 `--target deploy` 会先编译 `RegularToDfa`，再调用对应 Qt 套件的 `windeployqt`，产物在 `build\bin`。如果只想编译、不想部署，去掉 `--target deploy` 即可，但这时直接双击 exe 会提示缺少 Qt DLL。 批处理模式可以这样核对测试数据： ```powershell .\build\bin\RegularToDfa.exe --batch ` .\docs\submit\测试数据\测试输入\08_实验样例_多规则合并.rex ` --out .\build\test-out\08.txt ``` 想双击不弹控制台窗口，配置时加 `-DREGULAR_TO_DFA_WIN_GUI=ON`。这样 `--batch` 的标准输出也看不到，批处理请用 `--out` 写文件。 #### Qt Creator 1. 用 Qt Creator 打开 `CMakeLists.txt`。 2. Kit 选 **Desktop Qt 6.11.2 MSVC2022 64bit**，不要选 MinGW。 3. 选 Release，构建并运行。 Qt Creator 运行时会自己把 Qt 的 `bin` 目录加进环境，所以 IDE 里能跑； 但把 exe 单独拷出去仍然需要部署。可以在 Qt Creator 的构建目录里执行： ```powershell & C:\Qt\6.11.2\msvc2022_64\bin\windeployqt.exe ` --release --no-translations --compiler-runtime ` --dir ``` 或者用命令行构建目录里的 `deploy` 目标： ```powershell cmake --build --config Release --target deploy ``` #### 提交或拷给别人 把整个 `bin` 目录压缩提交，不要只拷 `RegularToDfa.exe`。动态 Qt 程序 至少需要 exe 同目录下的 `Qt6Core.dll`、`Qt6Gui.dll`、`Qt6Widgets.dll` 以及 `platforms\qwindows.dll`；`windeployqt` 会把这些、图片插件、样式 插件和 VC 运行库一起准备好。 如果目标电脑提示缺少 `MSVCP140.dll` 或 `VCRUNTIME140.dll`，运行目录里的 `vc_redist.x64.exe` 安装一次即可。 ### 静态编译单个 exe 官方 Qt 的 `msvc2022_64` 是动态库版本，`REGULAR_TO_DFA_STATIC_QT=ON` 对它不会产生单文件 exe。要单文件，得换成静态 Qt。这里使用 Windows 的 MSYS2，在 UCRT64 shell 里： ```bash pacman -S mingw-w64-ucrt-x86_64-qt6-static cmake -B build -G Ninja -DCMAKE_BUILD_TYPE=Release \ -DCMAKE_PREFIX_PATH=/ucrt64/qt6-static \ -DREGULAR_TO_DFA_STATIC_QT=ON cmake --build build ``` `REGULAR_TO_DFA_STATIC_QT=ON` 会显式导入 Windows 平台插件（静态 Qt 不导入 插件的话，运行时会报 "no Qt platform plugin could be initialized"），并把 libgcc / libstdc++ 一起静态链进来。 ## 清理 cmake 提供了统一的清理命令 ```bash cmake -E remove_directory build ``` 这会同时删掉 `build/msvc-qt-debug`、`build/msvc-qt-release` 等所有配置 目录；下次构建需要重新 configure 和 deploy。