编译原理第三章

编译原理

——第三章词法分析王金伟计算机与信息工程学院天津师范大学TJNU-COCIE-WJW22023/7/23第三章词法分析3.1对于词法分析器的要求3.2词法分析器的设计3.3正规表达式与有限自动机3.4词法分析器的自动产生（LEX）TJNU-COCIE-WJW32023/7/23词法分析的任务从左至右逐个字符的对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为由单词符号串组成的程序词法分析器：执行词法分析的程序输入：源程序输出：单词符号词法分析器的构造方法手工方法：根据词法直接编程序(有限自动机)自动方法：利用一些工具LexTJNU-COCIE-WJW42023/7/233.1对词法分析器的要求源程序词法分析器单词符号1.单词符号概念

指语言中具有独立意义的最小的语法符号

例：C=A*3.14+5

单词：

C，A ——变量

3.14,5 ——常数

=，*，+ ——算符一、词法分析器的功能和输出形式TJNU-COCIE-WJW52023/7/232.单词的种类（1）基本字（保留字，关键字） 由程序语言定义的具有固定意义的标识符。 用户不能用来表示变量名，函数名等标识符

例：C语言中的“if”“else”“while”…（2）标识符 用户使用的，用来表示各种名字，变量名，函数名等TJNU-COCIE-WJW62023/7/232.单词的种类（续）（3）常数 整型、实型、逻辑、字符…

例：1000，3.14，TRUE，“Abcd”（4）运算符

+、-、*、/…（5）界符 ，；{}（）…TJNU-COCIE-WJW72023/7/23词法分析器输出的单词符号常常用二元式来表示：

<单词种别，单词符号的属性值>二、单词的表示形式TJNU-COCIE-WJW82023/7/231.单词种别 通常用整数编码来表示 （1）关键字，运算符，界符一字一种编码（处理起来比较方便）例：if，else，‘(’，‘+’，…

（2）常数按类型分别给出编码

例：整型，实型，布尔型，…

（3）标识符统归一种，只给一个编码例：变量名，函数名等都是一种编码TJNU-COCIE-WJW92023/7/23 1.单词种别（续）注意：

(1)若一个种别只包含一个单词符号（一种一字），对于该单词符号，种别编码就可以代表它自身了。

例如：关键字，运算符，界符

(2)若一个种别包含有多个单词符号（一种多字），对于该种别的每个单词符号，除了给出种别编码，还需给出单词符号的属性值

例如：整型常数，实型常数，布尔常数，标识符TJNU-COCIE-WJW102023/7/232.单词符号的属性信息单词符号的属性：指单词符号的特性或特征单词符号的属性值：反映单词特性或特征的值TJNU-COCIE-WJW112023/7/232.单词符号的属性信息（续）属性值的表示方法： （1）基本字，运算符，界符（一字一种）只给其种别编码，不给出它的属性值例：基本字while表示成：<$WHILE,->

（2）常数表示成标准的二进制形式例：1024表示成：<$CONST,1024的二进制表示>

（3）标识符用字符串编码或对应的符号表项地址例：name表示成：<$ID，“name”>

或<$ID,指向name的符号表项的指针>TJNU-COCIE-WJW122023/7/23例1：FORTRAN编译程序的词法分析器，在扫描输入串：IF（5.EQ.M）GOTO100

输出的单词如下：

单词符号 <单词种别编码，单词符号的属性值>IF <34，->左括号 <2，->整常数 <20，5的二进制表示>等号 <6，->标识符 <26，‘M’>右括号 <16，->GOTO <40，->标号 <19，‘100’二进制表示>三、例子TJNU-COCIE-WJW132023/7/23例2：考虑下面C++的一段代码：

while(i>=j)i--;经词法分析器处理后，将被转换成如下单词符号序列： 单词符号 <单词种别编码，单词符号的属性值>while <while，->( <(，->i <id，指向i的符号表项的指针>>= <>=，->j <id，指向j的符号表项的指针>) <)，->i <id，指向i的符号表项的指针>-- <--，->； <;,->TJNU-COCIE-WJW142023/7/233.2词法分析器的设计源程序预处理子程序输入缓冲区扫描器扫描缓冲区输入列表单词符号一、词法分析器的结构TJNU-COCIE-WJW152023/7/231.

输入缓冲区、预处理子程序（1）输入源程序文本，放入输入缓冲区中，词法分析工作可在这个输入缓冲区中工作（2）剔除无用的空白，跳格(TAB)，回车，换行等编辑性字符；若空白符号为单词符号的界符，就将若干空白和并为1个（3）剔除注释行，比如/*…*/（4）如果是FORTRAN语言，区分标号区、续行区和给出句末符（5）源程序的出错列表打印（6）将预处理好的子程序放到扫描缓冲区中TJNU-COCIE-WJW162023/7/232.扫描缓冲区、扫描器（1）扫描缓冲区设两个半区，可互补使用设两个指针起点指针：指出正在识别单词起点位置搜索指针：向前搜索以寻找单词终点（2）扫描器：扫描缓冲区，直接进行单词的识别前半区后半区起点指针搜索指针TJNU-COCIE-WJW172023/7/23源程序预处理子程序输入缓冲区扫描器扫描缓冲区输入列表单词符号二、词法分析器的工作过程TJNU-COCIE-WJW182023/7/23 1.超前搜索

(1)关键字的识别 前提：允许用户使用基本字（关键字）

例：试分析下面FORTRAN的几个语句（1）DO99K=1，10（2）IF(S.EQ.M)GOTO55（3）DO99K=1.10（4）IF(S)=55超前扫描很多字符，直到扫描到可以肯定词性的地方为止

PROGRAM

SUM

S=0

DO

99

I=1,100

S=S+I

99

CONTINUE

…

END

三、单词符号的识别TJNU-COCIE-WJW192023/7/231.超前搜索法（续1）

(2)标识符的识别 一般是以字母开头后跟数字/字母的字符串，后边一般都有算符和界符，比较好识别

(3)常数的识别

例：对于FORTRAN 5.EQ.M （5==M）

5.E08 （5*108)

