第4章-词法分析ppt课件.ppt

《第4章-词法分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章-词法分析ppt课件.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌第第4 4章章 词法分析词法分析 本章将讨论词法分析程序的设计原则，本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析单词的描述技术，识别机制及词法分析程序的自动构造原理。程序的自动构造原理。4.1 对于词法分析程序的要求对于词法分析程序的要求4.2 正规表达式与正规集（正规语言）正规表达式与正规集（正规语言）4.3 有穷自动机有穷自动机4.5 正规文法与有穷自动机的等价性正规文法与有穷自动机的等价性4.4 正规式与有穷自动机的等价性正规式与有穷自动机的等价性4.6 词法分析程序的自动构造词法分析程序的自动构造武汉理

2、工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌本章重点本章重点 单词的描述工具单词的描述工具 单词的识别系统单词的识别系统 设计和实现词法分析程序设计和实现词法分析程序首先需要描述和刻画程序设计语言中的首先需要描述和刻画程序设计语言中的原子单位原子单位单词，其次需要识别单词单词，其次需要识别单词和执行某些相关的动作和执行某些相关的动作。描述程序设计语言的词法的机制是正则描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。表达式，识别机制是有穷状态自动机。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌词法分析程序词法分析程序 实现词法分析（实现词法分析（le

3、xical analysislexical analysis）的程）的程序称为词法分析程序（或扫描器）。序称为词法分析程序（或扫描器）。对构成源程序的字符串从左到右的扫描，对构成源程序的字符串从左到右的扫描，逐个字符地读入源程序字符并按照构词规则逐个字符地读入源程序字符并按照构词规则切分成一个一个具有独立意义的单词。并确切分成一个一个具有独立意义的单词。并确定其属性（如保留字、标识符、运算符、界定其属性（如保留字、标识符、运算符、界限符和常量等）。再把它们转换成长度统一限符和常量等）。再把它们转换成长度统一的标准形式的标准形式属性字（属性字（TOKENTOKEN）。）。词法分析程序的主要任务：

4、词法分析程序的主要任务：武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 词法分析是编译过程中的第一个阶段，词法分析是编译过程中的第一个阶段，在语法分析前进行在语法分析前进行 。也可以和语法分析结。也可以和语法分析结合在一起作为一遍，由语法分析程序调用合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析词法分析程序来获得当前单词供语法分析使用。使用。源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token. .词法分析程序和语法分析程序的关系词法分析程序和语法分析程序的关系武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天

5、煌 词法分析工作从语法分析工作独立出词法分析工作从语法分析工作独立出来的原因：来的原因：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 4.1 4.1 对于词法分析器的要求对于词法分析器的要求4.1.1 4.1.1 词法分析器的功能和输出形式词法分析器的功能和输出形式功能：输入源程序，输出单词符号。功能：输入源程序，输出单词符号。 单词符号是一个程序语言的基本语法符号。单词符号是一个程序语言的基本语法符号。单词的分类（五类）：单词的分类（五类）：(1) 关键字：关键字：由程序语言定义的具有固定意义

6、的标由程序语言定义的具有固定意义的标识识 符。也称为保留字或基本字。符。也称为保留字或基本字。(2) 标识符：标识符：用来表示程序中各种名字的字符串。用来表示程序中各种名字的字符串。(3) 常常 数：数：常数的类型一般有整型、实型、布尔型、常数的类型一般有整型、实型、布尔型、文字型。文字型。(4) 运算符：运算符：如如+、 、*、/ 等。等。(5) 界限符：界限符：如逗号、分号、括号等。如逗号、分号、括号等。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 一个程序语言的关键字、运算符、界限符都是固一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标识符和

7、常数通定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。常是不确定的。 词法分析器所输出的单词符号常常表示成如词法分析器所输出的单词符号常常表示成如下的二元式：下的二元式： （单词种别，单词符号的属性值）（单词种别，单词符号的属性值） 单词种别通常用整数编码。一个语言的单词符号如何分单词种别通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码，是一个技术性的问题。它主要取种，分成几种，怎样编码，是一个技术性的问题。它主要取决于处理上的方便。标识符一般统归为一种。常数则直按类决于处理上的方便。标识符一般统归为一种。常数则直按类型（整、实、布尔等）分种。关键字可将其全体视为一

