编译原理

持续更新…

一、概述

一个编译器的结构

• 词法分析：词法分析（lexical analysis）是编译器的第一个步骤，它负责读入组成源程序的字符流，并将它们组织成为更有意义的词素（lexeme）序列，对于每个词素，词法分析器产生一个二元组形式的词法单元（token）作为输出
• 语法分析：语法分析（syntax analysis）使用由词法分析生成的词法单元来构建树形的中间表示，通常为一个语法树（syntax tree）
• 语义分析：语义分析器（semantic analyzer）使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。 它可时也收集类型信息，并提这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用
• 中间代码生成器
• 代码优化器
• 代码生成器

二、词法分析

1 词法分析介绍

1.1 词法分析的主要任务

词法分析是编译的第一个阶段。它的主要任务是读取源程序的输入字符，识别出各个单词，将它们组成词素，生成并输出一个词法单元（token）。词法分析器通常要和符号表进行交互，当词法分析器发现了一个标识符的词素时，它将这个词素添加到符号表中。在某些情况下，词法分析器也会从符号表中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元。

另外，在读取源程序字符的过程中，词法分析器还会做一些额外工作，比如：

• 过滤掉源程序中的注释和空白（如换行符、空格、制表符等用于分割词法单元的字符）
• 将编译器生成的错误消息与源程序的位置关联（如记录下遇到的换行符个数，以便给予每个错误消息一个行号）

因此，词法分析器可以分为两个原子模块：

1. 扫描阶段
2. 词法分析阶段

1.2 词法单元、模式、词素

词法分析中首先要了解三个相关但有区别的术语：

• 词法单元：是一个由词法单元名（种别码）和一个可选的属性值组成：

  token<词法单元名，属性值>

  其中：

  • 词法单元名是一个表示某种词法单位的抽象符号，类比于英文的名词、动词、形容词一样，常见的词法单元名如：关键字if、else，常量int、float等。
  • 属性值是可选的，比如，关键字if是程序设计中的唯一标识，事先已经确定，则不需要属性值；而常量0、1都能和词法单元名number匹配，但是对于代码生成器而言，需要具体知道number是什么，因此，还需要附加一个描述该词法单元的属性值。

• 模式：描述了一个词法单元的词素可能具有的形式。

• 词素：是源程序中的一个字符序列，它和某个词法单元的模式相匹配，并被词法分析器识别为词法单元的一个实例。

在很多程序设计语言中，词法单元可以总结为如下形式：

词法单元类型	词法单元名	举例
关键字	keyword	if、else、while、for、…
运算符	operator	+、-、*、/、=、…
标识符	identifier	变量名、数组名、…
常量	constant	10、88.88、…
标点符号（分隔符）	separator	{、}、(、)、…

2 串和语言

首先介绍几个基本概念：

2.1 字母表（alphabet）

字母表是一个有限的符号集合，以下例子都是字母表：

• 一个字母表包括英文字母、数字和标点符号
• 一个二进制字母表包括0、1两种数字
• ASCII字符集
• Unicode字符集

2.2 串（string）

串是某个字母表中符号的一个有穷序列。串s的长度通常记作|s|，是指s中符号出现的次数，例如apple是一个长度为5的串；空串的长度为0，用ε（Epsilon）表示。

如果x和y是串，那么x和y的连接xy是指把y附加到x后面形成的串，例如x=dog，y=banana，那么xy=dogbanana；空串ε是连接运算的单元，也就是说，对于任何串s都有sε=εs=s。

如果把两个串的连接看作是“乘积”，则串的指数运算如下：定义$s^0=\epsilon$，并且对于整数$i>0$，有$s^i=s^{i-1}s$，由于εs=s，则有$s^1=s,s^2=ss,s^3=sss...$

2.3 语言（language）

语言是某个给定字母表上一个任意的可数的串的集合。根据这个定义：

• 空集∅是语言
• 空串ε是语言
• 所有语法正确的C程序是语言
• 所有语法正确的英语句子是语言

2.4 语言上的运算

语言上的运算实际上等价于字母表上的运算，在词法分析中，最重要的运算是并、连接和闭包的运算。其中：

• 并运算是集合中的并 $\cup$ 运算
• 连接运算是指：以各种可能的方式，从第一个语言中任取一个串，再从第二个语言中任取一个串，然后将它们连接起来得到的所有串的集合
• 对于一个语言$L$的克林闭包（Kleene closure）记作$L^*$，是指将$L$连接0次或多次后得到的串的集合。对于$L^0$，即将$L$连接0次得到的串的集合，被定义为|ε|，对于$L$被归纳地定义为$L^{i-1}L$
• 语言$L$的正闭包是指$L^*$但不包含$L^0$

闭包closure是什么？todo

举个具体的例子：

令$L=\{A,B,...,Z,a,b,...,z\}$，$D=\{0,1,...,9\}$，前面说过，我们可以用两种方式来考虑$L$和$D$，这两种方式是等价的。一种方法是将$L$看成大小写组成的字母表，将$D$看成是10个数位组成的字母表；另一种方式是将$L$和$D$看作语言，它们中所有串的长度都为一。我们可以通过运算来得到新的语言：