直到超前扫描到字母Q时才能确定5的词性

3HABC （“ABC”）

3H是词头，代表长度为3的字符串常数TJNU-COCIE-WJW202023/7/231.超前搜索法（续2）

(4)算符和界符的识别 应将那些由多个字符复合成的算符和界符拼成一个单词符号

例：++ -- >= TJNU-COCIE-WJW212023/7/23 2.直接分析法 （1）基本思想 根据读来的第一个字符的种类分别转到各种子程序处理。这些子程序功能就是识别以相应字符开头的各种单词。 （2）方法 以FORTRAN语言为例，分成几种情况 ①以字母开头的 基本字、标识符、格式说明符，…IFWHILETJNU-COCIE-WJW222023/7/232.直接分析法（续1）②以小数点开头的.34 .EQ..TRUE..FALSE.等③以数字开头的常数、格式语句、重复说明WRITE(6,10)X,Y 10FORMAT(2X,F10.4,F9.3)④以*开头的：***⑤除此之外：都是一个基本字符表示一个单词TJNU-COCIE-WJW232023/7/23子程序1子程序2子程序3子程序4子程序5下一个语句字符是否读来该字符是什么读一个符号字母·数字*其他出口否是2.直接分析法（续2） 分析流程图TJNU-COCIE-WJW242023/7/233.状态转换图法(1)状态转换图：一张有限方向图(2)状态转换图的功能 识别（接受）一定的符号串（单词）TJNU-COCIE-WJW252023/7/233.状态转换图法（续1）(3)状态转换图的结构

①结点：代表状态，用圆圈表示

②箭弧：状态之间用箭弧连接

③箭弧上的标记：代表在射出节点下可能出现的字符或字符串

例：注意：一个完整的状态转换图有n个状态，其中有一个初态，至少要有一个终态(用双圆圈表示)TJNU-COCIE-WJW262023/7/233.状态转换图法（续2）(4)举例

例1：构造一个识别标识符的状态转换图 解：

其中“*”表示在该状态下多读进一个字符 识别：name1TJNU-COCIE-WJW272023/7/233.状态转换图法（续3）

例2：构造一个识别整数的状态转换图，说说识别256过程 解：TJNU-COCIE-WJW282023/7/233.状态转换图法（续4）

例3：识别FORTRAN实型常数的状态转换图解：

实数：小数形式：3.4 13.4 34.

指数形式：3E+05即3X105TJNU-COCIE-WJW292023/7/23四、综合例子用状态转换图法，构造一个识别某一个简单语言（SL）的所有单词符号的词法分析器TJNU-COCIE-WJW302023/7/23单词符号种别编码助记符号内码值DIMIFDOSTOPEND标识符常数（整型）=+***,（）1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR-----内部字符串标准二进制-------1、SL的单词符号及其内部表示（P42)TJNU-COCIE-WJW312023/7/232.为了讨论方便，对SL加三点限制（1）所有基本字都规定为保留字（用户不能用它们来定义标识符的，避免超前搜索）（2）对基本字只构造一个基本字表，不构造其状态转换图（只要识别出是一个标识符，就去查基本字表看看是否是基本字）（3）对基本字，标识符和常数之间要留有间隔符（避免超前搜索）TJNU-COCIE-WJW322023/7/233.构造能够识别SL单词的状态转换图(P43)TJNU-COCIE-WJW332023/7/23 4.状态转换图的程序实现