8、种，型（整、实、布尔等）分种。关键字可将其全体视为一种，也可以一字一种。采用一字一种的分法实际处理起来较为方也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般用一符一种的分法。性的运算符视为一种。至于界符一般用一符一种的分法。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 如果一个种别只含一个单词符号，那么，如果一个种别只含一个单词符号，那么，对于这个单词符号，种别编码就完全代表它对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个

9、单词符号，那自身了。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性信编码之外，还应给出有关单词符号的属性信息。息。 单词符号的属性是指单词符号的特性或单词符号的属性是指单词符号的特性或特征。属性值则是反应特性或特征的值。例特征。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的有关信如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；对于某息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为个常数，则将存放它的常数表项的指针作为其属性值。其属性

10、值。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 在教材中，我们假定关键字、运算符和界限在教材中，我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出符都是一符一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一其种别编码，不给出它自身的值。标识符单列一种。常数按类型分种。种。常数按类型分种。考虑下述考虑下述C十代码段：十代码段： while（ij）i； 经词法分析器处理后，它将被转换为如下的经词法分析器处理后，它将被转换为如下的单词符号序列：单词符号序列： while， （，（， id，指向，指向i的符号表项的指针的符号表项的指针 ，

11、id，指向，指向j的符号表项的指针的符号表项的指针 ），）， id，指向，指向i的符号表项的指针的符号表项的指针 ， ；，；，武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.1.24.1.2词法分析器的设计词法分析器的设计 我们将按照词法分析的任务和作为一个独我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。立子程序的要求来考虑词法分析器的设计。一、一、 输入、预处理输入、预处理 词法分析器工作的第一步是输入源程序文词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分

12、析的工作（单词符冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。符号的识别工作将是比较方便的。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 某些跳格符、回车符和换行符等编辑性字符，在某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其别处的任何出现都没有意义，预处理时可以将其剔掉。剔掉。 注解部分注解部分仅在于改善程序的易读性和易理解性。仅在于改善程序的易读性和易理解

13、性。对于它们，预处理时可以将其剔掉。对于它们，预处理时可以将其剔掉。 空白符（一个或相继数个）用作单词符号之间的空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。把相继的若干个空白结合成一个。 我们可以构造一个预处理子程序，它能够完我们可以构造一个预处理子程序，它能够完成上面所述的任务。成上面所述的任务。预处理的主要工作：预处理的主要工作：武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌二、二、 单词符号的识别：超前搜索单词符号的识别：超前搜索 词法分析器的结构如图词法分析器的

14、结构如图4.14.1所示。所示。图图4.1 词法分析器词法分析器武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌三、三、 状态转换图状态转换图 状态转换图是一张有限方向图。在状态转换状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符点（即箭弧始结点）状态下可能出现的输入字符或字符类。例如，图或字符类。例如，图4.2（a）表示：在状态）表示：在状态1下，下，若输入字符为若输入字符为X，则读

15、进，则读进X，并转换到状态，并转换到状态2。若。若输入字符为输入字符为Y，则读进，则读进Y，并转换到状态，并转换到状态3。一张。一张转换图只包含有限个状态（即有限个结点），其转换图只包含有限个状态（即有限个结点），其中有一个被认为是中有一个被认为是初态初态，而且实际上至少要有一，而且实际上至少要有一个个终态终态（用双圈表示）。（用双圈表示）。123XY图图4.2（a）转换图示例）转换图示例武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 一个状态转换图可用于识别（或接受一个状态转换图可用于识别（或接受)一定的一定的字符串。字符串。 例如，识别标识符的转换图如图例如，识别标识符的转换

