Re2DFA

Regular expression to DFA(Deterministic Finite State)

项目地址：https://github.com/LetMeFly666/Re2DFA

使用方法

在正则表达式输入框输入正则表达式后，点击“转换”即可。

当前字符、运算符支持范围详情请点击查看。

若输入不合法等导致程序出错，DFA等栏目将会显示默认状态。详情请看错误码

以“第一个字符为0，最后一个字符1，由0和1组成的字符串”为例：

运行程序：

主页：

输入前：

输入0(0|1)*1并点击转换：

NFA：

DFA：

简化DFA：

编译方法

在VS中添加QT插件，配置好QT环境后，F5编译运行即可。

例如

• 0(0|1)*1
• 1|(0(0|1)*1)*
• (a|b)*ab(a*|b)
• a((a|d)*(a|d)|ε)

实现目标

输入正则表达式，程序绘制出对应的简化DFA

概念

• 正则表达式
• 字符
• 实字符
• 空字符
• 运算符
• 选择符
• 连接符
• 括号符
• 重复符
• 错误码

@Input

名称	类型	描述
正则表达式	String	代表正则表达式的字符串，包括数个字符和运算符。

字符

名称	类型	描述
字符	Char	代表串中要出现的字符 •支持实字符a~z、A~Z、0~9 •支持空字符ε

运算符

名称	类型	描述
运算符	Operator	确定正则的运算规则 •支持选择符| •支持连接符· •支持重复符* •支持括号符()

名称	类型	描述
选择符	Operator	若a和b代表两个正则表达式，则a|b代表a或b，即无论是a还是b都能匹配正则表达式
连接符	Operator	若a和b代表两个正则表达式，则a·b代表a后b（·可省略，a·b等价于ab），即若一个串能从某处分成两串，使得前串匹配a且后串匹配b，则此串能匹配a·b
重复符	Operator	若a代表一个正则表达式，则a*代表数个a（个数n≥0），即若一个串能分成数个串，使得每个串都匹配a，则此串能匹配a*
括号符	Operator	若a代表一个正则表达式，则(a)等价于a。括号符不能拆开单独使用，但括号符可以提高优先级

优先级 () > * > · > |

错误码

为了使得用户输入错误表达式时程序不至于崩溃，程序具有了一定程度上的纠错功能。

目前支持以下错误处理：

值	类型	描述
0	Int	无误
1	Int	)找不到(
2	Int	双目运算符无法出栈两个NFA
3	Int	单目运算符无法出栈单个NFA
4	Int	NFA构建完毕后栈中FNA个数不为一
5	Int	出现不受支持的字符
6	Int	内置文件丢失
7	Int	无写文件权限

实现思路

输入的正则表达式 → 添加上省略的· → 转换为逆波兰表达式 → 转为NFA → 可视化显示NFA → NFA转为DFA(并可视化) -> 简化DFA(并可视化)

添加上省略的·

有以下情况需要在中间添加· ：

· ：194|183

ε ：206|181

程序内部用 . 代表 · ，用 , 代表 ε

• ab
• a(
• )a
• *b
• *(

逆波兰到NFA

构建NFA

构建NFA栈，从左到右遍历逆波兰表达式：

• 遇到字母：构建基本NFA入栈
• 遇到运算符：出栈相应数量的NFA，构建新的NFA入栈

最终栈中剩且仅剩下一个NFA记为最终的NFA

NFA的可视化

这里本来准备尝试使用GraphViz。但是放弃的原因有两点：

1. C语言不好配置GraphViz的头文件等，若直接调用编译好的dots.exe则Release需要增加20多M

2. GraphViz生成的图像不太好控制大小方向，且似乎没有颜色

当成功让QT显示了html 且 成功用js生成mermaid图后，决定使用此项目(https://github.com/mermaid-js/mermaid)的js将程序生成的源码转成图像。

在此对开源项目的开发者致敬！

NFA转为DFA

思想： λ（ε）合并、符号合并

初态：Start的ε闭包

每次：走一个Char后求闭包

一个新的状态集为一个DFA

简化DFA

思想： 将等价状态合并。

等价状态： 初态在同组，经过相同的路径到达的节点也在同组。

初始分组： 初始状态将“End节点”、“非End节点”划分为2组。

编程过程注意：

若采用map<DFA*, int>来记录每个DFA对应的组号，则迭代过程中要注意不同DFA是否为同组的问题。包括但不限于：

1. 起始状态不在同组但经过相同字符能到达同组的DFA不能划分为同组

2. 由组中不在终态的节点建立的节点的isEnd是false，但同组有End节点的话应修改新节点的isEnd为true。（在1.的条件下似乎不会有2.的情况出现）

Release

How To Release

打包QT程序所需依赖

1. QT所需

windeployqt Re2DFA.exe

其中 windeployqt 可以直接打开QT的命令行来使用。或者找到自己电脑上windeployqt.exe的位置。例如我电脑QT安装目录是F:\OtherApps\Program\QT\Apps，安装版本是msvc2017 x64 5.14.2，那么我电脑上windeployqt.exe就在：F:\OtherApps\Program\QT\Apps\5.14.2\msvc2017_64\bin\windeployqt.exe

"F:\OtherApps\Program\QT\Apps\5.14.2\msvc2017_64\bin\windeployqt.exe" Re2DFA.exe

上述操作最好在一个空的文件夹(With Re2DFA.exe included)中进行。

2. VS所需

然后添加VS编译出来的程序运行所需要的DLL文件，包括但可能不限于：

1. MSVCP140.dll

2. VCRUNTIME140.dll

3. VCRUNTIME140_1.dll

3. html所需

1. DFA_tail.html

2. DFA_head.html

3. initialDFA.html

4. mermaid.min.js

下载发行版

DLL、静态文件等依赖

QT所需

QT.Relaies.zip

VS所需

Dlls.Because.of.Visual.Sutdio.zip

静态文件

HtmlAndJs.zip

发行版

v0.0.1-x64

v0.0.1-x64-Release.zip

v0.0.1-x64-Release.zip镜像地址

单文件：Re2DFA.exe

Source code (zip)

Source code (tar.gz)

TODO

ForBetter

• 正则表达式与运算过多时，生成的SVG图片可能水平宽度过大，导致图片上的字体非常小

• 生成的SVG图片无法上下居中（若上下居中，则竖直高度过高时可能无法上下滑动导致内容显示不全）

• 便捷输入的各个字符按钮点击后只会将字符插入到输入框末尾，而不能插入到光标所在位置

• 便捷输入的各个字符按钮点击后不会自动聚焦到输入框，而是需要再次点击输入框才能继续按键输入

• 在缩放比例不是100%的Windows系统上，字体大小会发生变化

• 程序界面大小固定，不可放大。

BugFix

None