正则表达式 DFA 可视化与词法分析演示

词法分析器，根据正则表达式生成 DFA

• 将输入的正则表达式转化为“简化正则表达式”
• 将每一个“简化正则表达式”转化为 NFA
• 将一组 NFA 转化为一个 DFA，使得能依据“匹配字符串长度第一优先”、“匹配规则先后次序第二优先”进行词法分析
• 依据 DFA 将输入的字符串转化为分段结果和分类结果。

其中，输入的正则表达式中可能包含的语法结构有：字符的集合（如 [a-z0-9]）、可选的情形（即 r?）、多种循环（即 r* 与 r+）、字符串（如 "ab\n")、单字符、并集与连接；“简化正则表达式”中可能包含的语法结构有字符的集合、空字符串、星号表示的循环（即 r*）、并集与连接。

本项目实现了从「前端正则表达式」到「简化正则表达式」再到 NFA / DFA 的完整转换，并提供：

• 词法分析演示程序：lexer_test.exe
• DFA 可视化程序：dfa_visualizer.exe（直接生成 PNG，无需 Graphviz / dot）

功能概览

• 解析支持的前端正则语法：
  • 字符集合：如 [a-z0-9]
  • 可选：r?
  • 循环：r*、r+
  • 字符串："ab\n"
  • 单字符：a
  • 并集：r1 | r2
  • 连接：r1 r2
• 简化正则语法：字符集合、空串、星号、并集、连接。
• 自动从简化正则构造 NFA，再合并并转为 DFA。
• DFA 可视化：
  • 状态为圆，接受态双圈，编号从 1 开始。
  • 边合并同向多字符为单条边，标签显示集合或区间（如 [a-z]）。
  • 自环为从圆出发回到圆的曲线，带箭头。
  • 起始态箭头标注 INIT。
  • 边默认直线，若会穿过其他节点则自动弯曲绕行，标签跟随路径中点。
  • 随机力导向布局（可复现需固定随机种子），节点避免过于靠边。
• 交互式可视化：多次输入正则，依次生成 dfa_<n>.png。

目录结构

• main.c：词法分析演示入口（调用已生成的 DFA 对输入做分段与分类）。
• lexer.c/.h：正则简化、NFA 构造、NFA 合并与 DFA 转换、词法分析实现。
• lang_functions.c/.h：正则与自动机的基础数据结构与构造函数。
• dfa_visualizer.cpp：DFA 可视化，解析正则、生成 DFA 并绘制 PNG。
• Makefile：构建两个可执行文件。
• requirements.txt：依赖与使用说明（无需 Graphviz）。
• DFA可视化测例：包含10个DFA的可视化，在txt里写了正则表达式

环境与依赖（Windows）

• MinGW-w64 工具链：gcc / g++（支持 -std=c++17）。
• GDI+ 头文件与库（随 Windows SDK / MinGW-w64 提供）。
• make（如 mingw32-make）。
• 不需要 Graphviz / dot。

构建

在项目根目录执行：

make

生成：

• lexer_test.exe
• dfa_visualizer.exe

清理：

make clean

使用说明

DFA 可视化

.\dfa_visualizer.exe

• 按提示输入正则，输入 quit 退出。
• 每次输入会生成 dfa_<n>.png，包含状态编号、接受态双圈、起始箭头 INIT，边合并并标注字符集合。
• 对自环与普通边自动布置箭头、曲线与标签，避免穿过节点。

词法分析演示

.\lexer_test.exe

• 使用 create_default_rules 里的规则，依次对预设测试串分段并标注类别。
• 可在源码中调整测试用例或直接输入。（默认 10 条：空白、标识符、整数、运算符、比较、括号、标点、符号、字母、数字）。

支持的正则语法细节

• 字符集合：[a-z0-9]，范围与逐字符可混用。
• 字符串字面量："abc\n"
• 可选 / 星号 / 加号：?、*、+ 为后缀运算。
• 并集：|；连接为默认相邻。

可视化布局与风格

• 随机力导向布局，初始点集中于画布中部，迭代斥力/引力。
• 边直线为主，检测到会穿过其他节点时改为轻微弧线。
• 标签在实际绘制路径的中点，自环标签放在曲线中段。
• 字体：节点 Arial 15 加粗；边与自环标签 Arial 14；起始箭头标签 Arial 12 加粗。
• 画布尺寸：1400x900，节点半径约 34。

已知注意事项

• 力导向带随机性，如需复现可在 force_layout 中固定随机种子。
• 大量节点时可能仍有局部拥挤，可多次运行获取较分散的布局。
• 仅在 Windows / MinGW 环境下测试，其他平台需替换绘图实现。