• $L \bigcup D$是字母和数位的集合，令$S=L \bigcup D=\{A,B,...,Z,a,b,...,z,0,1,...,9\}$，则$S$是一个包含62个长度为1的串，每个串是一个字母或者一个数位。（或者说$S$是一个大小写和数位组成的字母表）
• $LD$是包含520个长度为2的串的集合，令$S=LD=\{A0,A1,...,A9,B0,B1...,B9,...,a0,a1,...,z9\}$，则$S$的数量为一个全排列，即$L元素的个数*D元素的个数=52*10=520$。
• $L^4$是所有由四个字母构成的串的集合，令$S=L^{4}=\{AAAA,AAAB,...,zzzz\}$，$S$的数量为$L元素的个数^4=52^4=7,311,616$
• $L^{*}$是所有由字母构成的串的集合（即克林闭包），包括空串ε，一个语言的克林闭包也可以表示为$S=L^{*}=L^0 \bigcup L^1 \bigcup L^2 \bigcup ... \bigcup L^n=\{\epsilon,L^1,L^2,L^3...,L^n\}，其中n为正整数$
• $L(L \bigcup D)^{*}$是所有以字母开头的，由字母和数位组成的串的集合
• $D^{+}$是由一个或多个数位构成的串的集合（即正闭包），不包括空串ε，即$K=D^{+}=D^1 \bigcup D^2 \bigcup ... \bigcup D^n=\{D^1,D^2,D^3...,D^n\}，其中n为正整数$

3 文法

这部分在后续的语法分析中会更加具体地介绍。

3.1 文法定义

这里的定义是指上下文无关文法。

文法描述了一个程序设计语言的层次化语法结构。文法由一个四元组构成：

$$G=(V_T,V_N,P,S)$$

其中：

• $G$是grammar的缩写

• $V_T$是terminal symbol的缩写，即终结符号集合，也被称作上文所述的词法单元（token）。终结符号是指该文法所定义语言的基本符号的集合。

• $V_N$是nonterminal symbol的缩写，即非终结符号集合，也被称作语法变量。它是用来表示一个终结符号串的集合。

• $P$是production的缩写，即产生式集合。它描述了某个构造的某种书写形式，换句话说就是描述了如何将终结符和非终结符组合的方法。

  产生式的形式如下：

  $$A \rightarrow \beta$$

  其中，$A$是产生式头（或左部）的非终结符号，$\beta$是产生式体（或右部）的由终结符和非终结符组成的序列。$\rightarrow$读作“可以具有如下形式”或“定义为”。因此，上述形式整体读作：“$A$定义为$\beta$”。

  其中，$A$中至少包含非终结符中的一个元素。

• $S$是start symbol的缩写，即开始符号。它用来描述文法中“最大的”语法成分。

根据上述定义，我们可以来描述一个if-else语句：

if (expression) statement else statement

即一个条件语句由关键字if、左括号(、表达式expression、语句statement、关键字else、右括号)、语句statement构成。它的产生式如下：

$$statement\;\rightarrow\;if\;(expression)\;statement\;else\; statement$$

其中，关键字if和括号这样的元素就是终结符号，而statement和expression这样的变量为非终结符。

下面用一个简单的例子来看看一个文法的完整书写格式。

我们在小学一年级学过加减法，一个加减法表达式由数位、加号、减号构成。比如3+6、7-1或者6，如果是两个数位，则它们之间必须用+或-相连。该文法的完整定义如下：

$$G=(V_T,V_N,P,S)=(\{+,-,0,1,2,3,4,5,6,7,8,9\},\{expr,digit\},P,expr)\\ P=\{expr\rightarrow\;expr\;+\;digit\\ expr\rightarrow\;expr\;-\;digit\\ expr\rightarrow\;digit\\ digit\rightarrow\;0|1|2|3|4|5|6|7|8|9 \}$$

其中，终结符号为

+ - 0 1 2 3 4 5 6 7 8 9

非终结符号为

expr      digit
表达式      数位

由于expr是整个文法中最大的语法成分，因此开始符号$S=expr$

产生式$P$的定义用白话描述：

表达式定义为表达式+数位
表达式定义为表达式-数位
表达式定义为数位
数位定义为符号0或1或2或3或4或5或6或7或8或9

这里的0,1,2...,9也被称为digit的候选式。

另外，在实际使用上，如果不会引起歧义，我们可以省略文法的其它部分，只保留产生式作为文法的定义。

3.2 文法推导

我们可以通过一个文法从开始符号出发，不断地将某个非终结符号替换为该非终结符号的某个产生式的体。比如，在上文中的文法：

$$expr\rightarrow\;expr\;+\;digit\\ expr\rightarrow\;expr\;-\;digit\\ expr\rightarrow\;digit\\ digit\rightarrow\;0|1|2|3|4|5|6|7|8|9$$

由于digit可以表示从0到9中的任意数位，再根据第三条产生式，单个数位本身就是表达式，而第一条和第二条说明：任何表达式后面跟一个+或-再跟一个数位可以构成一个新的表达式。因此，我们可以推导出9-5+2是一个表达式：

1. 因为9是数位，根据第三条可知，9是表达式
2. 因为5是数位，9是表达式，根据第二条可知，9-5也是表达式
3. 因为2是数位，9-5是表达式，根据第一条可知，9-5+2也是表达式

3.3 文法分类

todo

