编译原理第3章_词法分析

1、1v词法分析是编译的第一个阶段，在单词的级词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。别上分析和翻译源程序。v理论基础：理论基础： 有限自动机理论有限自动机理论 有限自动机理论与正规文法、正规式之间在描有限自动机理论与正规文法、正规式之间在描 述语言方面有一一对应的关系。述语言方面有一一对应的关系。 第第3章章 词法分析词法分析2本章在编译程序中的地位本章在编译程序中的地位表表格格管管理理词法分析器词法分析器语法分析器语法分析器语义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码

2、中间代码目标代码目标代码出出错错处处理理3v词法分析器的功能词法分析器的功能高级语言高级语言源程序源程序词法分词法分析器析器语法分语法分析器析器tokenget_next_token编译器其编译器其它阶段它阶段符号表符号表字符流字符流记号记号（流）（流）4v执行词法分析的程序称为执行词法分析的程序称为又称为又称为词法分析器词法分析器或或扫描扫描器器. . v词法分析的词法分析的任务任务：从左至右逐个地扫描源程序的字：从左至右逐个地扫描源程序的字符串符串, 按照按照词法规则词法规则识别出一个个正确的单词，并识别出一个个正确的单词，并转换为相应的转换为相应的二元式二元式形式，交给语法分析使用。形式

3、，交给语法分析使用。v把作为字符串的源程序改造成单词符号串的把作为字符串的源程序改造成单词符号串的词法分词法分析是编译的基础。析是编译的基础。3.1.1 设计设计词法分析器词法分析器时应考虑的几个问题时应考虑的几个问题3.1 词法分析与词法分析程序词法分析与词法分析程序53.1.2 词法分析阶段的必要性词法分析阶段的必要性 v词法分析的工作纳入整个语法分析中一揽子地进行，原则上是词法分析的工作纳入整个语法分析中一揽子地进行，原则上是可行的。可行的。 v在设计一个编译程序时，通常是把对源程序的结构分析分为词在设计一个编译程序时，通常是把对源程序的结构分析分为词法分析和语法分析两个相对独立的阶段来

4、完成。法分析和语法分析两个相对独立的阶段来完成。 第一，描述单词的结构比描述源程序的其它语法结构要简单第一，描述单词的结构比描述源程序的其它语法结构要简单得多，仅使用得多，仅使用3 3型文法也就基本够用了。型文法也就基本够用了。 第二，由于把词法分析和语法分析分开，可使编译程序各部第二，由于把词法分析和语法分析分开，可使编译程序各部分的功能更为单一，整个编译程序的结构也更加清晰，从而分的功能更为单一，整个编译程序的结构也更加清晰，从而有利于编译程序的编写和调整。有利于编译程序的编写和调整。v上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译上述词法分析和语法分析两个阶段的划分，仅仅是对整个

5、编译程序的逻辑功能而言，而不一定指的是编译程序的执行流程。程序的逻辑功能而言，而不一定指的是编译程序的执行流程。63.1.3 词法分析器的输出形式词法分析器的输出形式v词法分析器输出的单词常常表示为词法分析器输出的单词常常表示为二元式二元式形式形式 (单词种别单词种别,单词符号的属性值单词符号的属性值) 单词种别提供给语法分析程序使用；单词符号的属性值提供给语义分析程序使用。具体的分类设计方法以方便语法分析程序使用为原则。73.1.3 词法分析器的输出形式词法分析器的输出形式v程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：关键字关键字( (保留字或基本字保留字或基本字) )：

6、如：如 if,then,else,while,doif,then,else,while,do等等 标识符标识符：用来表示各种名字，如：用来表示各种名字，如 x1x1常量常量：如：如 256256，3.143.14，true, abc true, abc 运算符运算符：如：如 、* *、/ / 等等等等分界符分界符：如：如 逗号，分号，冒号等逗号，分号，冒号等83.1.3 词法分析器的输出形式词法分析器的输出形式v单词种别单词种别: : 一个语言的单词符号如何分类、分为几类、如一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词何编码主要取决于处理上的方便。通常，

7、每种单词对应一个整数码。对应一个整数码。 注意：保留字、运算符和界符的个数确定，注意：保留字、运算符和界符的个数确定， 标识符和常数的个数不确定。标识符和常数的个数不确定。 保留字：保留字：可全体视为一种，也可一字一种；可全体视为一种，也可一字一种； 标识符：标识符：统归为一种；统归为一种； 常数：常数：统归为一种统归为一种,或按整、实、布尔等再分；或按整、实、布尔等再分； 运算符和界符：运算符和界符：一符一种，或统归为一种。一符一种，或统归为一种。93.1.3 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值 单词符号的属性是指单词符号的特征值 。如果一个种别只含有

8、一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因而不需要属性值。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性值。103.1.3 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值标识符和常数标识符和常数 标识符的标识符的内部码内部码 (如如ASCII码等等码等等)和和常数本身的值常数本身的值 (二二进制，逻辑值等进制，逻辑值等)来表示。来表示。 标识符的标识符的符号表入口地址符号表入口地址作为其单词符号的属性值作为其单词符号的属性值,常常量在其量在其常量表中的入口地址常量表中的入口地址作为其单