16、图如图4.2（b）所示。）所示。图图4.24.2（b b）识别标识符的转换图）识别标识符的转换图武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌图图4.24.2（c c）识别整数的转换图识别整数的转换图图图4.24.2（d d）识别识别FORTRAN实型常数的转换图实型常数的转换图武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.2 4.2 正规表达式与正规集（正规语言）正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，具加以

17、描述，并且基于这类描述工具，实现词法分析程序的自动构造。实现词法分析程序的自动构造。 正规表达式是典型的词法规则描述正规表达式是典型的词法规则描述工具。工具。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌正规式正规式定义定义（正规式和它所表示的正规集）：（正规式和它所表示的正规集）： 设字母表为设字母表为 ， 辅助字母表辅助字母表 = ， ， ， ， ， ， ， 正规式也称正则表达式。正规式也称正则表达式。 正规表达式（正规表达式（regular expression）是说明单词的）是说明单词的模式模式(pattern)的一种重要的表示法（记号），是定义的一种重要的表示法（记号）

18、，是定义正规集的数学工具。我们用以描述单词符号。下面正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。是正规式和它所表示的正规集的递归定义。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌1. 和和 都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集分别为集分别为 和和 ； 2. 对任何对任何a ，a是是 上的一个正规式，它所表上的一个正规式，它所表示的正规集为示的正规集为a；3. 假定假定e1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集分别为正规集分别为L(e1)和和L(e2)，那么，那么，(e1),

19、e1 e2, e1 e2, e1 也都是正规式也都是正规式, 它们所表示的正规集分它们所表示的正规集分别为别为L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 。4. 仅由有限次使用上述三步骤而定义的表达式仅由有限次使用上述三步骤而定义的表达式才是才是 上的上的正规式正规式，仅由这些正规式所表示的，仅由这些正规式所表示的集合才是集合才是 上的上的正规集正规集。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌注意注意:其中其中“ ”、 “ ”、 “ ”均为均为正规式正规式运算符：运算符：2. “ ”读为读为“连接连接”；3. “ ”读为读为“闭包闭包”（即

20、，任意有限次的自重（即，任意有限次的自重复连接）。复连接）。 在不致混淆时，括号可省去，但规定算符在不致混淆时，括号可省去，但规定算符的优先顺序为的优先顺序为“ ”、“ ”、“ ” 。连接符。连接符“ ”一般可省略不写。一般可省略不写。“ ”、“ ”和和“ ” 都是左结合的。都是左结合的。1. “ ”读为读为“或或” ；武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例子例子令令 =a，b， 上的正规式和相应的正规上的正规式和相应的正规集的例子有：集的例子有：正规式正规式 正规集正规集 a a a b a,b ab ab (a b)(a b) aa,ab,ba,bb a ,a,a,

21、 任意个任意个a的串的串武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌正规式正规式 正规集正规集(a b) ,a,b,aa,ab 所有由所有由a 和和b组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继上所有含有两个相继 的的a或两个相继的或两个相继的b组成组成 的串的串武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌讨论下面两个例子讨论下面两个例子例例4.2 有有 =d=d，. .，e e，+ +，-,-,则则 上的正规式上的正规式 d d (.dd (.dd )(e(+ )(e(+ - -)dd)dd ) )表示的是无符号数表示的是无符号数的

22、集合。其中的集合。其中d d为为0 09 9的数字。的数字。结论：结论：程序设计语言的单词都能用正规式来定义。程序设计语言的单词都能用正规式来定义。例例4.1 令令 =l，d，则，则 上的正规式上的正规式 r=l (l d) 定定 义义的正规集为的正规集为: l, l l, l d, l d d,其中其中l代表字母代表字母,d代表数字代表数字,正规式正规式 即是即是 字母字母(字母字母 数字数字) ,它表示的它表示的正规集中的每个元素的模式是正规集中的每个元素的模式是“以字母打头的字母以字母打头的字母数字串数字串”,就是就是Pascal和多数程序设计语言允许的的和多数程序设计语言允许的的标识符

