参考《龙书》

目录

词法分析程序的设计词法分析器剔除空白和注释预读常量识别关键字和标识符 正则表达式 $RE$正规表达式与正规集正规文法 和 正规式正则文法构造正则式正则式构造正则文法 有穷状态自动机 $FA$ (finite automata)有穷自动机的三种表示形式根据 $FA$ 编写词法分析程序 有穷自动机及其与正则文法的等价性有穷自动机的形式化定义$DFA$ 的仿真算法（伪代码描述）$NFA$ 的确定化算法（不带 $\epsilon$ 转换）$\epsilon —NFA$（带有空转换的 $FA$）确定化$FA$ 与正则文法的转化正则文法 $\to FA$$FA\to$ 正则文法 正则式与 $FA$ 的等价性$DFA$ 的化简 ( $DFA$ 的最小化）词法分析器的自动生成模型

词法分析程序的设计

词法分析器

词法分析器从输入中读取字符，并将它们组成 “词法单元对象” 。除了用于语法分析的终结符号之外，一个词法单元对象还包含属性值；词法分析器使得语法分析器不需要考虑词法单元的词素表示方式 $$(词类符号，单词的属性值)$$ 词类符号供语法分析程序使用；单词自身的属性值供语义分析程序使用构成一个词法单元的输入字符序列称为词素 ($lexeme$)

---

需要识别的程序语言单词的分类：

关键字 (保留字或基本字)：if, else…标识符字面常数运算符分界符：,, :, ;…

---

词法分析器的接口设计

词法分析可作为单独一遍来实现 (多遍编译程序) 简化设计；改进编译效率 (词法分析只需要分析3型文法，而语法分析分析的是上下文无关文法)；增加编译系统的可移植性 词法分析程序作为语法分析程序的子程序 (单遍编译程序) 每当语法分析需要一个新的单词符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其单词符号返给语法分析

剔除空白和注释

遇到 空白 (空格、制表符或换行符)，注释 时不断读取输入字符，从而跳过了空白部分 注意：在错误消息中加入行号和上下文有助于定位错误。下面的代码使用 $line$ 统计输入中的换行符个数

预读

在决定向语法分析器返回哪个词法单元之前，词法分析器可能需要预先读入一些字符 例如， 词法分析器在遇到>之后必须预先读入一个字符。如果下一个字符是=，那么>就是字符序列>=的一部分，这个序列是代表>=运算符的词法单元的词素。否则>本身形成了> 运算符，词法分析器就多读了一个字符

---

一个通用的预先读取输人的方法是使用输入缓冲区。词法分析器可以从缓冲区中读取一个字符，也可以把字符放回缓冲区。同时，读取一块字符要比每次读取单个字符更加高效。我们可以用一个指针来跟踪已被分析的输入部分，向缓冲区放回一个字符可以通过回移指针来实现因为通常只需预读一个字符，所以一种简单的解决方法是使用一个变量，比如 peek, 来保存下一个输入字符；当词法分析器遇到不需要预读就能识别的字符时，peek就被设置为空白符。词法分析器在寻找下一个词法单元时会跳过这个空白符。我们假定，当词法分析器返回一个词法单元时，变量peek要么保存了当前词法单元的词素后的那个字符，要么保存空白符 例如，在读入一个数字的数位或一个标识符的字符时，词法分析器会预读一个字符。它在 $1$ 后面预读一个字符来区分 $1$ 和 $10$, 在 $t$ 后预读一个字符来区分 $t$ 和 $true$

常量

将字符组成整数并计算它的数值的工作通常是由词法分析器完成的 因此在语法分析和翻译过程中可以将数字当作一个单元进行处理例如，输入 $31+28+59$ 就被转换成序列 $$<num,31><+><num,28><+><num,59>$$

识别关键字和标识符

识别关键字和标识符的任务也由词法分析器完成；因此，语言的文法通常把标识符当作终结符号进行处理 例如，在处理输入 $count=count+increment;$ 时，词法分析器将其转换为词组单元序列 $$<id,"count"><=><id,"count"><+><id,"increment"><;>$$ 而语法分析器处理的就是终结符号序列 $id=id+id$

---

区分关键字和标识符

关键字通常也满足标识符的组成规则，因此可以将关键字作为保留字。只有当一个字符串不是关键字时它才能组成一个标识符

具体实现方法：用符号表保存字符串 (关键字和已经识别出的标识符)

单一表示。一个字符串表可以将编译器的其余部分和表中字符串的具体表示隔离开，编译器后面的步骤可以只使用指向表中字符串的指针或引用保留字。要实现保留字，可以在初始化时在字符串表中加入保留的字符串以及它们对应的词法单元。当词法分析器读到一个可以组成标识符的字符串或词素时，它首先检查这个字符串表中是否有这个词素。如是，它就返回表中的词法单元，否则返回带有终结符号 $id$ 的词法单元；如果不存在对应的条目，那么由 $id$ 和属性值 $s$ (词素) 组成的词法单元将被加入到字符串表中，并被返回

正则表达式 $RE$

正规表达式与正规集

正规式 / 正则表达式 正规表达式（regular expression）是说明单词的模式（pattern）的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号程序设计语言的单词都能用 正规式 来定义.

---

下面是正规式和它所表示的正规集的递归定义：

设字母表为 $\sum$，辅助字母表 ${\sum }^{\prime }=\{\varnothing ,\epsilon ,|,•,\ast ,(,)\}$ $\epsilon$ 和 $\varnothing$ 都是 $\sum$ 上的正规式，它们所表示的正规集分别为 $\{\epsilon \}$ 和 $\{\}$任何 $a\in \sum$，$a$ 是 $\sum$ 上的一个正规式，它所表示的正规集为 $\{a\}$假定 $e_1$ 和 $e_2$ 都是 $\sum$ 上的正规式，它们所表示的正规集分别为 $L(e_1)$ 和 $L(e_2)$，那么，$(e_1),e_1|e_2,e_1•e_2,e_1^{\ast }$ 也都是正规式，它们所表示的正规集分别为 $L(e_1),L(e_1)\cup L(e_2),L(e_1)L(e_2),(L(e_1){)}^{\ast }$仅由有限次使用上述三步骤而定义的表达式才是 $\sum$ 上的正规式，仅由这些正规式所表示的集合才是 $\sum$ 上的正规集

其中： $|$ 读为“或”（也有使用 $+$ 代替 $|$ 的） $•$ 读为“连接”，一般可省略不写 $\ast$ 读为“闭包”（即，任意有限次的自重复连接） 优先顺序：$\ast$、$•$、$|$

例

设 $\sum =\{a,b\}$， $\sum$ 上的正规式和相应的正规集的例子有： 正规式正规集$a$$\{a\}$$a$ | $b$$\{a,b\}$$ab$$\{ab\}$$a^{\ast }$$\{\epsilon ,a,aa,...\}$$(a$|$b)(a$|$b)$$\{aa,ab,ba,bb\}$$(a$|$b{)}^{\ast }$$\{a,b\}$上的任意串$(a$|$b{)}^{\ast }$$(aa$|$bbb)(a$|$b{)}^{\ast }$${\sum }^{\ast }$上所有含有两个相继的 $a$ 或三个连续的 $b$ 的 $a、b$ 串$(a$|$b{)}^{\ast }abb$以 $abb$ 结尾的 $a、b$ 串

例

$\sum =\{l，d\}$，$l$ 代表字母，$d$ 代表数字。正规式 $r=l(l|d{)}^{\ast }$ 表示标识符

例

$\sum =\{d,.,e,+,-\}$，$d$ 表示 $0$ ~ $9$ 的数字。正规式 $d^{\ast }(.d{d}^{\ast }|\epsilon )(e(+|-|\epsilon )d{d}^{\ast }|\epsilon )$ 表示无符号整数 例如：$3.6e2,471.88e-1$

---

若两个正规式 $e_1$ 和 $e_2$ 所表示的正规集相同，则说 $e_1$ 和 $e_2$ 等价，记为 $e_1=e_2$ 例如：$e_1=b(ab{)}^{\ast },e_2=(ba{)}^{\ast }b$；$e_1=(a|b{)}^{\ast },e_2=(a^{\ast }|b^{\ast }{)}^{\ast }$

设 $r,s,t$ 为正规式，正规式服从的代数规律有：

$r|s=s|r$ 交换律$r|(s|t)=(r|s)|t$ 结合律$(rs)t=r(st)$ 结合律$r(s|t)=rs|rt$ 分配律 $(s|t)r=sr|tr$$\epsilon r=r,r\epsilon =r$ ($\epsilon$为连接运算的幺元)$r|r=r$ ”或“的抽取律 $r^{\ast }=\epsilon |r|rr|\dots$

正规文法 和 正规式

正规文法 即 3型文法 / 右线性文法

正则式（正规式）与正则文法的等价性，即 正则语言可以由正则式定义，也可以由正则文法定义

对任一正则文法，存在一个定义同一个语言的正则式对每个正则式，存在一个生成同一语言的正则文法

正则文法构造正则式

正则文法正则式$A\to xBB\to y$$A=xy$$A\to xA$|$y$$A=x^{\ast }y$$A\to xA\to y$$A=x$|$y$

例

求下列正则文法对应的正则式 $$\begin{array}{r}G[S]:S\to aS|aB①\\ B\to bC②\\ C\to aC|a③\end{array}$$

解

从活符号 $C$ 开始 $$\begin{array}{rl}由③得C& =a^{\ast }a\\ 代入②得B& =b{a}^{\ast }a\\ 代入①得S& \to aS|ab{a}^{\ast }a\\ \therefore S& =a^{\ast }ab{a}^{\ast }a\end{array}$$

例

求下列正则文法对应的正则式 $$\begin{array}{rl}G[S]:S& \to bS|aA①\\ A& \to aA|bB②\\ B& \to aA|bC③\\ C& \to bS|aA|\epsilon ④\end{array}$$

解

由 $①、④$，$C\to S|\epsilon$ 所以 $B\to aA|bS|b,B=S|b$ 所以 $A=aA|b(S|b)=aA|bS|bb,A=S|bb$ 所以 $S=bS|a(S|bb)=(a|b)S|abb$ 因此 $S=(a|b{)}^{\ast }abb$ 即：以 $abb$ 结尾的 $a、b$ 串

正则式构造正则文法

首先对任意给定的正则式，生成产生式 $S\to \gamma$ （ $S$ 是文法的开始符号） 若有规则为重写为$A\to xy$$A\to xBB\to y$$A\to x^{\ast }y$$A\to xA$|$y$$A\to x$|$y$$A\to xA\to y$ 不断利用上述规则做变换，直到每个产生式右部最多包含有一个终极符为止（严格意义的正则文法，可以直接对应相应的有穷状态自动机）

例

将 $R=a(a|b{)}^{\ast }$ 转换为正规文法

解 $$\begin{array}{rl}G[S]:S& \to aA\\ A& \to aA|bA|\epsilon \end{array}$$

例

将 $R=(a|c|ba|bc{)}^{\ast }(b|\epsilon )$ 转换为正规文法

解

令 $\alpha =a|c|ba|bc$ $$\begin{gathered} G[S]:S\to \alpha S|b|\epsilon \\ 即:S\to aS|cS|baS|bcS|b|\epsilon \end{gathered}$$进一步转化为严格意义的正则文法： $$\begin{gathered} S\to aS|cS|bA|bB|b|\epsilon \\ A\to aS \\ B\to cS \end{gathered}$$

有穷状态自动机 $FA$ (finite automata)

有穷自动机作为一种识别装置，它能准确地识别正规集，即：识别正规文法所定义的语言和正规式表示的集合 有穷自动机分为两类：确定的有穷自动机（$DFA$），不确定的有穷自动机（$NFA$）

---

可以把 $FA$ 看作由一个读头和一个有穷状态转换器组成： 它可以从左至右从带上一次读一个字符， 每读一个字符改变一次状态在开始读字符前，$FA$ 处于 开始状态有一些状态指定为 终止状态当 $FA$ 处于终止状态又准备读带右边的字符时，带上的字符串就被 $FA$ 识别或接受，或者说，该串 $\in L(FA)$ (被 $FA$ 所识别的语言)$FA$ 定义了正则语言集合，因此对 $\sum$ 上的任意串 $w$，能够判定它是可接受的还是不可接受的

有穷自动机的三种表示形式

若 $FA$ 处于状态 $q_i$，正在读字符 $a$，而状态应转换为 $q_j$ ，则

状态转换函数 $f:f(q_i,a)=q_j$状态装换图，节点代表状态，弧代表转换，弧上符号代表输入字符 状态转换矩阵 $M:M[q_i,a]=q_j$

例

给出识别语言 $\{以i为首的i，d串\}$ 的 $FA$ 的三种形式

解

状态转换矩阵中，列 $F$ 代表终止状态标记，对应行标记 1 表示该状态为终止状态

例 例

构造一个 $DFA$，它识别的语言为 $$\{x|x\in \{0,1{\}}^{\ast }，且当把x看成二进制数时，xMOD3=0\}$$($x$ 模3与0同余)

解

定义下列状态： $q_0,q_1,q_2$：分别对应除以 3 余数为 0,1,2 的 $x$ 组成的等价类 $q_s$: $FA$ 的开始状态$q_s$ 状态下读入0时，有$x=0$，应进入状态 $q_0$；读入1时，有 $x=1$，应进入状态 $q_1$；$q_1$状态下有 $x=3n+1$。读入0时，$x^{\prime }=2\times (3n+1)=6n+2$。所以，$\delta (q_1,0)=q_2$；读入1时，$x^{\prime }=2\times (3n+1)+1=6n+3$。所以，$\delta (q_1,1)=q_0$…依次分析可以画出下面的 $DFA$：

根据 $FA$ 编写词法分析程序

根据画出的（识别单词的）状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换伪代码： Start: getch; /*读入符号*/ While (ch=' ') do getch ; /*滤掉无用的空格*/ /*每进入一次case语句，都会识别出一个单词符号*/ case char of 'a'..'z': begin While letter or digit do begin concat; getch end; /*连接字符串*/ c:=reserve; /*查保留字表 */ if c=0 then return($ID,val) /*识别到一个标识符*/ else return(c，-) end; /*识别到一个保留字*/ '0'..'9':begin /*以无符号整数为例*/ While digit do begin concat; getch end; /*连接字符串*/ Return($INT, val) end; '+': Return($plus, _); '-': Return($minus, _); ')': Return($rpar, _); '<': begin /*超前搜索： 读取下一个字符,查看这一字符是否为‘=’,若是即为 ‘<=’； 是否为‘>’，若是即为‘< >’；否则为‘<’*/ end; ...... other {′$′, ′@′, ′?′, ′&′, ′^′, ′!′} error (24); /*报告源程序含有非法符号*/ END {of case} goto Start;

有穷自动机及其与正则文法的等价性

有穷自动机的形式化定义

确定的有穷自动机 $DFA$ (deterministic finite automata)

$DFA$ 是一个五元组：$M=（K，\Sigma ，f，S，Z）$

$K$：状态的有穷非空集 (对应文法中的 $V_N$)$\Sigma$：有穷输入字母表 (对应文法中的 $V_T$)$f$：$K\times \Sigma$ 到 $K$ 的一个映射（是单值函数） (对应文法中的 $P$)$S\in K$ 是开始状态 (对应文法中的 $S$)$Z\subseteq K$ 是终止状态集

不确定的有穷自动机 $NFA$ (nondeterministic finite automata)

$NFA$ 是一个五元组：$M=（K，\Sigma ，f，S，Z）$

$K$：状态的有穷非空集 (对应文法中的 $V_N$)$\Sigma$：有穷输入字母表 (对应文法中的 $V_T$)$f$：$K\times \Sigma$ 到 $K$ 的子集 (在离散数学中表示为 $2^K$) 的一个映射 (对应文法中的 $P$)$S\subseteq K$ 是开始状态集 (对应文法中的 $S$)$Z\subseteq K$ 是终止状态集

特别地，对于带空转换的 $NFA$:

$f$：$K\times (\Sigma \cup \{\epsilon \})$ 到 $K$ 的子集的一个映射

注意：$f,S$ 与 $DFA$ 不同

$DFA$ 与 $NFA$ 的两点区别

$NFA$ 可以有多个开始状态$NFA$ 的映射函数值可是多个状态或空集 ($1\to 多或1\to 空$） ($NFA$ 在任意时刻可以处于有穷多个状态)

---

例

构造一个 $DFA$，识别语言 $\{x000y|x,y\in \{0,1{\}}^{\ast }\}$

解

该语言定义的句子都会有三个连续的 0

该语言的正则表达式为 $(0|1{)}^{\ast }000(0|1{)}^{\ast }$。可以看出，$NFA$ 与正则表达式天然同构

例

识别实常数

解

以 $d$ 代表数字，$DFA$ 如图：

例

构造一个 $DFA$，识别语言 $\{0^n{1}^m|n,m\ge 0\}$

解 例

构造 $NFA$，识别语言 $\{x|x为非负偶整数，不允许0开头\}$

解

$NFAM$ 构造如下： 对应正规文法： $$\begin{gathered} S\to D_{1}A|2|4|6|8 \\ {D}_1\to 1|2|3|4|5|6|7|8|9 \\ A\to D_{1}A|0A|0|2|4|6|8 \end{gathered}$$

---

定理

对于任意两个有穷自动机 $M$ 和 $M^{\prime }$，如果 $L(M)=L(M^{\prime })$，则称 $M$ 与 $M^{\prime }$ 是等价的对任意的有穷自动机 $A$，都存在一个确定的有穷自动机 $A^{\prime }$，使得 $L(A^{\prime })=L(A)$。即：$NFA$ 与 $DFA$ 都识别同一语言类，$DFA$ 是 $NFA$ 的特例

$NFA$ 并不比 $DFA$ 识别能力强，但有时描述起来更容易、更自然。但在化为程序时，必须使用 $DFA$

格局运动（表示 $FA$ 识别正则句子的过程） 设 $M=\{K，\sum ，f，S，Z\}$ 是 $\sum$ 上的一个 $DFA$

$K\times {\sum }^{\ast }$上的元素 $(q，w)$ 称为 $K$ 的一个格局 ($w$ 表示待分析的串)如果 $f(q,a)=q’$，则称 $DFA$ 从格局 $(q,ax)$ 进入 $(q’，x)$ 为一次运动。记为 $(q，ax)⊢(q’，x)$，其中：$a\in \sum ,x\in {\sum }^{\ast }$

运动 $⊢$ 是格局上的一个二元关系

例 串 $bdbdd$ 的识别过程 解 $(q_1，bdbdd）⊢(q_2，dbdd)⊢(q_2，bdd)⊢(q_2，dd)⊢(q_2，d)⊢(q_2，\epsilon )$ 或 $(q_1，bdbdd){⊢}^{\ast }(q_2，\epsilon )$ $q_2\in F$，所以 $bdbdd$ 被识别。

$(q_2，\epsilon )$ 也被称为 终止格局

$FA$ 识别的语言

设 $M=（K，\Sigma ，f，S，Z）$是一个 $FA$，如果有 $$(S,w){⊢}^{\ast }(A,\epsilon )，且A\in Z，w\in {\Sigma }^{\ast }$$则称串 $w$ 可被 $M$ 识别$M$ 所识别的 ${\Sigma }^{\ast }$ 上的所有串，称为 $M$ 所识别的语言$FA$ 识别空串 如果开始状态也是终止状态，或是存在一条从初态到某个终止状态的 $\epsilon$ 道路，则空串可被 $FA$ 识别

例 构造 $FA$ 识别由偶数个 $0$ 和偶数个 $1$ 组成的串 解 构造 $FA$ 的状态转换图

于是 $FA$ 记为：$A=(\{S,A,B,C\},\{0,1\},f,S,\{S\})$ $$\begin{gathered} f(S,0)=A,f(A,0)=S,f(B,0)=C,f(C,0)=B, \\ f(S,1)=B,f(A,1)=C,f(B,1)=S,f(C,1)=A \end{gathered}$$

$101$ 能否被识别？ $$(S,101)⊢(B,01)⊢(C,1)⊢(A,\epsilon ),A\notin Z$$因此不能被识别

该语言直接写出文法有些困难，但是写出 $FA$ 之后就可以很方便的构造文法： $$\begin{array}{rl}G[S]:S& \to 0A|1B|\epsilon \\ A& \to 0S|1C\\ B& \to 0C|1S\\ C& \to 1A|0B\end{array}$$

例 构造 $DFA$ 识别含有奇数个1的0、1串

由 $FA$ 的状态转换图，可得正则式 $r=0^{\ast }1(0|10^{\ast }1{)}^{\ast }$ 或者 $r=(0|10^{\ast }1{)}^{\ast }10^{\ast }$

$DFA$ 的仿真算法（伪代码描述）

读入以 $EOF$ 结束的符号串 $x$，按 $DFA$ 的转换函数进行状态转换。如果 $DFA$ 接受 $x$，返回 $YES$，否则返回 $NO$

int smlt_DFA() { int S; char C; S = S0; //开始状态 C = nextchar(); while (C != EOF) { S = move(S, C); // 状态转移函数 move C = nextchar(); } if (S is in Z) return YES; else return NO; }

$NFA$ 的确定化算法（不带 $\epsilon$ 转换）

思路：就像32位的寄存器，在某一时刻，虽然它的每一个位有一个状态（1或0），但这32位组合在一起也是一种状态。因此，可以考虑让 $NFA$ 的一组状态对应 $DFA$ 的一个状态

已知：$NFA{M}_1=(K，\Sigma ，f，S，F)$，且 $\epsilon \notin \Sigma$。求： $DFA{M}_2=(K^{\prime }，\Sigma ，f^{\prime }，S^{\prime }，F^{\prime })$

步骤：

$S^{\prime }=\{S_1，S_2，...，S_n\}$ ，其中 $S_i\in S(i=1$ ~ $n)$ 为 $M_1$ 开始状态 $K^{\prime }=\{S^{\prime }\}$对 $K^{\prime }$ 中的新状态 $P$，针对每个 $a\in \Sigma$，求 $f^{\prime }(P,a):$ $$Q=f^{\prime }(P,a)=\{f(t,a)|t\in P\}$$若 $Q$ 不在 $K^{\prime }$ 中，则 $K^{\prime }=K^{\prime }\cup \{Q\}$重复第二步，直至 $K^{\prime }$ 中所有新状态的映射都计算完标记终止状态 若 $K^{\prime }$ 中的状态 $P$ 包含 $F$ 中的状态，则令 $P\in F^{\prime }$

例 构造有穷自动机，它识别的语言为以 $abb$ 结尾的 $a、b$ 串，并将其确定化 $(1)$ 构造 $NFA$，识别以 $abb$ 结尾的 $a、b$ 串 $(2)$ $NFA$ 转化为 $DFA$

$$\begin{array}{rl}G[S]：S& \to bS|aX\\ X& \to aX|bY\\ Y& \to aX|bZ\\ Z& \to aX|bS|\epsilon \end{array}$$

例 已知 $NFAM$，求 $DFAM$ 解

$\epsilon —NFA$（带有空转换的 $FA$）确定化

在构造有穷自动机时，使用空转换是很方便的。空转换就是输入字符是空串 $\epsilon$ 的转换。具有空转换的有穷自动机记为 $\epsilon -NFA$$\epsilon$ 弧表明 $NFA$ 在某状态下，不读入任何字符（不移动读头）而只改变状态(自动转换)

例 识别语言 $\{a^n{b}^m{c}^k|n,m,k\ge 0\}$ 解

---

因为 $NFA$ 与 $DFA$ 在功能上是等价的，即接收相同的语言类。所以对任意的 $\epsilon$-$NFAM$，都存在一个确定的 $DFA{M}^{\prime }$，使得 $L(M)=L(M^{\prime })$，即空转换可以消除

带有空转换的 $NFA$ 的确定化算法：

由 $\epsilon$-$NFA$ 构造等价的 $DFA$ 的算法与不带有空转换的 $NFA$ 确定化的算法类似，只是需要引进状态集的 $\epsilon$-闭包（$\epsilon$-CLOSURE）的概念，并在算法中，凡是涉及到状态集时就用与它相对应的 $\epsilon$-闭包代替

定义状态集 $I$ 的空闭包： 设 $I$ 是一状态集，$C(I)$ 是其空闭包（$\epsilon$-closure($I$)），

若 $P\in I$，则 $P\in C(I)$对于 $P\in I$，若 $f(P,\epsilon )=Q$，则 $Q\in C(I)$ 即从 $P$ 出发，经过任意条 $\epsilon$ 弧所能到达的任何状态 $Q$，都属于 $C(I)$

在确定化算法中，状态集由它的 $\epsilon$闭包代替，即可消除 $\epsilon$ 转换

定理

对任何一个具有 $\epsilon$ 转移的不确定的有穷自动机 $NFAN$，一定存在一个不具有 $\epsilon$ 转移的不确定的有穷自动机$NFAM$ ，使得 $L(M)=L(N)$

例

$$\begin{array}{rl}C(S)& =\{S,A\}\\ C(A)& =\{A\}\end{array}$$

将状态集都用其空闭包表示，其余步骤与不带 $\epsilon$ 转换的确定算法相同

$DFA$ 如下：

例 解 该 $NFAM$ 识别的语言是 $L(M)=(a|b{)}^{\ast }abb$ 转换后的 $DSAM$ 的状态图

$FA$ 与正则文法的转化

定理

对任意的正则文法 $G=(V_N,V_T,P,S)$，都存在一个有穷自动机 $A$，使得 $L(A)=L(G)$对任一 $DFA$ (或 $NFA$ )，都存在一个正则文法 $G$，使 $L(G)=L(A)$文法 $G$ 是正则的，当且仅当存在一个 $FA$，使$L(G)=L(M)$

正则文法 $\to FA$

已知： $G=(V_N，V_T，P，S)$ 是正则文法。用文法的非终极符作为状态，开始符号作为开始状态。再增加一个新的符号 $R$，作为终止状态

注意，这里的正则文法指严格意义上的正则文法，即 $a\in V_T$ 而非一个终结符号串 (因为 $FA$ 是一个符号一个符号地读入)

右线性文法$FA$$q_i\to a{q}_j$$f(q_i,a)=q_j$$q_i\to a$$f(q_i,a)=R$$A\to \epsilon$$A$ 也作为终止状态

例 $$\begin{array}{rl}G[S]:S& \to 0S|1A\\ A& \to 0A|1S|\epsilon \end{array}$$

解

$FA\to$ 正则文法

设 $FAM=(Q，\sum ，\delta ，q_0，F)$

对于转换函数 $\delta (A,t)=B$，可写一产生式 $A\to tB$对于可接受状态 $z$，增加一产生式 $z\to \epsilon$$S=q_0$$V_T=\sum$

例 已知 $L(G)=\{x|x\in \{0,1{\}}^{\ast },且不含两个相邻的1\}$， 求文法 $G$ 解

该语言属于正则语言，容易给出 $FAM$，如下图所示 根据 $FAM$，可以构造出如下的正则文法： $$\begin{array}{rl}G[S]:S& \to 0S|1A|\epsilon \\ A& \to 0S|\epsilon \end{array}$$

例

---

**左线性正则文法 $G$ 构造 $FAM$

对于 $A\to a$ 的产生式，按归约理解(自底向上)，句子中的第1个字符，都是用 $A\to a$ 的产生式进行归约的。对应到 $FA$ 中，$FA$ 从开始状态出发，读到句子的第一个字符 $a$, 将它归约为 $A$。此时引入初态 $q$, 定义为：$f(q,a)=A$对于 $A\to Ba$ 的产生式，$FA$ 应该在状态 $B$ 读入 $a$, 其状态转为$A$, 即 $f(B,a)=A$按归约来说，如果一个输入串是文法 $G$ 产生语言的合法句子，它最终应该被归约成开始符号。所以 $G$ 的开始符号就是 $FAM$ 的终止状态

例 构造下述文法 $G[S]$ 的自动机： $$\begin{array}{rl}S& \to A0\\ A& \to A0|S1|0\end{array}$$该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？ 解

确定化：

正规式: $00(0|10{)}^{\ast }$

例 考虑 $字母表=\{a\}$ 上的语言，该语言包含的所有串的长度要么是 2 的倍数，要么是 3 的倍数，其中包括了空串 （1）试写出该语言的正则表达式 （2）画出识别该语言的不确定有限自动机（NFA）；你可直接画NFA，不必运用机械 算法从正则表达式得到 （3）画出识别该语言的确定有限自动机（DFA）；你可直接画DFA，不必运用机械算法从上一小题的NFA确定化得到

提示：串长只能是 2、3 的倍数，如：$aaaaa$ 不满足要求

（1）$(aa{)}^{\ast }|(aaa{)}^{\ast }$ （2）

（3）

或

例 写出下列语言的正规式描述：所有不含子串011的01串

先画出含有子串 011 的 DFA 对上面的自动机求补得到 DFA，即，将它的非终结状态改为终结状态，终结状态改为非终结状态，同时删去不可终止的状态 依据该 DFA 可写出正则文法： 由正则文法改造可得正则式 $1^{\ast }(0|01{)}^{\ast }$ (如果直接用 DFA 写正则式的话，得到的不是最简的正则式)

正则式与 $FA$ 的等价性

定理

对于 $\Sigma$ 上的 $NFAM$，可构造一个 $\Sigma$ 上的正则式 $r$，使 $L(r)=L(M)$对于 $\Sigma$ 上的每个正则式 $r$，可构造 $\Sigma$ 上的 $NFAM$，使 $L(M)=L(r)$

---

正则表达式（RE）可看做是一种“程序设计语言”，用来表示某些重要的应用，比如文本搜索应用或编译器部件

例如：

搜索命令 (Linux 的 grep…) 搜索系统把正则表达式转换成 $DFA$ 或 $NFA$，并在所搜索的文件上模拟这个自动机词法分析器生成器。词法分析器是编译器部件，接受本质上是正则表达式的记号形式的描述，产生一个 $DFA$，识别在输入中下一个出现的记号是哪一个

---

$NFA\to RE$ 的步骤（纸上作业法）：

新增两个状态 $x，y$ $x$ 为新的初态结点，用 $\epsilon$ 弧连向原来所有的初态结点。 $y$ 为新的终态结点，将原来所有的终态结点用 $\epsilon$ 弧连向 $y$。形成与 $M$ 等价的 $M^{\prime }$对 $NFA{M}^{\prime }$ 中的结点按下图所示规则合并弧和去状态 反复使用这些规则，直到 $NFAM$ 中只剩下结点 $x，y$。其弧上的标记即为所求的正则式 $R$（结果不唯一）

例： 已知 $FA$，求正则式 解 所求正则式 $r=(a|b|c(a|b{)}^{\ast }d{)}^{\ast }$

例： 已知 $FA$，求正则式

解 利用规则删去一个状态时，必须注意到一切与之有关的支路

所求正则式 $r=(00^{\ast }1{)}^{\ast }00^{\ast }0$ （或 ：$r=0(0|10{)}^{\ast }0$）

例 已知 $L(G)=\{x|x\in \{0,1{\}}^{\ast },且不含11子串\}$ （1） 试构造识别该语言的 $NFA$ （2） 求出 $NFA$ 对应的正则式 （3） 给出该语言的正则文法 $G$ 解 （1） （3）根据 $FAM$，给出对应的正则文法（右线性）： $$\begin{array}{rl}G[S]:S& \to 0S|1A|\epsilon \\ A& \to 0S|\epsilon \end{array}$$

（2）根据 $NFA\to RE$ 的纸上作业法，可得 $$R=(0|10{)}^{\ast }(1|\epsilon )$$

例 求下列 $FAM$ 所描述的语言

解 (1) $\{w|w\in \{0,1{\}}^{\ast },且包含至少一个0\}$ (2) $\{0\}$ (3) $\{\epsilon \}$

---

正则式 $R$ 构造等价的 $NFAM$

我们希望能够给出一种比较“机械”的方法，使得计算机系统能够按照规则自动进行 $NFA$ 与正则表达式之间的转换

相应的等价转换方法如下：

与 $r=r_1|r_2$ 等价的 $\epsilon$-$NFA$

其中，$M_1$ 识别 $r_1$，$M_2$ 识别 $r_2$

与 $r=r_1{r}_2$ 等价的 $\epsilon$-$NFA$ 与 $r=r_1^{\ast }$ 等价的 $\epsilon$-$NFA$ 例 构造与 $r=(0|1{)}^{\ast }0|(00{)}^{\ast }$ 等价的 $\epsilon$-$NFA$ 解

---

正则式 $R\to NFAM$（适合手工推导）

引进两个状态 $x$ 和 $y$，$x$ 是 $NFAM$ 的开始状态，$y$ 是终止状态，$x$ 引向 $y$ 的弧上标记为正则式$R$，即把正则式表示成拓广转换图运用如下的三条转换规则不断加入新结点进行分解，直到每个弧的标记只是 $V_T$ 中的一个字符或 $\epsilon$ 为止，所得的 $NFAM$ 即为所求

例 已知正则式 $r=b^{\ast }(d|ad)(b|ad{)}^{\ast }$，构造等价的$NFAM$ 解

例 已知正则式 $r=1(01{)}^{\ast }(0^{\ast }|1^{\ast })0$ ，构造等价的 $NFAM$ 解

根据正则式定义语言的特征，可以使 $NFAM$ 的状态图更简化

注意，上面的状态转换图在 $(01{)}^{\ast }$ 的部分进行了简化

例 语言 $<无符号数>$ $(a)$ 正则式表示 $$d{d}^{\ast }(.d{d}^{\ast }|\epsilon )(e(+|-|\epsilon )d{d}^{\ast }|\epsilon )$$

$(c)$ $FA$ $(d)$ 正则文法定义 $$\begin{array}{rl}N& \to d{N}_1\\ N_1& \to d{N}_1|.N_2|e{N}_4|\epsilon \\ N_2& \to d{N}_3\\ N_3& \to d{N}_3|e{N}_4|\epsilon \\ N_4& \to d{N}_5|+N_6|-N_6\\ N_5& \to d{N}_5|\epsilon \\ N_6& \to d{N}_5\end{array}$$

$DFA$ 的化简 ( $DFA$ 的最小化）

在编译程序中，词法分析器（扫描器）的效率是很重要的。如果可能的话，应该使构造的 $DFA$ 最小（即状态数最少）。实际上，对于任何给定的 $DFA$ ，都有与之等价且唯一的具有最小状态数的 $DFA$ 存在

$DFAM$ 的每个可达状态存储一个输入字符子串的等价类，记为 $set(q)$对于同一正则语言 $L$，不同结构的自动机模型对 ${\sum }^{\ast }$ 进行的等价划分不同，所得到字符子串的等价类也可能不同使 ${\sum }^{\ast }$ 划分形成的等价类个数最少，即：用来存储字符子串的状态数最少的自动机，便可实现自动机的最小化

定义

化简的 $FA$：是指没有多余状态且状态中没有两个是互相等价的多余状态：从 $DFA$ 的开始状态出发，任何输入串也不能到达的那个状态在 $DFA$ 中，状态 $s$ 和 $t$ 状态等价的条件是： （1） 一致性条件：$s$ 和 $t$ 必须同时为可接受态或不可接受态 (即 $f(s,a),f(t,a)$ 均有定义或无定义) （2） 蔓延性条件：对于所有输入符号， $s$ 和 $t$ 必须转换到等价的状态集里 ($f(s,a),f(t,a)$属于相同的状态集)如果 $DFA$ 的状态 $s$ 和 $t$ 不等价，则称 $s$ 和 $t$ 是可区分的

---

分割法将 $DFA$ 最小化：将 $DFA$ 的状态集分割成一些不相交的子集，使得任何不同子集的状态都是可区分的，而同一子集中的任何状态都是等价的

把 $DFA$ 的终态和非终态分开，形成具有两个子集的基本划分对当前已划分出的子集 $I^{(1)},I^{(2)},\dots ,I^{(n)}$，看每一个 $I^{(i)}$ 是否能进一步分割 如果 $s,t\in I^{(i)}$ ，若 $f(s,a)$ 和 $f(t,a)$ 属于不同子集，则 $I^{(i)}$ 应进一步细分，使 $s$ 和 $t$ 属于 $I^{(i)}$ 的不同子集 (蔓延性)； 若 $s$ 有定义，而 $t$ 无定义，则 $s$ 和 $t$ 也是可区分的，应划分在 $I^{(i)}$ 的不同子集中 (一致性)重复进行上一步中的划分，直到每个子集无法再分割对每个子集，选一个状态为代表，删去其余等价状态 例如，若 $I^{(i)}=\{S_1,S_2,S_3\}$，删去 $S_2,S_3$。原 $DFAM$ 中有指向 $S_2,S_3$ 的有向边，均改为指向$S_1$；所有$S_2,S_3$ 引出的弧，均已由 $S_1$ 引出 (由蔓延性保证)若子集中有初态，则该状态为新的初态；若子集中有终态，则该状态为新的终态

例 将下图所示的 $DFAM$ 最小化。 解 先画出状态转换矩阵，便于之后的观察

将 $M$ 的状态按照终态和非终态分成两个子集 $$P_0=(\{1,2,3,4\},\{5,6,7\})$$在任一含两个或以上元素的子集中寻找可区分元素。例如可以在 $P_0$ 中寻找一个子集和一个输入符号，使该子集中的状态可区分。考察：$\{1,2,3,4\}$。因为 $\{1,2{\}}_a=\{6,7\}\subset \{5,6,7\},\{3,4{\}}_a=\{1,4\}\subset \{1,2,3,4\}$，所以 $$P_1=(\{1,2\},\{3,4\},\{5,6,7\})$$继续在任一含两个或以上元素的子集中寻找可区分元素。例如可以在 $P_1$ 中考察子集 $\{3,4\}$：由于 $\{3{\}}_a=\{1\},\{4{\}}_a=\{4\}$ 所以 $$P_2=(\{1,2\},\{3\},\{4\},\{5,6,7\})$$在 $P_2$ 中考察 $\{5,6,7\}$ ： 由于 $\{5{\}}_a=\{7\},\{6,7{\}}_a=\{4\}$ 所以 $$P_3=(\{1,2\},\{3\},\{4\},\{5\},\{6,7\})$$经观察，不能再划分了令 $1$ 代表 $\{1,2\}$，$6$ 代表 $\{6,7\}$，消去 $2$ 和 $7$ 。把原来指向 $2$ 和 $7$ 的弧，指向 $1$ 和 $6$ 。最小化的 $DFA$ 如右图：

---

定理

对于有同一接受集的 $FA$，与之等价且具有最小状态数的 $DFA$ 在同构意义下是唯一的（不考虑状态命名）可通过构造最小 $DFA$，证明正则式的等价性

例 通过构造下列正则式的最小 $DFA$，证明它们是等价的 $$(a|b{)}^{\ast },(a^{\ast }|b^{\ast }{)}^{\ast },((\epsilon |a)b^{\ast }{)}^{\ast }$$

解 它们对应的 $NFA$ 分别为

经确定化以及化简后对应的最小 $DFA$ 均为：

词法分析器的自动生成模型

词法分析器的自动生成是指能够自动构造分析表(即状态转换矩阵)。这种词法分析程序的总控制程序是根据分析表的内容进行操作，实现状态的变迁和单词的识别自动构造词法分析器的难点在于构造分析表，对于实际的程序设计语言来说，需要借助词法分析器的自动生成工具LEX来实现LEX源程序是使用LEX语言编写的词法规则说明，经过LEX编译后形成目标文件YYLEX.C，再用C编译器对YYLEX.C进行编译，生成目标程序YYLEX.EXE，它就是词法分析程序。用YYLEX.EXE就可以将字符串源程序转换成符号串源程序