regex – 生成具有死亡或多余状态的DFA的正则表达式

前端之家收集整理的这篇文章主要介绍了regex – 生成具有死亡或多余状态的DFA的正则表达式前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我想在我的词法分析器中实现DFA最小化器,但我似乎无法生成看起来不像它已经是表达式的最小DFA的DFA.

我正在使用来自后缀正则表达式的thomson构造构建的NFA构建DFA.这几乎就是龙书中描述的内容.为了使词法分析器使用来自开始状态的epsilon转换来组合几个NFA.正是在这个组合的NFA上应用了DFA算法.

那么,是否有任何“已知”正则表达式将生成一个DFA,它将为死态消除和状态最小化提供一个很好的测试平台?

我当然可以破解一个奇怪的DFA并在其上应用算法,但它不是一个真正的测试用例吗?如果我正在构建DFA的方法不容易出现死状态,那么该信息将同样有价值,因为那时我可以完全跳过实现状态消除功能.

编辑:如果您需要实现详细信息以便准确回答,则代码github上可用,特别是NFA.csDFA.cs类.另外,我在blog posts上写了一个关于我正在使用的构造算法的系列,如果有帮助的话.

好的,所以我发现这是一个完全迂回的方式.我创建了一个可视化正则表达式的工具,因为我的解析器得到了很好的调试输出.这恰当地说明了这样一种表达方式:使用标准的汤普森构造技术会给你一个非常愚蠢的自动机:(a b c)| abc

工具中显示http://regexvisualizer.apphb.com/?Regex=%28a%2Bb%2Bc%2B%29%2B%7Cabc&NfaSize=300&DfaSize=250#

该工具目前执行直接的汤普森结构,没有任何优化.如果删除完全多余的表达式的| abc部分,则表达式应保持不变.它没有.

原文链接:https://www.f2er.com/regex/356938.html

猜你在找的正则表达式相关文章