9、词符号的属性值。作为其单词符号的属性值。每个基本字占一个单词种别，单词符号的属性值缺省每个基本字占一个单词种别，单词符号的属性值缺省。对于界符，运算符通常一个符号一个种别，单词符号的对于界符，运算符通常一个符号一个种别，单词符号的属性值缺省属性值缺省例例: : 参见参见P42.P42.表表3.1 3.1 单词符号及种别编码单词符号及种别编码113.1.4 词法分析器作为独立子程序词法分析器作为独立子程序v词法分析可采用如下两种处理结构词法分析可采用如下两种处理结构：把词法分析程序作为主程序。将词法分析作为把词法分析程序作为主程序。将词法分析作为独立的一遍来完成独立的一遍来完成。把词法分析程序作

10、为语法分析程序调用的子程把词法分析程序作为语法分析程序调用的子程序。序。v每当语法分析器需要一个单词符号时就调用这个子程每当语法分析器需要一个单词符号时就调用这个子程序。序。v每一次调用，词法分析器从源程序字符串中识别出一每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析个单词符号，并把它的内部表示二元组交给语法分析器处理。器处理。123.1.5 源程序的输入、预处理源程序的输入、预处理及超前搜索及超前搜索词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表133.1.5 源程序的

11、输入、预处理源程序的输入、预处理及超前搜索及超前搜索1.输入缓冲区输入缓冲区n词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。n输入串一般放在一个输入串一般放在一个输入缓冲区输入缓冲区中。词法分中。词法分析器的工作可以直接在输入缓冲区中进行。析器的工作可以直接在输入缓冲区中进行。但在许多情况下，可以先但在许多情况下，可以先预处理预处理输入串，识输入串，识别工作将更方便。别工作将更方便。14扫描缓冲区的结构扫描缓冲区的结构v词法分析器对扫描缓冲区进行扫描时一般词法分析器对扫描缓冲区进行扫描时一般使用两使用两个指示器个指示器，一个指向当前正在识别的单词的开始一个指向

12、当前正在识别的单词的开始位置位置, , 即指向新单词的首字符即指向新单词的首字符; ; 另一个用于向前另一个用于向前搜索以寻找单词的终点。搜索以寻找单词的终点。v不论扫描缓冲区设得多大都不能保证单词符号不不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最会被缓冲区的边界所打断。因此，扫描缓冲区最好使用如下好使用如下一分为二的区域一分为二的区域： 起点指示器起点指示器搜索指示器搜索指示器15在扫描缓冲区中扫描在扫描缓冲区中扫描v假定每个半个区可容假定每个半个区可容120120个字符，而这两个半区又个字符，而这两个半区又是是互补互补的。的。v如果搜索指示器从单词起

13、点出发搜索到一个半区的如果搜索指示器从单词起点出发搜索到一个半区的边缘但尚未达到单词的终点，那么就调用预处理子边缘但尚未达到单词的终点，那么就调用预处理子程序，令其把后续的程序，令其把后续的120120个字符装入另一个半区。个字符装入另一个半区。v认定在另一半区一定可以达到单词的终点。这意味认定在另一半区一定可以达到单词的终点。这意味着对着对标识符和常数的长度标识符和常数的长度实际上必须加以限制，否实际上必须加以限制，否则即使缓冲区再大也无济于事。则即使缓冲区再大也无济于事。23 ：=100； begin .ab1 起点起点搜索搜索163.1.5 源程序的输入、预处理及超前搜索源程序的输入、预

14、处理及超前搜索2.预处理预处理v预处理的原因预处理的原因 源程序中包含源程序中包含回车回车, ,换行换行, ,多余空白符多余空白符, ,注释行等编注释行等编辑辑字符字符, , 它们对程序逻辑功能无任何影响，它们对程序逻辑功能无任何影响， 在词法分在词法分析之前析之前, ,首先要剔除掉这些符号首先要剔除掉这些符号, ,使得词法分析更为简单。使得词法分析更为简单。 一行语句结束应配上一个特殊字符说明。一行语句结束应配上一个特殊字符说明。 有些语言要识别标号区，区分标号语句，找出续有些语言要识别标号区，区分标号语句，找出续行符连接成完整语句等。行符连接成完整语句等。 输出源程序清单以便复核。输出源程

15、序清单以便复核。173.1.5 源程序的输入、预处理及超前搜索源程序的输入、预处理及超前搜索 预处理子程序任务预处理子程序任务 从输入缓冲区中读取源程序，预处理从输入缓冲区中读取源程序，预处理后送入扫描缓冲区。此时，扫描缓冲区的字后送入扫描缓冲区。此时，扫描缓冲区的字符都是有效字符。符都是有效字符。 词法分析程序这时可以再对扫描缓冲词法分析程序这时可以再对扫描缓冲区进行扫描。区进行扫描。183.1.5 源程序的输入、预处理及超前搜索源程序的输入、预处理及超前搜索v超前搜索超前搜索一般高级语言不必一般高级语言不必超前搜索超前搜索，每个单词间有明，每个单词间有明确的确的界符界符；某一些语言的单词间

