第4章 词法分析

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

2、和实现词法分析程序设计和实现词法分析程序首先需要描述和刻画程序设计语言中的首先需要描述和刻画程序设计语言中的原子单位原子单位单词，其次需要识别单词单词，其次需要识别单词和执行某些相关的动作和执行某些相关的动作。描述程序设计语言的词法的机制是正则描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。表达式，识别机制是有穷状态自动机。回顾回顾 什麽是词法分析程序什麽是词法分析程序 实现词法分析（实现词法分析（lexical analysislexical analysis）的程序称为词法分）的程序称为词法分析程序（或扫描器）。析程序（或扫描器）。对构成源程序的对构成源程序的字符串字符

3、串从左到右进行从左到右进行扫描扫描，逐个逐个字符地读入源程序字符并按照构词逐个逐个字符地读入源程序字符并按照构词规则规则切分成切分成一个一个具有独立意义的一个一个具有独立意义的单词单词。并并确定其属性确定其属性（如保留字、标识符、运算符、（如保留字、标识符、运算符、界限符和常量等）。再把它们界限符和常量等）。再把它们转换成转换成长度统长度统一的标准形式一的标准形式属性字属性字（TOKENTOKEN）。）。词法分析程序的主要任务：词法分析程序的主要任务： 词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分

4、析使用。源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token. .词法分析程序和语法分析程序的关系词法分析程序和语法分析程序的关系 词法分析工作从语法分析工作独立出词法分析工作从语法分析工作独立出来的原因：来的原因：简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 4.1 4.1 对于词法分析器的要求对于词法分析器的要求4.1.1 4.1.1 词法分析器的功能和输出形式功能：输入源程序，输出单词符号。功能：输入源程序，输出单词符号。 单词符号是一个程序语言的基本语法符号。单词符号是一个程序语言的基本语法符号。单词的分类（五

5、类）：单词的分类（五类）：1. 关键字：关键字：由程序语言定义的具有固定意义的标识由程序语言定义的具有固定意义的标识 符。也称为保留字或基本字。符。也称为保留字或基本字。2. 标识符：标识符：用来表示程序中各种名字的字符串。用来表示程序中各种名字的字符串。3. 常常 数：数：常数的类型一般有整型、实型、布尔型、常数的类型一般有整型、实型、布尔型、文字型。文字型。4. 运算符：运算符：如如+、 、*、/ 等。等。5. 界限符：界限符：如逗号、分号、括号等。如逗号、分号、括号等。 一个程序语言的关键字、运算符、界限符都是一个程序语言的关键字、运算符、界限符都是固定的，即数量有限及意义明确；而对于标

6、识符和固定的，即数量有限及意义明确；而对于标识符和常数通常是不确定的。常数通常是不确定的。 词法分析器所输出的单词符号常常表示成如词法分析器所输出的单词符号常常表示成如下的二元式：下的二元式： （单词种别，单词符号的属性值）（单词种别，单词符号的属性值） 单词种别通常用整数编码。单词种别通常用整数编码。单词符号的属性是指单词符号的特性或单词符号的属性是指单词符号的特性或特征。特征。属性值则是反应特性或特征的值。属性值则是反应特性或特征的值。例如，对于某个标识符，常将存放它的例如，对于某个标识符，常将存放它的有关信息的符号表项的指针作为其属性值；有关信息的符号表项的指针作为其属性值；对于某个常数

7、，则将存放它的常数表项的指对于某个常数，则将存放它的常数表项的指针作为其属性值。针作为其属性值。 我们假定关键字、运算符和界限符都是一符我们假定关键字、运算符和界限符都是一符一种。对于它们，词法分析器只给出其种别编码，一种。对于它们，词法分析器只给出其种别编码，不给出它自身的值。标识符单列一种。常数按类不给出它自身的值。标识符单列一种。常数按类型分种。型分种。考虑下述考虑下述C代码段：代码段： while（ij）i； 经词法分析器处理后，它将被转换为如下的经词法分析器处理后，它将被转换为如下的单词符号序列：单词符号序列： while，关键字，关键字|指向指向while的关键字表项的指针的关键字

