16 | NFA和DFA：如何自己实现一个正则表达式工具？
该思维导图由 AI 生成，仅供参考
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了如何自己实现一个正则表达式工具，重点讨论了NFA和DFA的原理及其在正则表达式处理中的应用。文章首先介绍了FSA（有限自动机）的概念，包括确定的有限自动机（DFA）和非确定的有限自动机（NFA）的特点。然后详细讨论了如何从正则表达式生成NFA，并介绍了NFA的特点和转换成DFA的过程。作者强调了理解NFA和DFA的重要性，以及它们与正则表达式的等价性。通过本文，读者可以快速了解正则表达式工具的实现原理，以及NFA和DFA在词法分析中的应用，为进一步深入学习提供了基础知识。文章还介绍了如何利用NFA来识别字符串是否符合正则表达式，以及NFA算法的特点和性能问题。最后，提出了将NFA转换成DFA的可能性，以简化字符串匹配过程。整体而言，本文为读者提供了深入理解正则表达式工具实现原理的重要知识，同时也展示了NFA和DFA在实际应用中的潜力和局限性。文章还介绍了如何利用NFA来识别字符串是否符合正则表达式，以及NFA算法的特点和性能问题。最后，提出了将NFA转换成DFA的可能性，以简化字符串匹配过程。整体而言，本文为读者提供了深入理解正则表达式工具实现原理的重要知识，同时也展示了NFA和DFA在实际应用中的潜力和局限性。
《编译原理之美》，新⼈⾸单¥59
全部留言(16)
- 最新
- 精选
刘桢尤雨溪:会编译原理真的可以为所欲为作者回复: 我最近鼓励公司里的一个vue活跃分子学习编译原理，增加成长的后劲。
2020-05-1412
峰老师：为什么NFA要加空转换这样的操作呢，感觉对表达能力并没有扩展。作者回复: 加空转换不是为了扩展表达能力，而是为了能够通过一个简单标准的方法，把正则文法转换成NFA。
2019-09-2228- 漠北感觉很像递归转成动态规划
作者回复: 你离散数学学得不错！
2021-03-304 
xindoohttps://github.com/xindoo/regex 我用java写了个正则引擎，包含了老师这节讲的内容，readme中附了博客，欢迎各位查阅。作者回复: 看到了，很不错！期待你的博客！
2020-05-194
维李设论这里的柯林闭包和js中的闭包有什么关系吗？mdn中的定义是函数及其环境的混合，我理解的是js中的闭包是对理算数学中柯林闭包的扩展，推到极致是可以用集合去解释的，不知道我理解的对不对作者回复: 你是指kleene closure？ 这两个闭包不是一回事。 前者是一个集合运算，也就是我们在正则表达式等场合下常用的*的来源。 后者仅仅指引用了本作用域之外的自由变量。至于是否可以用集合计算来解释，我相信可以。因为整个现代数学的公理化过程（至少是一个流派），都是基于集合理论的。
2020-09-161
芒果讲的深入原理，收益匪浅，NFA转DFA可以用子集法作者回复: 对。 这些算法有兴趣的话，还可以往细里去追究一下，比如深度优先vs宽度优先，时间复杂度，等等。
2020-01-041
醉雪飘痕请问老师，您的图是用什么工具做得呀？编辑回复: 是用Mac自带的Keynote呐~😜
2019-09-221
沉淀的梦想感觉NFA的匹配很适合并行啊，如果对于每个转换条件，开个线程并行匹配，这样就不需要回溯了，是不是能提升不少效率，虽然浪费了一些算力作者回复: 嗯，如果计算机有多余的算力的情况下。
2019-09-2221- 飞翔老师NFA2DFA这个函数的这一行dfaState = findDFAState(dfaStates, nextStateSet);中的nextStateSet是不是应该是calculatedClosures这个？还有，这一节的代码怎么运行啊，一直编不过
作者回复: 我明天抽空检查一下代码库是否存在编译问题，再给你回复。最近有点忙，回复大家迟了点。
2019-09-29 
余晓飞文中代码块 int | [a-zA-Z][a-zA-Z0-9]* | [0-9]* 最后一个字符*应该是+作者回复: get!是小编的问题，谢谢提醒，已更新。
2019-09-28