16、没有明确的某一些语言的单词间没有明确的界符界符，究竟起，究竟起什么作用，要在上下文环境中才能识别。什么作用，要在上下文环境中才能识别。在读在读到一个单词后，在输入缓冲区或扫描缓冲区上到一个单词后，在输入缓冲区或扫描缓冲区上做个标记，然后继续向前读，直到明确了刚才做个标记，然后继续向前读，直到明确了刚才单词的含义之后，再退回到坐标记出重新分析单词的含义之后，再退回到坐标记出重新分析，这个过程就是这个过程就是超前搜索超前搜索。193.1.5 源程序的输入、预处理及超前搜索源程序的输入、预处理及超前搜索v超前搜索超前搜索超前搜索举例超前搜索举例(FORTRAN(FORTRAN语句语句) )：(1)I

17、F(M) 10,20,30(1)IF(M) 10,20,30 算术条件语句算术条件语句(2)IF(5.EQ.M) GOTO 50(2)IF(5.EQ.M) GOTO 50 逻辑条件语句逻辑条件语句(3)IF=100(3)IF=100 简单变量赋值简单变量赋值(4)If(100)=ABC(4)If(100)=ABC 下标变量赋值下标变量赋值当读到当读到IFIF是不能区分是不能区分IFIF做什么，需要超前搜做什么，需要超前搜索。索。203.2 词法分析程序设计词法分析程序设计v构造词法分析程序的方法构造词法分析程序的方法v词法分析程序的编写词法分析程序的编写1.1.构造词法分析程序的方法构造词法分

18、析程序的方法用用手工方式手工方式，即根据识别语言单词的状，即根据识别语言单词的状态转换图，使用某种高级语言，例如，态转换图，使用某种高级语言，例如，C C语言直接编写词法分析程序。语言直接编写词法分析程序。利用利用自动生成工具自动生成工具LEXLEX自动生成词法分析自动生成词法分析程序。程序。21有限自动机有限自动机 文法和语言文法和语言正规式与有限自动机正规式与有限自动机主要内容主要内容223.2 有限自动机 3.2.1 3.2.1 确定的有限自动机确定的有限自动机1 1 有限自动机：有限自动机： 有限自动机是一种识别装置，他能准确的识别正有限自动机是一种识别装置，他能准确的识别正规集，它为

19、词法分析程序的构造提供了方法和工具。规集，它为词法分析程序的构造提供了方法和工具。 有限自动机是具有离散输入输出系统的数学模型有限自动机是具有离散输入输出系统的数学模型，它具有有限数目的内部状态，系统可以根据当前所，它具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继行为。其处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去输入处理的信息当前状态概括了过去输入处理的信息233.2 有限自动机2 2 有限自动机的模型：有限自动机的模型：a a b bc cd de e243.2 有限自动机2 2 有限自动机的模型：有限自动机的模型：a a b bc c

20、d de e253.2 有限自动机2 2 有限自动机的模型：有限自动机的模型：a a b bc cd de e263.2 有限自动机2 2 有限自动机的模型：有限自动机的模型：a a b bc cd de e z z273.2 有限自动机2 2 有限自动机的模型：有限自动机的模型：a a b bc cd de e z z28注：注： 可以用状态转换图表示状态变换，状态可以用状态转换图表示状态变换，状态用结点表示，读入符号用边表示用结点表示，读入符号用边表示3.2 有限自动机29例：正规式例：正规式=（）*的状态转换图形如下：的状态转换图形如下：3.2 有限自动机30例：正规式例：正规式=（）*

21、的状态转换图形如下：的状态转换图形如下：3.2 有限自动机313.2 有限自动机32 3.2.1 3.2.1 确定的有限自动机确定的有限自动机3.2 有限自动机：输入字符的有限集合（或有穷字母表），每：输入字符的有限集合（或有穷字母表），每个元素是一个输入字符个元素是一个输入字符33 3.2.1 3.2.1 确定的有限自动机确定的有限自动机3.2 有限自动机34 3.2.1 3.2.1 确定的有限自动机确定的有限自动机3.2 有限自动机352. 状态转换关系表示状态转换关系表示状态转换矩阵状态转换矩阵：DFA的映射关系有一个矩阵来表示的映射关系有一个矩阵来表示状态转换图：状态转换图：注：注：1

22、）用矩阵表示转换便于计算机处理，但不直观；用）用矩阵表示转换便于计算机处理，但不直观；用状态转换图标是比较直观状态转换图标是比较直观2）在整个状态转换图中只有一个初始状态结点，用）在整个状态转换图中只有一个初始状态结点，用“”射入的结点表示初始状态，可有若干终止状态（射入的结点表示初始状态，可有若干终止状态（也可能没有），用双圆圈表示。若初始状态结点同时也可能没有），用双圆圈表示。若初始状态结点同时又是终止状态结点，则表示空串又是终止状态结点，则表示空串可为相应可为相应DFA识别识别3.2 有限自动机363.2 有限自动机37输输入入状状态态ab0121322133*333.2 有限自动机0

23、01 12 23 3383.2 有限自动机0 01 12 23 3393.2 有限自动机40故：故：DFADFA：M=(0,1,2,3,a,b,c,f,0,1,2,M=(0,1,2,3,a,b,c,f,0,1,2,3)3)其中：其中：f f f(0,a)=1 f(0,b)=1 f(0,a)=1 f(0,b)=1 f(0,c)=1 f(1,a)=1 f(0,c)=1 f(1,a)=1 f(1,b)=1 f(1,c)=1 f(1,b)=1 f(1,c)=1 f(2,a)=3 f(2,b)=2 f(2,a)=3 f(2,b)=2 f(2,c)=2 f(3,b)=3 f(2,c)=2 f(3,b)=3

