编译原理之美
宫文学
北京原点代码 CEO
46197 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 45 讲
开篇词 (1讲)
编译原理 · 期中考试周 (1讲)
编译原理之美
15
15
1.0x
00:00/00:00
登录|注册

16 | NFA和DFA:如何自己实现一个正则表达式工具?

一课一思
课程小结
把NFA转换成DFA
从正则表达式生成NFA
NFA和DFA
正则表达式工具实现

该思维导图由 AI 生成,仅供参考

回顾之前讲的内容,原理篇重在建立直观理解,帮你建立信心,这是第一轮的认知迭代。应用篇帮你涉足应用领域,在解决领域问题时发挥编译技术的威力,积累运用编译技术的一手经验,也启发你用编译技术去解决更多的领域问题,这是第二轮的认知迭代。而为时三节课的算法篇将你是第三轮的认知迭代。
在第三轮的认知迭代中,我会带你掌握前端技术中的核心算法。而本节课,我就借“怎样实现正则表达式工具?”这个问题,探讨第一组算法:与正则表达式处理有关的算法。
在词法分析阶段,我们可以手工构造有限自动机(FSA,或 FSM)实现词法解析,过程比较简单。现在我们不再手工构造词法分析器,而是直接用正则表达式解析词法。
你会发现,我们只要写一些规则,就能基于这些规则分析和处理文本。这种能够理解正则表达式的功能,除了能生成词法分析器,还有很多用途。比如 Linux 的三个超级命令,又称三剑客(grep、awk 和 sed),都是因为能够直接支持正则表达式,功能才变得强大的。
接下来,我就带你完成编写正则表达式工具的任务,与此同时,你就能用正则文法生成词法分析器了:
首先,把正则表达式翻译成非确定的有限自动机(Nondeterministic Finite Automaton,NFA)。
其次,基于 NFA 处理字符串,看看它有什么特点。
然后,把非确定的有限自动机转换成确定的有限自动机(Deterministic Finite Automaton,DFA)
最后,运行 DFA,看看它有什么特点。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
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-14
    12
  • 老师:为什么NFA要加空转换这样的操作呢,感觉对表达能力并没有扩展。

    作者回复: 加空转换不是为了扩展表达能力,而是为了能够通过一个简单标准的方法,把正则文法转换成NFA。

    2019-09-22
    2
    8
  • 漠北
    感觉很像递归转成动态规划

    作者回复: 你离散数学学得不错!

    2021-03-30
    4
  • xindoo
    https://github.com/xindoo/regex 我用java写了个正则引擎,包含了老师这节讲的内容,readme中附了博客,欢迎各位查阅。

    作者回复: 看到了,很不错!期待你的博客!

    2020-05-19
    4
  • 维李设论
    这里的柯林闭包和js中的闭包有什么关系吗?mdn中的定义是函数及其环境的混合,我理解的是js中的闭包是对理算数学中柯林闭包的扩展,推到极致是可以用集合去解释的,不知道我理解的对不对

    作者回复: 你是指kleene closure? 这两个闭包不是一回事。 前者是一个集合运算,也就是我们在正则表达式等场合下常用的*的来源。 后者仅仅指引用了本作用域之外的自由变量。至于是否可以用集合计算来解释,我相信可以。因为整个现代数学的公理化过程(至少是一个流派),都是基于集合理论的。

    2020-09-16
    1
  • 芒果
    讲的深入原理,收益匪浅,NFA转DFA可以用子集法

    作者回复: 对。 这些算法有兴趣的话,还可以往细里去追究一下,比如深度优先vs宽度优先,时间复杂度,等等。

    2020-01-04
    1
  • 醉雪飘痕
    请问老师,您的图是用什么工具做得呀?

    编辑回复: 是用Mac自带的Keynote呐~😜

    2019-09-22
    1
  • 沉淀的梦想
    感觉NFA的匹配很适合并行啊,如果对于每个转换条件,开个线程并行匹配,这样就不需要回溯了,是不是能提升不少效率,虽然浪费了一些算力

    作者回复: 嗯,如果计算机有多余的算力的情况下。

    2019-09-22
    2
    1
  • 飞翔
    老师NFA2DFA这个函数的这一行dfaState = findDFAState(dfaStates, nextStateSet);中的nextStateSet是不是应该是calculatedClosures这个?还有,这一节的代码怎么运行啊,一直编不过

    作者回复: 我明天抽空检查一下代码库是否存在编译问题,再给你回复。最近有点忙,回复大家迟了点。

    2019-09-29
  • 余晓飞
    文中代码块 int | [a-zA-Z][a-zA-Z0-9]* | [0-9]* 最后一个字符*应该是+

    作者回复: get!是小编的问题,谢谢提醒,已更新。

    2019-09-28
收起评论
显示
设置
留言
16
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部