回顾之前讲的内容,原理篇重在建立直观理解,帮你建立信心,这是第一轮的认知迭代。应用篇帮你涉足应用领域,在解决领域问题时发挥编译技术的威力,积累运用编译技术的一手经验,也启发你用编译技术去解决更多的领域问题,这是第二轮的认知迭代。而为时三节课的算法篇将你是第三轮的认知迭代。
在第三轮的认知迭代中,我会带你掌握前端技术中的核心算法。而本节课,我就借“怎样实现正则表达式工具?”这个问题,探讨第一组算法:与正则表达式处理有关的算法。
在词法分析阶段,我们可以手工构造有限自动机(FSA,或 FSM)实现词法解析,过程比较简单。现在我们不再手工构造词法分析器,而是直接用正则表达式解析词法。
你会发现,我们只要写一些规则,就能基于这些规则分析和处理文本。这种能够理解正则表达式的功能,除了能生成词法分析器,还有很多用途。比如 Linux 的三个超级命令,又称三剑客(grep、awk 和 sed),都是因为能够直接支持正则表达式,功能才变得强大的。
接下来,我就带你完成编写正则表达式工具的任务,与此同时,你就能用正则文法生成词法分析器了:
首先,把正则表达式翻译成非确定的有限自动机(Nondeterministic Finite Automaton,NFA)。
其次,基于 NFA 处理字符串,看看它有什么特点。
然后,把非确定的有限自动机转换成确定的有限自动机(Deterministic Finite Automaton,DFA)
最后,运行 DFA,看看它有什么特点。