4 正则表达式

4.1 基本概念

如果要描述C语言所有合法标识符的合集，它差不多就是在2.4中的例子：

• $L(L \cup D)^{*}$是所有以字母开头的，由字母和数位组成的串的集合

唯一不同的是C语言中标识符可以有下划线。

在这个例子中，我们可以首先给出字母$L$和数字$D$集合，然后通过并、连接、闭包运算来描述标识符。正则表达式是一种更紧凑的表示方法，它可以描述所有通过某个字母表上的符号通过运算而得到的语言。

正则表达式可以由较小的正则表达式递归构建，下面两个规则构成了归纳基础：

1. $\epsilon$是一个正则表达式，$L(\epsilon)=|\epsilon|$，即该语言只包含空串
2. 如果$\alpha$是字母表$\Sigma$上的一个符号，那么$\alpha$是一个正则表达式，并且$L(\alpha)=|\alpha|$。也就是说这个语言仅包含一个长度为1的符号串$\alpha$。

假设$r$和$s$都是正则表达式，分别表示语言$L(r)$和$L(s)$，将小的正则表达式构造为大的正则表达式的归纳步骤有如下四步：

1. $(r)|(s)$是一个正则表达式，表示语言$L(r)\cup L(s)$
2. $(r)(s)$是一个正则表达式，表示语言$L(r)L(s)$
3. $(r)^*$是一个正则表达式，表示语言$(L(r))^*$
4. $(r)$是一个正则表达式，表示语言$L(r)$，这一条的意思是在表达式两边加括号并不影响表达式所表示的语言。

另外，为了简化，我们可以将不必要的括号去掉，在去掉括号之前，需要先进行如下约定：

1. 一元运算符$*$具有最高优先级，并且是左结合的
2. 连接具有次高优先级，并且是左结合的
3. $|$运算的优先级最低，并且是左结合的

左结合和右结合的概念是指在相同运算优先级下，操作符对操作数的执行顺序：

如果一个操作符对其操作数是自左向右执行的，则称该操作符是左结合的；

如果一个操作符对其操作数是自右向左执行的，则称该操作符是右结合的；

比如，赋值运算符=是右结合的，a=b=c的运算顺序就是先将c赋值b再将b赋值a。

加法+是左结合的，a+b+c的运算顺序就是先计算a+b再计算(a+b)+c

4.2 使用正则表达式描述语言

现在使用正则表达式来描述语言，令字母表$\Sigma=\{a,b\}$，则：

• 正则表达式$a|b$表示语言$\{a,b\}$
• 正则表达式$(a|b)(a|b)$表示语言$\{aa,ab,ba,bb\}$，即字母表$\Sigma$上长度为2的所有串的集合，也可以用另一个等价正则表达式来描述：$aa|ab|ba|bb$
• 正则表达式$a^*$表示语言$\{\epsilon,a,aa,aaa,...\}$，即所有由零个或多个$\alpha$组成的串的集合
• 正则表达式$(a|b)^*$表示语言$\{\epsilon,a,b,aa,ab,ba,bb,aaa,...\}$，即所有由零个或多个$\alpha$或$b$组成的串的集合
• 正则表达式$a|a^*b$表示语言$\{a,b,ab,aab,aaab,...\}$，即$\alpha$和以$b$结尾的零个或多个$\alpha$组成的串的集合

可以用正则表达式定义的语言叫做正则集合（regular set）。如果两个正则表达式可以表示同样的语言，则称它们等价，例如$(a|b)=(b|a)$，正则表达式遵循一些代数定律，每个定律中两个不同形式的表达式等价。如下图：

4.3 正则定义

为了方便，我们可以给正则表达式命名，之后将这些名字像使用符号一样使用这些名字。如果$\Sigma$是基本符号的集合，那么一个正则定义是具有如下形式的定义序列：

$$d_1 \to r_1\\ d_2 \to r_2\\ ...\\ d_n \to r_n$$

其中：

• 每个$d_i$都是一个新符号，它们都不在$\Sigma$中，并且各不相同
• 每个$r_i$是字母表$\Sigma\cup\{d_1,d_2,...,d_{i-1}\}$上的正则表达式

并且，为了防止递归定义，我们限制每个$r_i$中只含有$\Sigma$中的符号和它之前定义的各个$d_j$，并且，我们可以为每个$r_i$构造出只包含$\Sigma$中符号的正则表达式。比如我们可以首先将$r_2$（它只能使用$d_1$）中的$d_1$替换为$r_1$，然后再将$r_3$中的$d_1$和$d_2$替换为$r_1$和替换之后的$r_2$，以此类推，最终，每个$r_i$中都只包含$\Sigma$中的符号。

前面提到C语言中标识符应该是数字、字母、下划线组成的串，我们用$letter\_$表示字母或下划线，用$digit$表示数位，它的正则定义如下：

$$letter\_ \to A|B|...|Z|a|b|...|z|\_\\ digit \to 0|1|...|9\\ id \to letter\_(letter\_|digit)^*$$

4.4 正则表达式的扩展

下面介绍一种当今仍在使用的扩展正则表达式表示法：