23、的词法规则。标识符的词法规则。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌正规式的等价性正规式的等价性若两个正规式若两个正规式e1和和e2所表示的正规集所表示的正规集相同相同,则说则说e1和和e2等价等价,写作写作e1=e2。例如：例如： e1= (a b)， e2 = b a， e1= e2 又如：又如： e1= b(ab) , e2 =(ba) b， e1= e2 e1= (a b) , e2 =(a b ) ， e1= e2武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌设设U,V,W为正规式，正规式服从的代数规律有：为正规式，正规式服从的代数规律有：1. U

24、 V=V U “或或”服从交换律服从交换律2. U (V W)=(U V) W“或或”的可结合律的可结合律3. (UV)W=U(VW)“连接连接”的可结合律的可结合律4. U(V W)=UV UW (V W)U=VU WU分配律分配律5. U=U, U =U 是是“连接连接”的恒等的恒等元元 素零一律素零一律6. U U=UU =U UU “或或”的抽取律的抽取律武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.3 4.3 有穷自动机有穷自动机 有穷自动机有穷自动机(也称有限自动机也称有限自动机)作为一种识别装作为一种识别装置，它能准确地识别正规集，即识别正规文法所置，它能准确地

25、识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自和不确定的有穷自动机动机(Nondeterministic Finite Automata) 。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌关于关于有穷自动机有穷自动机讨论如下内容：讨论如下内

26、容： 确定的有穷自动机确定的有穷自动机DFA 不确定的有穷自动机不确定的有穷自动机NFA NFA的确定化的确定化 DFA的最小化的最小化武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌1. K1. K是一个有穷状态集，它的每个元素称为一个状态；是一个有穷状态集，它的每个元素称为一个状态；4.3.1 4.3.1 确定的有穷自动机确定的有穷自动机DFADFA 一、一、DFADFA定义：定义： 一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，s0 ，Z）, ,其中其中: :2. . 是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷

27、字母表，它的每个元素称为一个输入符号，所以也称所以也称为输入符号表；为输入符号表；3. . f是转换函数，是在是转换函数，是在KK上的单值部分映射。即，如果上的单值部分映射。即，如果 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把，我们把kj称作称作ki的一个的一个后继状态；后继状态；5. . Z K是一个终态集是一个终态集（可空）（可空），终态也称可接受状态或结，终态也称可接受状态或结束状态。束状态。4. s0 KK是唯一的一个初态；是唯一的一个初态；武汉理工大学计算机科学系

28、陈天煌武汉理工大学计算机科学系陈天煌二、一个二、一个DFA DFA 的例子：的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中其中f定义为：定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 显然，一个显然，一个DFA可用一个矩阵表示，可用一个矩阵表示，该矩阵的行表示状态，列表示输入字该矩阵的行表示状态，列表示输入字符，即符，即k行行a列的列的 矩阵元素表示矩阵元素表示f（k，a）的值。这个矩阵称为状态转换矩阵。的值。这个矩阵称为

29、状态转换矩阵。状态状态ab SUVUQVVUQ- - QQQ对于上例，有如下状态转换矩阵对于上例，有如下状态转换矩阵注意：在状态矩阵中注意：在状态矩阵中 初态结点的旁边标以初态结点的旁边标以 ；终态结点旁边标终态结点旁边标 。f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 一个一个DFADFA也可表示成一张（确定的）状态也可表示成一张（确定的）状态转换图。转换图。注意：初态结点的旁边标以注意：初态结点的旁边标以 ； 终态结点则用双圈表示。终态结点则用双圈

30、表示。 假定假定DFA M含有含有 m个状态和个状态和 n个输入字符，个输入字符，那么，这个图含有那么，这个图含有m个状态结点，每个结点顶个状态结点，每个结点顶多有多有n条箭弧射出和别的结点相连接，每条箭条箭弧射出和别的结点相连接，每条箭弧用弧用中的一个不同输入字符作标记，整张图中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个（可以是含有唯一的一个初态结点和若干个（可以是0个）个）终态结点。终态结点。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌SUQVaabbbaa,b状态状态ab SUVUQVVUQ QQQ 对于对于* *中的任何字中的任何字，若存在一条从初态