思路：为每个状态结点都编写一个子程序

首先，设以下一些变量或过程

ch:字符变量,存放最新读进的源程序字符

strToken:字符数组,存放构成单词符号的字符串

GetChar:子程序过程,将下一输入字符读到ch中,搜索指示器前移一字符位置

GetBC:子程序过程,检查ch中的字符是否为空白,若是,则调用GetChar直至ch中进入一个非空白字符

Concat:子程序过程,将ch中的字符连接到strToken之后.例如,假定strToken原来的值为“AB”,而ch中存放着‘C’,经调用Concat后,strToken的值就变为“ABC”TJNU-COCIE-WJW342023/7/23 IsLetter和IsDigit:布尔函数过程,他们分别判断ch中的字符是否为字母和数字

Reserve:整型函数过程,对strToken中的字符串查找保留字表,若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）

Retract:子程序过程,将搜索指示器回调一个字位置，将ch置为空白字符

InsertId:整型函数过程,将strToken中的标识符插入符号表,返回符号表指针。

InsertConst:整型函数过程,将strToken中的常数插入到常数符号表,放回常数表针TJNU-COCIE-WJW352023/7/23然后，对每个状态编写一个对应的程序(1)对于不含回路的状态结点，采用分叉法例：

GetChar();If(IsLetter()){状态j对应的程序段}Elseif(IsDigit()){状态k对应的程序段}Elseif(ch=‘/’){状态l对应的程序段}Else{错误处理}TJNU-COCIE-WJW362023/7/23(2)对于含有回路的状态结点，对应一个while语句例：

(3)对于终态结点，用return(code,value)

其中，code是单词的种别编码，value是单词符号的属性值，或无定义。GetChar();while(IsLetter()orIsDigit()) GetChar();状态j对应的程序段TJNU-COCIE-WJW372023/7/235.状态转换图对应的词法分析程序伪代码（P45-46）TJNU-COCIE-WJW382023/7/23第1次上机作业

根据《编译原理》P45-46页的词法分析程序伪代码，用C语言实现，要求： 输入：由P43页表3.1中的单词，按词法规则组成的语句序列（或用文件存储，相当于源程序） 例如：IFi>0i=1 …输出：打印单词的种别（用表3.1中的助记符）和单词的属性值（表3.1中的内码值） 每行一词，格式 单词1：<种别编码1，属性值1>

单词2：<种别编码2，属性值2>

例如：

IF: <$IF，->TJNU-COCIE-WJW392023/7/233.3正规表达式与有限自动机

为了更好地使用状态图构造词法分析程序，为了讨论词法分析程序的自动生成，需要将状态转换图的概念形式化 词法分析器的构造的基本思路： 程序语言的描述

词法规则

正规表达式

有限自动机

词法分析程序TJNU-COCIE-WJW402023/7/231.字母表（基本字符集） 一个非空的由有限元素组成的集合，每个元素称为一个符号，一般用∑表示

例：∑={a,b,c}

元素：a，b，c

注:不同语言有不同的字母表

例：C语言的字母表中包含：字母A~Z,a~z，数字0~9，标点,.{}[]+-*/等一、基本概念TJNU-COCIE-WJW412023/7/232.字母表∑上的一个符号串（字） 由字母表∑中的符号所构成的一个有穷序列，一般用小写字母x,y表示

例：aa，ab，abc，…

注：

(1)符号的顺序不同代表不同的符号串 例如ab≠ba (2)不包含任何字符的序列称为空字，用ε来表示TJNU-COCIE-WJW422023/7/233.字(符号串)的连接 设x和y是两个字(符号串)，则定义xy为他们的连接

例：ab和ba连接是abba

注:(1)ε是连结运算的恒等元素εx=xε=x (2)字(符号串)的n次连接

xn=xxx…x n个

规定x0=ε x1=x，x2=xx，x3=xxx

例：x=ab，则

x0=ε

，x1=ab，x2=abab，x3=abababTJNU-COCIE-WJW432023/7/234.集合的(连接)积设U和V是两个“字(符号串)的集合”，则定义UV为他们的(连接)积

UV={xy|x∈U且y∈V}例：设U={a,ab},V={b,ba},

则UV={ab,aba,abb,abba}注：(1)集合的(连接)积不满足交换率

UV≠VU (2)集合的(连接)积满足结合率

(UV)W=U(VW)TJNU-COCIE-WJW442023/7/235.集合V的n次(连接)积记为：

Vn=VVV…V n个

规定V0={ε}例：设V={a,b}，那么

