【编译原理】编译原理知识点汇总·词法分析器（正则式到NFA、NFA到DFA、DFA最小化）

🌈 个人主页：十二月的猫-CSDN博客
🔥 系列专栏： 🏀编译原理_十二月的猫的博客-CSDN博客

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光

1. 前言

2. 词法

2.1 字母表与符号串

2.2 构成符号串（正则表达式）

2.3 正则表达式（新内容）

2.3.1 正规式

2.3.2 正规式的语法规则

2.3.3 正规集

2.3.4 正规式与正规集示例

3. 词法分析（有限状态自动机为主）

3.1 词法分析器的任务

3.2 词法分析器结构（有限状态机的词法分析器）

3.2.1 输入缓冲区

3.2.2 预处理子程序

编辑

3.2.3 扫描缓冲区

3.2.4 扫描仪（装载词法分析器核心分析程序）

3.3 自动机（扫描仪中的核心部分）

3.3.1 不确定自动机NFA（两个节点·第一点）

3.3.2 确定自动机DFA（两个节点·第二点）

3.3.3 自动机的表示

3.3.4 DFA和NFA的区别与联系（两个节点·综合）

3.4 自动机的生成与优化

3.4.1 RE--NFA（三条线·第一线）

3.4.1.1 Thompson算法

3.4.1.2 Thompson算法的应用

3.4.1.3 总结

3.4.2 NFA--DFA（三条线·第二线）

3.4.2.1 子集构造法

3.4.2.2 子集构造法的例子

3.4.3 DFA最优化（三条线·第三线）

3.4.3.1 Hopcroft算法

3.4.3.2 Hopcroft算法的例子

4.习题

5. 总结

1. 前言

为什么打算开始这一系列的文章——编译原理🎄🎄

其实本学期开始就一直想持续更新，陆陆续续主要更新了实验部分。

正好趁着快要考试，便和大家一起花费几天的时间回顾编译原理的知识点。

目前，十二月猫的回顾计划如下🔞🔞：

日期计划	具体任务	完成进度
第一天	概论与文法+词法分析	⏩
第二天	语法分析	📫︎
第三天	语义分析+代码生成	📫︎
第四天	按题型学习	📫︎
第五天	按题型学习	📫︎
第六天	往年题练习	📫︎

祝大家都能取得好成绩呀~~🥰🥰

参考书籍：

英文名：Compilers: Principles,Techniques,and Tools （龙书）🦖

作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman

        1．本课程介绍编译器构造的一般原理和基本实现方法，主要介绍编译器的各个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。

        2．本课程在介绍命令式程序设计语言实现技术的同时，强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。

        3．本课程强调形式化描述技术，并以语法制导定义作为翻译的主要描述工具。

        4．本课程强调对编译原理和技术在宏观上的理解，而不把读者的注意力分散到一些枝节的算法上，如计算开始符号集合和后继符号集合的算法，回填技术等。作为原理性的教材，本书介绍基本的理论和方法，而不偏向于某种源语言或目标机器。

2. 词法

这个话题很有趣😝😝

前面我们已经学习了语法，也就是平常所说的文法。

同时为了理解文法，我们也已经学习了构成单词的词法。

其实按照正常的顺序，我们应该是先学习词法，再来学习文法的，毕竟字母构成单词，单词构成句子嘛~~~😔

但是由于语法分析那一块的内容较多，于是将文法移动到了编译原理概论一块🤯🤯，同时为了理解语法又先把词法的内容也做了涉及。

下面，大家假装不知道，我们简单再来学习一次词法😎😎（肯定是有新内容的，宝，别直接跳了）

单词构成句子，有句子才有语法。

因此想要理解文法，我们只能先来看看词法——单词是如何由字母构成的。

2.1 字母表与符号串

字母表是也就是字母集合，字母就是构成单词的基本。

我们平常所说的单词例如：abandon、abuse🤓，本质都是符号串，因此这里就将研究扩展到符号串，而不仅仅是英语单词。

一句话理解：

字母表：字母构成的集合。
符号：字母表集合中的元素
符号串：符号构成的序列（可以为空）

2.2 构成符号串（正则表达式）

词法研究目的：研究字母如何构成单词抽象化后研究符号如何构成符号串

思考逻辑：如果掌握符号构成符号串的规则，我们就能够知道每一个符号串是否满足构成规则，那么判断符号串是否正确也就不在话下了。

构成符号串：符号运算法则

到这里我们就不难将符号串和符号联系起来了——符号通过运算能够变为符号串

上面这一切运算规则有一个更加高级的名字———正则表达式

✨正则表达式能够将符号转变为符号串 ✨

