编译原理

发布日期: 2023-05-31

更新日期: 2023-06-25

文章字数: 5.5k

阅读时长: 19 分

阅读次数:

编译原理

编译原理 3：词法分析

第二章中，我们对语言进行了介绍。也正是在第二章中，我们说到，程序设计语言中的大多数单词，都可以用正则文法来描述，即正则文法生成的语言中的句子就是程序设计语言中大多数单词。

本章我们将介绍一种用来描述正则语言的、更紧凑的方法，即正则表达式。

1. 正则表达式

我们上一章定义语言的时候讲到过，语言是句子集合。句子则可以由定义的文法中的开始符号和产生式推导得到。因此可以在语言上进行多种运算，例如：交并补、乘积（连接）、闭包。

例如下面的语言：

语言$L$首先由语言${a}$和${a,b}^*$乘积得到。注意这里a和b都是句子
语言$L$然后再和语言${\varepsilon}$和语言${.}{a,b}{a,b}^*$的乘积进行乘积

语言可以进行交并补运算

用人话来说，语言$L$中的句子是这样构成的：

句首是字符a
然后是任意长度的ab字符串
然后：
- 要么连接空串，表示句子已经结束
- 要么连接,_，然后再连接a+任意长度ab字符串或者b+任意长度ab字符串

A. 正则表达式

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表示方法。

例如上面的语言$L$，用正则表达式描述为：

$r = a(a|b)^*(\varepsilon|(.|\_)(a|b)(a|b)^*)$

其中：

$|$表示或
$^*$表示闭包
$()$表示分组
$\varepsilon$表示结束
$xy$表示拼接

从上面的例子中可以看出：

正则表达式可以由较小的正则表达式按照特定规则递归地构建
每个正则表达式$r$定义（表示）一个语言，记为$L(r)$。这个语言也是根据$r$的子表达式所表示的语言递归定义的

B. 正则表达式的规则（运算）

正则表达式的定义是一个递归的定义，因此我们必须要给出最小正则表达式和递归规则才算给出了完整的正则表达式的定义。

$\varepsilon$是一个RE，且$L(\varepsilon)={\varepsilon}$
字母表上的任意一个符号都是一个正则表达式，且所表示的语言为其本身。即：
$\forall a \in \Sigma, L(a)=\{a\}$
假设$a$和$s$都是RE，表示的语言分别是$L(r)$和$L(s)$，则
- 或：$r|s$是一个RE，$L(r|s) = L(r) \cup L(s)$
- 连接：$rs$是一个RE，$L(rs) = L(r)L(s)$
- 克林闭包：$r^$是一个RE，$L(r^) = L(r)^*$
- 分组：$(r)$是一个RE，$L((r)) = L(r)$

运算的优先级为：克林闭包，连接，或者

我们举一个字符串拼接的正则表达式的例子：

正则表达式的例子

然后我们再给出表示整数的正则表达式的例子：

注意十进制整数正则表达式，$0$和其他数字是分开的

表示整数的正则表达式

C. 正则语言

我们将可以用RE定义的语言叫做正则语言（Regular Language）或正则集合（Regular Set）

D. 正则表达式的代数定律

正则表达式的运算是符合一些代数定律的

正则表达式运算的代数定律

E. 正则文法与正则表达式的关系

实际上，正则文法和正则表达式是等价的，即：

对任何正则文法$G$，存在定义同一语言的正则表达式$r$
对任何正则表达式$r$，存在生成同一语言的正则文法$G$

2. 正则定义

为了方便，我们可以给某些正则表达式命名，而后像使用字母表中的符号一样去使用这些正则表达式，这就是正则定义的思想。

A. 正则定义的定义

正则定义是具有如下形式的定义序列：

$d_1\rightarrow r_1\\ d_2\rightarrow r_2\\ \cdots\\ d_n\rightarrow r_n$

其中：

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

注意，正则定义的关键就是第一条，第一条声明了新的符号，而第二条生命了这个定义序列是新符号到正则表达式的转换

正则定义的本质

B. 正则定义的例子

我们接下来举几个例子

C语言中标识符的正则定义

无符号数：整数&浮点数的正则定义

3. 有穷自动机

A. 介绍

有穷自动机 （Finite Automata，FA）由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型

MeCuloch和Pitts

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。注意状态是对过去输入信息处理状况的概括

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

有穷自动机的经典例子：电梯

B. 有穷自动机模型

有穷自动机由：

输入带，Input Tape
读头，Head
有穷控制器，Finit Control

三部分组成。其模型为

有穷自动机模型

C. 有穷自动机的表示