V0={ε} V1={a,b} V2=VV={aa,ab,ba,bb} V3=VVV=V2V={aaa,aba,baa,bba, aab,abb,bab,bbb} V4=VVVV=V3V=…TJNU-COCIE-WJW452023/7/236.闭包 设V是一个字（符号串）的集合， 则V的闭包定义为V*，

V*=V0∪V1∪V2∪…

注：闭包V*

中的每个字都是由V中的字经过有限次连接而成的7.正则闭包V+的定义为

V+=VV*TJNU-COCIE-WJW462023/7/238.∑*定义（∑的闭包）用∑*来表示∑上所有字的全体，空字ε也包括在其中 ∑*

=∑0∪∑1∪∑2∪…例：设∑={a，b}，求∑* ∑*={ε,a,b,aa,ab,ba,bb,aaa,…}注:(1)用Φ来表示不含任何元素的集合，称为空集，即{}(2)ε，{}，{ε}之间的区别

ε：空字；

{}：空集；

{ε}：仅含有空字的集合TJNU-COCIE-WJW472023/7/23

词法分析器需要识别语言中具有不同特征的字

例如：识别“标识符”、识别“数”，等等。

我们可以把具有相同特征的字放在一起组成一个集合，即所谓的正规集 然后使用一种形式化的方法来表示正规集，即所谓的正规式

注意： 正规式是描述单词结构的一种形式； 正规集是该类单词的全集。二、正规式与正规集TJNU-COCIE-WJW482023/7/231.正规式与正规集的定义（递归的定义方法）(1)ε和φ是∑上的正规式,它们所表示的正规集分别为{ε}和φ(2)任何a∈∑,是∑上的一个正规式,他所表示的正规集为{a}(3)假定U和V都是∑上的正规式，他们所表示的正规集分别记为L(U)和L(V)，那么

(a)(U|V)是正规式，所表示的正规集为L(U)∪L(V) (b)(UV)是正规式，所表示的正规集为L(U)·L(V)（连接积）

(c)(U)*是正规式，所表示的正规集为(L(U))*（闭包） 仅由有限次使用(1)(2)(3)所得到的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。

注：|(或)、·(连接)、*(闭包,任意有限次的自重复连接)

运算的优先级为：“*”>“·”>“|”TJNU-COCIE-WJW492023/7/232.举例例1.令∑={a,b}

正规式 正规集

a b a|b ab (a|b)(a|b) a* (a|b)* ba* a(a|b)* (a|b)*(aa|bb)(a|b)* {a}{b}{a,b}{ab}{aa,ab,ba,bb}{ε,a,aa,…任意个a的串}{ε,a,b,aa,ab,…所有a,b组成的串}{b,ba,baa,baaa,…}∑上以a为首的字的全体∑上含有aa或bb的字的全体TJNU-COCIE-WJW502023/7/23例2.令∑={A，B,0,1}

正规式 正规集

A B 0 1 A|B 0|1 (A|B|0|1) (A|B|0|1)* (A|B)(A|B|0|1)* (0|1)(0|1)* {A}{B}{0}{1}{A,B}{0,1}{A,B,0,1}∑上字的全体，包含空字ε∑上“标识符”的全体∑上“数”的全体(不包含空字)TJNU-COCIE-WJW512023/7/233.两个正规式的等价 若两个正规式U和V所表示的正规集相同，则认为二者等价，记为： U=V例：证明b(ab)*=(ba)*b

证明：因为，L(b(ab)*)=L(b)L((ab)*) ={b}·{ε,ab,abab,…} ={b,bab,babab,…}

又因为，L((ba)*b)=L((ba)*)L(b) ={ε,ba,baba,…}·{b} ={b,bab,babab,…}

因此，L(b(ab)*)=L((ba)*b)