2.3 正则表达式（新内容）

通过上面的分析，我们已经确定：

字母构成单词需要用到正则表达式。
词法就是字母构成单词的规则。
只有了解词法才能写出好的词法分析器。

因此，这里猫猫带大家来深入看看词法与正则表达式~~🥰🥰

2.3.1 正规式

正规式就是正则表达式

2.3.2 正规式的语法规则

语法规则元素集合：

正规式：辅助字母表中元素的有序组合就是正规式

语法规则：

2.3.3 正规集

定义：正规式所表示的单词构成的集合就是正规集

正规式与符号集：正规式代表一批单词，这些单词构成正规集。也就是前面说的符号集，因为符号串也就是单词

2.3.4 正规式与正规集示例

由此可见正规式能够很好体现单词组成的各种规则~~😇😇

！！！！！！！！！结论：程序设计语言的单词都能用正规式来定义！！！！！！！！！！

其实，用文法也可以把字符转变为单词，但是由于下面将会讲自动机来作为核心处理器件，因此仅仅讲正则式来表示字符转单词。也就是说，如果是手工写词法分析器，更合适的字符转单词形式应该是文法，然后根据文法的一步步推导和产生式去写swich语句完成词法分析。

（如果想更深入了解手写方式，可以看看我在编译原理实验部分的词法分析器：【编译原理】词法分析器设计（山东大学实验一）_山东大学编译原理实验-CSDN博客）

3. 词法分析（有限状态自动机为主）

通过上面的学习，我们已经对文法和词法有了更深入的理解。

词法就是字母如何组成单词———采用正则表达式就可以定义组成规则。

文法就是单词如何组成句子———采用产生式+推导就可以定义文法。

3.1 词法分析器的任务

判断单词是否符合正则表达式的规则。
明确给出合法单词的属性Token（保留字、标识符、运算符、界符、常量等）。

后续语法分析器将拿 单词流+每个单词的Token 放到文法中去判断其是否符合文法规则。

Token内容：

保留字则用数字表示（再到保留字表中查即可）。
数字直接存储其值
标识符保存其值
等等

词法分析器作用：

判断单词的合法性。
简化存储，将后续分析所不需要的内容舍弃。

3.2 词法分析器结构（有限状态机的词法分析器）

3.2.1 输入缓冲区

输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。这个缓冲区的作用就是缓存输入的单词流。

3.2.2 预处理子程序

3.2.3 扫描缓冲区

为了超前搜索的需要。预处理每次处理的是一个字符，处理后就要放入扫描器中进行后续处理。

但是有时候需要对连续几个字符进行联合起来的扫描才有意义，因此需要扫描缓冲区来存储预处理后的字符，最后统一给扫描仪。

例如：

只有搜索过+后面的字符才能判断是++还是+1

假如没有扫描缓冲区：

“+”从预处理程序中出来给到扫描仪。扫描仪还想看下一个字符，于是只好把手头的“+”输出，但是这是不合理的，因为必须要同时看“+”和下一个字符再做输出。

扫描缓冲区的作用：

每一个字符既输入到扫描仪中也放到扫描缓冲区中，如果需要读取下一个字符，则先读取下一个同时不允许扫描缓冲区更新。此时前一个字符从缓冲区中获取，就可以同时看两个字符再做判断了。

3.2.4 扫描仪（装载词法分析器核心分析程序）

自动机形式的词法分析器中的扫描仪就是自动机
手工形式的词法分析器中的扫描仪就是手工编写的扫描代码

这里我们只研究自动机形式的扫描仪💯💯！！！

核心结构：

扫描仪是词法分析器的核心部件，其输入是经过预处理后的单词，同时有缓冲区用来保证其能够超前搜索几个字符一起判断。扫描器的任务就是：

完成一个个单词的合法性判断。
以及完成一个个单词的Token判断。

手写程序的扫描仪的优缺点：

优点：

每一个过程都可控制。
debug过程容易。
词法分析整个过程是白盒的，可以做局部修改让词法分析更准确。

缺点：

每一个程序语言都有一套手写程序的方式，彼此之间没什么可以重用的程序。
手写程序工作量大，都是ifelse处理起来非常复杂

自动机的扫描仪的优缺点：

优点：

所有程序只要给出词法规则，就可以生成一个自动机。
所有单词通过自动机看是否走得到终态就可以判断是否合法。
通过对每一个终态附加状态和功能就可以实现对每一个单词Token的输出。
两个任务的完成整体非常简单并且工程化

缺点：

词法分析的过程是黑盒模型。
词法分析的局部方式不可以修改，完全由自动机生成理论决定。
什么样的正规式就生成什么样的自动机，不可以定制。