31、结点到某一终，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字符态结点的通路，且这条通路上所有弧的标记符连接成的字符串等于串等于，则称，则称可为可为DFA M所所识别识别（读出读出或或接受接受）。若）。若M的初态结点同时又是终态结点，则空字的初态结点同时又是终态结点，则空字可为可为M所识别（或接所识别（或接受）受）DFA M所能识别的字的全体记为所能识别的字的全体记为L(M) 。 如有如有 =abb，显然，显然可为上例的可为上例的DFA M所所识别识别。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 如果一个如果一个DFA M的输入字母表为的输入字母

32、表为，则我们也称则我们也称M是是的一个的一个DFA。换言之换言之： 若若t* ，f (S，t) =P，其中，其中S为为DFA M的的初态，初态，PZ，Z为终态集。则称为终态集。则称t 可为可为DFA M所接受（所接受（识别识别）。）。结论：结论：上的一个字集上的一个字集V *是正规的，是正规的，当且仅当存在当且仅当存在上的上的DFA M，使得，使得VL（ M）。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌*上的符号串上的符号串t 在在DFA M上运行上运行:一个输入符号串一个输入符号串t，（将它表示成，（将它表示成T t1的形式，其的形式，其中中T， t1 *）在）在DFA M

33、=（K，f，S，Z）上运行的定义为：）上运行的定义为：f（Q， Tt1）=f（f（Q，T），），t1）,其中其中QK;扩充转换函数扩充转换函数f 为为 K*K上的映射，且：上的映射，且： f（ki， ）= ki 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例：证明例：证明t=baab被下图的被下图的DFA所接受所接受。 bSUVQabbb,aaaf（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属于终态。属于终态。 得证。得证。武汉理工大学计算机科学系陈天煌

34、武汉理工大学计算机科学系陈天煌三、三、DFADFA的确定性表现两个方面：的确定性表现两个方面：1. 1. 映射映射f：KK是一个单值函数。也就是说，是一个单值函数。也就是说，对任何状态对任何状态sK和输入符号和输入符号a a，f（s，a）唯一唯一地确定了下一状态。从转换图的角度来看，假定字地确定了下一状态。从转换图的角度来看，假定字母表母表含有含有n n个输入字符，那么，任何一个状态结个输入字符，那么，任何一个状态结最多只有最多只有n n条弧射出，而且每条弧以一个不同的输条弧射出，而且每条弧以一个不同的输入字符标记。入字符标记。 2. 2. DFA有且仅有唯一的一个初态有且仅有唯一的一个初态s

35、0K 。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.3.2 4.3.2 非确定的有穷自动机非确定的有穷自动机NFANFA1. K. K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2. . 是一个有穷字母表，它的每个元素称为一个输入符是一个有穷字母表，它的每个元素称为一个输入符 号，所以也称号，所以也称为输入符号表；为输入符号表；3. . f 是是状态状态转换函数，是在转换函数，是在K*K的子集的映射，即，的子集的映射，即，f: f: K*2K ；表明在某状态下对于某；表明在某状态下对于某输入符号可能有多个后输入符号可能有多个后继状态；继状

36、态；5. . Z K是一个终态集是一个终态集（可空）。（可空）。4. S K K是一个非空初态集；是一个非空初态集； 一一、NFA定义定义：一个非确定的有穷自动机（一个非确定的有穷自动机（NFA）M是一个五元组：是一个五元组：M=（K，f，S ，Z）, ,其中其中: :武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌二、一个二、一个NFA NFA 的例子：的例子：NFA M=（S，P，Z，0，1，f，S，P，Z）其中其中 ： f（S，0）=Pf（Z，0）=Pf（P，1）=Zf（Z，1）=Pf（S，1）=S，ZSPZ00,1111状态图表示状态图表示武汉理工大学计算机科学系陈天煌武汉