• 单目后缀运算符$+$表示一个或多个，即一个正则表达式及其语言的正闭包。$+$和$*$具有同样的优先级和结合性。
• 单目后缀运算符$?$表示零个或一个，$?$和$*$具有同样的优先级和结合性。
• 字符类。一个正则表达式$a_1|a_2|...|a_n$（$a_i$是字母表中的各个符号）可以缩写为$[a_1a_2...a_n]$，如果它们构成一个逻辑上连续的序列，比如连续的字母，可以表示为$[a_1-a_n]$，因此$[abc]$是$a|b|c$的缩写，$[a-z]$是$a|b|...|z$的缩写。

根据这个扩展表示法，我们可以将上面C语言中标识符的正则定义改为：

$$letter\_ \to [A-Za-z\_]\\ digit \to [0-9]\\ id \to letter\_(letter\_|digit)^*$$

5 词法单元的识别

词法单元识别即根据输入的字符串中找出某个模式匹配的词素。

5.1 状态转换图

作为构造词法分析器的中间步骤，首先将模式转换成具有特定风格的流图，即状态转换图（transition diagram），它有一组被称为状态（state）的结点或圆圈，词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而转换图中的每个状态代表一个可能在这个过程中出现的情况。状态图中的边（edge）从图的一个状态指向另一个状态，每条边的标号包含了一个或多个符号。如下图所示：

图中，每个结点都表示一个状态，并且：

• 有一个开始状态，它由一条没有出发结点的、标号为start的边指明，在读入任何符号之前，状态转换图总是位于开始状态
• 用双圈表示的叫做接受状态（最终状态），如图中标号为3的圆圈，它表示已经找到了一个词素，最终状态可以有多个
• 如果需要回退一个位置，那么我们会在接受状态的附近标上$*$，如果需要回退多个位置，则对应地会附加多个$*$

上图中的状态转换图能够识别正则表达式$(a|b)^*abb$，即由$a$和$b$组成的，以字符串$abb$结尾的语言。我们将结合下一节进行具体介绍。

5.2 有穷自动机

• 有穷自动机（finite automata，FA）由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型
• 这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）
• 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

有穷自动机在本质上与状态转换图类似，但前者只能对每个可能的输入回答“是”或者“否”。

对于一个输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该自动机FA接收（识别、定义）。比如对于上图中的自动机，我们的输入串如果为aabbabb，则前四个字母aabb都可以被状态0接收，之后，对于后三个字母abb，则依次由状态1，2，3接收，由于这个状态转换是从初始状态0到终止状态3，因此输入串aabbabb能够被上图中的自动机接收。另外，在自动机的匹配过程中，当输入串的多个前缀与一个或多个模式匹配时，总是会选择最长的前缀进行匹配，即遵循最长子串匹配原则。

5.3 有穷自动机的分类

有穷自动机FA分为两类

• 不确定有穷自动机（nondeterministic finite automata，NFA）对其边上的标号没有任何限制。一个符号标记离开同一状态的多条边，并且空串也可以作为标号
• 确定有穷自动机（deterministic finite automata，DFA）对于每个状态及自动机输入字母表中的每个符号，有且只有一条离开该状态、以该符号为标号的边

确定和不确定的有穷自动机能识别（接收）的语言的集合是相同的。事实上，这些语言的集合正好就是能够用正则表达式描述的语言的集合，这个集合中的语言称为正则语言（regular language）。

在实践中，我们不会想用正则表达去描述空的语言，但是有穷自动机可以定义空语言，因此，在理论研究中，$\emptyset$被视为一个额外的正则表达式，这个表达式被用于定义空语言。

DFA的完整定义为一个五元组：

$$M=(S,\Sigma,\delta,S_0,F)$$