或许，现在你对上面的这两个分析会感到无法理解😪😪

没关系，通过下面对自动机的学习我相信大家都能感受到自动机的优缺点的🤓🤓

3.3 自动机（扫描仪中的核心部分）

根据前面的词法分析器结构，我们知道词法分析器中最重要的部分是扫描仪。

扫描仪用来扫描分析单词，有两种制造方法：1、自动机；2、手工编写

这里，我们只研究自动机式的扫描仪而不探讨手工编写要如何实现扫描仪.我们讨论的自动机都是有穷自动机，其定义如下：

有穷自动机是描述特定类型算法的数学方法。
有穷自动机中圆圈表示状态，带有箭头的线表示记录一个状态向另一个状态的转换。

如果想更深入了解手写方式，可以看看我在编译原理实验部分的词法分析器：【编译原理】词法分析器设计（山东大学实验一）_山东大学编译原理实验-CSDN博客

根据扫描仪结构图：

我们接下里要研究两个节点三条线，分别是：

不确定自动机NFA
确定自动机DFA
RE--NFA算法
NFA--DFA算法
DFA--最优DFA算法

3.3.1 不确定自动机NFA（两个节点·第一点）

定义：

记住NFA的五大状态：状态集、字母表、状态转化函数、初始状态、最终状态

例子：

可接受状态：

一句话：一个串t如果能在状态机上走到终态，那么说明串t为状态机接受，也就是符合状态机对应的词法规则。

L(M)：NFA M所能接受的符号串的全体记为 L(M)。

3.3.2 确定自动机DFA（两个节点·第二点）

定义：

和上文相同，DFA和NFA的定义都是五条要求

可接受状态：

确定性：

DFA和NFA最大的区别就是：确定性，DFA是确定的，NFA是不确定的

我们更喜欢确定的DFA，因为这样我们在输入一个串t后，根据串t的每一个字母我们才能够确定性的找到下一个状态。NFA的不确定性让状态转化也是不确定的，这就会让我们在一个串t走不到终态时不能肯定是选择路径问题还是串是无法被接受的。

3.3.3 自动机的表示

自动机的表示（状态转换图、有向图）：

自动机可以以多种形式存在于编译器中，其中两种常见的形式是：

图形表示：状态转换图可以在纸上画出，或者以图形的形式在计算机中呈现。在图形中，每个状态用节点表示，每条边表示状态之间的转换关系。边上标记的字符表示触发状态转换的输入字符。
数据结构表示：在计算机程序中，状态转换图可以用数据结构来表示。常见的数据结构包括有限状态自动机（Finite State Automaton）和状态转换表（Transition Table）。有限状态自动机是一种抽象的数学模型，可以用于表示状态和状态之间的转换关系。状态转换表是一种表格形式的数据结构，用于存储状态转换图的信息，包括当前状态、输入字符和下一个状态。

例子（左边为状态转化表；右边为图表表示）：

状态转换图由两部分构成：

状态：表示在词素识别过程中可能出现的情况。
可以看作是对前一部分字符串处理情况的总结；
某些状态为接受状态或最终状态，表明已找到词素；
加*的接受状态表示最后读入的符号不纳入词素；
开始状态 (初始状态)：用start边表示。
边：从一个状态指向另一个状态。
边的标号是一个或多个符号；
若当前状态为s，下一个输入符号为a，就沿着从s离开，标号为a的边到达下一个状态。

3.3.4 DFA和NFA的区别与联系（两个节点·综合）

前面提过，有限状态机本质上和状态转换图相同，但有限自动机只回答Yes/No（可以进行修改让其还能反映状态）。有限状态机分为两类：

非确定有限自动机（NFA）：对边上的标号没有限制，一个符号可以出现在离开同一个状态的多条边上，ϵϵ可以做标号。
确定有限自动机（DFA）：对于每个状态以及每个标号，有且只有一条边（或最多只有一条边）。

两种自动机的功能是一致的，前者能识别的模式后者也一定能识别；同理亦然。

NFA：

一个自动机接受的输入串，当且仅当存在一条从开始状态到某个接受状态的路径，且该路径各条边上的标号按顺序组成该串。

同理，自动机接受的语言就是从开始状态到达接受状态的所有路径的标号串的集合。

NFA的定义包括如下部分：

一个有限的状态集合
一个输入符号集合
转换函数
一个被指定的开始状态
一组被指定为接受状态的接受状态集合

一个NFA的示例（包括正则、NFA图和转换表）如下：

DFA：

DFA是一种特殊的NFA，他们的差异在于：