24、 f(3,c)=2 f(3,b)=3 f(3,c)=2 f(3,b)=33.2 有限自动机413 3）一步动作）一步动作每读一个字符，状态就向前进至下每读一个字符，状态就向前进至下一个状态；记为：一个状态；记为：“”k k表示自动机做了表示自动机做了K K步动作步动作* *表示自动机做了表示自动机做了0 0步动作或步动作或0 0步以步以上动作。上动作。+ +表示自动机做了表示自动机做了1 1步动作或步动作或1 1步以步以上动作。上动作。4 4）DFADFA对字符串的识别对字符串的识别定义：串定义：串a a*为为DFA M=(Q, ,f，q0,Z)所识别，当且仅当（所识别，当且仅当（q0,a）

25、* *(q,),(q,),且且q qZ3.2 有限自动机42DFADFA的确定性表现在的确定性表现在对任何状态对任何状态q Qq Q，在读入了输入符号，在读入了输入符号a a 之后，能够之后，能够唯一地确定唯一地确定下一个状态下一个状态映射函数映射函数f f：Q QQQ是一个是一个单值单值函数函数从状态转换图来看，若字母表从状态转换图来看，若字母表含有含有n n个个输入字符，那末任何一个状态结点输入字符，那末任何一个状态结点最多有最多有n n条弧射出条弧射出，而且每条弧以一个，而且每条弧以一个不同的输入不同的输入字符字符标记。标记。3.2 有限自动机43443.2 有限自动机不能被自动机接受的

26、字符串有两种情况不能被自动机接受的字符串有两种情况45例例：证明证明t=baab被下图的被下图的DFA所接受。所接受。f（S，baab）=f（f（S，b），），aab） = f（V，aab）= f（f（V，a），），ab） =f（U，ab）=f（f（U，a），），b） =f（Q，b）=QQ属于终态。属于终态。得证。得证。bSUVQabba, baa3.2 有限自动机46识别过程有两种方法：识别过程有两种方法：1）用转换函数的形式）用转换函数的形式2）用状态转换图）用状态转换图3.2 有限自动机47例P32 例2-153.2 有限自动机483.2.2 非确定的有限自动机3.2 有限自动机v定义定

27、义2.272.27 非确定的有穷自动机非确定的有穷自动机NFANFA也是一个五元组也是一个五元组 M=M=（Q Q， ，f f，q q0 0，Z Z ），其中：），其中： Q Q：为状态的有限状态集合；：为状态的有限状态集合； ：为有穷输入字母表；：为有穷输入字母表； f f：为为S S * * 到到S S的幂集的幂集(2(2S S) )的一种映射的一种映射: :S S * * 2 2S S 注意：后续状态是不唯一的，它是状态集注意：后续状态是不唯一的，它是状态集Q Q的子集的子集 q q0 0： Q Q是初始状态集，是初始状态集， Z Z： Q Q为终止状态集为终止状态集( (可空可空).)

28、.493.2.2 非确定的有限自动机3.2 有限自动机 注意：注意： 非确定主要是指后续状态可以有多个非确定主要是指后续状态可以有多个 DFADFA是是NFANFA的特例的特例 非确定的有限自动机也可以用状态图非确定的有限自动机也可以用状态图及状态矩阵表示及状态矩阵表示503.2 有限自动机设设NFA M=(q0,q1,0,1,f,q0q1)NFA M=(q0,q1,0,1,f,q0q1)映射为：映射为：字符状态01q0q0q1q1q0.q1q0至少包含一个至少包含一个1 1的二进制串的二进制串51NFA的矩阵表示v例：例：NFA M=(SNFA M=(S，P P，ZZ，00，11，f f，S

29、S，PP，Z)Z)其中：其中： f(f(S S，0)=P0)=Pf(Sf(S，1)=S1)=S，ZZf(Zf(Z，0)=P0)=Pf(Zf(Z，1)=P1)=Pf(Pf(P，1)=Z1)=Zv矩阵表示矩阵表示从从NFA的矩阵表示中可以看出，表项是状态的集合，的矩阵表示中可以看出，表项是状态的集合，而在而在DFA的矩阵表示中，表项是一个状态的矩阵表示中，表项是一个状态输入输入状态状态0 01 1S SPPS,ZS,ZP PZZZ ZPPPP52v一个含有一个含有m m个状态，个状态，n n个输入字符的个输入字符的NFANFA的状态转换图：的状态转换图：有有m m个结点，每个结点可射出若干条弧与别