所以，b(ab)*=(ba)*b (证毕）TJNU-COCIE-WJW522023/7/234.正规式的性质设U，V，W是上的∑正规式，则(1)U|V=V|U 或的交换律(2)U|(V|W)=(U|V)|W 或的结合律(3)U(VW)=(UV)W 连接积的结合律(4)U(V|W)=(UV)|(UW) 分配律

(V|W)U=VU|WU (5)εU=Uε=U TJNU-COCIE-WJW532023/7/23(1)U|V=V|U 或的交换律证明：因为，L(U|V)=L(U)∪L(V)

又因为，L(V|U)=L(V)∪L(U)=L(U)∪L(V)

因为，L(U|V)=L(V|U)

所以，U|V=V|UTJNU-COCIE-WJW542023/7/23(2)U|(V|W)=(U|V)|W 或的结合律证明： 因为，L(U|(V|W))=L(U)∪L(V|W) =L(U)∪L(V)∪L(W)又因为，L((U|V)|W)=L(U|V)∪L(W) =L(U)∪L(V)∪L(W)因此，L(U|(V|W))=L((U|V)|W)

所以，U|(V|W)=(U|V)|W (3)(4)(5)留给同学们课下证明TJNU-COCIE-WJW552023/7/23下面，我们把状态转换图再形式化一下及所谓的有限自动机有两种：确定的有限自动机（DFA） （DeterministicFiniteAutomata)非确定的有限自动机（NFA） （Non-deterministicFiniteAutomata)TJNU-COCIE-WJW562023/7/231.定义：一个确定有限自动机（DFA）M是一个五元式：M=(S,∑,f,s0,F)，其中S是一个有限的状态集合，它的每个元素我们称为一个状态∑是一个有穷的输入符号的字母表，它的每个元素我们称为一个输入字符f是从S×∑→S的单值部分映射s0是S的一个元素，为初始状态，它是唯一的状态集合F是终止状态的集合，它是S的子集(可空)三、确定的有限自动机（DFA）

（DeterministicFiniteAutomata)TJNU-COCIE-WJW572023/7/23注意：所谓的自动机不是指一台实际的机器，而是一种数学模型（集合，函数，序列…），利用它模拟计算机识别的功能所谓确定性是指，f(s,a)=s’

是单值函数。对任何状态s∈S，和输入符号a∈∑，f(s,a)唯一的确定下一个状态所谓有限性是指，S是一个有限的状态集合，并且∑是一个有限的输入符号的字母表用上述5条，来定义一个DFA，来完成识别一个序列是否被机器所接受TJNU-COCIE-WJW582023/7/23例：设一个奇偶校验器，其功能是，用来识别由1和0组成的序列是否含有奇数个1。解：设DFAM=(S,∑,f,s0,F)来表示奇偶校验器，其中1)S：{EVEN，ODD}2)∑：{0，1}3)f:f(EVEN,0)=EVEN f(EVEN,1)=ODD f(ODD,0)=ODD f(ODD,1)=EVEN4)s0:EVEN5)F:{ODD}注意：如果一个序列使自动机从开始状态出发，最后达到一个终态，那么该输入序列就被该自动解接受（识别，读出），否则将被拒绝。TJNU-COCIE-WJW592023/7/23例：1101110

EVENODDEVENEVENODDEVENODDODDf: f(EVEN,0)=EVENf(EVEN,1)=ODDf(ODD,0)=ODDf(ODD,1)=EVEN—1—〉—1—〉—0—〉—1—〉—1—〉—1—〉—0—〉TJNU-COCIE-WJW602023/7/232.DFAM的表示方法状态转换矩阵表示法(用一个“表”来表示)设矩阵的行表示状态，列表示输入字符，矩阵元素是

f（s，a）的值例：设DFAM=({0,1,2,3},{a,b},f,0,{3})，其中

f:f(0,a)=1, f(0,b)=2

f(1,a)=3, f(1,b)=2

f(2,a)=1, f(2,b)=3

f(3,a)=3, f(3,b)=3输入字符状态ab012313132233TJNU-COCIE-WJW612023/7/23(2)用状态转换图来表示例：设DFAM=({0,1,2,3},{a,b},f,0,{3})，其中

f:f(0,a)=1, f(0,b)=2

f(1,a)=3, f(1,b)=2

f(2,a)=1, f(2,b)=3

f(3,a)=3, f(3,b)=3TJNU-COCIE-WJW622023/7/233.DFAM的识别功能对于∑*中任何字α，如果存在一条从初态结点到某个终态结点的道路，这条路上所有的标识符连成的字等于α

，则α可被DFAM所识别(接受，读出)例：∑*={aa,bb,ab,baa,aba,bbb,bba,…}

TJNU-COCIE-WJW632023/7/23注意：(1)若M的初态结点同时又是终态节点，则空字可被M识别(2)DFAM所能识别的字的全体记为L(M)(3)如果一个DFAM的输入字母表为∑，则我们称M是∑上的一个DFA(4)若V是∑上的一个正规集，当且仅当存在一个∑上的DFAM，使得V=L(M)TJNU-COCIE-WJW642023/7/231.定义:一个非确定有限自动机（NFA）M是一个五元式M=(S,∑,f,S0,F)，其中S是一个有限的状态集合，它的每个元素我们称为一个状态∑是一个有限的输入符号的字母表，它的每个元素我们称为一个输入字符f是从S×∑*→2S的部分映射，其中，2S表示S的幂集合（所有S的子集组成的集合）