没有ϵϵ的转换
不会有多个离开统一状态的相同标号的边

显然，判断一个串能否被DFA接受要比NFA更高效；而且每一个NFA都有与之等价的DFA存在。

3.4 自动机的生成与优化

通过3.3自动机的学习，我们已经知道自动机是什么，也知道了自动机的作用。

是什么：正规式生成的状态转化机

作用：判断串是否被正规式接收

回想我们前面的任务1——判断单词是否合法 ，这个任务也就是判断单词是否被正规式接收。于是我们断定这个自动机能够很好的解决我们的需要，那么问题就来了🙈🙈。

我们要如何得到正规式的自动机呢？
得到的自动机如何保证一定是DFA的？（因为NFA不确定）
DFA能否进一步优化呢？

下面我们就来针对这三者来讲讲~~💞💞

3.4.1 RE--NFA（三条线·第一线）

主要内容：

正则式和NFA是等价的。
NFA可以转化为正则式。
正则式可以转化为NFA。

定理（L前面提过：语法构成的广义上的语言）：

3.4.1.1 Thompson算法

通用原则：

一个圆圈前加一个箭头表示初始状态，两个圆圈表示终结状态，中间用箭头连接，箭头上标明要输入的字符
初始态和最终态只有一个（保证简单性），因此有时候会刻意加上终态和初态去连接。

规则：

1. 对于 ε，构造为

2. 对于a （输入的字符以a为例），构造为

3. 对于 a | b，构造为

4. 对于 ab，构造为

5. 对于 a* = a^n | ε，构造为

3.4.1.2 Thompson算法的应用

设正则表达式 1*0(0|1)*, 构造等价的NFA：

3.4.1.3 总结

Thompson算法虽然是针对RE---NFA的，但是本质上也可以调转方向，从NFA---RE也是同样适用的。
到这里，我们就能够从正规式制造出自动机了，离成功更近一步😺😺。但是通过前面的分析我们也知道NFA自动机由于其不确定性，我们是无法直接拿来完成单词合法性判断的💢💢。

3.4.2 NFA--DFA（三条线·第二线）

3.4.2.1 子集构造法

算法描述：

核心函数：

3.4.2.2 子集构造法的例子

将上图根据子集构造法写出状态转换图：

这个图可以换一个等价写法：

到这里就可以画出NFA对应的DFA了（因为状态转换图和DFA等价）

双圈的表示终态，这个是怎么来的呢？

这个是因为在原始的NFA中，9为终态，所以新的DFA中所有包含9的状态都被认为是终态。看状态转换图1、2、3、4、5都包含9状态，因此都是终态。

子集构造法生成的DFA不一定是最简的，如图所示：

理论上，最坏情况下DFA的状态个数会是NFA状态个数的指数多个。

DFA的接受状态所对应的NFA状态子集中至少包括一个NFA的接受状态。如果其中包括多个对应于不同模式的NFA接受状态，则表示当前的输入前缀对应于多个模式，存在冲突，解决方式：找出第一个列出的这样的模式，将该模式作为此DFA接受状态的输出。

因此，我们还需要对DFA进行优化处理，使其状态最少~~

3.4.3 DFA最优化（三条线·第三线）

最小化DFA的基本问题是状态之间的可区分关系：

如果存在串x，使得从状态s1和s2，一个到达接受状态，而另一个到达非接受状态，那么x就区分了s1和s2
对于两个状态s1s1和s2s2，如果存在某个串区分了s1s1和s2s2，我们说s1s1和s2s2是可区分的，否则它们是不可区分的

可区分状态可以理解为两个（或多个）状态根本不是一类，根据下一个输入的符号，不同状态得到的结果可能会出现不同。而不可区分状态就是，这两个（或多个）状态，无论下一个接收的符号是什么，得到的结果都是一样的。

简单来说：DFA中有很多状态看起来是不同的，但是在状态转移中是一样的，因此本质上属于一个状态，可以合并

3.4.3.1 Hopcroft算法

Hopcroft算法的基本思想，要理解需要对抽象代数略作回忆：

发现：原DFA状态之间的“不可区分”关系满足自反、对称、传递三个性质，因此是等价关系。
先确定状态，首先构造新DFA的两个状态，分别对应原DFA的接受状态集合和非接受状态集合，这两个集合肯定不是等价类；Hopcrof算法的目标（也是过程）就是根据每个集合中原DFA状态之间是否可区分，将之分裂，直到每个集合都成为（基于不可区分关系的）等价类为止。
再确定转换，即根据原DFA中状态之间的转换关系，确定新DFA状态之间的转换关系