• $S$为一个有穷的状态集合
• $\Sigma$为一个输入符号集合，即输入字母表（input alphabet）。我们假设空串$\epsilon$不是该集合中的元素
• $\delta$为一个转换函数（transition function），它为每个状态和输入符号中的每个符号都给出了相应的后继状态的集合。即对于$S$中任意的状态$s$，给定任意一个字母表$\Sigma$中的符号$a$，$\delta(s,a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态
• $S_0$为开始状态，或者称为初始状态，它是$S$中的一个状态
• $F$为所有接收状态（接收状态可能不止一个）的集合

对于NFA的定义，与DFA的区别在于：

• $\delta$转换函数中，对于$S$中任意的状态$s$，给定任意一个字母表$\Sigma$中的符号$a$，$\delta(s,a)$表示从状态$s$出发，沿着标记为$a$的边所能到达的状态集合（与DFA相比，NFA所能到达的状态集合不唯一），且字符集中可以包括空串ε

在5.1图中的转换图就描述了这样的一个NFA。因为当读入字符a时，自动机所能进入的状态并不是唯一确定的（可以是状态0，也可以是状态1）。我们可以用一张转换表来描述，如下：

状态\输入	a	b	$\epsilon$
0	{0,1}	{0}	$\emptyset$
1	$\emptyset$	{2}	$\emptyset$
2	$\emptyset$	{3}	$\emptyset$
3	$\emptyset$	$\emptyset$	$\emptyset$

表的各行对应于状态，各列对应于输入符号和空串。对于一个给定状态和给定输入的条目就是将NFA的转换函数应用到这些参数得到的值。如果转换函数没有给出结果，就把$\emptyset$放入对应的表项中。比如，上表中，在状态0输入字符a，自动机所能进入的状态为{0,1}集合，可以是状态0，也可以是状态1，因此也确定了它是一个NFA。

转换表的优点在于我们可以很清楚直观地看到一个给定状态和输入符号所对应的转换，但是缺点在于，如果字母表很大，且大多数状态\输入字符没有对应的转换时，需要填充很多$\emptyset$，这占用了大量无用空间。

对于DFA的转换图，和NFA有一点点区别。DFA没有了ε上的转换动作，且表中的表项没有花括号集合，而是一个确定的状态。如下图的DFA：

它接收的语言与5.1图中的NFA所能表示的语言相同，都是$(a|b)^*abb$，它的转换表如下：

状态\输入	a	b
0	1	0
1	1	2
2	1	3
3*	1	0

如上所述，在DFA的转换表中，没有对于空串的转换动作，且所有的表项都对应确定的状态。

对于一个给定输入串ababb，这个DFA的状态进入序列为0、1、2、1、2、3，对于最后的输入，自动机处于最终状态，因此它回答yes。

我们可以用如下的伪代码来模拟这个DFA：

// s：当前状态
s=s0;
// c：当前字符
c = nextChar();
while(c!=eof){
    // 不断地遍历串，直到结束
    // 根据当前状态和字符，决定自动机的状态
    s=move(s,c);
    c = nextChar();
}
if (s在接收状态集F中) return "yes";
else return "no";

5.4 从正则表达式到有穷自动机

实际上，给定一个正则表达式，则一定能够构造一个DFA，但是，直接构造比较困难。由于一个NFA也能够转化为等价的DFA。且在语法分析实现的层面，我们更倾向于DFA。

我们将首先介绍如何构造一个NFA，然后再将NFA转化为DFA。一般的构造步骤如下：

正则表达式--->NFA--->DFA

5.4.1 从正则表达式构造NFA

现在我们介绍一个从正则表达式构造NFA的Mcmaughton-Yamada-Thompson算法，它可以将任何正则表达式转变为接收相同语言的NFA。

• 算法输入：字母表$\Sigma$上的一个正则表达式$r$

• 算法输出：一个接收$L(r)$的NFA $N$

• 方法：首先对$r$进行语法分析，分解除组成它的子表达式。构造一个NFA的规则，分为基本规则和归纳规则两组。基本规则处理不包含运算符的子表达式，而归纳规则根据一个给定表达式的直接子表达式的NFA构造出这个表达式的NFA。

• 基本规则：对于表达式$\epsilon$，构造出对应的NFA：

  

  这里i是一个新状态，也是这个NFA的开始状态；f是另一个新状态，是这个NFA的终止状态。由i到f之间的有向边ε表示从状态i只需要接收空串就可以到达状态f。

  对于字母表$\Sigma$中的符号$a$对应的NFA：

  

  同样，这里i是一个新状态，也是这个NFA的开始状态；f是另一个新状态，是这个NFA的终止状态。从i到f需要接收一个符号a。

  在这两个基本构造规则中，对于ε和某个a作为r的子表达式的每次出现，我们都是用新状态分别构造出一个独立的NFA。

• 归纳规则：假设正则表达式$s$和$t$的NFA分别为$N(s)$和$N(t)$：

  1. 对于$r=s|t$的NFA，即$N(r)$，可以按照下图方式构造得到。

  

  这里的i和f是新状态，分别是$N(r)$的开始和接收状态。从i到$N(s)$和$N(t)$的开始状态各有一个$\epsilon$转换，从$N(s)$和$N(t)$到接收状态f也各有一个$\epsilon$转换。

  2. 对于$r=st$的NFA，可以按照下图方式构造：

     

     $N(s)$的开始状态变成了$N(r)$的开始状态，$N(t)$的接收状态变成$N(r)$的唯一接收状态。$N(s)$的接收状态和$N(t)$的开始状态合并为一个状态，合并后的状态拥有原来进入和离合并前的两个状态的全部转换。一个路径不可能在离开$N(s)$后再次进入$N(s)$，因此，$N(r)$恰好接收$L(s)L(t)$，它是$r=st$的一个正确的NFA。

  3. 对于$r=s^*$的NFA，可以按照下图方式构造：

     

     这里，i和f是两个新状态，分别是$N(r)$的开始和唯一接收状态，要从i到达f，我们可以沿着标号为ε的路径前进，这个路径对应于$L(s)^0$中的一个串。我们也可以到达$N(s)$的开始状态，然后经过该NFA，再零次或多次从它的接收状态回到它的开始状态并重复上述过程。因此，它可以接收$L(s)^1$、$L(s)^2$等集合中的所有串，因此$N(r)$识别的所有串的集合就是$L(s)^*$。

  4. 最后，对于$r=(s)$，那么$L(r)=L(s)$，我们可以直接把$N(s)$当做$N(r)$。

经过该算法构造的NFA具有如下性质：

• $N(r)$的状态数最多为$r$中出现的运算符和运算分量的总数的2倍，这是因为算法的每一个构造步骤最多只引入两个新状态。
• $N(r)$有且仅有一个开始状态和一个接收状态，接收状态没有出边，开始状态没有入边。
• $N(r)$中除接收状态之外的每个状态要么有一条标号为符号表$\Sigma$中符号的出边，要么有两条标号为$\epsilon$的出边。

下面尝试使用该算法为正则表达式$r=(a|b)^*abb$构造一个NFA。下图展示了$r$的一颗语法分析树：

对于子表达式$r_1$，即第一个$a$，构造如下的NFA：

同理，对于$r_2$：

现在我们可以使用Mcmaughton-Yamada-Thompson算法，将$N(r_1)$和$N(r_2)$合并，得到$r_3=r_1|r_2$的NFA：

$r_4$的NFA和$r_3$相同。$r_5=(r_3)^*$的NFA构造如下图：

现在考虑$r_6$，它是表达式中的另一个$a$，因此，我们的状态必须使用新的而不能重复使用为$r_1$构造的那个NFA：

要得到$r_7=r_5r_6$的NFA，我们应用上述算法，得到如下图所示的NFA：

最终我们得到下图所示的$(a|b)^*abb$的NFA：

5.4.2 从NFA到DFA的转换

我们利用子集构造法的技术，可以将NFA转化为DFA，其基本思想是：让构造的得到的DFA的每个状态对应于NFA的一个状态集合。

• 算法输入：一个NFA $N$

• 算法输出：一个接收同样语言的DFA $D$

• 方法：我们的算法为$D$构造一个转换表Dtran。$D$的每个状态是一个NFA状态集合，我们构造Dtran，使得D"并行地"模拟$N$在遇到一个给定输入串时可能执行的所有动作。我们面对的第一个问题是正确处理$N$的空串$\epsilon$转换。在下表中我们可以看到一些函数的定义，这些函数描述了一些需要在这个算法中执行的$N$的状态集上的基本操作。$s$标识$N$的单个状态，$T$标识$N$的一个状态集合。

  操作	描述
  $\epsilon-closure(s)$	能够从NFA的状态$s$开始只通过$\epsilon$转换到达的NFA状态集合
  $\epsilon-closure(T)$	能够从$T$中某个NFA状态$s$开始只通过$\epsilon$转换到达的NFA状态集合
  $move(T,a)$	能够从$T$中某个状态$s$出发通过标号为$a$的转换到达的NFA状态集合

  我们必须找出当$N$读入了某个输入串之后可能位于的所有状态集合。首先，在读入第一个输入符号之前，$N$可以位于集合$\epsilon-closure(s_0)$中的任何状态上，其中$s_0$是开始状态。下面进行归纳。

  • 假设$N$在读入输入串$x$之后可以位于集合$T$中的状态上，如果下一个输入符号是$a$，那么$N$可以立即移动到集合$move(T,a)$中的任何状态。
  • $N$可以在读入$a$后再执行几个$\epsilon$转换，因此$N$在读入$xa$后可以位于$\epsilon-closure(move(T,a))$中的任何状态上。

  根据这些思想，我们可以得到$D$的状态集合Dstates和$D$的转换函数Dtran，算法如下：

  一开始，ε-closure(s0)是Dstates中的唯一状态，且它未加标记;
  while(在Dstates中有一个未标记状态T){
      给T加上标记;
      for(每个输入符号a){
          U=ε-closure(move(T,a));
          if(U不在Dstates中) 将U加入到Dstates中，且不加标记;
          Dtran[T,a]=U;
      }
  }

  $D$的开始状态是$\epsilon-closure(s_0)$，接收状态是所有至少包含了$N$的一个接收状态的状态集合。我们只需要说明对NFA的任何状态集合$T$计算$\epsilon-closure(T)$，就可以完整地描述子集构造法。这个计算过程是从一个状态集合开始的一次简单的图搜索过程，不过此时假设这个图中只存在标号为$\epsilon$的边，算法如下：

  将T的所有状态压入stack中;
  将ε-closure(T)初始化为T;
  while(stack非空){
      将栈顶元素t弹出栈;
      for(每个满足如下条件的u：从t出发有一个标号为ε的转换到达状态u)
          if(u不在ε-closure(T)中){
              将u加入到ε-closure(T)中;
              将u压入栈stack中;
          }
  }

我们拿5.4.1中的NFA$(a|b)^*abb$来应用上述算法：

一开始，ε-closure(s0)是Dstates中的唯一状态，且它未加标记;

等价NFA的开始状态$A$是$\epsilon-closure(0)$，即能够从状态0出发，只经过标号为$\epsilon$的路径到达的所有状态：$A=\{0,1,2,4,7\}$。由于路径可以不包含边，因此0状态也属于集合A。此时，A是Dstates状态中的唯一状态，且它未加标记，

while(在Dstates中有一个未标记状态T){
    给T加上标记;
    ...
}

进入循环，为$A$加上标记。

for(每个输入符号a){
    U=ε-closure(move(T,a));
    if(U不在Dstates中) 将U加入到Dstates中，且不加标记;
    Dtran[T,a]=U;
}

NFA中的字母表是$\{a,b\}$，因此我们需要分别计算$Dtran[A,a]=\epsilon-closure(move(A,a))$和$Dtran[A,b]=\epsilon-closure(move(A,b))$。

在状态$A=\{0,1,2,4,7\}$中，只有状态2和状态7具有$a$的转换，分别到达状态3和状态8，因此$move(A,a)=\{3,8\}$，则$\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}$，因此我们有：