（f是非单值的M是非确定）状态集合S0是初始状态集合，它是S的子集状态集合F是终止状态的集合，它是S的子集四、非确定的有限自动机(NFA)

（Non-deterministicFiniteAutomata)TJNU-COCIE-WJW652023/7/232.NFAM表示方法(1)用状态矩阵表示例：设NFAM=({0,1,2},{a,b},f,{0},{1,2})，其中

f:f(0,aa)={1}, f(0,bb)={2}

f(0,a)={0}, f(0,b)={0}

f(1,a)={1}, f(1,b)={1}

f(2,a)={2}, f(2,b)={2}字状态aabbab0121--2--012012TJNU-COCIE-WJW662023/7/23(2)用状态转换图表示例：设NFAM=({0,1,2},{a,b},f,{0},{1,2})，其中

f:f(0,aa)={1}, f(0,bb)={2}

f(0,a)={0}, f(0,b)={0}

f(1,a)={1}, f(1,b)={1}

f(2,a)={2}, f(2,b)={2}TJNU-COCIE-WJW672023/7/233.NFAM识别条件 对于∑*中的任何字α若存在一条从某一个初态到某一个终态的通路且这条路上所有弧的标记字连接成的字等于α

，则α可被NFAM识别(读出，接受)4.有限自动机的等价 对任何两个有限的自动机M1和M2，若有L(M1)=L(M2)，则称M1与M2等价。

TJNU-COCIE-WJW682023/7/23注:(1)若M的某些结点既是初态结点又是终态结点，或者存在一条从某初态结点到某个终态结点的ε通路，那么空字ε可为M所识别

(2)DFA是NFA的一个特例，对于每个NFAM存在一个DFAM’使得L(M)=L(M’)，也就是说M和M’是等价的TJNU-COCIE-WJW692023/7/23定理1：对于任何∑上NFAM都可构造一个∑上的正规式V，使得L(V)=L(M)其中，L(M)是∑上NFAM所能识别的字的全体，L(V)是∑上的正规集五、正规式与有限自动机的等价性TJNU-COCIE-WJW702023/7/23问题：如何由一个NFAM，构造一个正规式V方法：(1)在M转换图上加进X结点和Y结点，从X结点用弧ε连接M的所有初态结点，M的所有终态结点用弧ε连接到Y，得到一个NFAM’，且L(M)=L(M’)(2)使用替换规则逐步消去M’的所有结点，直到只剩下X结点和Y结点，在消去过程中，逐步使用正规式来标记箭弧TJNU-COCIE-WJW712023/7/23替换规则：TJNU-COCIE-WJW722023/7/23例：对于一个∑上的NFAM，构造一个正规式V，使得L(M)=L(V)

TJNU-COCIE-WJW732023/7/23第二步，消去结点1第三步，消去结点0第一步：加入X结点和Y结点得到一个M’，且L(M’)=L(M)TJNU-COCIE-WJW742023/7/23定理2.对于∑上的每一个正规式V，存在一个∑上的DFAM，使得L(M)=L(V)问题：如何由一个正规式V，构造一个DFAM思路：分两步走

1.根据V，构造一个NFAM’，使得L(M’)=L(V)

2.将M’确定化，变为DFAMTJNU-COCIE-WJW752023/7/23方法：

第一步，在∑上构造一个NFAM’ (1)构造一个拓广的转换图TJNU-COCIE-WJW762023/7/23 (2)使用分裂规则对V进行分裂，加进新结点，直到把图转换成每条弧上标识为∑上的一个字符或ε

最后得到一个NFAM’

且L(M’)=L(V)TJNU-COCIE-WJW772023/7/23第二步，把M’确定化定义1

某个状态集I的ε(空字)闭包：ε_CLOSURE(I)

是一个状态集，由两部分组成:状态集I中的所有状态。从I中的状态出发经过任意条ε弧，所能到达的状态的全体。定义2

某个状态集I的a弧转换：move(I,a)

是一个状态集，是从I中的状态出发经过一条a弧到达的状态的全体。定义3

Ia=ε_CLOSURE(move(I,a))是一个状态集。TJNU-COCIE-WJW782023/7/23例：有如下一个NFAN的状态转换图假定I={1,2}，求Ia=？解：

move(I,a)={ }

Ia=ε_CLOSURE(J)={ }1a5438εε267εεεaa4,5,35,6,2,4,7,3,8aaa543ε6ε2ε7ε8J=TJNU-COCIE-WJW792023/7/23例3：有如下一个状态转换图已知K={5,4,1}求Ka

，Kb

解：求Ka