有穷自动机最核心的就是状态和状态之间的跳转。而从表示状态和状态之间的跳转这一个角度出发的，给出的有穷自动机的表示称为转换图（Transition Graph）。

图中：

结点表示有穷自动机的状态
有向边表示有穷自动机状态的跳转，对应字母表中的符号

转换图是有穷自动机的一种表示

D. 有穷自动机接受/定义的语言

给定输入串$x$，如果存在一个对应于串$x$的从初始状态到某个终止状态的转换序列，则称串$x$被该有穷自动机接收

由一个有穷自动机$M$接收的所有串构成的集合称为是该有穷自动机定义（或接收）的语言，记为$L(M)$

有穷自动机接受的语言

注意，上面这个有穷自动机中，在0状态接收到一个1之后，既可能保持在0状态，也有可能进入到1状态，因此这个有穷自动机是不确定有穷自动机，这个在后面会讲到

若现在已经有有穷自动机（可以以状态图的形式表示，也可以以其他形式表示），输入一个串，如果从初始状态开始租个扫描符号，将符号作为动作，最终能够进入到终止状态，则称这个串与该有穷自动机匹配。

E. 最长子串匹配原则

有穷自动机可以用状态图表示。而检查某个串是否被这个有穷自动机接受就是在其状态图中从起始状态开始，不断经过状态转换，看看最后能否到达终止状态。

然而，输入的串中的子串可能会当输入串的多个前缀与一个或多个模式匹配。此时，总是选择最长的前缀进行匹配。

这样说不太好理解，举下面的例子：

输入串<和串<=
输入串+和串++

给定的以转换图表示的有穷自动机

此时，如果在遇到第一个终止状态就停下的，那么<=就会被识别位<，++被识别为+，就会存在问题。因此，才声明有穷自动机匹配串的时候遵循最长子串匹配原则。

具体在操作上，就是：

最长子串匹配原则

4. 有穷自动机的分类

有穷自动机分为两类：

确定有穷自动机 （Deterministic Finite Automata，DFA）
非确定有穷自动机（Nondeterministic Finite Automata，NFA）

A. 确定有穷自动机 DFA

定义一个有穷自动机为一个五元组

有穷自动机的定义

注意，确定有穷状态机中的转换函数$\delta$是状态机的关键，它直接决定了状态机转换图的外型。

我们接下来给出一个确定有穷自动机的例子：

识别字符串中abb的确定有穷自动机

注意，这里我们用转换函数表示转换函数

B. 非确定有穷自动机 NFA

非确定有穷自动机同样为一个五元组

非确定有穷自动机的定义

注意，非确定有穷自动机和确定有穷自动机唯一的区别有就是转换函数：

确定有穷自动机，$\delta: S\times\Sigma\rightarrow S$
不确定有穷自动机，$\delta：S\times\Sigma\rightarrow 2^S$

也就是说，不确定有穷自动机状态转换的结果有多个可能

同样，我们给出一个不确定有穷自动机的例子：

实际上就是前面介绍有穷自动机时候的例子，只不过加上了转换表

C. DFA和NFA的等价性

DFA和NFA看似是两种有穷自动机，但实际上两者是具有等价性的，等价的地方就在于，DFA和NFA可以识别相同的语言。

形式化的表述为：

对任何非确定的有穷自动机$N$ ，存在定义同一语言的确定的有穷自动机$D$
对任何确定的有穷自动机$D$ ，存在定义同一语言的非确定的有穷自动机$N$

举例而言，这两种NFA和DFA都可以识别以abb结尾的字符串。只不过NFA在0状态遇到a之后需要跳转到状态1

DFA和NFA可以识别相同的语言

而以abb结尾的字符串，是可以使用正则表达式$(a|b)^abb$来表示，因此*正则文法、正则表达式和有穷自动机实际上是等价的。这个我们后面会讲

正则文法、正则表达式和有穷自动机是等价的

此外，也是从上面的例子中我们能看出，等价的DFA和NFA虽然识别的语言相同，但是对于人类来说，NFA更易于理解，比较直观简洁。而对于计算机来说，DFA是更好的实现。

所以各有各的好处

D. 带$\varepsilon$边的NFA

我们前面给出FA定义的时候说过，边一般适合字母表中的符号对应一个边。而我们在定义串的时候说，串是字符的克林闭包，从而产生了空串$\varepsilon$。

因此，$\varepsilon$其实是一个串，而不是符号，因此$\varepsilon \notin \Sigma$，但是有的时候，在NFA的边中引入空边非常有用。

例如下面带空边的NFA：

带空边的NFA

这个带空边的NFA表示：

在状态A只接受0、在状态B只接受1、在状态C只接受2
空边表示不需要接受任何符号就可以进入下一个状态