37、理工大学计算机科学系陈天煌矩阵表示矩阵表示简化为简化为0 01 1SPS,Z0 0PZ0 0ZPP1 1+01SPS,Z0PZ0ZPP1+武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFAN，一定存在一个不具有，一定存在一个不具有 转移的不确定转移的不确定的有穷自动机的有穷自动机NFA，使得，使得L(M)=L(N)。定理：定理：与上例等价的一个与上例等价的一个NFA：c12 3abc2acbb31acabb武汉理工大学计算机科学系陈天煌武汉理工

38、大学计算机科学系陈天煌 类似类似DFA, 对对NFA M= K， ，f，S，Z 也有如下定义：也有如下定义：*上的符号串上的符号串t t在在NFA M上运行：上运行：一个输入符一个输入符号号串串 t，（我们将它表示成，（我们将它表示成T t1的形式，其中的形式，其中T，t1 *）在）在NFA M上运行的定义为：上运行的定义为：f（Q， Tt1）=f（f（Q，T），），t1） 其中其中QK。*上的符上的符号号串串 t 被被NFA M接受：接受：若若t *，f(S0，t)=P，其中，其中S0 S，P Z，则称，则称 t为为NFA M所所接受（识别）接受（识别）武汉理工大学计算机科学系陈天煌武汉理工

39、大学计算机科学系陈天煌* *上的符号串上的符号串t t被被NFA MNFA M接受也可以这样理解接受也可以这样理解: : 对于对于*中的任何一个串中的任何一个串t，若存在一条从，若存在一条从某一初态结到某一终态结的道路，且这条道某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串路上所有弧的标记字依序连接成的串(不理采不理采那些标记为那些标记为的弧的弧)等于等于t，则称，则称t可为可为NFA M所识别所识别(读出或接受读出或接受)。若。若M的某些结既是初的某些结既是初态结又是终态结，或者存在一条从某个初态态结又是终态结，或者存在一条从某个初态结到某个终态结的道路结到某个终态结

40、的道路,其上所有弧的标记均其上所有弧的标记均为为，那么空字可为，那么空字可为M所接受。所接受。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌结论：结论： NFA M所能接受的符所能接受的符号号串的全体记串的全体记为为 L(M)。 上一个符上一个符号号串集串集V 是正规的，是正规的，当且仅当存在一个当且仅当存在一个 上的不确定的有穷上的不确定的有穷自动机自动机M，使得，使得V=L(M)。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.3.3 NFA4.3.3 NFA与与DFADFA的等价性：的等价性：显然，显然， DFA是是NFA的特例。的特例。 对于每个对于每个N

41、FA M，存在一个，存在一个DFA M ，使，使得得L( M ) =L( M )。对每个对每个NFA M存在着与之存在着与之等价的等价的DFA M。即：对于任何两个有穷自动机即：对于任何两个有穷自动机M和和M，如果，如果L( M )=L( M )，则称，则称M与与M是等价的。是等价的。有一种算法，将有一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA。这种算法称为这种算法称为子集法子集法。与某一与某一NFANFA等价的等价的DFADFA不唯一。不唯一。武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌 从从NFA的矩阵表示中可以看出，表项通的矩阵表示中可以看出，表项通常

42、是一状态的集合，而在常是一状态的集合，而在DFA的矩阵表示中，的矩阵表示中，表项是一个状态，表项是一个状态，NFA到相应的到相应的DFA的构造的构造的基本思路是：的基本思路是： DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状态。的一组状态。 DFA使用它的状态去记录在使用它的状态去记录在NFA读入一读入一个输入符号后可能达到的所有状态个输入符号后可能达到的所有状态.武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌一、一、NFA确定化算法（确定化算法（NFANFADFADFA的转换）的转换）: 假设假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个按如下办