$$Dtran[A,a]=\epsilon-closure(move(A,a))=\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}$$

我们称这个集合为$B$，得到$Dtran[A,a]=B$。

在状态$A=\{0,1,2,4,7\}$中，只有状态4具有$b$的转换，到达状态5，因此$move(A,b)=\{5\}$，则$\epsilon-closure(\{5\})=\{1,2,4,5,6,7\}$，因此我们有：

$$Dtran[A,b]=\epsilon-closure(move(A,b))=\epsilon-closure(\{5\})=\{1,2,4,5,6,7\}$$

我们称这个集合为$C$，得到$Dtran[A,b]=C$。

经过本轮循环，我们的栈中得到了两个未加标记的集合B和C，继续进行这个算法，

对于状态$B=\{1,2,3,4,6,7,8\}$，需要计算$Dtran[B,a]=\epsilon-closure(move(B,a))$和$Dtran[B,b]=\epsilon-closure(move(B,b))$。

在状态$B=\{1,2,3,4,6,7,8\}$中，仍然只有状态2和状态7具有$a$的转换，因此仍然得到$Dtran[B,a]=Dtran[A,a]=B$；状态4和状态8具有$b$的转换，分别到达状态5和状态9，因此得$move(B,b)=\{5,9\}$，则$\epsilon-closure(\{5,9\})=\{1,2,4,5,6,7,9\}$，因此我们有：

