编译原理课件chap03(陈火旺).ppt

第三章 词法分析第三章第三章 词法分析词法分析 编译程序首先是在单词级别上来分析和翻译编译程序首先是在单词级别上来分析和翻译源程序的。词法分析的任务是：从左至右逐个字源程序的。词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，符地对源程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中把作为字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词间程序。因此，词法分析是编译的基础。执行词法分析的程序称为法分析的程序称为词法分析器词法分析器。3 3。1 1 对词法分析器的要求对词法分析器的要求 3.1.1 3.1.1 词法分析器功能和输出形式词法分析器功能和输出形式 输入源程序，输出单词符号。输入源程序，输出单词符号。程序语言的单词符号一般分为五种：关键字，标程序语言的单词符号一般分为五种：关键字，标识符，常数，运算符，界符识符，常数，运算符，界符第三章 词法分析 词法分析器输出的单词符号常常表示为二元词法分析器输出的单词符号常常表示为二元式：式：（单词种别，单词符号的属性值）（单词种别，单词符号的属性值）单词种别单词种别通常用整数编码。一个语言的单词符通常用整数编码。一个语言的单词符号如何分种，分成几种，怎样编码是一个技号如何分种，分成几种，怎样编码是一个技术问题。它取决于处理上的方便。标识符一术问题。它取决于处理上的方便。标识符一般统归为一种。常数则宜按类型（整、实、般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可视其全体为一种，布尔等）分种。关键字可视其全体为一种，也可以一字一种。采用一字一种的分法实际也可以一字一种。采用一字一种的分法实际处理起来较为方便。运算符可采用一符一种处理起来较为方便。运算符可采用一符一种的分法，但也可以把具有一定共性的运算符的分法，但也可以把具有一定共性的运算符视为一种。至于界符一般一符一种的分法。视为一种。至于界符一般一符一种的分法。第三章 词法分析 如果一个种别只含有一个单词符号，那么如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那自身了。若一个种别含有多个单词符号，那麽，对于它的每个单词符号，除了给出种别麽，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的编码之外，还应给出有关单词符号的属性信属性信息。息。单词符号的属性是指单词符号的特征或特单词符号的属性是指单词符号的特征或特性。性。属性值属性值则是反映特性或特征的值。例如，则是反映特性或特征的值。例如，对于某个对于某个标识符标识符，常将存放它有关信息的，常将存放它有关信息的符符号表号表项的项的指针指针作为其属性值；对于某个作为其属性值；对于某个常数常数，则将存放它的则将存放它的常数表项常数表项的的指针指针作为其属性值。作为其属性值。第三章 词法分析 作为例子考虑下述作为例子考虑下述C+C+代码段：代码段：while(i=j)i-;while(i=j)i-;经词法分析器处理后，它将转换为如下的单词经词法分析器处理后，它将转换为如下的单词符号序列：符号序列：id,id,指向指向i i的符号表项的指针的符号表项的指针 =,-=,-id,id,第三章 词法分析3.1.2 3.1.2 词法分析器作为独立子程序词法分析器作为独立子程序 我们把词法分析器安排成一个独立子我们把词法分析器安排成一个独立子程序，每当语法分析器需要一个单词程序，每当语法分析器需要一个单词符号时就调用这个子程序。每一次调符号时就调用这个子程序。每一次调用，词法分析器就从符号串中识别出用，词法分析器就从符号串中识别出一个单词符号，把它交给语法分析器。一个单词符号，把它交给语法分析器。这样，把词法分析器安排成一个子程这样，把词法分析器安排成一个子程序似乎比较自然。在后面的讨论中，序似乎比较自然。在后面的讨论中，我们假定词法分析器是按这种方式进我们假定词法分析器是按这种方式进行工作的。行工作的。第三章 词法分析3 3。2 2 词法分析器的设计词法分析器的设计 3 3。2 2。1 1 输入、预处理输入、预处理 词法分析器工作的第一步是输入源程序文本。输入词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称串一般放在一个缓冲区中，这个缓冲区称输入缓冲区输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但词法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的在许多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。识别工作将是比较方便的。预处理工作预处理工作包括对空白符、跳格符、回车符和换行包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。我们可以设符等编辑性字符的处理，及删除注解等。我们可以设想构造一个预处理子程序，他完成上面的工作。每当想构造一个预处理子程序，他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字词法分析器调用它时就处理出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接扫描缓冲区）。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。进行单词符号的识别工作。第三章 词法分析 分析器对扫描缓冲区进行扫描时一般分析器对扫描缓冲区进行扫描时一般使用两个指示器，一个指向当前正在识使用两个指示器，一个指向当前正在识别单词的开始位置。（指向新单词的首别单词的开始位置。（指向新单词的首字符），另一个用于向前搜索以寻找单字符），另一个用于向前搜索以寻找单词的终点。词的终点。不论扫描缓冲区设得多大都不能保证不论扫描缓冲区设得多大都不能保证单词符号不会被缓冲区的边界所打断。单词符号不会被缓冲区的边界所打断。因此，扫描缓冲区最好使用如下一分为因此，扫描缓冲区最好使用如下一分为二的区域：二的区域：第三章 词法分析 假定每半个区可容假定每半个区可容120120个字符，而这个字符，而这两个半区又是互补的。如果搜索指示器两个半区又是互补的。如果搜索指示器从单词起点出发搜索到半区的边缘但尚从单词起点出发搜索到半区的边缘但尚未达到单词的终点，那么就调用预处理未达到单词的终点，那么就调用预处理子程序，令其把后续的子程序，令其把后续的120120个字符装入另个字符装入另半区。我们认定在另半区一定可以达到半区。我们认定在另半区一定可以达到单词的终点。这意味着得标示符和常数单词的终点。这意味着得标示符和常数的的长度长度实际上必须加以限制，否则即使实际上必须加以限制，否则即使缓冲区再大也无济于事。缓冲区再大也无济于事。第三章 词法分析图图3 3。1 1词法分析器词法分析器 3。2。2 单词符号的识别：超前搜索单词符号的识别：超前搜索词法分析器的结构图如图词法分析器的结构图如图3。1所示。所示。第三章 词法分析当词法分析器调用预处理子程序处理当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后，出一串输入字符串放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新串。它又调用预处理程序装入新串。下面我们来介绍单词符号识别的一下面我们来介绍单词符号识别的一个简单方法个简单方法-超前搜索超前搜索第三章 词法分析关键字的识别关键字的识别像像FORTRAN这样的语言，关键字不加保这样的语言，关键字不加保护（只要不引起矛盾，用户可以用它们作为普护（只要不引起矛盾，用户可以用它们作为普通标识符），关键字和用户自定义的标识符或通标识符），关键字和用户自定义的标识符或标号之间没有特殊的界符作间隔。这使得关键标号之间没有特殊的界符作间隔。这使得关键字的识别甚为麻烦。请看下面例子：字的识别甚为麻烦。请看下面例子：1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4 IF(5)=55 这四个语句都是正确的这四个语句都是正确的FORTRAN语句。语句。语句语句1和和2分别是分别是DO和和IF语句，它们都是以某语句，它们都是以某基本字开头的。语句基本字开头的。语句3和和4是赋值语句，它们都是赋值语句，它们都是以用户自定义的标识符开头的。是以用户自定义的标识符开头的。第三章 词法分析为了从为了从1 1、2 2中识别出关键字中识别出关键字DODO和和IFIF，我们必须，我们必须要能够区别要能够区别1 1、3 3和区别和区别2 2、4 4。语句。语句1 1、3 3的区别在于的区别在于等号之后的第一个界符：一个为逗号，另个为句末等号之后的第一个界符：一个为逗号，另个为句末符。语句符。语句2 2、4 4的主要区别在于右括号后的第一个字的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。这就是说，为了符：一个为字母，另一个为等号。这就是说，为了识别识别 1 1、2 2句中的关键字，我们必须超前扫描许多个句中的关键字，我们必须超前扫描许多个字符，超前到能够肯定词性的地方为止。对于字符，超前到能够肯定词性的地方为止。对于1 1、3 3来说，尽管都以来说，尽管都以D D和和O O两个字母开头，但不两个字母开头，但不能一见能一见DODO就认定是就认定是DODO语句。我们们必须超前搜语句。我们们必须超前搜索，跳过所有的字母和数字，看看是否有等号。如索，跳过所有的字母和数字，看看是否有等号。如果有，再向前搜索。若下一个界符是逗号，则可以果有，再向前搜索。若下一个界符是逗号，则可以肯定肯定DODO应为关键字。否则，应为关键字。否则，DODO不构成关键字，它只不构成关键字，它只是用户标识符的头两个字母。所以为了区别是用户标识符的头两个字母。所以为了区别1 1和和3 3，我们必须超前扫描到等号后的第一个界符处。我们必须超前扫描到等号后的第一个界符处。第三章 词法分析 对于对于2 2和和4 4来说，必须超前扫描到与来说，必须超前扫描到与IFIF后的后的左括号相对应的那个右括号之后的第一个字符左括号相对应的那个右括号之后的第一个字符为止。若此字符是字母，则得逻辑为止。若此字符是字母，则得逻辑IFIF。若此字。若此字符为数字，则得算术符为数字，则得算术IFIF。否则，应认为是用户。否则，应认为是用户自定义标识符自定义标识符IF.IF.标识符的识别、常数的识别及算符和界符的识符的识别、常数的识别及算符和界符的识别相类似可以参考课本识别相类似可以参考课本P40,P41这里就不再这里就不再多述。多述。3。2。3状态转换图状态转换图使用状态转换图是设计使用状态转换图是设计词法分析器词法分析器的一种的一种好好途径途径。转换图是一张有限方向图。在转换图中，。转换图是一张有限方向图。在转换图中，结点代表状态，用园圈表示。状态之间用箭弧结点代表状态，用园圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符（即箭弧始结点）状态下可能出现的输入字符或字符类。或字符类。第三章 词法分析 例如图例如图3。2（a)表示：表示：在状态在状态1下，若输入下，若输入字符为字符为X，则读进，则读进X，并转换到状态，并转换到状态2。若输入字符为若输入字符为y，则，则读进读进Y，并转换到状，并转换到状态态3。一张转换图只。一张转换图只包含有限个状态包含有限个状态（即有限个结点），（即有限个结点），其中有一个被认为其中有一个被认为是初态，而且实际是初态，而且实际上至少要有一个终上至少要有一个终态（用双圈表示）。态（用双圈表示）。图图3 3。2 2状态转换图状态转换图第三章 词法分析 一个状态转换图可用于一个状态转换图可用于识别一定识别一定的字符串的字符串。例如，识别标识符的转换图。例如，识别标识符的转换图如图如图3 3。2 2（b)b)所示。其中所示。其中0 0为初态，为初态，2 2为为终态。这个转换图识别标识符的过程是：终态。这个转换图识别标识符的过程是：从初态从初态0 0开始，若在状态开始，若在状态0 0下输入字符是下输入字符是字母，则读进它，并转入状态字母，则读进它，并转入状态1 1。在状。在状态态1 1之下，若输入字符为字母或数字，之下，若输入字符为字母或数字，则读进它，并重新进入状态则读进它，并重新进入状态1 1。一直重。一直重复这个过程直到发现输入字符不再是字复这个过程直到发现输入字符不再是字母或数字时（这个字符已经被读进）就母或数字时（这个字符已经被读进）就近入状态近入状态2 2。状态。状态2 2是终态，它意味着到是终态，它意味着到此已经识别出一个标识符。终态上打个此已经识别出一个标识符。终态上打个*号，表示多读进了一个不属于标识符号，表示多读进了一个不属于标识符部分的字符，应把它退还给输入串，如部分的字符，应把它退还给输入串，如果在状态果在状态0 0时输入字符不为时输入字符不为“字母字母”，则意味着这个转换图不工作。则意味着这个转换图不工作。图图3 3。2 2状态状态 转换图转换图第三章 词法分析又如书中图又如书中图3。2（c)是识别整数的转是识别整数的转换图。其中换图。其中0为初态，为初态，2为终态。为终态。书中图书中图3。2（d)是一个识别是一个识别FORTRAN实型常数的转换图。其中实型常数的转换图。其中0态态为初态，为初态，7态为终态。态为终态。一个非常重要的事实是，一个非常重要的事实是，大多数大多数程序程序语言的单词符号都可以用语言的单词符号都可以用转换图转换图予以识予以识别。作为一个综合例子，课本别。作为一个综合例子，课本P43构造了构造了一个识别某个简单语言的所有单词符号一个识别某个简单语言的所有单词符号的转换图。希望同学们好好读一下。的转换图。希望同学们好好读一下。第三章 词法分析 3。2。4状态转换图的实现状态转换图的实现转换图容易用程序实现。最简单的办转换图容易用程序实现。最简单的办法是让每个状态结点对应一小段程序。法是让每个状态结点对应一小段程序。在编制程序的过程中课本引进了一组在编制程序的过程中课本引进了一组全局变量和过程。将它们作为实现转换全局变量和过程。将它们作为实现转换图的基本成分。希望同学能记住它们。图的基本成分。希望同学能记住它们。第三章 词法分析3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机 为了更好地使用状态转换图构造词法为了更好地使用状态转换图构造词法分析器，为了讨论词法分析器的自动生分析器，为了讨论词法分析器的自动生成，还需要将成，还需要将转换图转换图的概念的概念形式化形式化。为。为此我们引入：正规式，正规集，自动机此我们引入：正规式，正规集，自动机等概念。等概念。3.3.1正规式与正规集正规式与正规集对于字母表对于字母表，我们感兴趣的是它的，我们感兴趣的是它的一些特殊的字集，即所谓正规集。我们使用一些特殊的字集，即所谓正规集。我们使用正规式这个概念来表示正规集。正规式这个概念来表示正规集。第三章 词法分析下面是正规式和正规集的定义：下面是正规式和正规集的定义：（1）和和 都是都是上的正规式，他们所表示的正规集分上的正规式，他们所表示的正规集分别为别为和和；（2）任何）任何a,a是是上的一个正规式，它所表示的正上的一个正规式，它所表示的正规集为规集为a；（3）假定）假定U和和V都是都是上的正规式，他们所表示的正规上的正规式，他们所表示的正规集分别记为集分别记为L(U)和和L(V),并且，并且，(U|V),(UV)和（和（U)*也都也都是正规式，它们所表示的正规集分别为是正规式，它们所表示的正规集分别为L(U)L(V),L(U)L(V)(连接积）和（连接积）和（L(U)*（闭包）（闭包）仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上上的正规式。仅由这些正规式所表示的字集才是的正规式。仅由这些正规式所表示的字集才是上的正上的正规集。规集。第三章 词法分析通过这一节的学习，根据给出的简单正规式，应会写通过这一节的学习，根据给出的简单正规式，应会写出其正规集。出其正规集。3。1令令=a,b其正规式和正规集如下：其正规式和正规集如下：正规式正规式正规集正规集ba*上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字的字a(a|b)*上所有以上所有以a为首的字。为首的字。（a|b)*(aa|bb)(a|b)*正规集是正规集是所有两个相继的所有两个相继的a或相继或相继的的b的字。的字。第三章 词法分析3。2令令=A,B,0,1,则：则：正规式正规式正规集正规集(A|B)(A|B|0|1)*上的上的“标识符标识符”的全体的全体（0|1）（）（0|1）*上上“数数”的全体的全体若两个正规式所表示的正规集相同，则认若两个正规式所表示的正规集相同，则认为二者为二者等价。等价。两个等价的正规式两个等价的正规式U和和V记为记为U=V。例如：例如：b(ab)*=(ba)*b等价等价第三章 词法分析 a ab b-(a)a 一个正规式可以表示若干个符号串一个正规式可以表示若干个符号串,(b)b 其正规集就是这些符号串的集合其正规集就是这些符号串的集合a|b a,bab aba*,a,aa,aaa,aaaa,.b*,b,bb,bbb,bbbb,.-(a|b)*a和b组成的所有串a*|b*,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,.aba*以ab开头后接若干个(包括0个)a组成的串(a|b)*(aa|bb)(a|b)*上所有含有两个相继的a或两个相继的b组成的串第三章 词法分析例：令d，e，则上的正规式d*(.dd*|)(e(+|-|)dd*|)表示的是所有无符号数。其中d为09中的数字。比如：2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。设r，s，t为正规式，正规式服从代数规律有：1、r|ss|r 交换律2、r|(s|t)(r|s)|t 结合律3、(rs)t=r(st)结合律第三章 词法分析4.r(s|t)=rs|rt 分配律 (s|t)r=sr|tr 分配律5.r=r 零一律 r=r 零一律程序设计语言中的程序设计语言中的单词单词既能用既能用正规文法正规文法表示，又能用表示，又能用正规式正规式来表示来表示.正规文法正规文法:l|ll|l l|d|l l|d|l|d|d d|d d|d l l表示表示a-za-z中的任何英文字母，中的任何英文字母，d d表示表示0-90-9中的任何数字中的任何数字正规式正规式:标识符标识符:e1=字母字母(字母字母|数字数字)*无符号整数无符号整数:e2=dd*第三章 词法分析3.3.2确定有限自动机（确定有限自动机（DFA)有穷自动机：是一种自动识别装置，能有穷自动机：是一种自动识别装置，能正确正确识别识别正规集正规集；确定有限自动机确定有限自动机(DFA)是一个五元式是一个五元式M=(S,s0,F)其中其中:(1)S是一个有限集，它的每个元素称为一个状态。是一个有限集，它的每个元素称为一个状态。（2）是一个有穷字母集，它的每个元素称为一个输入是一个有穷字母集，它的每个元素称为一个输入字符。字符。（3）是一个从是一个从Sx 至至S的的单值部分映射单值部分映射。(s,a）=S。意味着：当现行状态为。意味着：当现行状态为s、输入字符为、输入字符为a时，时，将转换到下一个状态将转换到下一个状态S。我们称。我们称S为为s的后继状态。的后继状态。（4）S0 S，是唯一的初态。，是唯一的初态。（5）F S，是一个终态集（可空），是一个终态集（可空）第三章 词法分析显然，显然，DFA可以用一个矩阵表示，该矩可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵阵的行表示状态，列表示输入字符，矩阵元表示元表示(s,a）的值，该矩阵称为状态转换）的值，该矩阵称为状态转换矩阵。矩阵。DFA也可以表示成一张（确定的）状态也可以表示成一张（确定的）状态转换图。假定转换图。假定DFAM含有含有m个状态个状态n个输个输入字符，那末，这张图含有入字符，那末，这张图含有m个状态结点，个状态结点，每个结点顶多有每个结点顶多有n条箭弧射出和别的结点相条箭弧射出和别的结点相连接，每条箭弧用连接，每条箭弧用 上的一个不同字符作标上的一个不同字符作标记，整张图含有唯一的初态和若干个（可记，整张图含有唯一的初态和若干个（可以是以是0个）终态结点。个）终态结点。第三章 词法分析对于对于*中的任何一个字符中的任何一个字符，若，若存在一条从存在一条从初态结点初态结点到某一到某一终态结终态结点点的通路，且这条通路上所有箭弧的通路，且这条通路上所有箭弧的标记符连接成的字等于的标记符连接成的字等于，则称，则称 为为DFAM所所识别识别（读出读出或或接受接受）。）。若若M的初态结点同时又是终态结的初态结点同时又是终态结点，则为空字点，则为空字 可以为可以为M所识别。所识别。DFAM所能识别的字的全体记为所能识别的字的全体记为L(M).第三章 词法分析例例有有DFAM=(0,1,2,3,a,b,0,3)其中：其中：（0,a)=1;（0,b)=2（1,a)=3;（1,b)=2（2,a)=1;（2,b)=3（3,a)=3;（3,b)=3问：有几个状态？几个输入字符问：有几个状态？几个输入字符？并画出其转换图。？并画出其转换图。L(M)=?解：有解：有0，1，2，3共四个状态。共四个状态。输入字符为输入字符为a,b两个。其状态转两个。其状态转换图如右换图如右L(M)为在为在 上所有含相继两个上所有含相继两个a或或相继两个相继两个b的字。的字。（a|b)*(aa|bb)(a|b)*正规集是正规集是所有两个相继的所有两个相继的a或或相继相继b的字。的字。第三章 词法分析 3。3。3 非确定有限自动机非确定有限自动机(NFA)一个非确定有限自动机（一个非确定有限自动机（NFA)是一个五是一个五元式元式M=(S,S0,F)其中其中:(1)S同同3。3。2的的1（2）同）同3。3。2的的2（3）是一个从是一个从Sx*到到S的的子集的映照子集的映照，即即：Sx*2s(4)S0 S,是一个非空的初态是一个非空的初态集集；（5）F S，是一个终态集（可空），是一个终态集（可空）第三章 词法分析例：一个NFA，M(0,1,2,3,4,a,b,f,0,2,4)其中：f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4状态图表示如下：第三章 词法分析03412abbba,ba,ba,b说明：一个初态，二个终态。说明：一个初态，二个终态。DFA是是NFA的特例。的特例。定定理理：对对于于每每个个NFA M，存存在在一一个个DFA M，使得，使得L(M)=L(M)。对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如果，如果L(M)=L(M)，则称，则称M与与M是等价的。是等价的。第三章 词法分析显然，显然，NFA也可以表示成一张状态转也可以表示成一张状态转换图。假定换图。假定NFA含有含有m个状态个状态n个输入个输入字符，那末，这张图含有字符，那末，这张图含有m个状态结点，个状态结点，每个结点可以射出若干条箭弧和别的结每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用点相连接，每条箭弧用*上的一个字上的一个字（不一定要不同的字而且可以是空字（不一定要不同的字而且可以是空字）作标记（称为输入字），整张图至少含作标记（称为输入字），整张图至少含有一个的初态和若干个（可以是有一个的初态和若干个（可以是0个）终个）终态结点。某结点既可以是初态也可以是态结点。某结点既可以是初态也可以是终态结点。终态结点。第三章 词法分析对于对于*中的任何一个字符中的任何一个字符，若存在，若存在一条从一条从初态结点初态结点到某一到某一终态结点终态结点的通路，的通路，且这条通路上所有箭弧的标记符连接成且这条通路上所有箭弧的标记符连接成的字（忽略那些标记为的字（忽略那些标记为 的弧）等于的弧）等于，则称则称 为为NFAM所所识别识别（读出读出或或接受接受）。）。若若M的初态结点同时又是终态结点，的初态结点同时又是终态结点，或者存在一条某处态结点到某各终态结或者存在一条某处态结点到某各终态结点的点的 通路，则为空字通路，则为空字 可以为可以为M所识别。所识别。这里应注意这里应注意DFA与与NFA的异同点。的异同点。第三章 词法分析显然显然DFA是是NFA的特例。对于每个的特例。对于每个NFAM存在一存在一个个DFAM”，使，使L(M)=L(M”)。其证明如下（略）。其证明如下（略）在这个证明中特别强调的是课本在这个证明中特别强调的是课本P49页下边提页下边提到的对到的对M的状态转换图进一步施行图的状态转换图进一步施行图3。7所示所示的替换，其中的替换，其中k是新引入的状态。是新引入的状态。第三章 词法分析书中的这个图书中的这个图3。7同时也是从正规式画有限自动同时也是从正规式画有限自动机状态转换图的重要方法。对于正规式中的机状态转换图的重要方法。对于正规式中的连接连接可按可按1式画其转换图，对于式画其转换图，对于或或可用可用2式，对于式，对于闭包闭包可用可用3式。式。将将正规式正规式转换为转换为状态转换图状态转换图灵活使用这些规则非常重灵活使用这些规则非常重要的。要的。如：正规式：如：正规式：R=(a*b)*ba(a|b)*可以画为：可以画为：第三章 词法分析其中（其中（a*b)*和和(a|b)*分别可以看成一个闭包。形成分别可以看成一个闭包。形成A和和G结点。结点。例例：画出正规式：画出正规式：（a|b)*(aa|bb)(a|b)*对应的对应的NFA第三章 词法分析NFA转换为等价的转换为等价的DFA从从NFA的矩阵表示中可以看出，表项通常的矩阵表示中可以看出，表项通常是一是一状态的集合状态的集合，而在，而在DFA的矩阵表示中，的矩阵表示中，表项是一个表项是一个状态状态，NFA到相应的到相应的DFA的构的构造的基本思路是：造的基本思路是：DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状态的一组状态.DFA使用它的状态去记使用它的状态去记录在录在NFA读入一个输入符号后可能达到的读入一个输入符号后可能达到的所有状态所有状态.第三章 词法分析定义定义1：集合：集合I的的-闭包闭包：令令令令I I是一个状态集的子集，定义是一个状态集的子集，定义是一个状态集的子集，定义是一个状态集的子集，定义-closure-closure（I I）为：）为：）为：）为：1 1）若）若）若）若s sI I，则，则，则，则s s-closure-closure（I I）；）；）；）；2 2）若）若）若）若s sI I，则从，则从，则从，则从s s出发经过任意条出发经过任意条出发经过任意条出发经过任意条 弧能够到达的弧能够到达的弧能够到达的弧能够到达的任何状态都属于任何状态都属于任何状态都属于任何状态都属于-closure-closure（I I）。）。）。）。状态集状态集状态集状态集-closure-closure（I I）称为）称为）称为）称为I I的的的的-闭包闭包闭包闭包为了使得为了使得为了使得为了使得NFANFA确定化，我们首先给出两个定义：确定化，我们首先给出两个定义：确定化，我们首先给出两个定义：确定化，我们首先给出两个定义：56432a a a aa a 1例：如图所示的状态图：例：如图所示的状态图：例：如图所示的状态图：例：如图所示的状态图：令令令令I=1I=1，求，求，求，求-closure-closure（I I）=？根据定义：根据定义：根据定义：根据定义：-closure-closure（I I）=1=1，33第三章 词法分析JJ是从状态子集是从状态子集是从状态子集是从状态子集I I中的每个状态出发，经过标记为中的每个状态出发，经过标记为中的每个状态出发，经过标记为中的每个状态出发，经过标记为a a的弧的弧的弧的弧而达到的状态集合而达到的状态集合而达到的状态集合而达到的状态集合.I Ia a是状态子集是状态子集是状态子集是状态子集,其元素为其元素为其元素为其元素为J J中的状态，加上从中的状态，加上从中的状态，加上从中的状态，加上从J J中每一个中每一个中每一个中每一个状态出发通过状态出发通过状态出发通过状态出发通过弧到达的状态弧到达的状态弧到达的状态弧到达的状态定义定义2:令令I是是NFAM的状态集的一个子集的状态集的一个子集,a定义定义:Ia=-closure(J)其中其中J=(s,a)S SI I56432a a a aa a 1例：令例：令例：令例：令I=1I=1，求，求，求，求I Ia a=?I Ia a=-closure(J)=-closure(J)=-closure(1=-closure(1，a)a)）=-closure(2=-closure(2，44）=2=2，4 4，66第三章 词法分析状态集合I的有关运算的例子I=1,-closure(I)=?；I=5,-closure(I)=?；(1,2,a)=?-closure(5,3,4)=?；状态集合状态集合I I的的a a弧转换弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。12534687aaa第三章 词法分析状态集合I的有关运算的例子I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；(1,2,a)=5,3,4-closure(5,3,4)=2,3,4,5,6,7,8；12534687aaa第三章 词法分析 NFA确定化算法:假设NFA N=(K,f,K0,Kt)按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：1.构造DFA M的状态，选择NFA N的状态的一些子集构成：M的状态集S由K K的的一些子集一些子集组成。用S1 S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，S的状态就是S1 S2；第三章 词法分析2M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是；3构造构造DFAM的转换函数，根据新构造的状的转换函数，根据新构造的状态和字母表中的字符构造：态和字母表中的字符构造：转换函数是这样定义的：转换函数是这样定义的：d(S1S2,.Sj,a)=R1R2.Rt 其中其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)为为M的开始状态；的开始状态；5St=SiSk.Se，其中，其中SiSk.Se S且且Si,Sk,.Se Kt第三章 词法分析构造构造NFAN的的状态状态K K的子集的子集的算法：的算法：把多值转换函数所转换到的多值（多状态）的集把多值转换函数所转换到的多值（多状态）的集合作为一个子集，映射到合作为一个子集，映射到DFA的一个新的状态的一个新的状态假定所构造的子集族为假定所构造的子集族为C，即，即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1开始，令开始，令-closure(K0)为为C中唯一成员，并中唯一成员，并且它是未被标记的。且它是未被标记的。第三章 词法分析2while（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T；for每个输入字母每个输入字母adoU:=-closure(T,a)；ifU不在不在C中中then将将U作为未标记的子集加在作为未标记的子集加在C中中第三章 词法分析 NFA的确定化 例子4f35621iaaaabbbb第三章 词法分析4f35621iaaaabbbb第三章 词法分析 等价的DFAaCDBAEFSbaaaaabbbbbabF第三章 词法分析三、确定有穷自动机三、确定有穷自动机DFA的化简的化简（消除多余状态（消除多余状态+合并等价状态）：合并等价状态）：将多余状态消除而形成一个最小的等价的将多余状态消除而形成一个最小的等价的DFA 1、多余状态的概念：、多余状态的概念：从该自动机的从该自动机的开始状态开始状态出发，任何输入串也出发，任何输入串也不能到达的那个状态。不能到达的那个状态。下图中的哪些状态是多余的？下图中的哪些状态是多余的？第三章 词法分析01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S60化简后的结果：左右等价第三章 词法分析01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价第三章 词法分析2、等价的条件（状态、等价的条件（状态S和和T）一一致致性性条条件件状状态态S和和T必必须须同同时时为为可可接接受受状状态或不可接受状态（终态还是非终态）。态或不可接受状态（终态还是非终态）。蔓延性条件蔓延性条件对于所有输入符号，状态对于所有输入符号，状态S和状和状态态T必须转换到等价的状态里。必须转换到等价的状态里。3、合并等价状态的方法（分割法）、合并等价状态的方法（分割法）方法：将方法：将DFA的状态分割成一些互不相交的子集。不的状态分割成一些互不相交的子集。不同子集的状态是可区别的，同一子集中的任何两个状同子集的状态是可区别的，同一子集中的任何两个状态是等价的。态是等价的。合并等价状态：发现等价状态，并将这些等合并等价状态：发现等价状态，并将这些等价状态合并成一个状态。价状态合并成一个状态。第三章 词法分析1643257aaaaaaabbbbbbb例子：将图中的DFA M最小化。第三章 词法分析 将将M分成两个子集：分成两个子集：一个终态（可接受态）组成，一个非终态组成。一个终态（可接受态）组成，一个非终态组成。P0(1,2,3,4,5,6,7)第第1个子集个子集1,2,3,4中：中：1,2中的状态和中的状态和3,4中的任何状态在读入中的任何状态在读入a后到达了不等价的状态，两个状态都是不可区别后到达了不等价的状态，两个状态都是不可区别的。的。P1(1,2,3,4,5,6,7)P1中的中的3,4对应输入符号对应输入符号a或或b，将再分割：，将再分割：P2(1,2,3,4,5,6,7)P2中的中的5,6,7可有输入符号可有输入符号a或或b，分割为：，分割为：第三章 词法分析1643257aaaaaaabbbbbbbP3(1,2,3,4,5,6,7)1,2,6,7不能再分割，也即等价的。16435aaaaabbbbb第三章 词法分析 DFA的最小化算法的最小化算法 DFA M=DFA M=（K,f,kK,f,k0 0,k,kt t),),最小状态最小状态DFAM 1.1.构造状态的一初始划分构造状态的一初始划分：终态终态k kt t 和非终态和非终态K-K-k kt t两组两组(group)(group)2.2.对对施施用用过程过程PPPP 构造新划分构造新划分new new 3 3.如如new new =,=,则令则令 finalfinal=并继续步骤并继续步骤4 4，否则否则:=newnew重复重复2.2.4.4.为为finalfinal中的每一组选一代表，这些代中的每一组选一代表，这些代表构成表构成M的状态。若的状态。若k是是一代表且一代表且f(k,a)=t,f(k,a)=t,令令r r是是t t组的组的代表，则代表，则M中有一中有一转换转换f(k,a)=r(k,a)=r第三章 词法分析 M M 的开始状态是含有的开始状态是含有S S0 0的那组的代表的那组的代表 M M 的终态是含有的