Re2DFA

Re2DFA

Regular expression to DFA(Deterministic Finite State)

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

使用方法

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

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

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

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

运行程序:

主页:

MainPage

输入前:

BeforeInput

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

NFA:

NFA

DFA:

DFA

简化DFA:

DFA Simplified

编译方法

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

例如

实现目标

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

概念

@Input

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

字符

名称 类型 描述
字符 Char 代表串中要出现的字符
•支持实字符a~zA~Z0~9
•支持空字符ε

运算符

名称 类型 描述
运算符 Operator 确定正则的运算规则
•支持选择符|
•支持连接符·
•支持重复符*
•支持括号符()
名称 类型 描述
选择符 Operator ab代表两个正则表达式,则a|b代表a或b,即无论是a还是b都能匹配正则表达式
连接符 Operator ab代表两个正则表达式,则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

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

逆波兰到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

    BugFix

    None