J={5,3}Ka=ε_CLOSURE(J)={5,3,1}求KbJ={5,2,4}Kb=ε_CLOSURE(J)={5,2,4,1,6,Y}εεX12a5εε6bab43aabbYTJNU-COCIE-WJW802023/7/23(1)基本思想:把NFA的一些状态，即状态子集，合并为DFA的一个状态。子集法TJNU-COCIE-WJW812023/7/23(2)具体做法：假设有一个NFAN，∑={a1…ak}，初始状态集是S0，用子集法把N转换为DFAM。第一步：构造一张表第二步：将表中出现的每个状态子集看成一个状态，该表就是所求DFAM的状态转换表，其中M的初态是该表的首行首列那个状态M的终态是那些含有原来NFA终态的状态子集所对应的状态IIa1…Iak状态子集…状态子集…………………状态子集ε_CLOSURE(S0)k+1列TJNU-COCIE-WJW822023/7/23例1：假设有一个NFAN，S0={1}，F={4}，∑={a,b}

用子集法把N转换为DFAM。解：第一步，构造一张表。IIaIb{1,2,4}{2,4}{2,4}{2,4}{3}{3}{3}{2,4}{3}TJNU-COCIE-WJW832023/7/23第二步，将表中的每个状态子集看成一个状态，得到DFAM的状态转换表。状态ab012111222IIaIb{1,2,4}{2,4}{2,4}{2,4}{3}{3}{3}{2,4}{3}012111222状态abTJNU-COCIE-WJW842023/7/23例2：设∑={a，b}，有∑上的一个正规式(a|b)*(aa|bb)(a|b)*，构造NFAM’，并且确定化解：第一步，构造一个NFAM’①②TJNU-COCIE-WJW852023/7/23③TJNU-COCIE-WJW862023/7/23④得到一个NFAM’且L(M’)=L(V)TJNU-COCIE-WJW872023/7/23第二步，用子集法对M’进行确定化①构造一张表IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J)J={5,3}J={5,4}{X,5,1}{5,3,1}{5,3,1}{5,3,1}{5,4,1}{5,4,1}{5,4,1}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,2,6,Y}{5,3,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,4,1,6,Y}{5,4,1,2,6,Y}{5,3,1,6,Y}{5,3,1,6,Y}J={5,3}J={5,4}J={5,2,3}J={5,2,4}J={5,2,3,6}J={5,4,6}J={5,3,6}J={5,2,4,6}J={5,3,6}J={5,2,4,6}J={5,2,3,6}J={5,4,6}TJNU-COCIE-WJW882023/7/23IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J){X,5,1}{5,3,1}{5,4,1}{5,3,1,2,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}{5,3,1,6,Y}{5,3,1}{5,3,1,2,6,Y}{5,3,1}{5,3,1,2,6,Y}{5,3,1,6,Y}{5,3,1,6,Y}{5,3,1,2,6,Y}{5,4,1}{5,4,1}{5,4,1,2,6,Y}{5,4,1,6,Y}{5,4,1,2,6,Y}{5,4,1,2,6,Y}{5,4,1,6,Y}②把每个子集看成一个状态，得到一个DFAM， 且L(M)=L(M’)sab012345613136632254554012345612325134455366TJNU-COCIE-WJW892023/7/23sab012345613136632254554TJNU-COCIE-WJW902023/7/231.化简的概念 寻找一个状态比DFAM少的DFAM’，使得

L(M’)=L(M)六、确定有限自动机的化简（最少化）TJNU-COCIE-WJW912023/7/232.两个状态等价的概念 设s和t是M两个不同的状态，从s出发能读出某个字而停于终态，那么同样，从t出发也能读出同一个字而停在终态，反之亦可3.两个状态是可区别的 若DFAM的两个状态s和t不等价，则称这两个状态是可区别的

注：终态和非终态是可区别的，因为终态可以读出空字ε，而非终态不能读出空字εTJNU-COCIE-WJW922023/7/234.化简DFA的一般步骤

(1)

检查状态转换函数是否为全函数。 所谓全函数，是指每个状态对每个输入符号都有转换 若不是全函数，可以引入一个“死状态”d，d对所有输入符号都转换到d，如果状态s对输入符号a没有转换，那么加上从s到d的a转换。

(2)用化简算法进行化简

(3)去掉死状态TJNU-COCIE-WJW932023/7/235.DFA化简算法 (1)基本思想 把M的状态集分割为一些不相交的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的，最后让每个子集选一个代表，同时消去其他等价状态

TJNU-COCIE-WJW942023/7/23(2)化简算法①对M的状态集S进行划分： 把S的终态和非终态分开，分成终态集和非终态集，形成基本分划П，显然这两个子集是可区别的。②假定到某个时候П含有m个子集，

记П={I(1),I(2),…I(m)}