30、的结点相个结点，每个结点可射出若干条弧与别的结点相连接，每条弧用连接，每条弧用 * * 上的一个字来表示上的一个字来表示( (这些字可以这些字可以相同，也可以是相同，也可以是)。v整个图至少有一个初始结点以及若干个整个图至少有一个初始结点以及若干个( (可以是可以是0 0个个) )终态结点，某些结点既可以是初态结点，又可以是终态结点，某些结点既可以是初态结点，又可以是终态结点。终态结点。f(S，0)=Pf(S，1)=S，Zf(Z，0)=Pf(Z，1)=Pf(P，1)=ZSPZ00,1111状态图表示53DFADFA与与NFANFA的主要区别的主要区别（1 1）DFADFA任何状态都没有任何状态

31、都没有转换，即没有任何转换，即没有任何状态可以不进行输入符号的匹配就直接进入状态可以不进行输入符号的匹配就直接进入下一个状态；下一个状态；（2 2）DFADFA对任何状态对任何状态q q和任何输入符号和任何输入符号a a，最多，最多只有一条标记为只有一条标记为a a的边离开的边离开q q，即转换函数，即转换函数：S S S S是一个单值部分函数。是一个单值部分函数。（3 3）DFADFA的初态唯一，的初态唯一，NFANFA的初态为一集合。的初态为一集合。54*上的符号串t被NFA M接受（识别）:v对于对于*中的任何一个串中的任何一个串t，若存在一条从某一初态，若存在一条从某一初态结点到某一终

32、态结点的通路，且这条通路上所有结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的串弧的标记字依序连接成的串(不理采那些标记为不理采那些标记为的弧的弧)等于等于t，则称，则称t可为可为NFA M所识别所识别(读出或接读出或接受受)。v若若M的某些结点既是初态结点又是终态结点；或的某些结点既是初态结点又是终态结点；或者存在一条从某个初态结点到某个终态结点的道者存在一条从某个初态结点到某个终态结点的道路路,其上所有弧的标记均为其上所有弧的标记均为，那么空字，那么空字可为可为M所所接受。接受。55例：例：给出一个非确定的有限自动机给出一个非确定的有限自动机M=(q0,q1,q2,q3,q

33、4,0,1,f,q0,q2,q4)状态函数状态函数f为：为：f(q0,0)=q0,q3 f(q0,1)=q0,q1f(q1,0)= f(q1,1)=q2f(q2,0)=q2 f(q2,1)=q2f(q3,0)=q4 f(q3,1)= f(q4,0)=q4 f(q4,1)=q43.2 有限自动机56状态矩阵（状态表）状态矩阵（状态表）01Q0q0,q3q0,q1)Q1Q2Q2q2Q2Q3Q4q4Q4q43.2 有限自动机57状态图状态图3.2 有限自动机58输入串：输入串：010110有：有：q0，q0，q0，q1，q2，q2可以识别可以识别3.2 有限自动机594v例例13a2a b接受串接受

34、串abb的移动序列的移动序列:-12424abb -1342424bba -转换（转换（ -transition）:是无需考虑输入串是无需考虑输入串就有可能发生的转换。就有可能发生的转换。3.2 有限自动机603.2.3 3.2.3 确定的有限自动机与非确定的有限自确定的有限自动机与非确定的有限自动机的等价动机的等价3.2 有限自动机v定义：对于任何两个有限自动机定义：对于任何两个有限自动机M M和和MM，如果，如果L(M)=L(M)L(M)=L(M)，则称，则称M M与与MM等价。等价。613.2.3 3.2.3 确定的有限自动机与非确定的有限自动机的等价确定的有限自动机与非确定的有限自动机

35、的等价3.2 有限自动机v自动机理论中一个重要的结论：判定两个自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。自动机等价性的算法是存在的。v对于每个对于每个NFA MNFA M存在一个存在一个DFA MDFA M，使得，使得 L(M)=L(M)L(M)=L(M)。亦即。亦即DFADFA与与NFANFA描述能力相同。描述能力相同。623.2 有限自动机定义定义2.282.28设非确定的有限自动机设非确定的有限自动机M=(M=(Q，f，q0，Z ) )。假设假设I I是是M M的状态集的状态集Q Q的一个子集（即的一个子集（即I I Q），则定），则定义义closure(I)clo

36、sure(I)为：为：1 1）若）若qIqI，则，则q closure(I);q closure(I);2 2）若）若qIqI，则对任意，则对任意qfqf（q, )q, )，有，有q q closure(I);closure(I);状态集状态集closure(I)closure(I)称为状态集称为状态集I I的的闭包闭包633.2 有限自动机例例2-182-18给定非确定的有限自动机给定非确定的有限自动机M1M1，如下图所示，如下图所示61b 234578aa 643.2 有限自动机设设I=5I=5，则，则closure(I)= closure(I)= closure(5)=5,6,2clos

37、ure(5)=5,6,2设设I=1I=1，则，则closure(I)= closure(1)=1,2closure(I)= closure(1)=1,2设设I=1,5I=1,5，则，则closure(I)= closure(1closure(I)= closure(1，5)5) = closure(2) = closure(2)closure(5)closure(5) =1,2,5,6 =1,2,5,66566练习：练习：4f35621i aaaabbbbclosure(i) closure(1)closure(5) closure(1,6)673.2 有限自动机定义定义2.292.29 设非