$$Dtran[B,a]=\epsilon-closure(move(B,a))=\epsilon-closure(\{5,9\})=\{1,2,3,4,6,7,8\}=B\\ Dtran[B,b]=\epsilon-closure(move(B,b))=\epsilon-closure(\{5,9\})=\{1,2,4,5,6,7,9\}=D$$

我们称这个新状态集合为$D$，得到$Dtran[B,b]=D$。

继续进行这个算法，对于状态$C$，按照上述方法可得：

$$Dtran[C,a]=\epsilon-closure(move(C,a))=\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}=B\\ Dtran[C,b]=\epsilon-closure(move(C,b))=\epsilon-closure(\{5\})=\{1,2,4,5,6,7\}=C$$

对于状态$D$：

$$Dtran[D,a]=\epsilon-closure(move(D,a))=\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}=B\\ Dtran[D,b]=\epsilon-closure(move(D,b))=\epsilon-closure(\{5,10\})=\{1,2,4,5,6,7,10\}=E$$

对于新状态$E$：

$$Dtran[E,a]=\epsilon-closure(move(E,a))=\epsilon-closure(\{3,8\})=\{1,2,3,4,6,7,8\}=B\\ Dtran[E,b]=\epsilon-closure(move(E,b))=\epsilon-closure(\{5\})=\{1,2,4,5,6,7\}=C$$

至此，没有新状态出现，且这个DFA的所有状态都被加上标记。在这个例子中我们实际构造出5个不同的DFA状态，这些状态、它们对应的NFA状态集以及$D$的转换表如下：

NFA状态	DFA状态	a	b
{0,1,2,4,7}	A	B	C
{1,2,3,4,6,7,8}	B	B	D
{1,2,4,5,6,7}	C	B	C
{1,2,4,5,6,7,9}	D	B	E
{1,2,4,5,6,7,10}	E	B	C

根据转换表，可以得到$D$的转换图如下：

5.4.3 DFA状态数最小化

在上一节我们得到了经由NFA转换的DFA，对于同一个语言，可以有多个可识别该语言的DFA，且这些DFA的状态名称、状态个数都可以不同。在使用上它们都是正确的，但我们总是希望使用DFA的状态数尽可能地少，而状态名称是次要的，它只是一个标识状态的符号而已。如果我们只需改变状态名字就可以将一个自动机转换为另一个自动机，我们就称这两个自动机是同构的。

可以证明，任何正则语言都有一个唯一的（不计同构）状态数目最少的DFA，且从任意一个接受相同语言的DFA出发，通过分组合并等价的状态，我们总是可以构建得到这个状态数最少的DFA。例如，上一节最后构造的DFA就可以将状态划分为{A,C},{B},{D},{E}然后合并等价状态就可以得到这个最小DFA。

下面我们介绍这个将任意DFA转化为等价的状态最少的DFA的算法。该算法首先创建出输入DFA的状态集合的划分。首先介绍一个概念：如果分别从状态s和t出发，沿着标号为x的路径到达的两个状态中只有一个是接受状态，我们说串x区分状态s和t。如果存在某个能够区分状态s和t的串，那么它们就是可区分的。空串ε可以区分任何一个接受状态和非接受状态。

对于上一节中的DFA，如图：

串bb区分状态A和B，因为从A出发经过bb的路径会到达非接受状态C，而从B出发则会到达接受状态E。

DFA状态最小化的的工作原理是将一个DFA状态集合划分为多个组，每个组中的各个状态之间相互不可区分。然后，将每个组中的状态合并成状态最少的DFA的一个状态。算法在执行过程中维护一个状态集合的划分，划分中的每个组内的各个状态尚不能区分，但是来自不同组的任意两个状态是可区分的。当任意一个组都不能再被分解为更小的组时，这个划分就不能再进一步简化，此时我们就得到了状态最少的DFA。

