本文内容：介绍正则定义，正则表达式，有穷自动机（确定的有穷自动机 DFA，不确定的有穷自动机 NFA）， NFA 转换为等价的 DFA，DFA 的化简，识别单词的 DFA ，典型例题及详细解答。
在前面我们说过，程序设计语言中的大多数单词都可以用正则文法来描述，在这一章中我们将介绍描述正则语言的更紧凑的方法——正则表达式。
正则表达式
语言是一个集合，因此我们可以在语言上进行多种集合运算。比如说并运算，乘积运算（即连接运算），闭包运算等等。
接下来我们看一个语言的例子，如下图所示：
这个语言的字首是字母 a，接下来连接一个任意长度的 a,b 串，再接下来连接一个空串。连接一个空串就代表句子已经结束了。除此之外，我们还可以连接一个点号（.）或者下划线（_）或者一个长度大于等于1 的 a,b串。
这个式子写起来比较复杂，因此我们要介绍正则表达式。
正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表达方式。
例如上面的语言可以用正则表达式来表示，如下图所示。
这个正则表达式表示，句子的第一个符号是字母 a ，接下来连接一个任意长度的 a,b串，再接下来连接一个空串。连接一个空串就代表句子已经结束了。除此之外，我们还可以连接一个点号（.）或者下划线（_）或者一个长度大于等于1 的 a,b 串。
从这个例子中，我们可以看出，正则表达式可以用较小的正则表达式根据特定规则来构建。
每个正则表达式 r 定义（表示）一个语言，记为 L（r）。这个语言也是根据 r 的子表达式所表示的语言 递归 定义的。
正则表达式的定义
- 空串是一个正则表达式，那么它所表达的语言也只包括空串。
- 字母表上的任何一个符号都是一个正则表达式，那么它所表示的语言只包含它本身。
- 假设 r 和 s 都是正则表达式，它们表示的语言分别是 L（r）和 L（s），则
- r|s （r 或 s）也是一个正则表达式，它们表示的语言是 L（r|s）=L（r）∪ L（s）
- rs（r 和 s 的连接）也是一个正则表达式，它们表示的语言是 L（rs）=L（r）L（s）
- r* （r 的克林闭包）也是一个正则表达式，它们表示的语言是 L（r*）=（L（r）） *
- （r）也是一个正则表达式，它表示的语言是 L（（r））=L（r）
例子
例1：假设符号表中有 a,b。则 a 是一个正则表达式，b 也是一个正则表达式。可以推导出以下的正则表达式：
- a|b（a或b）也是一个正则表达式（直接通过正则表达式的定义得到）
- （a|b）( a|b )（a或b 连接上 a或b）也是一个正则表达式。它表示这个串由两个符号构成，第一个符号是 a 或者 b，第二个符号也是 a 或者 b。（因为L（r）可以由 r 的子表达式所表示的语言递归构建而成，所以结合正则表达式的定义也成立）
- a*（a的克林闭包）也是一个正则表达式（直接通过正则表达式的定义得到）a 的克林闭包表示将任意个 a 连接起来。
- （a|b）* （a 或 b 的克林闭包，表示任意长度的 a,b 串）也是一个正则表达式。（递归定义正则表达式）
- （a|a*b）（a或 a的克林闭包b，表示 a 或者 若干个 a 后面连接一个 b）
例2：描述 C 语言中无符号整数的正则表达式
- 十进制整数的正则表达式：第一个符号是1~9中的一个数字，接下来连接若干个 0~9 的数字，或者连接符号 0。
- 八进制整数的正则表达式：第一个符号是数字0，第二个符号是1~7中的一个数字，接下来连接若干个 0~7 中的数字。
- 十六进制整数的正则表达式：第一个符号是0，第二个符号是 x，第三个符号是1~f中的符号，接下来连接若干个0~f 中的符号。
正则语言
可以用正则表达式定义的语言叫做正则语言或正则集合。
正则表达式的代数定律
正则表达式也遵循一些代数定律，如下图所示：
正则文法与正则表达式等价
对于任何一个正则文法 G，存在定义同一语言的正则表达式 r。
对任何正则表达式 r，存在生成同一语言的正则文法 G。
正则定义
为了方便起见，我们可以给某些正则表达式命名，像使用字母表中的符号一样，使用这些名字来构造正则表达式。（这就是正则定义提出的定义和基本思想）
例题
例1：C语言中标识符的正则定义。
第一个正则表达式，表示0~9中的某个数字，我们给它取一个名字，digit
第二个正则表示式，表示一个字母（小写字母或大写字母）和一个下划线。我们给它取一个名字，letter_
接下来我们用起好的这两个名字，来构造第三个正则表达式。
第三个正则表示式，首先是一个 letter_，接下来连接一个 letter _ 或 digit 构成的字符串。这个表达式表示的是字母打头的字符数字串。（正是标识符的定义）
例2：（整型或浮点数）无符号数的正则定义
digit，还是表示一个数字
digits，digit 连接上一个 digit 的克林闭包，表示的是一个长度>=1 的数字串。
optionalFraction，点号（.）后面连接一个 digits 或 这个表达式是一个空串。（这个符号表示的是一个小数部分，或一个空串）代表可选的小数部分。
optionalExponent，大写字母 E 后面连接一个 + （正号）或 一个 -（负号）或直接连接一个长度大于等于1 的数字串（digits），或者这个表达式为空串。可选的指数部分。
number，长度大于等于1 的数字串，连接一个可选的小数部分，连接一个可选的指数部分。
- 当可选的小数部分为空串时，这个表达式为一个整数的若干次幂，如 2E-3
若可选的指数部分为空串时，这个正则表达式为小数。比如说 2.15
若可选的小数部分和可选的指数部分都为空串时，这个正则表达式为整数。比如说 2
- 若可选的小数部分和可选的指数部分都不为空串时，这个正则表达式为指数形式的浮点数。比如说 2.15E+3, 2.15E-3。
- 当指数为正号时，指数是可以省略的，如 2.15E3
有穷自动机 FA
有穷自动机（Finite Automata，FA）由两位神经物理学家Meculoch 和 Pitts 于 1948年提出，是对一类处理系统建立的数学模型。
这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。
系统只需要根据当前所处的状态和当前面临的输入信息，就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。
FA 的典型例子
电梯控制装置
- 输入：顾客的乘梯需求（所要到达的层号）
- 状态：电梯所处的层数+运动方向
- 电梯控制装置并不需要记住先前全部的服务要求，只需要知道电梯当前所处的状态以及还没有满足的所有服务请求。
FA 模型
输入带：用来存放输入符号串
读头：从左向右逐个读取输入符号，不能修改（只读），不能往返移动
有穷控制器：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态。
FA 的表示：转换图
有穷自动机可以用转换图来表示。
转换图
结点：FA 的状态
- 初始状态（开始状态）：只有一个，由 start 箭头指向
- 终止状态：可以由多个，用双圈表示（下例中的 3）
带标记的有向边：如果对于输入 a ，存在一个从状态 p 到状态 q 的转换，就在 p、q 之间画一条有向边，并标记上 a。
在这个图中，一共有4个状态，分别为状态0，状态1，状态2，状态3。状态0为初始状态，状态3为终止状态。
FA定义（接受）的语言
给定输入串 x，如果存在一个对应于 串 x 的从初始状态到某个终止状态的转换序列，则称 串 x 被该 FA 接受。
由一个有穷自动机 M 接受的所有串构成的集合称为是该 FA定义（或接收）的语言，记为 L（M）。
对于 abbaabb来说，我们可以判断是否为这个 FA 所接受。
接受第一个 a后，由初始状态0转换到状态 0，再遇到两个 b 后，依然保持状态 0，遇到下个 a 时，还保持状态 0，再遇到一个 a 时，转换到状态1，接下来两个 b，分别转换到状态2，和最终状态3。
最长子串匹配原则
当输入串的多个前缀与一个或多个模式匹配时，我们总是选择最长的前缀进行匹配。
对于上图来说，当遇到 < 号时，转换到状态1，当遇到 < = 号时，转换到状态2。
即：在到达某个终态之后，只要输入带上还有符号，DFA 就继续前进，以便找到尽可能长的匹配。
有穷自动机的分类
- 确定的有穷自动机（DFA）
- 不确定的有穷自动机（NFA）
确定的有穷自动机 DFA
例子
在这个 有穷自动机DFA 中，
状态集S 包含 4个状态。分别是：状态0， 状态1， 状态2， 状态3。
输入字母表Σ 中包含的元素是 符号a，符号b。
转换函数 δ ，我们用一个转换表来表示。例：状态0 遇到符号 a 时，变成状态1，状态0 遇到 符号 b 时，依旧是状态 0。以此类推，完成转换表。
DFA 的算法实现
- 输入：以文件结束符 eof 结尾的字符串 x，DFA 的开始状态为 s0，接受状态集 F，转换函数 move
- 输出：如果 D 接受 x，则回答“yes”，否则回答“no”
- 方法：将下述算法应用于输入串 x
s=s0;
c=nextChar(); //返回输入串x的下一个符号
while(c!=eof)
{
s=move(s,c); //从状态s出发，沿着标记为c的边所能到达的状态
c=nextChar();
}
if(s在F中)
return "yes";
else
return "no";非确定的有穷自动机 NFA
非确定有穷自动机NFA 和确定的有穷自动机DFA 唯一的区别是：从状态 s 出发，能到达的状态可能有多个。（并不是唯一确定的）
因此，转换函数为集合，而不是元素。
例子
在这个例子中，在初始状态0，遇到符号 a 的时候，它进入的状态包含状态0和状态1 ，两个元素。在状态0 时，遇到符号 b 时，它进入的状态只有 状态 0，因此集合中只有状态 0 一个元素。
如果转换函数 没有给出对应于 状态-输入对的信息，就把空集 放入到相应的表项中。
带有 ε边 的 NFA
在状态 a，不需要遇到任何符号，即可进入状态 b，在状态 b，不需要任何符号，即可进入状态 c。
一旦进入状态 b，就不再接受符号 0，同理，一旦进入状态 c，就不在接受符号 1。
这个带有 空边 的NFA 接受的语言是 由若干个 0 连接 若干个 1 再连接上 若干个 2。（r=0 * 1 * 2*）
带有 ε边 和 不带有 ε边 的 NFA的等价性
不带 空边 的 状态 A：由若干个0构成
不带 空边 的 状态 B：由若干个0 连接 若干个 1 构成
不带 空边 的 状态 C：由若干个0 连接 若干个 1 连接 若干个 2 构成
但是 状态A,B,C 都可以概括为 若干个 0 连接 若干个 1 再连接上 若干个 2 构成。
DFA 和 NFA 的等价性
对任何非确定的有穷自动机 N，存在定义同一语言的确定的有穷自动机 D。
对任何确定的有穷自动机 D，存在定义同一语言的非确定的有穷自动机 N。
DFA 和 NFA 可以识别相同的语言
这两个 DFA 和 NFA 都识别的是以 abb结尾 的 a,b 串。
从正则表达式到有穷自动机
正则表达式是采用符号序列的模式，它可以很直观的描述单词的构成。但在构造分析器时，我们真正实现和模拟的是 DFA。因此这涉及到从正则表达式到有穷自动机的转换。
我们知道，从正则表达式到 DFA 的转换是比较困难的。所以我们通常是 将正则表达式 转换成 NFA ，再将 NFA 转换 成 DFA。
根据 RE 构造 NFA
不停的分解子表达式，即可求得最终的 NFA。
例子
r=（a|b）*abb 对应的 NFA
我们首先将 （a|b)* abb 分解成 4 个子表达式连接的形式。再将 （a|b）* 继续进行分解，最终得到最后结果。
从 NFA 到 DFA 的转换
从 NFA 转换到 DFA 时，我们要构造新的状态。
比如说，在初始状态 a ，遇到符号 a 时，可能继续保持 状态 a，也有可能转换到 状态 b。因此构造新的状态 a,b。
DFA 的每个状态都是由 NFA 中的状态构成的集合，即 NFA 状态集合的一个子集。
从带有 ε 边 的 NFA 到 DFA 的转换
因为 状态 A 不需要任何输入，即可转换成状态 B，状态 C。所有在遇到输入 0时，它既可以是状态 A，也可以是 状态 B，状态 C。后面同理，即可得状态表。
子集构造法
计算 ε-closure 空闭包函数
识别单词的 DFA
识别标识符的 DFA
第一部分识别字母和下划线，第二部分识别字母和下换线和数字 组成的串。
因为这个 NFA 就是 DFA，因此不需要进行转换。
识别无符号数的 DFA
第一部分是长度大于等于1的数字串，第二部分是可选的小数部分（两个子表达式进行或运算得到的），第三部分是可选的指数部分（两个子表达式进行或运算得到的）。
再将 NFA 转换成 DFA，如下图所示。
识别各进制无符号整数的 DFA
识别注释的 DFA
识别 token 的 DFA
词法分析阶段的错误处理
- 词法分析阶段可检测错误的类型
- 单词拼写错误，例：int i=0x3G,float j=1.05e
- 非法字符，例：~@
-
词法错误检测
- 如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序。
错误处理
查找已扫描字符串中最后一个对应于某终态的字符
- 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
- 如果没找到，则确定出错，采用错误恢复策略。
错误恢复策略
最简单的错误恢复策略：“恐慌模式”恢复
从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止。
典型例题及详细解答
答案：D。词法分析器的输出结果是 单词的种别编码和自身值
答案：D。词法分析器不能 发现括号不匹配。
答案：B，不存在 这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。
答案：A，词法分析器的输入是 符号串。
答案：C，两个有穷自动机等价是指它们的 所识别的语言相等 。
答案：C，词法分析器用于识别 单词。
答案：C，正则表达式和等价是指 代表同一正则集。
答案：D。A->A1|A10|0。可看出来是C。第一个数字是0，第二个数字是 0或 10 组成的 任意长度的符号串，第三个数字是1。
答案：C。交换律。
答案：D，aabb。根据输入走自动机，发现不能到终态，即不能识别。
答案：C，有限状态自动机能识别 正规语言。
答案：B，多个初始状态的集合 不是DFA的成分。
答案：D。含偶数个0的二进制数，才能转换到最终状态。
答案：C，定义。
答案：B。可以进行恒等变换。
答案：D。定义。
答案：D。两个DFA等价是指 这两个DFA接受的语言相同。
答案：D。可以进行恒等变换。
答案：C，词法分析器的加工对象是 源程序
答案：C，如果一个正规式所代表的集合是无穷的，则它必含有的运算是 闭包运算“* ”
答案：C，恒等变换。
答案：B。
答案：A。