43、法构造一个DFA M=(S, ,d,S0,St)，使得，使得L(M)=L(N)：1. M的状态集的状态集S由由K K的一些子集的一些子集组成。用组成。用S1 S2. Sj表示表示S的元的元素，其中素，其中S1, S2,. Sj是是K的状态。并且约定，状态的状态。并且约定，状态S1, S2,. Sj是是按某种规则排列的，即对于子集按某种规则排列的，即对于子集S1, S2= S2, S1,来说，来说，S的的状态就是状态就是S1 S2；2 M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是 ；3转换函数是这样定义的：转换函数是这样定义的： d(S1 S2,. Sj,a)= R1R2. Rt

44、 其中其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a)4 S0= -closure(K0)为为M的开始状态；的开始状态；5 St=Si Sk. Se， 其中其中 Si Sk. Se S且且Si , Sk,. Se Kt武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌二、二、定义对状态集合定义对状态集合I的几个有关运算：的几个有关运算：1. 状态集合状态集合I I的的-闭包闭包，表示为，表示为-closure(I)，定义为一状，定义为一状态集，是状态集态集，是状态集I中的任何状态中的任何状态S经任意条经任意条弧而能到达的状弧而能到达的状态的

45、集合。态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于-closure(I)。2. 状态集合状态集合I I的的a a弧转换弧转换，定义状态集合定义状态集合J表示为表示为 J=move(I,a) ，其中其中J是所有那些可从是所有那些可从I中的某一状态经过一条中的某一状态经过一条a弧而到达的状弧而到达的状态的全体。态的全体。Ia=-closure(J ) =-closure(move(I,a) )武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌状态集合状态集合I的有关运算的例子的有关运算的例子I= 1 , -closure(I) = 1,2 ；I= 5 , -closur

46、e(I) = 5,6,2 ；Move ( 1,2 , a ) = 5, 3, 4 -closure( 5, 3, 4 ) = 2, 3,4, 5,6, 7, 8 ；12534687aa a武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌三、三、构造构造NFA N的的状态状态K K的子集的子集的算法：的算法： 假定所构造的子集族为假定所构造的子集族为C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI为状态为状态K的子集。的子集。1. 开始，令开始，令 -closure(K0)为为C中唯一成员，并且它是未被标中唯一成员，并且它是未被标记的。记的。2.while

47、（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T； for 每个输入字母每个输入字母a do U:= -closure(move(T,a)； if U不在不在C中中 then 将将 U作为未标记的子集作为未标记的子集Ti加在加在C中中 武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌例子例子aaIaIbi，1，21,2,31,2,41,2,31,2,3,5,6,f1,2,41,2,41,2,31,2,4,5,6,f1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,5,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,6,f1,2,

48、3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,fI4f35621i aabbbb武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌等价的等价的DFAaCDBAEFSbaaaaabbbbbabF武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌4.3.44.3.4确定有穷自动机的化简确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余相等价的。一个有穷自动机可以通过消除多余状

49、态和合并等价状态而转换成一个最小的与之状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。即等价的有穷自动机。即用一个状态代替所有与用一个状态代替所有与其等价的状态。其等价的状态。 所谓有穷自动机的多余状态，是指这样的所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有也不能到达的那个状态；或者从这个状态没有通路到达终态。通路到达终态。DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA武汉理工大学计算机科学系陈天煌武汉理工大学计算机科学系陈天煌1.没有多余状态没有多余状态(死

50、状态死状态) )；2.2.没有两个状态是互相等价（不可区别）。没有两个状态是互相等价（不可区别）。两个状态两个状态s和和t可区别：可区别：不满足不满足兼容性兼容性同是终态或同是非终态；同是终态或同是非终态；传播性传播性从从s出发读入某个出发读入某个a a和从和从 t 出发出发读入某个读入某个a到达的状态等价。到达的状态等价。一、一、最小状态最小状态DFA的含义：的含义：两个状态两个状态s和和t等价：等价： 如果由如果由 s 出发能导出的所有串的集合与出发能导出的所有串的集合与 t 出发能出发能导出的所有串的集合相等，我们称状态导出的所有串的集合相等，我们称状态 s 与状态与状态 t 是是等价的