最开始，我们将划分出两个组：接受状态组和非接受状态组。算法的基本步骤是从当前划分中取一个状态组，比如接受状态组A，并选定一个输入符号x，检查x是否可以用于区分A中的某些状态。我们检查A中这些状态在x上的转换，如果这些转换到达的状态落入当前维护的状态集合的不同（两个或以上）划分中，我们就将A分割成多个组，使得这些组中的任意状态在x上的转换都到达同一个划分组。对于所有的输入符号重复这个分隔过程，直到无法根据某个输入符号对任意个组进行分割为止。下面给出这个算法：

• 算法输入：一个DFA $D$，它的状态集合为$S$，输入字母表为$\Sigma$，开始状态为$s_0$，接受状态集为$F$。

• 算法输出：一个DFA $D'$，它和$D$接受相同的语言，且状态数最少。

• 方法：

  1. 首先构造包含两个组$F$和$S-F$的初始划分$\prod$，这两个组分别是$D$的接受状态和非接受状态组。

  2. 应用下面的过程构造新的划分$\prod_{new}$：

     $$最初，令\prod_{new}=\prod;\\ for (\prod中的每个组G)\{\\ 将G划分为更小的组，使得两个状态s和t在同一小组中当且仅当对于所有的输入符号a，\\状态s和t在a上的转换都到达\prod中的同一组;\\ /*在最坏情况下，每个状态各自组成一个组*/ 在\prod_{new}中将G替换为对G进行划分得到的那些小组;\\ \}$$

  3. 如果$\prod_{new}=\prod$，令$\prod_{final}=\prod$并接着执行步骤4；否则，用$\prod_{new}$替换$\prod$并重复步骤2。

  4. 在划分$\prod_{final}$的每个组中选取一个状态作为该组的代表。这些代表构成了状态最少的DFA得状态。$D'$的其他部分按如下步骤构建：

     1. $D'$的开始状态是包含了$D$的开始状态的组的代表。
     2. $D'$的接受状态是那些包含了$D$的接受状态的组的代表。请注意，每个组中要么只包含接受状态，要么只包含非接受状态，因为我们一开始就将这两类状态分开了，而步骤2中的过程总是通过分解已经构造得到的组来得到新的组。
     3. 令$s$是$\prod_{final}$中某个组G的代表，并令DFA$D$中在输入$a$上离开$s$的转换到达状态$t$。令$r$为$t$所在组$H$的代表。那么在$D'$中存在一个从$s$到$r$在输入$a$上的转换。注意，在$D$中，组$G$中的每一个状态必然在输入$a$上进入组$H$中的某个状态，否则组$G$应该已经被步骤2中的过程分割成更小的组了。

让我们重新考虑上节构建的DFA：

按照算法，我们首先将状态划分为两个组{A,B,C,D},{E}，分别为非接受状态组和接受状态组。下面构造$\prod_{new}$，我们考虑输入符号a和b，对于接受状态组，由于它只包含一个状态，不可再被分割，因此{E}原封不动地保留在$\prod_{new}$中。

另一个组{A,B,C,D}是可以被分割的，依照步骤2的算法：对于输入a，这些状态都跳转到状态B，状态B属于$\prod$中的组{A,B,C,D}，因此对于输入a来说，无法区分这些状态。下面考虑输入b，状态A,B,C经过b分别到达状态C,D,C，这些状态都属于组{A,B,C,D}，因此b也无法区分状态A,B,C；但是对于状态D，经过b到达状态E，状态E属于组{E}，而{E}与{A,B,C,D}并不是$\prod$上的同一组，因此我们可以将状态D拆分出来，{A,B,C,D}被替换为{A,B,C}和{D}。这一轮得到的$\prod_{new}$是{A,B,C},{D},{E}，由于出现了新状态，我们需要用$\prod_{new}$替换$\prod$并重复步骤2，进入下一轮。

在下一轮中，我们可以把{A,B,C}分割为{A,C}和{B}，因为状态A,C经过b都到达状态C，属于组{A,C}，而状态B经过b到达状态D，属于组{D}。这一轮中得到的$\prod_{new}$是{A,C},{B},{D},{E}，由于出现了新状态，我们需要用$\prod_{new}$替换$\prod$并重复步骤2，进入下一轮。

在下一轮中，无论经过a还是b，我们都无法分隔{A,C}，这一轮中的状态与上一轮相同：$\prod_{new}=\prod$，令$\prod_{final}=\prod$并接着执行步骤4；

在划分$\prod_{final}$的每个组中选取一个状态作为该组的代表。这些代表构成了状态最少的DFA的状态。我们分别挑选A,B,D,E作为这四个组的代表，其中A为开始状态，E为唯一的接受状态。它的转换表如下：

DFA状态	a	b
A	B	A
B	B	D
D	B	E
E	B	A

由于删掉了状态C，原来DFA中到达C的状态改为状态C所处组的代表的状态，即替换为A。对应的修改为A经过b的转换和E经过b的转换；其他的转换和之前的DFA转换相同。

5.5 练习

下面我们通过编程实现来练习一下这部分的算法。至此为止，我们已经可以实现：

1. 正则转换NFA的算法
2. NFA转换DFA的算法
3. DFA状态数最小化的算法
4. 验证某个串是否被NFA/DFA所接受的算法

这里给出我的代码，点击查看