因此，上面那个NFA接受的语言的正则表达式就是：$r=0^1^2^*$，即若干个0、1、2组成的串

带空边的NFA其实是为了方便人类理解所写的。而我们上面讲过，NFA一定有一个能表示相同语言的DFA与之对应。例如上面的带空边的NFA与之对应的DFA为：

不带空边的DFA和带空边的NFA的对应

注意这里最核心的就是01、12这样的连接处

E. DFA的算法实现

我们前面说了，NFA适合表意，主要用于给人类看；而DFA适合用于算法实现。我们下面出给一个DFA算法实现的例子。

我们现在要设计一个能够识别以文件结束符eof结尾的字符串x的算法。而DFA则可以接受指定模式的串。因此我们这里的算法其实就是DFA的算法实现。

假设我们现在经过设计，得到了一个确定有穷自动机$D$，其开始状态为$s_0$，接收状态集$F$，转换函数$move$。该有穷自动机输入为串$x$，若$D$接受串$x$，则输出yes，否则输出no。

则该DFA的算法实现如下：

DFA算法的实现

算法的关键就是：

move函数的实现
F的实现

5. 正则表达式到确定有穷自动机

我们前面介绍了正则表达式和有穷自动机。我们使用正则表达式去描述一个串的构成，而DFA可以按照上面介绍的框架，很容易的就用算法去实现出来。

因此，如果我们想要让计算机去识别是一个指定模式的串，就需要使用DFA。同样的，我们在构造或者说实现分析器的时候，尽管我们人类使用正则表达式去分析，但是计算机的算法中模拟的也是DFA。

因此我们就需要实现正则表达式到有穷自动机的转换，这就是这一节我们要干的事。

A. 实现

一般来说，我们给定一个RE，然后直接从RE来构造出DFA是比较困难的。

很难从正则表达式直接构建出确定有穷状态机

因此，我们在实现的时候，一般是先从RE中构建出NFA，然后再从NFA构建出DFA

先构建表达正则表达式的NFA，然后再构建表达相同语言的DFA就会简单很多

B. 从RE构建NFA

我们前面介绍了RE的定义。RE的定义是一个递归定义，我们定义了RE的最小元素和RE的运算规则，从而给出了RE的完整定义。

那么如何从RE构建NFA？其实我们就是需要把RE的运算规则使用NFA的状态转换表示出来就好了。

1) 最小RE

首先给出最小RE对应的NFA

最小RE包含空串和符号

2) RE的运算规则

我们接下来给出RE运算规则对应的NFA

RE运算规则对应的NFA

3) RE构建NFA的例子

我们接下来举几个例子来实际运用一下：

首先我们画出初始状态和终止状态，中间有一条边，就是我们的RE
然后把正则表达式进行分解，分解成四个正则表达式连接的格式
继续拆分正则表达式
- 后三个正则表达式已经是最小了，没有办法再拆分了
- 第一个正则表达式拆分克林闭包
然后再把正则表达式的或运算拆分

RE转NFA的第一个例子

这样，给定一个正则表达式RE，我们就能够购进出来对应的NFA

C. 从NFA构建DFA

NFA适合人类阅读，但是不适合计算机的算法实现，因此我们在写代码实现之前需要把NFA转换为DFA。而后根据DFA去设计状态机集合和转换函数，最后实现出来串匹配算法。

1) 转换算法

假设我们给定下面的NFA，我们构建表示相同语言的DFA

NFA的转换图和转换表

首先：

DFA的初始状态和NFA相同
而后NFA处于状态A的时候，如果接受一个符号a，既可能进入状态B，有可能维持状态A。所以此时，我们可以为DFA构建一个新状态AB，来表示在状态A接收到符号a之后进入的状态。
接下来对于NFA，由于其可能处于状态A，也有可能处于状态B。而处于
- 状态A时候接受符号a，那么可能进入到状态A，也可能进入到状态B。
- 状态B时不接受符号a
- 状态A时不接受符号b
- 状态B时接受符号b，那么可能进入到状态B，也可能进入状态C
即NFA接下来可能处于状态B，也可能处于状态C。对应的，DFA的状态AB在接受到符号a、b时候的表现也要和NFA相同。因此为DFA构建新状态BC
同样的分析。对于NFA，接下来可能处于状态B，也可能处于状态C。那么
- 状态B时接受符号b，可能进入到状态C，也可能停留在状态B
- 状态B不接受符号c
- 状态C时接受符号c，可能进入到状态D，也可能停留在状态C
- 状态C时不接受符号b
即NFA接下来可能处于状态C，也可能处于状态D。所以接下来为DFA构建新状态CD