并且，属于不同子集的状态是可区别的。 检查П中的每个I(i)看能否进一步划分： 对于某个I(i)

另I(i)={q1,q2,…,qk}

若存在一个输入字符a使得I(i)a不全包含在现行П的某个子集I(j)中，就将I(i)一分为二TJNU-COCIE-WJW952023/7/23

[例如，假定状态s1和s2经a弧分别到达状态t1和t2，而t1和t2属于现行П的两个不同的子集，那就将I(i)分成两半I(i1)和I(i2)

使得一半含有s1：

I(i1)={s|s∈I(i)且s经a弧到达t1所在的子集中的某状态}

另一半含有s2：

I(i2)=I(i)-I(i1)]

注意：由于t1和t2是可区别的，即存在一个字w，t1将读出w而停于终态，而t2或读不出w或虽然可读出w但不到达终态；或者情形恰好相反。因而字aw就将状态s1和s2区别开来。也就是说I(i1)中的状态与I(i2)中的状态是可区别的③一般地，若I(i)a落入现行П中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入П的同一子集，这样再形成新的分划TJNU-COCIE-WJW962023/7/23④重复上述过程，直至分划中所含的子集数不再增长为止。至此，П中的每个子集已不可再分。也就是说，每个子集中的状态是互相等价的，而不同子集中的状态则是互相可区别的。⑤经过上述过程后，得到一个最后分划П.对于这个П中的每个子集，选取子集中的一个状态代表其它状态。

[例如，假定I={q1,q2,…,qk}是这样一个子集，可挑选q1代表这个子集。在原来的自动机中，做：

a.凡导入到q2,…,qk的弧都改成导入q1

b.将q2,…,qk从原来的状态集S中删除

c.若I中含有原来的初态，则q1是新初态

d.若I中含有原来的终态，则q1是新终态]

到此，得到一个化简得DFAM’，使得L(M)=L(M’)TJNU-COCIE-WJW972023/7/236.

例题例1:把DFAM’进行化简例2：设计一个DFA，其输入字母表是{a，b}，它能接受以a开始以b结尾的所有序列。TJNU-COCIE-WJW982023/7/23例1:把DFAM’进行化简解:①把M状态集分为两组:终态结点{3，4，5，6}非终态结点{0，1，2}②考察{3，4，5，6}因为，{3，4，5，6}a= {3，4，5，6}b=所以，{3，4，5，6}不可再分③考察{0，1，2}因为，{0，1，2}a=所以，{0，1，2}必可再分看图，把{0，1，2}分割为{1}和{0，2}{3，6}{4，5}{3，4，5，6}{3，4，5，6}J={3，6}J={4，5}{1，3}{3，4，5，6}J={1，3}{0，1，2}TJNU-COCIE-WJW992023/7/23④考察{0，2}因为，{0，2}a= {0，2}b=所以，{0，2}必可再分所以，把M分割为{0}，{1}，{2}，{3，4，5，6}⑤用状态3代替状态4，5，6，把引向状态4，5，6的箭弧都引向状态3，把4，5，6消去，得到一个DFAM’J={1}J={2，5}{1}{1}{2，5}{3，4，5，6}{0，2}{1}TJNU-COCIE-WJW1002023/7/23TJNU-COCIE-WJW1012023/7/23例2：设计一个DFA，其输入字母表是{a，b}，它能接受以a开始以b结尾的所有序列。解:(1)根据题意，得到相应的正规式：

a(a|b)*b(2)由以上正规式构造相应的NFA为：TJNU-COCIE-WJW1022023/7/23①②a(a|b)*bTJNU-COCIE-WJW1032023/7/23③TJNU-COCIE-WJW1042023/7/23④得到一个NFAM’且L(M’)=L(V)TJNU-COCIE-WJW1052023/7/23(3)用子集法对M’进行确定化①构造一张表IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J)J={1}--{X}{1,2,3}{1,2,3}{2,3}{2,3}{2,3,Y}--{2,3}{2,3,Y}{2,3}{2,3,Y}{2,3,Y}J={2}J={2,Y}J={2}J={2,Y}J={2}J={2,Y}TJNU-COCIE-WJW1062023/7/23IIa=ε_CLOSURE(J)Ib=ε_CLOSURE(J){X}{1,2,3}{2,3}{2,3,Y}{1,2,3}{2,3}{2,3}{2,3}--{2,3,Y}{2,3,Y}{2,3,Y}②把每个子集看成一个状态，得到一个DFAM， 且L(M)=L(M’)sab01231222--33301231233223TJNU-COCIE-WJW1072023/7/23sab01231222--333TJNU-COCIE-WJW1082023/7/23(4)对M进行化简加入死状态4TJNU-COCIE