8、表项的指针 （，界限符（，界限符|指向（的界限符表项的指针指向（的界限符表项的指针 id，标识符，标识符|指向指向i的符号表项的指针的符号表项的指针 ，运算符，运算符|指向的运算符表项的指针指向的运算符表项的指针 id，标识符，标识符|指向指向j的符号表项的指针的符号表项的指针 ），界限符），界限符|指向）的界限符表项的指针指向）的界限符表项的指针 id，标识符，标识符|指向指向i的符号表项的指针的符号表项的指针 ，运算符，运算符|指向的运算符表项的指针指向的运算符表项的指针 ；，界限符；，界限符|指向；的界限符表项的指针指向；的界限符表项的指针4.1.24.1.2词法分析器的设计词法分析器的

9、设计 我们将按照词法分析的任务和作为一个独我们将按照词法分析的任务和作为一个独立子程序的要求来考虑词法分析器的设计。立子程序的要求来考虑词法分析器的设计。一、一、 输入、预处理输入、预处理 词法分析器工作的第一步是输入源程序文词法分析器工作的第一步是输入源程序文本。输入串一般是放在一个缓冲区中，这个缓本。输入串一般是放在一个缓冲区中，这个缓冲区称输入缓冲区。词法分析的工作（单词符冲区称输入缓冲区。词法分析的工作（单词符号的识别）可以直接在这个缓冲区中进行。但号的识别）可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词在许多情况下，把输入串预处理一下，对单词符号的识别工作将是

10、比较方便的。符号的识别工作将是比较方便的。 某些跳格符、回车符和换行符等编辑性字符，在别处的任何出现都没有意义，预处理时可以将其剔掉。 注解部分注解部分仅在于改善程序的易读性和易理解性。仅在于改善程序的易读性和易理解性。对于它们，预处理时可以将其剔掉。对于它们，预处理时可以将其剔掉。 空白符（一个或相继数个）用作单词符号之间的空白符（一个或相继数个）用作单词符号之间的间隔，即用作界符。在这种情况下，预处理时可间隔，即用作界符。在这种情况下，预处理时可把相继的若干个空白结合成一个。把相继的若干个空白结合成一个。 我们可以构造一个预处理子程序，它能够完我们可以构造一个预处理子程序，它能够完成上面所

11、述的任务。成上面所述的任务。预处理的主要工作：预处理的主要工作：二、二、 单词符号的识别：超前搜索单词符号的识别：超前搜索 词法分析器的结构如图词法分析器的结构如图4.14.1所示。所示。图图4.1 词法分析器词法分析器 当词法分析器当词法分析器调用预处理子程序调用预处理子程序处理出一串输入字处理出一串输入字符放进扫描缓冲区符放进扫描缓冲区之后，分析器就从之后，分析器就从此缓冲区中逐一识此缓冲区中逐一识别单词符号。当缓别单词符号。当缓冲区里的字符串被冲区里的字符串被处理完之后，它又处理完之后，它又调用预处理程序装调用预处理程序装入新串。入新串。三、三、 状态转换图状态转换图 状态转换图是一张有

12、限方向图。在状态转换状态转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符点（即箭弧始结点）状态下可能出现的输入字符或字符类。或字符类。123XY图图4.2（a）转换图示例）转换图示例一张转换图只包含有限个状态（即有限个一张转换图只包含有限个状态（即有限个结点），其中有一个被认为是结点），其中有一个被认为是初态初态，而且实际，而且实际上至少要有一个上至少要有一个终态终态（用双圈表示）。（用双圈表示）。

13、一个状态转换图可用于识别（或接受一个状态转换图可用于识别（或接受)一定的一定的字符串。字符串。 例如，识别标识符的转换图如图例如，识别标识符的转换图如图4.2（b）所示。）所示。图图4.24.2（b b）识别标识符的转换图）识别标识符的转换图图图4.24.2（c c）识别整数的转换图识别整数的转换图图图4.24.2（d d）识别识别FORTRAN实型常数的转换图实型常数的转换图4.2 正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，具加以描述，并且基

14、于这类描述工具，实现词法分析程序的自动构造。实现词法分析程序的自动构造。 正规表达式是典型的词法规则描述正规表达式是典型的词法规则描述工具。工具。正规式正规式定义定义（正规式和它所表示的正规集）：（正规式和它所表示的正规集）： 正规式也称正则表达式。正规式也称正则表达式。 正规表达式（正规表达式（regular expression）是说明单词）是说明单词的模式的模式(pattern)的一种重要的表示法（记号），是定的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。是正规式和它所表示

15、的正规集的递归定义。设字母表为设字母表为 ，辅助字母表，辅助字母表 = = ， ， ， ， ， ， ，1. 1. 和和 都是都是 上的正规式，它们所表示的正规集分上的正规式，它们所表示的正规集分别为别为 和和 ；1. 和 都是 上的正规式，它们所表示的正规集分别为 和 ； 2. 对任何a ，a是 上的一个正规式，它所表示的正规集为a；3. 假定假定e1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集分别为正规集分别为L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正规式也都是正规式,它们所表示的正规集分它们所表示的正规集分别为别

16、为L(e1), L(e1) L(e2), L(e1)L(e2)和和(L(e1) 。4. 仅由有限次使用上述三步骤而定义的表达式仅由有限次使用上述三步骤而定义的表达式才是才是 上的上的正规式正规式，仅由这些正规式所表示的，仅由这些正规式所表示的集合才是集合才是 上的上的正规集正规集。注意:其中“ ”、 “ ”、 “ ”均为正规式运算符：2. “ ”读为读为“连接连接”；3. “ ”读为读为“闭包闭包”（即，任意有限次的自重（即，任意有限次的自重复连接）。复连接）。 在不致混淆时，括号可省去，但规定算符在不致混淆时，括号可省去，但规定算符的优先顺序为的优先顺序为“ ”、“ ”、“ ” 。连接符。连

17、接符“ ”一般可省略不写。一般可省略不写。“ ”、“ ”和和“ ” 都是左结都是左结合的。合的。1. “ ”读为读为“或或” ；例子令 =a，b， 上的正规式和相应的正规集的例子有：正规式 正规集 a a a b a,b ab ab (a b)(a b) aa,ab,ba,bb a ,a,aa, 任意个任意个a的串的串正规式 正规集(a b) ,a,b,aa,ab 所有由a 和b组成的串(a b) (aa bb)(a b) 上所有含有两个相继上所有含有两个相继 的的a或两个相继的或两个相继的b组成组成 的串的串讨论下面两个例子例例4.2 有有 =d=d，. .，e e，+ +，-,-,则则 上

18、的正规式上的正规式 d d (.dd (.dd )(e(+ )(e(+ - -)dd)dd ) )表示的是无符号数表示的是无符号数的集合。其中的集合。其中d d为为0 09 9的数字。的数字。它表示的正规集它表示的正规集中的每个元素的模式是中的每个元素的模式是“无符号数无符号数” 。结论：结论：程序设计语言的单词都能用正规式来定义。程序设计语言的单词都能用正规式来定义。例例4.1 令令 =l，d，则，则 上的正规式上的正规式 r=l (l d) 定定 义义的正规集为的正规集为: l, l l, l d, l d d,其中其中l代表字母代表字母,d代表数字代表数字,正规式即是正规式即是 字母字母

19、(字母字母 数字数字) ,它表示的正规集中的每个元素的模式是它表示的正规集中的每个元素的模式是“以字母以字母打头的字母数字串打头的字母数字串”, ,这是早期多数高级程序设计语这是早期多数高级程序设计语言允许的的标识符的词法规则。言允许的的标识符的词法规则。正规式的等价性正规式的等价性若两个正规式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为正规式，正规式服

20、从的代数规律有：1. U 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 有穷自动机有穷自动机 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找

21、特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。关于有穷自动机我们将讨论如下问题: 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化1. K1. K是一个有穷状态集，它的每个元素称为一个状态；是一个有穷状态集，它的每个元素称为一个状态；4.3.1 4.3.1 确定的有穷自动机确定的有穷自动机DFADFA 一、一、DFADFA定义：定义： 一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，s0

22、，Z）, ,其中: :2. . 是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，所以也称所以也称为输入符号表；为输入符号表；3. . f是转换函数，是在是转换函数，是在KK上的单值部分映射。即，如果上的单值部分映射。即，如果 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，将转换为下一个状态时，将转换为下一个状态kj，我们把，我们把kj称作称作ki的一个的一个后继状态；后继状态；5. . Z K是一个终态集是一个终态集（可空）（可空），终态也称可接受状态或结，终态也称可接受状态或结束

23、状态。束状态。4. s0 KK是唯一的一个初态；是唯一的一个初态；二、一个二、一个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）的值。这个矩阵称为状态转换矩阵。的值。这个矩阵称为状态转换矩阵。状态状态ab SUVUQVV

24、UQ 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也可表示成一张（确定的）状态也可表示成一张（确定的）状态转换图。转换图。注意：初态结点的旁边标以注意：初态结点的旁边标以 ； 终态结点则用双圈表示。终态结点则用双圈表示。 假定假定DFA M含有含有 m个状态和个状态和 n个输入符号，个输入符号，那么，这个图含有那么，

25、这个图含有m个状态结点，每个结点顶个状态结点，每个结点顶多有多有n条箭弧射出和别的结点相连接，每条箭条箭弧射出和别的结点相连接，每条箭弧用弧用中的一个不同输入符号作标记，整张图中的一个不同输入符号作标记，整张图含有唯一的一个初态结点和若干个（可以是含有唯一的一个初态结点和若干个（可以是0个）个）终态结点。终态结点。SUQVaabbbaa,b状态状态ab SUVUQVVUQ QQQ对于对于* *中的任何字中的任何字t t，若存在一条从初态结点到某一终，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符号连接成的符态结点的通路，且这条通路上所有弧的标记符号连接成的符号串等于号串等

26、于t t，则称，则称t t可为可为DFA MDFA M所所识别识别（读出读出或或接受接受）。若）。若M M的的初态结点同时又是终态结点，则空字初态结点同时又是终态结点，则空字可为可为M M所识别（或接所识别（或接受）。受）。DFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L(M) L(M) 。 如有如有t=abb，显然，显然可为上例的可为上例的DFA M所所识别识别。 如果一个如果一个DFA M的输入符号表为的输入符号表为，则我们，则我们也称也称M是是的一个的一个DFA。换言之换言之： 若若t* ，f (S，t) =P，其中，其中S为为DFA M的初态，的初态，PZ，Z为终态集

27、。则称为终态集。则称t 可为可为DFA M所接受（所接受（识识别别）。）。结论：结论：上的一个字集上的一个字集V *是正规的，当且仅是正规的，当且仅当存在当存在上的上的DFA M，使得，使得VL（ M）。*上的符号串上的符号串t 在在DFA M上运行上运行:一个输入符号串一个输入符号串t t，（将它表示成，（将它表示成TtTt1 1的形式，其的形式，其中中TT，t t1 1 * *）在）在DFA M=DFA M=（K K，f f，S S，Z Z）上运行的定义为：）上运行的定义为：f f（Q Q， TtTt1 1）=f=f（f f（Q Q，T T），），t t1 1）, ,其中其中QK;QK;扩

28、充转换函数扩充转换函数f f为为 K K* KK上的上的映射，且：映射，且： f f（k ki， ）= k= 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属于终态。得证。属于终态。得证。三、三、DFADFA的确定性表现两个方面：的确定性表现两个方面：1. 1. 映射映射f：KK是一个单值函数。也就是说，是一个单值函数。也就是说，对任何状态对任何状态sK和输入符号和输入符号

29、a a，f（s，a）唯一唯一地确定了下一状态。从转换图的角度来看，假定字地确定了下一状态。从转换图的角度来看，假定字母表母表含有含有n n个输入符号，那么，任何一个状态结个输入符号，那么，任何一个状态结最多只有最多只有n n条弧射出，而且每条弧以一个不同的输条弧射出，而且每条弧以一个不同的输入字符标记。入字符标记。 2. 2. DFA有且仅有有且仅有唯一唯一的一个初态的一个初态s0K 。4.3.2 4.3.2 非确定的有穷自动机非确定的有穷自动机NFANFA1. K. K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2. . 是一个有穷字母表，它的每个元素称为

30、一个输入符是一个有穷字母表，它的每个元素称为一个输入符号，所以也称号，所以也称为输入符号表；为输入符号表；3. . f是是状态状态转换函数，是在转换函数，是在K*K的子集的映射，即，的子集的映射，即，f: f: K*2K ；表明在某状态下对于某；表明在某状态下对于某输入符号可能有多输入符号可能有多个后继状态；个后继状态；5. . Z K是一个终态集是一个终态集（可空）。（可空）。4. S K K是一个非空初态集；是一个非空初态集； 一、一、NFANFA定义定义：一个非确定的有穷自动机（一个非确定的有穷自动机（NFANFA）M M是一个五元组：是一个五元组：M=M=（K K，f f，S S ，Z

31、 Z）, ,其中其中: : 同前，一个含有同前，一个含有m m个状态和个状态和n n个输入符号的个输入符号的NFANFA可表示成如下的状态转换图：可表示成如下的状态转换图： 该图含有该图含有m m个状态结点，每个结点可射出若干个状态结点，每个结点可射出若干条箭弧与别的结点相连接，每条弧用条箭弧与别的结点相连接，每条弧用*中的一个字中的一个字（不一定要不同的字而且可以是空字。）作标记（不一定要不同的字而且可以是空字。）作标记（称为输入字），整张图至少含有一个初态结点以（称为输入字），整张图至少含有一个初态结点以及若干个（可以是及若干个（可以是0 0个）终态结点。个）终态结点。 某些结点既可以是初

32、态结点也可以是终态结点。某些结点既可以是初态结点也可以是终态结点。 显然，一个显然，一个NFA可用一个矩阵表示，该矩阵的行可用一个矩阵表示，该矩阵的行表示状态，列表示输入符号，即表示状态，列表示输入符号，即k行行a列的列的 矩阵元素矩阵元素表示表示f（k，a）的值。这个矩阵称为状态转换矩阵。）的值。这个矩阵称为状态转换矩阵。二、一个二、一个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状态图表示状态图表示矩阵表示简化为简化为01SPS,Z0P

33、Z0ZPP1+0 01 1SPS,Z0 0PZ0 0ZPP1 1+ 类似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所所接受（识别）接受（识别）* *上的符号

34、串t t被NFA MNFA M接受也可以这样理解: : 对于对于*中的任何一个串中的任何一个串t，若存在一条从，若存在一条从某一初态结到某一终态结的道路，且这条道某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串路上所有弧的标记字依序连接成的串(不理采不理采那些标记为那些标记为的弧的弧)等于等于t，则称，则称t可为可为NFA M所识别所识别(读出或接受读出或接受)。 若若M的某些结既是初态结又是终态结，的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的或者存在一条从某个初态结到某个终态结的道路道路,其上所有弧的标记均为其上所有弧的标记均为，那么空字可，那么

35、空字可为为M所接受。所接受。结论： NFA M所能接受的符所能接受的符号号串的全体记串的全体记为为 L(M)。 上一个符上一个符号号串集串集V 是正规的，是正规的，当且仅当存在一个当且仅当存在一个 上的不确定的有穷上的不确定的有穷自动机自动机M，使得，使得V=L(M)。例：NFA M=(S,Q,V,U,Z,0,1,f,S,Z)其中f(S,0)=V,Q f(S,1)=U,Q f(V,0)=Z f(Q,0)=V,Q f(Q,1)=U,Q f(U,1)=Z f(Z,0)=Z f(Z,1)=Z考察它接受符号串的过程。SU10,1010ZQV0,1100,1步骤当前状态输入串余留可能后继选择，SU10,

36、1010ZQV0,1100,1若选若选V V呢？呢？若选呢？若选呢？4.3.3 NFA4.3.3 NFA与与DFADFA的等价性：的等价性：显然，显然， DFA是是NFA的特例。的特例。 对于每个对于每个NFA M，存在一个，存在一个DFA M ，使，使得得L( M ) =L( M )。对每个对每个NFA M都存在着与都存在着与之等价的之等价的DFA M。即：对于任何两个有穷自动机即：对于任何两个有穷自动机M和和M，如果，如果L( M )=L( M )，则称，则称M与与M是等价的。是等价的。有有一种算法，将一种算法，将NFA转换成接受同样语言转换成接受同样语言的的DFA。这种算法称为这种算法称

37、为子集法子集法。与某一与某一NFANFA等价的等价的DFADFA不唯一。不唯一。 从NFA的矩阵表示中可以看出，表项通常是一状态的集合，而在DFA的矩阵表示中，表项是一个状态，NFA到相应的DFA的构造的基本思路是： 用用DFADFA的每一个状态对应的每一个状态对应NFANFA的一组状态。的一组状态。 使用使用DFA的一个状态去记录在的一个状态去记录在NFA读入读入一个输入符号后可能达到的所有状态一个输入符号后可能达到的所有状态.一、一、NFA确定化算法（NFANFADFADFA的转换）的转换）: 假设假设NFA N=(K, ,f,K0,Kt),按如下办法构造一个按如下办法构造一个DFA M=

38、(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 其中其中 R1,R2

39、,. , 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经任意条经任意条弧而能到达的状弧而能到达的状态的集合。态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于 -closure (I)。2. 状态集合状态集合

40、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, -closure(I)=5,6,2；move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；12534687aa a例1:例2: -closure(0)=(0)=0 0，1 1，2

41、 2，4 4，7 7图图4.4 NFA N 4.4 NFA N 即即0 0，1 1，2 2，4 4，7 7中的任一状态都是从状态中的任一状态都是从状态0 0经任意条经任意条弧可到达的状态。弧可到达的状态。令令0 0，1 1，2 2，4 4，7 7=A=A，则，则 move(A,a)=move(A,a)=3 3，8 8，因，因为在状态为在状态0 0，1 1，2 2，4 4和和7 7中，只有状态中，只有状态2 2和和7 7有有a a弧射出，分别弧射出，分别到达状态到达状态3 3和和8 8。而而 -closure ( (3 3，8 8)=)=1 1，2 2，3 3，4 4，6 6，7 7，8 8。

42、三、三、构造NFA N的状态状态K K的子集的子集的算法： 假定所构造的子集族为假定所构造的子集族为C，即，即C= (T1, T2,. TI),其中其中T1, T2,. TI为状态为状态K的子集。的子集。1. 开始，令开始，令 -closure(K0)为为C中唯一成员，并且它是未被标中唯一成员，并且它是未被标记的。记的。2.while （C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T； for 每个输入字母每个输入字母a do U:= -closure(move(T,a)； if U不在不在C中中 then 将将 U作为未标记的子集作为未标记的子集Ti加在加在C中中 例 3

43、.3 应用左面的算法对图4.4的NFA N构造子集。解：步骤如下： 首先计算 -closure(0)，令T0= -closure (0)=0，1，2，4，7，T0未被标记，它现在是子集族C的唯一成员。 标记标记T0T0；令；令T1=T1= -closure (move(T0,a)=1(move(T0,a)=1，2 2，3 3，4 4，6 6，7 7，88，将，将T1T1加入加入C C中，中，T1T1未被标记。未被标记。 标记标记T1T1；计算；计算 -closure (move(T1,a)(move(T1,a)，结果为，结果为11，2 2，3 3，4 4，6 6，7 7，88，即，即T1T1，

44、T1T1已在已在C C中。中。 标记标记T2T2，计算，计算 -closure (move(T2,a)(move(T2,a)，结果为，结果为11，2 2，3 3，4 4，6 6，7 7，88，即，即T1T1，T1T1已在已在C C中。中。 令令T2=T2= -closure (move (T0,b)=1(move (T0,b)=1，2 2，4 4，5 5，6 6，77，将将T2T2加入加入C C中，它未被标记。中，它未被标记。 计算计算 -closure (move(T1,b)(move(T1,b)，结果为，结果为11，2 2，4 4，5 5，6 6，7 7，99，令其为，令其为T3T3，T3

45、T3加至加至C C中，它未被标记。中，它未被标记。 计算计算 -closure (move(T2,b)(move(T2,b)，结果为，结果为11，2 2，4 4，5 5，6 6，77，即，即T2T2，T2T2已在已在C C中。中。T0=0,1,2,4,7 1,2,3,4,6,7,81,2,4,5,6,7T1=1,2,3,4,6,7,81,2,3,4,6,7,81,2,4,5,6,7,9T2=1,2,4,5,6,71,2,3,4,6,7,81,2,4,5,6,7T3=1,2,4,5,6,7,91,2,3,4,6,7,81,2,4,5,6,7,10T4= 1,2,4,5,6,7,10 1,2,3,

46、4,6,7,81,2,4,5,6,7abI+标记T3，计算 -closure (move(T3,a)，结果为1，2，3，4，6，7，8，即T1。标记标记T4T4，计算，计算 -closure (move(T4,a)(move(T4,a)，结果为，结果为11，2 2，3 3，4 4，6 6，7 7，88，即，即T1T1。共构造了五个子集：共构造了五个子集：T0=0T0=0，1 1，2 2，4 4，7 7 T1=1T1=1，2 2，3 3，4 4，6 6，7 7，88T2=1T2=1，2 2，4 4，5 5，6 6，77T3=1T3=1，2 2，4 4，5 5，6 6，7 7，99T4=1T4=1

47、，2 2，4 4，5 5，6 6，7 7，1010 至此，算法终止。至此，算法终止。 计算计算 -closure (move(T3,b)(move(T3,b)，结果为，结果为11，2 2，4 4，5 5，6 6，7 7，1010，令其为，令其为T4T4，加入，加入C C中，中，T4T4未被标记。未被标记。计算计算 -closure (move(T4,b)(move(T4,b)结果为结果为11，2 2，4 4，5 5，6 6，77，即即T2T2。 那么图3.43.4的NFA NNFA N构造的DFA MDFA M为 S=T0 S=T0，T1T1，T2T2，T3T3，T4T4 =a,b =a,b

48、D(T0 D(T0，a)=T1 D(T2a)=T1 D(T2，a)=T1a)=T1 D(T0D(T0，b)=T2 D(T2b)=T2 D(T2，b)=T2b)=T2 D(T1D(T1，a)=T1 D(T3a)=T1 D(T3，a)=T1a)=T1 D(T1D(T1，b)=T3 D(T3b)=T3 D(T3，b)=T4b)=T4 D(T4,a)=T1D(T4,a)=T1 D(T4D(T4，b)=T2b)=T2 S0=T0 S0=T0 St=T4 St=T4 不妨将不妨将T0T0，T1T1，T2T2，T3T3，T4T4重新命名，重新命名，以利于书写，或用以利于书写，或用A A，B B，C C，D

49、D，E E或用或用0 0，1 1，2 2，3 3，4 4分分别表示。若采用后者，该别表示。若采用后者，该DFA MDFA M的状态转换图如图的状态转换图如图4.54.5所所示。示。 图4.5 DFA M 例子i,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,3,6,f1,2,4,5,6,f1,2,3,6,f1,2,3,5,6,f1,2,4,6,faa4f35621i aabbbb图4

50、.6 NFA M 1abI+则等价的DFA见图4.7。aCDBAEFSbaaaaabbbbbabF图4.7 DFA M2令令 S=i,1,2 , A=1,2,3, B=1,2,4, C=1,2,3,5,6,f D=1,2,4,5,6,f , E=1,2,4,6,f, F=1,2,3,6,fs sz z1 10,10,11 11 1开始状态：开始状态：S S、P P终止状态：终止状态：Z Z0 0P P 0 1 S P SZ P Z + Z P P 0 1SP P SZ P Z + SZ P SPZ+ Z P P+ SPZ P SPZ解答： 有状态矩阵如图：图4.11 NFA M54.3.4 4

51、.3.4 确定有穷自动机的化简 说一个有穷自动机是化简了的，即是说，说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。即等价的有穷自动机。即用一个状态代替所有与用一个状态代替所有与其等价的状态。其等价的状态。 所谓有穷自动机的多余状态，是指这样的所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串状态：从自动机的开始状态出发，任何

52、输入串也不能到达的那个状态；或者从这个状态没有也不能到达的那个状态；或者从这个状态没有通路到达终态。通路到达终态。DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA1.没有多余状态没有多余状态(死状态死状态) )；2.2.没有两个状态是互相等价（不可区别）。没有两个状态是互相等价（不可区别）。两个状态两个状态s s和和t t等价的条件是等价的条件是：同时满足同时满足一致性一致性同是终态或同是非终态；同是终态或同是非终态；传播性传播性对于所以输入符号对于所以输入符号,状态状态s s和状态和状态t t必须转换到等价的状态必须转换到等价的状态。一、一、最小状态DFA的含义：既：既： 如果由

53、如果由 s 出发能导出的所有串的集合与出发能导出的所有串的集合与 t 出发能出发能导出的所有串的集合相等，我们称状态导出的所有串的集合相等，我们称状态 s 与状态与状态 t 是是等价的。等价的。例子 C和和D同是终态，读入同是终态，读入a到达到达C和和F，C和和F同同是终态，是终态， C和和F读入读入a都到达都到达C，读入，读入b都到达都到达E。 C和和D等价。等价。aCDBAEFSbaaaaabbbbbabF图4.7 DFA M2二、二、“分割法”（逐步分组试探法）DFA的最小化算法的核心的最小化算法的核心 把一个把一个DFA的状态分成一些不相交的子集，的状态分成一些不相交的子集，使得任何不

54、同的两子集的状态都是可区别的，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。而同一子集中的任何两个状态都是等价的。 三、三、 DFA的最小化算法设有设有DFA M =DFA M =（K,f,kK,f,k0 0 ,k,kz z）, ,最小状态最小状态DFA MDFA M ，1. 1. 因为不难证明，如果因为不难证明，如果s si i是非终结状态，而是非终结状态，而s sj j是终结状态，是终结状态，那么那么s si i和和s sj j一定互不等价（根据等价的定义可知，它们导出的一定互不等价（根据等价的定义可知，它们导出的符号串集不同）。所以开始可以把符号串集不同）

55、。所以开始可以把K K中的终态和非终态分开，分中的终态和非终态分开，分成两个子集，形成一个基本划分：成两个子集，形成一个基本划分：P P2 2II1 1，I I2 2 （I I1 1II2 2K K，I I1 1II2 2）2. 2. 若此两个子集还可以进行划分，则作进一步的划分，形成若此两个子集还可以进行划分，则作进一步的划分，形成Pm ,Pm ,假定到某个时候假定到某个时候PmPm已经含有已经含有m m个子集，记为：个子集，记为：PmPmII1 1，I I2 2，I Im m ，设设s s 和和s s 是是I Ii i中的任意两个状态，如果对某个中的任意两个状态，如果对某个a,a,存在存在

56、I Ij j ，使，使 f(sf(s ,a), f(s,a), f(s ,a)I,a)Ij j ，则称，则称s s 和和s s 关于关于a a是拟等价是拟等价的。的。 如果存在s s ，s s IIi i，使得对字母表中的某个符号a, sa, s 和s s 不为拟等价，则我们说I Ii i是可分的。换句话说，令换句话说，令I Ii i ss1 1，s s2 2, , ，s sn n ，如果对某个，如果对某个aa，使得使得IaIai i f(s f(s1 1,a),a)，f(sf(s2 2,a),a)，f(sf(sn n,a),a)不全落在现行不全落在现行PmPm的某一个子集的某一个子集I Ij

57、 j之中；即之中；即IaIai i这个集合中的元素分别属于这个集合中的元素分别属于I I1 1，I I2 2，I Im m中的几个不同集合，则中的几个不同集合，则I Ii i可分为几个集合（至少可可分为几个集合（至少可一分为二）。一分为二）。 3 3转转2,2,上述过程务必一再重复，直到上述过程务必一再重复，直到P P中的每个集合均中的每个集合均是不可再分时为止。是不可再分时为止。此时，此时，P P所含的集合数不再增加，即所含的集合数不再增加，即P P中的每个集合中的中的每个集合中的状态互相等价，而不同集合间的状态互不等价。状态互相等价，而不同集合间的状态互不等价。4.4.为为P P中的每一组

58、选一代表，这些代表构成中的每一组选一代表，这些代表构成M M 的状态。把原来的状态。把原来导入非代表状态的弧均导入其代表即可，即若导入非代表状态的弧均导入其代表即可，即若k k 是一代表且是一代表且f(kf(k ,a)=t,a)=t,令令r r是是t t组的代表，则组的代表，则M M 中有一转换中有一转换f f (k(k ,a)=r,a)=r，M M 的的开始状态是含有开始状态是含有S S0 0的那组的代表，的那组的代表，M M 的终态是含有的终态是含有F F的那组的的那组的代表。代表。例：有例：有DFA M见图见图4.8，求，求其极小化后的其极小化后的DFA M 。a5.5.去掉去掉M M

59、中的死状态。中的死状态。b23641babaaaababb5b图4.8 DFA M374.4 正规式与有穷自动机的等价性一、定理：1.1. 对于 上的NFA MNFA M，可以构造一个 上的正规式R R，使得L L（R R）= =L L（M M）。2. 2. 对于对于 上的任一个正规式上的任一个正规式R R ，可以构造一个，可以构造一个 上的上的NFA M NFA M ，使得，使得L L（M M）= =L L（R R）。）。二、把 上的NFA M转换为一个 上的正规式R转换方法：我们把状态转换图的概念拓广，令每条弧可用一个正规式标记。1. 在M的状态图上加进两个结点x、y。从x结点用弧 连接到

60、M的所有初态结点，从M的所有终态结点弧 连接到y结点。形成一个与M等价的M ， M 只有一个初态和一个终态。二、把 上的NFA M转换为一个 上的正规式R2. 逐步消去逐步消去M 中的所有结点，直至只剩下中的所有结点，直至只剩下x结点和结点和y结结点。在消结过程中，点。在消结过程中，逐步用逐步用正规式来标记弧，其消结正规式来标记弧，其消结规则如下：规则如下：对于对于123R1 R2 代之为：代之为：12R1 R2 对于对于12R1 R2 代之为：代之为：12R1 | R2 对于对于代之为：代之为：12R1R2* R3 123R1 R2 R3 最后最后x结点和结点和y结点之间的弧上的标记就是所求