38、确定的有限自动机设非确定的有限自动机M=(M=(Q Q， ，f f，q q0 0，Z Z ) )。假设假设I IQ Q， ， 则定义则定义I I=closure(pf(q, )|q =closure(pf(q, )|q closure(I) closure(I)），）， 即即II是所有从是所有从I I的的闭包出发，经过一条闭包出发，经过一条弧到达的状态集的弧到达的状态集的闭包闭包683.2 有限自动机例例2-192-19给定非确定的有限自动机给定非确定的有限自动机M1M1，如下图所示，如下图所示61b 234578aa 693.2 有限自动机设设I=1,I=1,则则I I= = 55，4 4，

39、6 6，2 2，77Ib=3Ib=3，88设设I=5,I=5,则则Ia=Ia=Ib=3Ib=3，88设设I=1,5I=1,5Ia=5Ia=5，4 4，6 6，2 2，77Ib=3Ib=3，8870练习：练习：4f35621i aaaabbbb设设I=i，则，则Ia=? Ib=? 设设I=1，则，则Ia=? Ib=？ 设设I=i，5，则，则Ia=？Ib=?713.2 有限自动机定理定理2.12.1 对任何一个非确定的有限自动机对任何一个非确定的有限自动机M M，都存，都存在一个确定的有限自动机在一个确定的有限自动机MM，使，使L(M)=L(M)L(M)=L(M)v对于任何两个有限自动机对于任何两

40、个有限自动机M M和和MM，如果，如果L(M)=L(M)L(M)=L(M)，则称，则称M M与与MM等价。等价。v自动机理论中一个重要的结论：判定两个自自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。动机等价性的算法是存在的。723.2 有限自动机算法算法2.12.1：非确定的有限自动机的确定化算：非确定的有限自动机的确定化算法法子集法子集法输入：非确定的有限自动机输入：非确定的有限自动机M=(M=(Q，f，q0，Z ) )输出：确定的有限自动机输出：确定的有限自动机M=(M=(Q，f，q0，Z ) )算法：算法：P37P37733.2 有限自动机v对对NFA NFA 进行确定

41、化，构造状态转换进行确定化，构造状态转换表：表：1.1. = a= a1 1a ak k, , 则初始时该表有则初始时该表有k+1k+1列，列，分别为分别为I I、IaIa1 1 IaIak k，首行首列为首行首列为 - -closure(Xclosure(X) )，(X(X为开始结点为开始结点) )；742.2 有限自动机v对对NFA NFA 进行确定化，构造状态转换表：进行确定化，构造状态转换表：2.每行的值每行的值Iak = -closure(move(I,a)，其，其行行数未知；数未知；3.将新产生的将新产生的Iak集合加入到集合加入到I中作为新的一行，中作为新的一行，并求该集合并求该

42、集合I的的Ia1 Iak ，重复之，直到，重复之，直到状态不再增加；状态不再增加；4. 初态初态就是首行首列的状态，就是首行首列的状态，终态终态是含有原是含有原终态的集合。终态的集合。状态集合状态集合I的的a弧转换，表示为弧转换，表示为move(I,a)定定义为状态集合义为状态集合J，其中，其中J是所有那些可从是所有那些可从I的某一状态经的某一状态经过一条过一条a弧而到达的状态的全体弧而到达的状态的全体752.2 有限自动机v对对NFA NFA 进行确定化，构造状态转换表：进行确定化，构造状态转换表：v = a1ak, 则初始时该表有则初始时该表有k+1列，分别为列，分别为I、Ia1 Iak，

43、首行首列为首行首列为 -closure(X)，(X为开始为开始结点结点)；v每行的值每行的值Iak = -closure(move(I,a)，其其行数未知；行数未知；v将新产生的将新产生的Iak集合加入到集合加入到I中作为新的一行，并中作为新的一行，并求该集合求该集合I的的Ia1 Iak ，重复之，直到状态不再，重复之，直到状态不再增加；增加；1.初态初态就是首行首列的状态，就是首行首列的状态，终态终态是含有原终态的是含有原终态的集合。集合。76例6：将下述NFA确定化4f35621iaaaabbbbi,1,2 1,2,31,2,41,2,3 1,2,3,5,6,f1,2,41,2,4 1,2

44、,31,2,4,5,6,f1,2,3,5,6,f 1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f 1,2,3,6,f1,2,4,5,6,f1,2,4,6,f 1,2,3,6,f1,2,4,5,6,f1,2,3,6,f SABCDEFACACFFCBBDEDDEIIaIb1,2,3,5,6,f1,2,4,6,f77将将M确定化，并画出确定化后的状态转换图确定化，并画出确定化后的状态转换图（要求：写出步骤）（要求：写出步骤）(1) 给定非确定的有限自动机给定非确定的有限自动机M如下图所示如下图所示78aakyibxjab79NFANFA到相应的到相应的DFADFA的构造的基本思路是

45、：的构造的基本思路是： DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状态的一组状态80v NFA NFA确定化的实质是以确定化的实质是以原有状态集上的覆原有状态集上的覆盖片作为盖片作为DFADFA上的一个状态，将原状态间的转上的一个状态，将原状态间的转换改为覆盖片间的转换换改为覆盖片间的转换，从而把不确定问题确，从而把不确定问题确定化。定化。v 通常经过确定化之后，状态数增加，而且通常经过确定化之后，状态数增加，而且可能出现一些等价状态，这时需要可能出现一些等价状态，这时需要化简化简。813.2.4 3.2.4 确定的有限自动机的化简确定的有限自动机的化简化简条件：接受的语言

46、必须相同化简条件：接受的语言必须相同定义定义2.302.30 设确定的有限自动机设确定的有限自动机M M的两个不同状态的两个不同状态q1q1，q2q2，如果对任意输入字符串，如果对任意输入字符串，从，从q1q1，q2q2状状态出发，总是同时到达接受状态或拒绝状态之态出发，总是同时到达接受状态或拒绝状态之中，中，则称则称q1q1，q2q2是等价的。是等价的。3.2 有限自动机82 即对于即对于（ * *），有），有f(q1f(q1， )=p1)=p1，f(q2f(q2， )=p2 )=p2，p1,p2 Zp1,p2 Z或或p1,p2 Zp1,p2 Z，则，则q1q1，q2q2等价，等价，记作记作

47、q1q1q2q2。 如果两个状态不等价，则称如果两个状态不等价，则称q1q1，q2q2是可是可区别的区别的3.2 有限自动机83状态状态q1q1和和q2q2等价的条件等价的条件 一致性条件一致性条件 状态状态q1q1和和q2q2必须同必须同时为可接受状态或不可接受状态。时为可接受状态或不可接受状态。 蔓延性条件蔓延性条件 对于所有输入符号，对于所有输入符号，状态状态q1q1和状态和状态q2q2必须转换到等价的状态里。必须转换到等价的状态里。3.2 有限自动机843.2.4 3.2.4 确定的有限自动机的化简确定的有限自动机的化简定义定义2.312.31 如果从确定的有限自动机如果从确定的有限自

48、动机M M的初态开始，的初态开始，识别任何输入序列都不能达到的那些状态称识别任何输入序列都不能达到的那些状态称为为无关状态无关状态定义定义2.322.32 如果确定的有限自动机如果确定的有限自动机M M既没有无关状既没有无关状态，也没有彼此等价的状态，则称确定的有态，也没有彼此等价的状态，则称确定的有限自动机限自动机M M是是规约的规约的（即（即最小的确定的有限最小的确定的有限自动机自动机M M）。）。3.2 有限自动机85DFADFA的最小化的最小化就是寻求状态数最少的就是寻求状态数最少的DFADFA，即：，即：它没有多余状态它没有多余状态(死状态死状态) ；（消去）（消去）它的状态中没有两

49、个是互相等价的它的状态中没有两个是互相等价的（不可区别）（不可区别） 。（合并）（合并）3.2 有限自动机86C C和和D D同是终态同是终态, ,读入读入a a到达到达C C和和F F, , C C和和F F同是终态同是终态, , C C和和F F读入读入a a都到达都到达C C, ,读入读入b b都到达都到达E E. . C C和和D D等价等价 87v DFADFA的化简的必要性的化简的必要性 1234567abccbd7abcbd123456c887abcbd123456cabcd1234891 1 消除无关状态消除无关状态算法思想：算法思想： 标记出所有的非无关状态，删除未标记的标记

50、出所有的非无关状态，删除未标记的无关状态无关状态算法算法2.2 2.2 消除确定的有限自动机中的无关状消除确定的有限自动机中的无关状态。态。输入：确定的有限自动机输入：确定的有限自动机M=(QM=(Q，f f，q0q0，Z)Z)输出：消除了无关状态的确定的有限自动机输出：消除了无关状态的确定的有限自动机MM3.2 有限自动机909192算法：算法：标记开始状态标记开始状态q q0 0; ;While(While(存在未处理的标记状态存在未处理的标记状态) ) 取未处理的标记状态取未处理的标记状态q q，标记为处理，标记为处理，对所有对所有 a , a ,若若f(q,a)=p,f(q,a)=p,

51、且且p p未标记，标记未标记，标记p;p;删除未标记的状态及其相关的转换。删除未标记的状态及其相关的转换。3.2 有限自动机93例：设有例：设有DFA MDFA M如表如表2-62-6所示，用算法所示，用算法2.22.2消消除无关状态除无关状态Q010151272253575317013.2 有限自动机Q010151272253574*565*316*807*0194练习：对下图所示的确定的有限自动机练习：对下图所示的确定的有限自动机M消除无关状态消除无关状态952.2.消除等价状态消除等价状态划分法划分法划分法的思想：划分法的思想： 寻找且合并确定的有限自动机寻找且合并确定的有限自动机M M

52、中的等价中的等价状态，即将确定的有限自动机状态，即将确定的有限自动机M M的状态划分成的状态划分成互不相交的子集，使得任何两个不同子集的状互不相交的子集，使得任何两个不同子集的状态都是可区别的，而同一子集的任何两个状态态都是可区别的，而同一子集的任何两个状态都是等价的。从而得到一个确定的有限自动机都是等价的。从而得到一个确定的有限自动机M M等价的且最小的确定的有限自动机等价的且最小的确定的有限自动机MM3.2 有限自动机962.2.消除等价状态消除等价状态划分法划分法划分法的思想：划分法的思想：(1)(1)将将DFA MDFA M中的状态划分为互不相交的子集，中的状态划分为互不相交的子集，每

53、个子集内部的状态都等价；而在不同子集间每个子集内部的状态都等价；而在不同子集间的状态均不等价。的状态均不等价。(2)(2)从每个子集中任选一个状态作为代表，消从每个子集中任选一个状态作为代表，消去其它的等价状态。去其它的等价状态。(3)(3)把那些原来射入其他等价状态的弧改为射把那些原来射入其他等价状态的弧改为射入相应的代表状态入相应的代表状态3.2 有限自动机973.2 有限自动机98算法算法2.32.3：消除等价状态的划分法算法：消除等价状态的划分法算法输入：确定的有限自动机输入：确定的有限自动机M =(QM =(Q，f f，q0q0，Z)Z)输出：状态数量最少的与输出：状态数量最少的与M

54、 M等价的确定的有限等价的确定的有限自动机自动机MM算法：算法：(1)(1)把把M M的所有状态的所有状态Q Q按终态与非终态划分成两按终态与非终态划分成两个状态子集个状态子集Z Z及及Q-ZQ-Z，构成初始划分（或称基本，构成初始划分（或称基本划分），记做划分），记做=（Z,Q-Z）;3.2 有限自动机99(2)Do 设当前的划分设当前的划分 中已经含有中已经含有m个子集个子集 =（Q1 1,Q2 2,Qm m） 对对 中的每个含有多于一个状态的子集中的每个含有多于一个状态的子集Qi i= （qi1i1,qi2i2qinin)(n1）和每一个）和每一个a，考察，考察nririiaaqfaQf

55、Q1),(),(3.2 有限自动机1003.2 有限自动机iaia的的p p个不同的子集个不同的子集，则将，则将Q Qi i分为分为p p个更小的子集个更小的子集Q Qi i(1)(1),Q,Qi i(2)(2),Q,Qi i(p)(p)，对对Q Qi i(j)(j),f(Q,f(Qi i(j)(j),a),a)中的全部状态都落在中的全部状态都落在的同一的同一子集之中子集之中 如此，得到一个新的划分如此，得到一个新的划分newnew，去掉原划，去掉原划分中的子集分中的子集Q Qi i，加入新的子集，加入新的子集Qi(1),Qi(2),Qi(p)，数数目由原目由原来来的的m个变为个变为m+p-1

56、个个101 While(new= ) (3) (3)对所得到的最后划分对所得到的最后划分，重新命名每个子，重新命名每个子集集Qj=Qj1,Qj2Qjr为一个状态，这些状态为一个状态，这些状态组成了组成了M的状态集的状态集Q 若若Qj中含有中含有M的初态，则代表它的状态的初态，则代表它的状态为为M的初态；若的初态；若Qj中含有中含有M的终态，则代表的终态，则代表它的状态为它的状态为M的终态的终态 并将原来值为这些状态集的转换改为转换并将原来值为这些状态集的转换改为转换到它们的到它们的代表状态代表状态。3.2 有限自动机102例：对下图所示的确定的有限自动机例：对下图所示的确定的有限自动机M化化简

57、简3.2 有限自动机103(1)(1)基本划分：基本划分：0 0=Q1,Q2=Q1,Q2 其中：其中：Q1=1,2,3,4 Q2=5,6,7Q1=1,2,3,4 Q2=5,6,7(2)(2)考查子集考查子集Q1Q1：q=1q=1时，时，f(q,a)=6f(q,a)=6q=2q=2时，时，f(q,a)=7f(q,a)=7q=3q=3时，时，f(q,a)=1f(q,a)=1q=4q=4时，时，f(q,a)=4f(q,a)=4状态状态6,76,7和状态和状态1,41,4在不同的子集，所以状态在不同的子集，所以状态1,21,2和状态和状态3,43,4不等价不等价则则Q3=1,2,Q4=3,4Q3=1,

58、2,Q4=3,4， 1 1=Q2,Q3,Q4104(3)(3)考查考查Q2Q2：q=5q=5时，时，f(q,a)=7f(q,a)=7q=6q=6时，时，f(q,a)=4f(q,a)=4q=7q=7时，时，f(q,a)=4f(q,a)=4状态状态7 7和状态和状态4 4在不同的子集，所以状态在不同的子集，所以状态5 5和状态和状态6 6、7 7不等价，则将不等价，则将Q2Q2分成两个子集；分成两个子集；Q5=5,Q6=6Q5=5,Q6=6，77得到一个新的划分：得到一个新的划分：2=Q3,Q4,Q5,Q6= 1,2,3,4,5,6,71,2,3,4,5,6,7105(4)(4)考查考查Q3Q3：

59、q=1q=1时，时，f(q,a)=6f(q,a)=6q=2q=2时，时，f(q,a)=7f(q,a)=7状态状态6 6和状态和状态7 7在同一子集在同一子集q=1时，时，f(q,b)=3q=2时，时，f(q,b)=3划分不变划分不变2=Q3,Q4,Q5,Q6= 1,2,3,4,5,6,71,2,3,4,5,6,7106(5)(5)考查考查Q4Q4：q=3q=3时，时，f(q,a)=1f(q,a)=1q=4q=4时，时，f(q,a)=4f(q,a)=4状态状态1 1和状态和状态4 4在不同子集中，将在不同子集中，将Q4Q4划分成划分成两个子集两个子集Q7=3,Q8=4Q7=3,Q8=43=Q3,

60、Q5,Q5,Q6,Q7,Q8=3=Q3,Q5,Q5,Q6,Q7,Q8= 1,2,5,6,7,3,4 1,2,5,6,7,3,4107(6)(6)考查考查Q6Q6：q=6q=6时，时，f(q,a)=4f(q,a)=4q=7q=7时，时，f(q,a)=4f(q,a)=4q=6q=6时，时，f(q,b)=1f(q,b)=1q=7q=7时，时，f(q,b)=2f(q,b)=2划分不变划分不变3=Q3,Q5, Q6,Q7,Q8=3=Q3,Q5, Q6,Q7,Q8= 1,2,5,6,7,3,4 1,2,5,6,7,3,4108(7)(7)对最后划分中的子集重命名为状态：对最后划分中的子集重命名为状态：A: