1v内容：内容： 状态转换图、正规式和有限自动机、词法分析器的自动生成状态转换图、正规式和有限自动机、词法分析器的自动生成v掌握掌握: 正规式、状态转换图，正规式、状态转换图，DFN的概念、的概念、NFA的概念，将的概念，将NFA转转 换为换为DFA、DFA的化简、正规式与有限自动机间的转换。的化简、正规式与有限自动机间的转换。v理解理解: 正规文法与有穷自动机间的转换正规文法与有穷自动机间的转换 词法分析器的自动产生工具词法分析器的自动产生工具LEX 第第3章章 词法分析词法分析教学要求教学要求2本章在编译程序中的地位本章在编译程序中的地位表表格格管管理理词法分析器词法分析器语法分析器语法分析器语义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器源程序源程序单词符号单词符号语法单位语法单位中间代码中间代码中间代码中间代码目标代码目标代码出出错错处处理理3v执行词法分析的程序称为执行词法分析的程序称为又称为又称为词法分析器词法分析器或或扫描器扫描器. . v词法分析的词法分析的任务任务：从左至右逐个地扫描源程：从左至右逐个地扫描源程序的字符串序的字符串, 按照按照词法规则词法规则识别出一个个正识别出一个个正确的单词，并转换为相应的确的单词，并转换为相应的二元式二元式形式，交形式，交给语法分析使用。给语法分析使用。v把作为字符串的源程序改造成单词符号串的把作为字符串的源程序改造成单词符号串的词法分析是编译的基础。词法分析是编译的基础。3.1 设计设计词法分析器词法分析器时应考虑的几个问题时应考虑的几个问题43.1.1 词法分析阶段的必要性词法分析阶段的必要性 v词法分析的工作纳入整个语法分析中一揽子地进行，原则上是词法分析的工作纳入整个语法分析中一揽子地进行，原则上是可行的。可行的。 v在设计一个编译程序时，通常是把对源程序的结构分析分为词在设计一个编译程序时，通常是把对源程序的结构分析分为词法分析和语法分析两个相对独立的阶段来完成。法分析和语法分析两个相对独立的阶段来完成。 第一，描述单词的结构比描述源程序的其它语法结构要简单第一，描述单词的结构比描述源程序的其它语法结构要简单得多，仅使用得多，仅使用3 3型文法也就基本够用了。型文法也就基本够用了。 第二，由于把词法分析和语法分析分开，可使编译程序各部第二，由于把词法分析和语法分析分开，可使编译程序各部分的功能更为单一，整个编译程序的结构也更加清晰，从而分的功能更为单一，整个编译程序的结构也更加清晰，从而有利于编译程序的编写和调整。有利于编译程序的编写和调整。v上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译上述词法分析和语法分析两个阶段的划分，仅仅是对整个编译程序的逻辑功能而言，而不一定指的是编译程序的执行流程。程序的逻辑功能而言，而不一定指的是编译程序的执行流程。53.1.2 词法分析器的输出形式词法分析器的输出形式v词法分析器输出的单词常常表示为词法分析器输出的单词常常表示为二元式二元式形式形式 (单词种别单词种别,单词符号的属性值单词符号的属性值) 单词种别提供给语法分析程序使用；单词符号的属性值提供给语义分析程序使用。具体的分类设计方法以方便语法分析程序使用为原则。63.1.2 词法分析器的输出形式词法分析器的输出形式v程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：关键字关键字( (保留字或基本字保留字或基本字) )：如：如 if,then,else,while,doif,then,else,while,do等等 标识符标识符：用来表示各种名字，如：用来表示各种名字，如 x1x1常量常量：如：如 256256，3.143.14，true, true, abcabc 运算符运算符：如：如 、* *、/ / 等等等等分界符分界符：如：如 逗号，分号，冒号等逗号，分号，冒号等73.1.2 词法分析器的输出形式词法分析器的输出形式v单词种别单词种别: : 一个语言的单词符号如何分类、分为几类、如何一个语言的单词符号如何分类、分为几类、如何编码主要取决于处理上的方便。通常，每种单词对编码主要取决于处理上的方便。通常，每种单词对应一个整数码。应一个整数码。 注意：保留字、运算符和界符的个数确定，注意：保留字、运算符和界符的个数确定， 标识符和常数的个数不确定。标识符和常数的个数不确定。 保留字：保留字：可全体视为一种，也可一字一种；可全体视为一种，也可一字一种； 标识符：标识符：统归为一种；统归为一种； 常数：常数：统归为一种统归为一种,或按整、实、布尔等再分；或按整、实、布尔等再分； 运算符和界符：运算符和界符：一符一种，或统归为一种。一符一种，或统归为一种。83.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值 单词符号的属性是指单词符号的特征值 。如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了，因而不需要属性值。若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的属性值。93.1.2 词法分析器的输出形式词法分析器的输出形式v单词符号的属性值单词符号的属性值标识符和常数标识符和常数 标识符的标识符的内部码内部码 (如如ASCII码等等码等等)和和常数本身的值常数本身的值 (二进制，逻辑值等二进制，逻辑值等)来表示。来表示。 标识符的标识符的符号表入口地址符号表入口地址作为其单词符号的属性值作为其单词符号的属性值,常量在其常量在其常量表中的入口地址常量表中的入口地址作为其单词符号的属性作为其单词符号的属性值。值。每个基本字占一个单词种别，单词符号的属性值缺省每个基本字占一个单词种别，单词符号的属性值缺省。对于界符，运算符通常一个符号一个种别，单词符号的对于界符，运算符通常一个符号一个种别，单词符号的属性值缺省属性值缺省例例: : 参见参见P42.P42.表表3.1 3.1 单词符号及种别编码单词符号及种别编码103.1.3 词法分析器作为独立子程序词法分析器作为独立子程序v词法分析可采用如下两种处理结构词法分析可采用如下两种处理结构：把词法分析程序作为主程序。将词法分析作为把词法分析程序作为主程序。将词法分析作为独立的一遍来完成独立的一遍来完成。把词法分析程序作为语法分析程序调用的子程把词法分析程序作为语法分析程序调用的子程序。序。v每当语法分析器需要一个单词符号时就调用这个子程每当语法分析器需要一个单词符号时就调用这个子程序。序。v每一次调用，词法分析器从源程序字符串中识别出一每一次调用，词法分析器从源程序字符串中识别出一个单词符号，并把它的内部表示二元组交给语法分析个单词符号，并把它的内部表示二元组交给语法分析器处理。器处理。113.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。词词法法分分析析器器的的工工作作可可以以直直接接在在输输入入缓缓冲冲区区中中进进行行。但但在在许许多多情情况况下下，可可以以先先预预处处理理输输入入串串，识识别工作将更方便。（参见别工作将更方便。（参见P40 图图3.1）123.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索v预处理的原因预处理的原因 源程序中包含源程序中包含回车回车, ,换行换行, ,多余空白符多余空白符, ,注释行等编辑注释行等编辑字字符符, , 它们对程序逻辑功能无任何影响，它们对程序逻辑功能无任何影响， 在词法分析之前在词法分析之前, ,首首先要剔除掉这些符号先要剔除掉这些符号, ,使得词法分析更为简单。使得词法分析更为简单。 一行语句结束应配上一个特殊字符说明。一行语句结束应配上一个特殊字符说明。 有些语言要识别标号区，区分标号语句，找出续行符连有些语言要识别标号区，区分标号语句，找出续行符连接成完整语句等。接成完整语句等。 输出源程序清单以便复核。输出源程序清单以便复核。v 预处理子程序任务预处理子程序任务 从输入缓冲区中读取源程序，预处理后送入扫描缓冲从输入缓冲区中读取源程序，预处理后送入扫描缓冲区。此时，扫描缓冲区的字符都是有效字符。区。此时，扫描缓冲区的字符都是有效字符。 词法分析程序这时可以再对扫描缓冲区进行扫描。词法分析程序这时可以再对扫描缓冲区进行扫描。133.1.4 源程序的输入源程序的输入、预处理预处理及及超前搜索超前搜索v超前搜索超前搜索 对于有些语言，关键字不保护，关键字与用户自定义标对于有些语言，关键字不保护，关键字与用户自定义标识符间没有界符，要在上下文环境中识别单词，这时需要识符间没有界符，要在上下文环境中识别单词，这时需要超前搜索方法来识别关键字。超前搜索方法来识别关键字。 例如：例如：FORTRANFORTRAN语言：语言： 1. 1.DO10K=1DO10K=1，50 50 2.2.DO10K=1.50DO10K=1.50v扫描缓冲区的结构扫描缓冲区的结构 (自学自学) 16词法分析程序设计词法分析程序设计v 设计方法：设计方法： 写出该语言的词法规则；写出该语言的词法规则； 把词法规则转换为相应的把词法规则转换为相应的状态转换图状态转换图； 把各转换图的初态连在一起，构成识别该把各转换图的初态连在一起，构成识别该 语言的语言的自动机自动机； (4)(4)设计扫描器设计扫描器 173.2 正规文法和有限自动机正规文法和有限自动机v 这节介绍这节介绍词法规则词法规则的形式表示的形式表示(正规式正规式),从从正规式正规式向有限自动机的转化向有限自动机的转化.正规式正规式有限自动机有限自动机词法分析器词法分析器控制程序控制程序自动生成器自动生成器转化转化合成合成183.2.1 正规文法、正规集与正规式正规文法、正规集与正规式v正规文法：正规文法：是是chomsky3型文法。型文法。例如：标识符这种单词可以用下面的规则描述例如：标识符这种单词可以用下面的规则描述 | （ | ） 表示任意字母，表示任意字母， 表示任意数字表示任意数字注：正规文法描述是注：正规文法描述是正规集正规集的文法，可用于描述程序设计的文法，可用于描述程序设计语言的语法部分语言的语法部分。19v 对于一个正规文法的语言提炼出一个简洁的公式，用这个式对于一个正规文法的语言提炼出一个简洁的公式，用这个式子来对它进行子来对它进行形式化的表示形式化的表示，这个式子叫，这个式子叫正规式正规式。v正规式：正规式：也称也称正则表达式正则表达式,是说明是说明单词的模式单词的模式的一种重要的的一种重要的表示法（记号）；是定义正规集的数学工具；用来描述单词表示法（记号）；是定义正规集的数学工具；用来描述单词符号。符号。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集注：正规集是集合，可有穷也可无穷。注：正规集是集合，可有穷也可无穷。 可通过正规式来形式化表示。可通过正规式来形式化表示。v 正规集：正规集：由正规文法产生的语言所构成的集合。由正规文法产生的语言所构成的集合。203.2.1 正规文法、正规式与正规集正规文法、正规式与正规集下面以标识符为例说明下面以标识符为例说明正规式正规式与与正规集正规集: : 标识符标识符标识符标识符是以字母开头的字母数字串。是以字母开头的字母数字串。若用若用L L表示字母表示字母, , 用用D D表示数字表示数字, , 则标识符可表示为则标识符可表示为: L(L|D): L(L|D)* * 其中并置表示两者的其中并置表示两者的连接连接, |, |表示两者选一表示两者选一, *, *表示零次或多次引用。表示零次或多次引用。L(L|D)L(L|D)* * 为为标识符的正规式标识符的正规式，该正规式表示的集合为该正规式表示的集合为标识符的正规集标识符的正规集。21v下面是正规式和它所定义的正规集的递归定义。下面是正规式和它所定义的正规集的递归定义。 1) , 是是 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 , ; 2) 若若 a,则则 a 为正规式为正规式, 所表示的正规集为所表示的正规集为 a; 3) 设设U,V 为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U),L(V); 则则 U|V为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U) L(V); UV为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 L(U) L(V); V* 为为 上的正规式上的正规式, 所表示的正规集为所表示的正规集为 (L(V)* ; 4) 仅当有限次使用上述三步骤而定义的表达式仅当有限次使用上述三步骤而定义的表达式,才是才是 上的正上的正规式规式 ,而这些而这些正规式所表示的字集才是正规式所表示的字集才是上的正规集。上的正规集。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集或运算或运算连接积连接积22说明：说明：11上的一个上的一个字字指的是由指的是由中中字符构成的一个有穷序列字符构成的一个有穷序列; ; 不包含任何字符的序列称为空字（不包含任何字符的序列称为空字（）。）。 * *表示表示上所有字的全体上所有字的全体, , 包括空字（包括空字（）。）。 例如例如, , 若若=a, b=a, b 则则* *=, a, b, aa, ab, ba, bb, aaa, =, a, b, aa, ab, ba, bb, aaa, 2 2 表示不含任何元素的空集表示不含任何元素的空集 。 注意注意、 和和的区别：的区别： 表示不包含任何字符的序列表示不包含任何字符的序列, ,它是正规集中的一个元素；它是正规集中的一个元素； 表示不含任何字的集合表示不含任何字的集合, , 它是一个空的正规集；它是一个空的正规集； 表示由空字组成的集合。表示由空字组成的集合。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集233 3 使用括号可改变运算符的运算次序。使用括号可改变运算符的运算次序。 若若规规定定* *优优先先于于, , 优优先先于于|, |, 则则在在不不混混淆淆情情况况下下, ,可可省省 去括号。去括号。4 R4 R自身的自身的n n次连接记为次连接记为 R Rn n=RR=RRR R5 R5 R0 0=,=, R R* *=R=R0 0RR1 1RR2 2RR3 3, R, R* *为为R R的闭包的闭包 R R+ +=RR=RR* *, , 称称R R+ +是是R R的正闭包。的正闭包。 闭闭包包R R* *中中的的每每个个字字都都是是由由R R中中的的字字经经过过有有限限次次连连接接而而成成的。的。6 6 对于正规式对于正规式R R和和S, S, 若它们表示的正规集若它们表示的正规集L(R)=L(S), L(R)=L(S), 则称则称R R和和S S等价等价, , 记为记为R=SR=S。3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集24v 正规式具有下列性质：正规式具有下列性质： (1) (1) 交换律：交换律：R|S = S|R R|S = S|R (2) (2) 结合律：结合律：R|(S|T) = (R|S)|T, R(ST) = (RS)T R|(S|T) = (R|S)|T, R(ST) = (RS)T (3) (3) 分配律：分配律：R(S|T) = RS|RT, (R|S)T = RT|STR(S|T) = RS|RT, (R|S)T = RT|ST (4) (4) 同一律：同一律：R = R = RR = R = R3.2.1 正规文法、正规式与正规集正规文法、正规式与正规集例例3.1 =a,b, R=a(a3.1 =a,b, R=a(a| |b)b)* *是是上正规式上正规式, ,试求试求R R表示的正规集。表示的正规集。解解: L(R)=L(a(a: L(R)=L(a(a| |b)b)* *)=L(a)L(a)=L(a)L(a| |b)b)* *) ) =L(a)(L(a =L(a)(L(a| |b)b)* *=L(a)(L(a)L(b)=L(a)(L(a)L(b)* * = a(ab) = a(ab)* *= aa, b= aa, b* * =a, a, b, aa, ab, ba, bb, aaa, =a, a, b, aa, ab, ba, bb, aaa, =a,aa,ab,aaa,aab,aba,abb,aaaa, =a,aa,ab,aaa,aab,aba,abb,aaaa, 上所有以上所有以a为首的字为首的字25 例例3.2 3.2 判断下述正规式之间是否等价：判断下述正规式之间是否等价： (1)b(ab) (1)b(ab)* *与与(ba)(ba)* *b (2)(ab)b (2)(ab)* *与与a a* *b b* *解解: (1) : (1) b(ab)b(ab)* *对应的正规集是对应的正规集是b b后面出现任意多个后面出现任意多个abab对对 L(b(ab)L(b(ab)* *)=b,bab,babab, )=b,bab,babab, (ba) (ba)* *b b对应的正规集是对应的正规集是b b前面可出现任意个前面可出现任意个baba对对L(L(ba)(ba)* *b)=b)=b,bab,babab, b,bab,babab, , 因此两者等价因此两者等价。 正规式正规式b(ab)b(ab)* *及及(ba)(ba)* *b b都描述以都描述以b b开头且其后跟以零个或任意开头且其后跟以零个或任意多个多个abab所组成的字符串等。故我们说两个正规式等价，所组成的字符串等。故我们说两个正规式等价，(2)(ab)(2)(ab)* *对应的正规集以任意个对应的正规集以任意个abab对出现，即对出现，即 abababababab, , 而而a a* *b b* *对应的正规集则是任意个对应的正规集则是任意个a a后接任意个后接任意个b, b, 即即a aababb, b, 因此两者不等价。因此两者不等价。26例例3.3: 3.3: 设设 = = a,ba,b , , 则则正规式和正规集正规式和正规集: : a a b b (a(a b)(ab)(a b) b) a a* *(a(a b)b)* *aa abab* * a,ba,b aa,ab,ba,bbaa,ab,ba,bb ,a,aa,aaa,aaaa,a,aa,aaa,aaaa, = a= an n|n0|n0 ,a,b,aa,ab,ba,bb,aaa,aab,abb,a,b,aa,ab,ba,bb,aaa,aab,abb,bab,bba,bbb . bab,bba,bbb . = a, b = a, b* *a,ab,abb,abbb,abbbb,.a,ab,abb,abbb,abbbb,. = ab = abn n |n0|n027v通过这一节的学习，要求能根据给出的简单正规式，通过这一节的学习，要求能根据给出的简单正规式，会写出其表示的正规集。会写出其表示的正规集。例例3.4 令令=a,b,其正规式和正规集如下：其正规式和正规集如下： 正规式正规式 正规集正规集 1. ba* 2. a(a|b)* 3. (a|b)*(aa|bb)(a|b)*上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字。的字。上所有以上所有以a为首的字。为首的字。上所有含有两个相继的上所有含有两个相继的a或或两个相继的两个相继的b 的字。的字。28例例3.5: 令令=A,B,0,1 , 则：则： 正规式正规式 正规集正规集1.(A|B)(A|B|0|1)*2.(0|1)(0|1)* 3.问问: 正规式正规式 , , 0 , 110 , 0|1 , 1* 表示的正规表示的正规集是集是?答答: 正正规规集集分分别别是是 , , 0, 110, 0,1, ,1,11,111,=1* =1n | n0。上的上的“标识符标识符”的全体的全体 =A,B.A,B,0,1*上上“数数”的全体的全体 =0,1.0,1*293.2.1 正规文法、正规式与正规集正规文法、正规式与正规集v 三个概念之间的关系：三个概念之间的关系： 一个正规语言可以用正规文法来定义，也可以用正规一个正规语言可以用正规文法来定义，也可以用正规式来定义，有些正规语言很容易用文法定义，有些则用正式来定义，有些正规语言很容易用文法定义，有些则用正规式定义更容易。规式定义更容易。 一个正规语言是一个集合（正规集），那么这个集合一个正规语言是一个集合（正规集），那么这个集合可以用正规文法来定义，也可以用正规式来定义。可以用正规文法来定义，也可以用正规式来定义。303.2.2 有限自动机有限自动机v有限自动机（有限自动机（Finite Automata FA）是一种识别装置，它能准确地识别正规集。它是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具为词法分析程序的构造提供了方法和工具。 是一种具有离散输入输出系统的数学模型。它是一种具有离散输入输出系统的数学模型。它具有有限数目的内部状态，系统可以根据当前具有有限数目的内部状态，系统可以根据当前所处的状态和面临的输入字符决定系统的后继所处的状态和面临的输入字符决定系统的后继行为。其当前状态概括了过去处理的信息。行为。其当前状态概括了过去处理的信息。 313.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带注：状态分为初始状态、中间状态和终止状态。注：状态分为初始状态、中间状态和终止状态。 终止状态可以有若干个，而初始状态一般只有一个。终止状态可以有若干个，而初始状态一般只有一个。状态变换状态变换 z e d c b a有限状态控制器有限状态控制器读头读头323.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带状态状态: 初态初态 z e d c b a有限状态控制器有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态: 中间中间333.2.2 有限自动机有限自动机v有限自动机模型：有限自动机模型：输入带输入带状态状态: 终态终态 z e d c b a有限状态控制器有限状态控制器读头读头 z e d c b a有限状态控制器有限状态控制器读头读头状态状态: 非终非终态态注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，且此时状态为终态，则说明此输入串正确。注：读头全部读完，而此时状态不是终态，则说明此输入串错误。注：读头全部读完，而此时状态不是终态，则说明此输入串错误。状态的变换和符号的读入用一个图形结构来表示。（状态的变换和符号的读入用一个图形结构来表示。（状态转换图状态转换图）343.2.3 状态转换图状态转换图 P41 v状态转换图：状态转换图：状态转换图是一张有限方向图，只包含有限状态转换图是一张有限方向图，只包含有限个状态，即有限个结点。个状态，即有限个结点。P41P41 1. 1. 结点代表结点代表状态状态，用，用圆圈圆圈表示表示 2. 2. 终止状态终止状态用用双圈双圈表示表示 3. 3. 初始状态初始状态前标记符号前标记符号“ ”来表示（可省）来表示（可省） 4. 4. 状态之间用状态之间用箭弧箭弧连结，箭弧上的连结，箭弧上的标记标记代表在射出结点（即代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标箭弧始结点）状态下可能出现的输入字符或字符类，箭弧标记表示记表示状态转换的条件状态转换的条件。 5. 5. 状态图有状态图有一个初态，多个终态一个初态，多个终态。 6. 6. 状态转换图可识别一定的状态转换图可识别一定的字符串字符串（单词）。（单词）。 7. 7. 状态转换图用于表示单词结构状态转换图用于表示单词结构,从状态转换图的初态到终态从状态转换图的初态到终态间间, ,每条路径上字符的连接每条路径上字符的连接, ,就构成了该状态图的合法单词。就构成了该状态图的合法单词。35例例3.6 P41 3.6 P41 图图3.2(a)3.2(a)表示：表示：在状态在状态1 1下，若输入字符为下，若输入字符为X X，则读进，则读进X X，并转换到，并转换到状态状态2 2。若输入字符为若输入字符为Y Y，则读进，则读进Y Y，并转换到状态，并转换到状态3 3。若输入字符非若输入字符非X X和非和非Y Y，则此转换图不工作。，则此转换图不工作。231Y YX X36例例3.7 P41 3.7 P41 图图3.2(b)3.2(b)表示：识别标识符的状态转换图如下表示：识别标识符的状态转换图如下: :其中状态其中状态0 0为初态，为初态，2 2为终态；为终态；识别标识符的过程是：从初态识别标识符的过程是：从初态0 0开始，若在状态开始，若在状态0 0下输入字下输入字符为字母，则读进它，并转换到状态符为字母，则读进它，并转换到状态1 1。在状态在状态1 1之下，若输入字符为字母或数字，则读进它，并之下，若输入字符为字母或数字，则读进它，并重新进入状态重新进入状态1 1。一直重复这个过程直到发现输入字符不再是字母或数字时一直重复这个过程直到发现输入字符不再是字母或数字时（这个字符已经被读进）进入状态（这个字符已经被读进）进入状态2 2；状态状态2 2是终态，意味着到此已识别出一个标识符；是终态，意味着到此已识别出一个标识符；终态上打个星号表示单词尾部多跟一个字符终态上打个星号表示单词尾部多跟一个字符, ,应该去掉。应该去掉。若在状态若在状态0 0时输入的字符不为时输入的字符不为“字母字母”，则意味着这个转，则意味着这个转换图不工作。换图不工作。012 2(b)字母字母字母或数字字母或数字其它其它*37(c)012 2数字数字数字数字其它其它*例例3.8 P41 3.8 P41 图图3.2(c)3.2(c)表示：识别无符号整数的状态转表示：识别无符号整数的状态转换图如下：换图如下： 在在状状态态转转换换图图中中, , 到到达达单单词词符符号号的的终终态态时时即即给给出出相相应应的的单单词词编编码码。若若到到达达终终态态时时多多读读入入了了一一个个符符号号, ,则则识识别别出出该该单单词词后后再再将将多多读读入入的的那那个个符符号号退退回回。对对此此类类情情况况的的处处理理方方法是在终态上以法是在终态上以* *作为标识。作为标识。38例例3.9 P41 3.9 P41 图图3.2(d)3.2(d)表示：识别实数的状态转换表示：识别实数的状态转换图如下：图如下：01数字数字数字数字其它其它*23456数字数字数字数字 数字数字E或或e+ +或或 - -数字数字E或或e其它其它数字数字7(d)初态初态0 0终态终态7 7之之间任意一个路径都间任意一个路径都表示一个实数。表示一个实数。小数形式的实数：小数形式的实数：指数形式的实数：指数形式的实数：该转换图可以识别下面形式的一些实数该转换图可以识别下面形式的一些实数:123. , .123, 123E3 ,123.456,123.45e2 ,.123E+10, 123.456E-3 等等39状态转换图识别字符串状态转换图识别字符串: 综合例综合例v一个非常重要的事实是，一个非常重要的事实是，大多数程序语言的单词符大多数程序语言的单词符号都可以用状态转换图予以识别号都可以用状态转换图予以识别。v作为一个综合例子，作为一个综合例子，教材教材P42-P46.P42-P46.构造了一个识别构造了一个识别某个简单语言的所有单词符号的状态转换图，并给某个简单语言的所有单词符号的状态转换图，并给出了对应的词法分析程序。出了对应的词法分析程序。v希望同学们好好读一下。为完成的实验希望同学们好好读一下。为完成的实验 - - 设计并设计并实现一个小语言的词法分析程序实现一个小语言的词法分析程序, , 可以以这个例子可以以这个例子做参考。做参考。40识别简单语言单词符号的转换图识别简单语言单词符号的转换图v参见P43.图3.37非非*+312字母字母0*非字母与数字非字母与数字字母或数字字母或数字=数字数字数字数字空白空白*4*非数字非数字568*9*13其它其它2态：识别标识态：识别标识符和关键字符和关键字4态：识别整常数态：识别整常数8态：识别态：识别*9态：识别态：识别*13态：识别错误态：识别错误5态：识别态：识别=6态：识别态：识别+41v状态转换图容易用程序实现状态转换图容易用程序实现: 即容易由转换图编写词法分析程序。即容易由转换图编写词法分析程序。v最简单的办法是让每个状态结点对应一小段程序最简单的办法是让每个状态结点对应一小段程序。 根据画出的识别单词的状态转换图构造词法分根据画出的识别单词的状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的工作；词法分析程序的控制程序模拟状态转换图的状态转换。的状态转换。 3.2.4 状态转换图的实现状态转换图的实现 (自学自学) 49 本节内容及关系本节内容及关系正规表达正规表达式式E用用正规集正规集L(E)表示表示,值集值集正规文法正规文法G正规语言正规语言L(G)用用产生产生单词符号结单词符号结构的描述构的描述词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现有限自动机有限自动机 FA M状态转换图状态转换图单词符号集单词符号集L(M)形式化形式化识别识别,接受接受三者相同三者相同等价等价等价等价等价等价50 作业：作业： P64 8 (1) (2) 9 (1)51(b)012 20|10其它其它*0|1012 2(a)字母字母 字母字母其它其它*数字数字523.2.5 确定有限自动机确定有限自动机v确定有限自动机（确定有限自动机（DFA）(Deterministic FA) 一个确定有限自动机一个确定有限自动机(DFA M)是一个五元式是一个五元式: :DFA M=(S, , , s0, F)注：这里注：这里确定确定的含义，就是状态转换关系的含义，就是状态转换关系是一个函数，即对是一个函数，即对于给定的于给定的当前状态当前状态s和当前读入的字符和当前读入的字符a有有唯一确定唯一确定的的下一状下一状态态s。1. S 1. S 是有限是有限状态集状态集；2. 2. 是一个有穷字母表是一个有穷字母表, ,每个元素为一每个元素为一字符字符；3. s3. s0 0S,S,是是唯一唯一的的初态初态; ;4. F4. F S,S,是是终态集终态集（可空）。（可空）。 5. 5. 是一个是一个单值单值映射函数映射函数, (s,a)=s, (s,a)=s，指明若当前的状，指明若当前的状态为态为s s，而输入，而输入字符为字符为a a时，则下一个状态是时，则下一个状态是s s； 533.2.5 确定有限自动机确定有限自动机vDFA表示表示 状态转换矩阵状态转换矩阵 状态转换图状态转换图DFADFA的映射关系可以用一个矩阵表示：的映射关系可以用一个矩阵表示：该矩阵的该矩阵的行行表示表示状态状态列列表示输入表示输入字符字符，矩阵元素表示，矩阵元素表示(s,a)(s,a)的值的值该矩阵称为该矩阵称为状态转换矩阵或状态转换表状态转换矩阵或状态转换表54例如例如3.10 3.10 P48 P48 DFA M=( 0,1,2,3, a,b, , 0, 3) DFA M=( 0,1,2,3, a,b, , 0, 3) 其中其中为为: (0,a)=1 (1,a)=3 (2,a)=1 (3,a)=3: (0,a)=1 (1,a)=3 (2,a)=1 (3,a)=3 (0,b)=2 (1,b)=2 (2,b)=3 (3,b)=3 (0,b)=2 (1,b)=2 (2,b)=3 (3,b)=3 状态转换矩阵状态转换矩阵可表示为可表示为: : 状态图状态图可表示为可表示为: :ab012132213333状状态态字字 符符a012abbaabb355DFA识别识别(读出读出,接受接受)字字vDFADFA识别字识别字： 对于对于 * *中的任何一个字中的任何一个字 ，若存在一条从初态，若存在一条从初态结点到某一终态结点的结点到某一终态结点的通路通路，且这条通路上所有箭且这条通路上所有箭弧的标记符连接成的字等于弧的标记符连接成的字等于 ，则称，则称 为为DFA MDFA M所识所识别。别。例例: P48 : P48 图图3.53.5的的DFADFA识别字识别字abbab, abbab, 因为存在路因为存在路径径 012333012333；但不接受字；但不接受字ababa, ababa, 因为不存在识别因为不存在识别路径。路径。a,ba0123abbab56DFA识别字、语言识别字、语言L(M)vDFADFA识别空字识别空字 若若M M的初态结点同时又是终态结点，的初态结点同时又是终态结点，则称空字则称空字 可以为可以为DFA MDFA M所识别。所识别。例例: : 图图3.53.5的的DFADFA不识别空字不识别空字。vDFA MDFA M所能识别的字的全体记为所能识别的字的全体记为L(M)L(M)。例：例：P48 P48 图图3.53.5的的DFA MDFA M识别的字的全体识别的字的全体 L(M) = L(M) =上所有含有相继两个上所有含有相继两个a a或相继两个或相继两个b b的字的字 a,ba0123abbab57DFA：练习：练习1设有设有 DFA M=(0,1,2,a,b,DFA M=(0,1,2,a,b, ,0,1,2),0,1,2) 其中：其中： （0,a)=2; 0,a)=2; （0,b)=10,b)=1 （1,a)=; 1,a)=; （1,b)=21,b)=2 （2,a)=2; 2,a)=2; （2,b)=22,b)=2问问：该：该DFADFA有几个状态？几个输入字符？初态？终有几个状态？几个输入字符？初态？终态？画出其转换图。态？画出其转换图。n解解：有有0 0，1 1，2 2共共三三个个状状态态。0 0为为初初态态，1 1和和2 2为为终终态态。输入字符为输入字符为a,ba,b两个。两个。 其状态转换图如其状态转换图如: : a,ba012bb583.2.6 非确定有限自动机非确定有限自动机1.1.S S是一有限状态集是一有限状态集; ;2.2.是一个有穷字母表是一个有穷字母表, ,每个元素为一字符每个元素为一字符; ;3.3.F F S ,S ,是是终态集终态集。 4.4.S S0 0 S,S, 是是初态集初态集; ;5.5.是一个是一个多值多值映射函数映射函数, , S S * 2s 其含义为其含义为: :在状态在状态S S, ,输入输入字字时时, ,将转换到下一状态集将转换到下一状态集2s。一个非确定有限自动机一个非确定有限自动机(NFA M)是一个五元式是一个五元式: :NFA M=(S, , , S0, F)而而DFA是字符是字符注：非确定主要是指后继状态可有多个。注：非确定主要是指后继状态可有多个。 DFA是是NFA的特例。的特例。59如如:一个一个NFAMNFAM也可用状态图表示。也可用状态图表示。3.2.6 非确定有限自动机非确定有限自动机a0bba,ba|b123a60假定假定DFADFA有有m m个状态、个状态、n n个输入符个输入符, , 则状态转换图含则状态转换图含m m个状态个状态, , 每个状态最多有每个状态最多有n n条输出边与其它状态相连条输出边与其它状态相连, , 每条边用每条边用中中一个一个字符字符作标记，整个图含作标记，整个图含一个初态一个初态和若干个终态。和若干个终态。 假定假定NFANFA有有m m个状态、个状态、n n个输入字个输入字, , 则状态转换图含则状态转换图含m m个状态个状态, , 每个状态最多有每个状态最多有n n条输出边与其它状态相连条输出边与其它状态相连, , 每条边用每条边用* *中中一个字一个字作标记，整个图含作标记，整个图含若干个初态若干个初态和若干个终态。和若干个终态。NFANFA的状态转换函数的状态转换函数是一是一多值多值函数，即函数，即(s(si i, )=, )=某些某些状态的集合状态的集合 ，它表示由当前状态和当前输入字符不能唯，它表示由当前状态和当前输入字符不能唯一确定下一状态，即允许同一状态对同一输入字可有不同一确定下一状态，即允许同一状态对同一输入字可有不同输出边；而输出边；而DFADFA的状态转换函数的状态转换函数是一个是一个单值单值函数。函数。NFA和和DFA的主要区别的主要区别61例例3.11 DFA M=(s3.11 DFA M=(s0 0,s,s1 1,s,s2 2, a,b, , s, a,b, , s0 0,s,s2 2), ), 且且 (s(s0 0,a)= s,a)= s1 1, (s, (s0 0,b)= s,b)= s2 2, (s, (s1 1,a)= s,a)= s1 1 (s (s1 1,b)= s,b)= s2 2, (s, (s2 2,a)= s,a)= s2 2, (s, (s2 2,b)= s,b)= s1 1 试给出试给出M M的状态转换图与状态转换矩阵。的状态转换图与状态转换矩阵。 解：状态转换图：解：状态转换图： 状态转换矩阵：状态转换矩阵： 字符字符状态状态abs0s1s2s1s1s2s2s2s1as12 s2s0abbab62例例3.12 3.12 NFA M=(sNFA M=(s0 0,s,s1 1,s,s2 2,a,b, ,s,a,b, ,s0 0,s,s2 2,s,s1 1), ), 且且(s(s0 0,a)=s,a)=s2 2, (s, (s0 0, b)=s, b)=s0 0,s,s1 1, (s, (s1 1,a)= ,a)= (s(s1 1,b)=s,b)=s2 2, (s, (s2 2,a)=, (s,a)=, (s2 2,b)= s,b)= s1 1 试给出试给出M Mn n的状态转换图与状态转换矩阵。的状态转换图与状态转换矩阵。解解: : 状态转换图状态转换图: : 状态转换矩阵：状态转换矩阵： 字符字符状态状态abs0s2s0,s1s1s2s2s12 s1s0s2bbbba63NFA识别字识别字、空字、空字、L(M)v1. 1. NFANFA识别字识别字 对于对于 * *中的任何一个字中的任何一个字 ，若存，若存在一条从初态结点到某一终态结点的通路，且这条在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字通路上所有箭弧的标记符连接成的字( (忽略那些标忽略那些标记为记为 的弧的弧) )等于等于 ，则称，则称 为为NFA MNFA M所识别所识别( (读出或读出或接受接受) )。v2. NFA2. NFA识别空字识别空字 若若M M的初态结点同时又是终态结的初态结点同时又是终态结点点; ; 或者存在一条从某个初态结点到某个终态结点或者存在一条从某个初态结点到某个终态结点的的 通路，则称空字通路，则称空字 可以为可以为M M所识别。所识别。v3. NFA M3. NFA M识别的识别的上字的全体记为上字的全体记为L(M)L(M)。64例例3.13 P49 3.13 P49 图图3.63.6的的 NFA MNFA M：a5Y12a6aabXb34bb识别字识别字 abbababbab，路径是，路径是X55142666Y X55142666Y X555555 X555555 X5555514 X5555514 X555513 X555513 X55514 X55514 不接受字不接受字 ababaababa，不接受，不接受L(M)=L(M)=上所有含有相继两个上所有含有相继两个a a或相继两个或相继两个b b的字的字 n注意注意: : 图图3.53.5的的DFADFA与图与图3.63.6的的NFANFA识别的字集相同识别的字集相同，两个两个FAFA等价等价。65NFA：练习：练习练习练习1 1 如图的如图的FA MFA M是是NFANFA吗吗? L(M)=? L(M)=?n是是NFANFAnL(M)L(M) = =aam mb bn n|m0,n0|m0,n0练习练习2 2 如图的如图的FA MFA M是是NFANFA吗吗? L(M)=? L(M)=?aa0a,b1a,b2bba,bn是是NFANFAnL(M)=L(M)= 所所有有含含有有相相继继两两个个a a或相继两个或相继两个b b的字的字 ab01b2a663.3 正规式到有限自动机的构造正规式到有限自动机的构造v由正规式与有限自动机的等价性由正规式与有限自动机的等价性: P53(1)(1)对任何对任何FA MFA M，都存在一个正规式，都存在一个正规式r,r,使得使得L(r)=L(M)L(r)=L(M)。(2)(2)对任何正规式对任何正规式r r，都存在一个，都存在一个FA M,FA M,使得使得L(M)=L(r)L(M)=L(r)。673.3 正规式到有限自动机的构造正规式到有限自动机的构造3.3.1 3.3.1 由正规式构造等价的由正规式构造等价的NFAM NFAM 3.3.2 NFA M3.3.2 NFA M的确定化的确定化3.3.3 3.3.3 具有具有动作动作NFA MNFA M的确定化的确定化 3.3.4 DFA M3.3.4 DFA M的化简的化简( (最小化最小化) )683.3.1 由正规式构造等价的由正规式构造等价的NFAMX2 YRv由正规式构造等价的由正规式构造等价的NFA M的方法：的方法：P50(1) (1) 将正规式将正规式R R构造一个如下仅有两个结点构造一个如下仅有两个结点X,YX,Y的拓的拓广转换图。广转换图。69(2) (2) 采用下述三条转换规则构造采用下述三条转换规则构造NFA MNFA M。sisjr1 | r21.r1r2sisj2.sjsir1 r2sir1r2sjsk*3.sjsisir1r1sjsk3.3.1 由正规式构造等价的由正规式构造等价的NFA M70例例3.14 3.14 构造构造 b b* *(d|ad)(b|ab)(d|ad)(b|ab)+ + 对应的对应的NFANFA。解解: : 首先用首先用R R+ +=RR=RR* *把正规式改造为把正规式改造为 b b* *(d|ad)(b|ab)(b|ab)(d|ad)(b|ab)(b|ab)* * 然后构造其然后构造其NFA MNFA M，如下图所示：，如下图所示：3.3.1 由正规式构造等价的由正规式构造等价的NFAM(3)(3)重复步骤重复步骤2 2不断加入不断加入新结点新结点直到每个弧上的标记是直到每个弧上的标记是 上的上的一个字符一个字符或或为止。为止。71b*(d|ad)(b|ab)(b|ab)*XY(b|ab)*d|adb*b|abX132Yabadbdb|abb41235XYbX41d26bb3578adbaabY72例例3.15 3.15 P50P50 构构造造 (a|b)*(aa|bb)(a|b)*对对应应的的NFANFA。解解: : 构造其构造其NFA MNFA M，如下图所示：，如下图所示： (a|b)*(aa|bb)(a|b)*XY(a|b)*aa|bb(a|b)*X12Ybba|baaa|b312X4Y56123X4abababab2 Y743.3.2 NFA M的确定化的确定化v算法：算法： 由由NFA M=NFA M=（S, S, , f, S, f, S0 0, Z), Z)构造一个等构造一个等价的价的DFAMDFAM=(Q, =(Q, , , I, , I0 0, F), F) 取取I I0 0= S= S0 0； 若状态集若状态集Q Q中有状态中有状态I Ii i=s=s0 0,s,s1 1, , ，s sj j ，s sk kSS，0kj0kj，而且，而且M M机中有机中有f(=sf(=s0 0,s,s1 1, , ，s sj j,a)=f(s,a)=f(s0 0,a) f,a) f(s(s1 1,a)f(s,a)f(s2 2,a),a)f(sf(sj j,a)=s,a)=s0 0,s,s1 1, , s st t= I= It t 若若I It t不在不在Q Q中，则中，则I It t加入加入Q Q。 重复步骤重复步骤2 2 ，直到，直到Q Q中无新的状态加入为止。中无新的状态加入为止。 取终态取终态F=I|IQF=I|IQ且且IZIZ753.3.2 NFA M的确定化的确定化v构造状态子集表构造状态子集表上述过程也可用上述过程也可用表格法表格法来描述。其中来描述。其中列列是字符集是字符集的的字符字符，行行是是Q Q中的各中的各状态状态，开始仅包含，开始仅包含I I0 0状态，状态，随着算法的执行，随着算法的执行，Q Q的状态逐渐增多直至不再增多的状态逐渐增多直至不再增多为止。为止。表格的元素是表格的元素是映射函数。映射函数。763.3.2 NFA M的确定化的确定化v由状态子集表构造由状态子集表构造DFA DFA M M的状态转换表的状态转换表 状态子集表的每个状态子集是状态子集表的每个状态子集是DFA MDFA M的一个状态的一个状态 - - 重新编号重新编号。 DFA MDFA M唯一的初态是唯一的初态是I I0 0对应的状态子集。对应的状态子集。 DFA M DFA M的终态是含有原来的终态的终态是含有原来的终态Y Y的状态子集。的状态子集。77例：设有例：设有NFA M=(X,Y,0,1, NFA M=(X,Y,0,1, f f,X,Y),X,Y)且且f(X,0)=X, f(X,1)=Y, f(Y,0)=X,Y, f(Y,1)=X f(X,0)=X, f(X,1)=Y, f(Y,0)=X,Y, f(Y,1)=X 把它确定化。把它确定化。 解：解：1.M1.M的初态：的初态：I I0 0=X=X则则Q Q中就有了中就有了I I0 0状态；状态； 2. 2.由由Q Q中的状态中的状态I I0 0=X=X，查看，查看M M机有机有 f(X,0)=X, f(X,1)=Y=f(X,0)=X, f(X,1)=Y=I I1 1, , 此时此时Q Q里就有里就有I I0 0 ，I I1 1 由由Q Q中的状态中的状态I I1 1=Y=Y，查看，查看M M机有机有 f(Y,0)=Xf(Y,0)=X，Y =Y =I I2 2, f(Y,1)=X=, f(Y,1)=X=I I0 0, , 此时此时Q Q里就有里就有I I0 0 ,I,I1 1,I,I2 2 由由Q Q中的状态中的状态I I2 2=X,Y=X,Y，查看，查看M M机有机有 f(X,Y,0)=Xf(X,Y,0)=X，Y =Y =I I2 2,f(X,Y,1)=X,Y=,f(X,Y,1)=X,Y=I I2 2, , 此时此时Q Q里就里就 有有I I0 0 ,I,I1 1,I,I2 2 3.F=I 3.F=I1 1,I,I2 2 I I2 2=X,Y=X,YI I2 2=X,Y=X,Y I I2 2=X,Y=X,YI I1 1=Y=YI I2 2=X,Y=X,Y I I1 1=Y=YI I1 1=Y=YI I0 0=X=X I I0 0=X=X1 0 字符QXY01100 78I I2 2=X,Y=X,YI I2 2=X,Y=X,YI I2 2=X,Y=X,YI I1 1=Y=YI I2 2=X,Y=X,YI I1 1=Y=YI I1 1=Y=YI I0 0=X=X I I0 0=X=X1 0 字符QCCCBC BBAA 1 0 QAB11100C0解：解：1.构造状态子集表：构造状态子集表：3.3.确定的确定的DFA MDFA M：2.2.重命名：重命名：79NFA确定化：练习确定化：练习1设有设有NFA M=(x,y,a,b,x,y), NFA M=(x,y,a,b,x,y), 其中其中定义如定义如下下: (x,a)=x,y (x,b)=y: (x,a)=x,y (x,b)=y(y,a)= (y,b)=x,y(y,a)= (y,b)=x,y试构造相应的试构造相应的 DFAMDFAM。解：解：1.1.构造状态子集表：构造状态子集表： axbyabbNFAxx,y y x,y x,y x,y y x,y aa021bbDFAbx 0 b a 字符字符Q1 211 1210 b aQ2.2.重命名：重命名：3.3.确定的确定的DFA MDFA M：803.3.3 具有具有弧的弧的NFA M确定化确定化 v_闭包闭包可以从某状态或某些状态通过可以从某状态或某些状态通过 弧弧所能到达的所所能到达的所有状态的集合。有状态的集合。假定假定I I是是NFA MNFA M的状态集的一个子集，的状态集的一个子集，v状态集合状态集合I的的_闭包（闭包（ _CLOSURE(I)形式定义如下：形式定义如下： (1)(1)若若s si iI, I, 则则s si i _CLOSURE(I)_CLOSURE(I)； (2) (2)若若s si iI, I, 则从则从s si i出发经过任意段的出发经过任意段的 弧弧所能到达的任意所能到达的任意 状态状态s sj j属于属于 _CLOSURE(I)_CLOSURE(I)。 81例例3.163.16：若若 I=X I=X 则则_CLOSUR(I)=X, _CLOSUR(I)=X, 5, 5, 11 I=5, 1 I=5, 1 I=2 I=2a5Y12a6aabXb34bb _CLOSUR(I)=5, 1 _CLOSUR(I)=5, 1 _CLOSUR(I)=2, 6, Y _CLOSUR(I)=2, 6, Y823.3.3 具有具有弧的弧的NFA M确定化确定化v闭包间的转换：闭包间的转换： 设设 _CLOSURE(I)=s_CLOSURE(I)=s1 1 , s , s2 2 ,. ,. ， s sk k 当当读入字母表中的字母读入字母表中的字母a a时，它转换到另一闭包时，它转换到另一闭包 _CLOSURE(J)_CLOSURE(J)。 对对NFA MNFA M的任一状态子集的任一状态子集I, I, 若若a a是是中的一个中的一个字符，则定义字符，则定义 Ia=_CLOSURE(J) 其中其中J= qJ= q|(q, a)=q|(q, a)=q 且且 qI; qI; aa 表示表示: J: J是从是从I I中某一状态出发经过中某一状态出发经过a a所能到达的所所能到达的所有状态的集合有状态的集合。 83例例3.17 3.17 对下图对下图, ,取取I=I= _CLOSUREI=1,2, _CLOSUREI=1,2, 求从状态求从状态I I出发经一条有向边出发经一条有向边a a所能所能 到达的状态集到达的状态集J J和和 _CLOSURE(J)_CLOSURE(J)。a1524a6378a J=5, 3 ,4 Ia=_CLOSURE(J)=5, 6, 2, 3, 8, 4, 784设有设有NFA MNFA M=(S, , , =(S, , , S S0 0 , Z), Z)构造一个等价的构造一个等价的 DFA M DFA M=(Q, , ,=(Q, , ,I I , F) , F) 设设= a1,a2, = a1,a2, , ak , ak v构造一张状态转换子集表构造一张状态转换子集表第一行第一列为第一行第一列为 I=_CLOSUR(S I=_CLOSUR(S0 0) )，以此，以此I I求求 I Ia1a1,I,Ia2a2, ,I,Iakak。把把没没有有在在第第一一列列出出现现过过的的I Iaiai填填入入空空行行第第一一列列，以以此此 I Iaiai为为新的新的 I I，再求，再求I Ia1a1,I,Ia2a2，I Iakak。重复重复的过程，直到所有求出的的过程，直到所有求出的I Iaiai都在第一列出现为止。都在第一列出现为止。 I Ia1 Ia2 Iak_CLOSUR(S0)3.3.3 具有具有弧的弧的NFA M确定化确定化85例例3.17 3.17 正规式正规式(a|b)*(aa|bb)(a|b)*(a|b)*(aa|bb)(a|b)*的的NFA MNFA M如下如下: : 试将其确定化为试将其确定化为DFA MDFA M。34251X6abababab2 Y86解解: :构造一张状态子集表构造一张状态子集表 = a, b IIaIbX,1,21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,41,2,31,2,4,5,6,Y1,2,3,5,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y34251X6abababab2 Y873.3.3 具有具有弧的弧的NFA M确定化确定化v由状态子集表构造由状态子集表构造DFADFA的状态转换表。的状态转换表。 状态子集表的每个状态子集是状态子集表的每个状态子集是DFA MDFA M的一个状的一个状态态 - - 重新编号。重新编号。 DFA DFA M M唯唯一一的的初初态态是是_CLOSUR(S_CLOSUR(S0 0) )对对应应的的状状态态子集。子集。 DFA M DFA M的的终态终态是含有原来的终态是含有原来的终态Y Y的状态子集。的状态子集。88由状态子集表构造由状态子集表构造DFADFA的状态转换矩阵的状态转换矩阵: : I Ia Ib X, 5, 1 初 0 5, 3, 1 1 5, 4, 1 2 5, 3, 1 1 5, 3, 1, 2, 6, Y 3 5, 4, 1 2 5, 4, 1 2 5, 3, 1 1 5, 4, 1, 2, 6, Y 5 5, 3, 1, 2, 6, Y 终3 5, 3, 1, 2, 6, Y 3 5, 4, 1, 6, Y 4 5, 4, 1, 6,Y 终 4 5, 3, 1, 6, Y 6 5, 4, 1, 2, 6, Y 5 5, 4, 1, 2, 6, Y 终5 5, 3, 1, 6, Y 6 5, 4, 1, 2, 6, Y 5 5, 3, 1, 6, Y 终6 5, 3, 1, 2, 6, Y 3 5, 4, 1, 6, Y 489Qab012132214335464564635a2 32 52 42 6120abbaababbaabb于是得到对应的于是得到对应的DFAMDFAM如下：如下：重命名：重命名：90NFANFA确定化的实质是以确定化的实质是以原有状态集上的原有状态集上的覆盖片作为覆盖片作为DFADFA上的一个状态，将原状上的一个状态，将原状态间的转换改为覆盖片间的转换态间的转换改为覆盖片间的转换，从而，从而把不确定问题确定化。通常经过确定化把不确定问题确定化。通常经过确定化之后，状态数增加，而且可能出现一些之后，状态数增加，而且可能出现一些等价状态，这时需要等价状态，这时需要化简化简。913.3.4 DFAM的化简的化简vNFANFA确定化所得的确定化所得的DFADFA可能含有多余的状态需化简。可能含有多余的状态需化简。v所谓一个所谓一个DFA M=(S, DFA M=(S, , , , s, s0 0, F) , F) 的的化简化简( (最少化、最小化最少化、最小化),), 是指寻找一个状态数比较少的是指寻找一个状态数比较少的DFA MDFA M, , 使使L(ML(M)=L(M)=L(M)。v化简的原则：化简的原则：受的语言是等价的。受的语言是等价的。v思想思想-划分法划分法1.1.把把DFA MDFA M的的状态集状态集S S分划成一些不相交的子集分划成一些不相交的子集, , 使属于同一使属于同一子集的子集的状态都等价状态都等价, , 属于不同子集的属于不同子集的状态可区别状态可区别。2.2.从从每个子集选一个代表每个子集选一个代表, , 消去其他等价状态。消去其他等价状态。3.3.把那些原来导入子集各状态的弧都导入此代表状态。把那些原来导入子集各状态的弧都导入此代表状态。v化简后的化简后的DFA MDFA M 满足下述条件：满足下述条件： (1) (1)无多余状态；无多余状态； (2) (2)状态集中无相互等价的状态。状态集中无相互等价的状态。92状态的等价和可区别定义状态的等价和可区别定义v定义定义: : 设设s,ts,t S S是两个不同的状态是两个不同的状态, , 若对任何若对任何 * *, , 从从s(s(或或t)t)出发能读出出发能读出而停于而停于某个终态某个终态，则称，则称s s和和t t是是等价状态。等价状态。否则，称否则，称s s和和t t是是可区别的，即不等可区别的，即不等价的。价的。v例如例如: : 终态和非终态是可区别的，因为终态能读出终态和非终态是可区别的，因为终态能读出空字空字，而非终态不行。，而非终态不行。v又如：又如：P51.P51.图图3.83.8的的DFADFA中的状态中的状态1 1和和2 2是可区别的，是可区别的，因为状态因为状态1 1能读出能读出a a而停于终态，但状态而停于终态，但状态2 2读出读出a a后不后不能停于终态。能停于终态。v等价状态定义了状态集合上的等价关系。因此，等价状态定义了状态集合上的等价关系。因此，状状态集合能被划分成等价类。态集合能被划分成等价类。933.3.4 DFA M的化简的化简vDFA MDFA M的化简方法：的化简方法：(1)(1)首先将首先将DFA MDFA M的状态集的状态集S S中的中的终态终态与与非终态非终态分开分开, ,形成两个子集形成两个子集, ,得到基本划分。得到基本划分。(2)(2)对当前已划分出的对当前已划分出的I I(1),I,I(2), ,I,I(m)子集子集, , 看每看每个个I I是否能进一步划分。对某个是否能进一步划分。对某个I I(i)= = s1,s2,s1,s2,sk, ,sk, 若存在输入字符若存在输入字符aa使得使得I Ia a(i)不全包含在当前划分的某个子集不全包含在当前划分的某个子集I I(j)中中, , 即跨越两即跨越两个子集个子集, , 则将则将I I(i)一分为二。一分为二。(3)(3)重复重复(2), (2), 直到每个子集均不能再分。直到每个子集均不能再分。 不能再分是指子集要么仅有一个状态，要么有多不能再分是指子集要么仅有一个状态，要么有多个状态但这些状态是等价的。个状态但这些状态是等价的。94例例3.15 3.15 化简由例化简由例3.143.14得到的得到的DFADFA。2 32 52 42 6120abbaababbaabbab解解: : (1)(1)先将状态集先将状态集S=0,1,2,3,4,5,6S=0,1,2,3,4,5,6划分为终态集划分为终态集3,4,5,63,4,5,6和非终态集和非终态集0,1,20,1,2。 (2.1) (2.1)考察非终态考察非终态0,1,2:0,1,2:因因0,2,1,a=1,30,2,1,a=1,3不属于不属于3,4,5,63,4,5,6和和0,1,2,0,1,2,由于由于1 1状态经状态经a a弧到达弧到达3 3状态状态( (是终态是终态) )，而状态，而状态0 0、2 2经经a a弧到达弧到达1 1状态状态( (是非终态是非终态), ), 故应把故应把1 1状态状态分出，故将分出，故将0,1,20,1,2分为分为0,20,2和和11。 95 考察考察0,2 :0,2 :因因0,2,b=2,4,0,2,b=2,4,不属于已划分出的不属于已划分出的某个子集某个子集, , 故故0,20,2划分为划分为 00和和22。(2.2)(2.2)考察终态集考察终态集3,4,5,63,4,5,6：3,4,5,6,a=33,4,5,6,a=3, ,6, 6, 属属于于3,4,5,6,3,4,5,6,故不划分。故不划分。 3,4,5,6,b=43,4,5,6,b=4, ,5,5,属于属于3,4,5,6,3,4,5,6,故不划分。故不划分。(3)(3)整个划分为整个划分为4 4个组个组 0,1,2,3,4,5,60,1,2,3,4,5,6(4)(4)令状态令状态3 3代表代表33，4 4，5 5，6,6,把原来到达状态把原来到达状态4 4，5 5，6 6的弧的弧都导入都导入3 3，并删除，并删除4 4，5 5，6 6得：得： 2 32 52 42 6120abbaababbaabbab961203 3aabbbaab2 32 52 42 6120abbaababbaabbab97DFA的化简：练习的化简：练习将如图所示的将如图所示的 DFA M DFA M 最小化。最小化。baACBDbbbbaEaaACbbaA,Ba=B A,BA,Bb=C,E C,D,EC,D,Ea=B A,BC,D,Eb=D,C C,D,E分成分成 2个子集个子集, 选代表选代表分别为分别为A和和C, 最后得到最后得到最最小化的小化的DFA, 如图示。如图示。983.3.4 正规文法与有限自动机正规文法与有限自动机v关系定理：关系定理： 设设G=(VG=(VN N,V,VT T,P,S),P,S)是正规文法，则存在一个有限是正规文法，则存在一个有限自动机自动机M=(S, , , sM=(S, , , s0 0, Z), Z)使得使得L(G)L(G)L(M)L(M) 注：注：1）正规文法分为右线性文法或左线性文法，但对一）正规文法分为右线性文法或左线性文法，但对一个正规文法，不能既是右线性，又是左线性。个正规文法，不能既是右线性，又是左线性。 2）对每个自动机）对每个自动机M都存在一个右线性正规文法都存在一个右线性正规文法GR和和左线性正规文法左线性正规文法GL，使得，使得L(M)=L(GR)=L(GL)993.4 词法分析器的自动产生词法分析器的自动产生v回顾词法分析器的构造过程：回顾词法分析器的构造过程： 正规式正规式NFADFANFADFA最小化最小化DFADFA词法分析器词法分析器v每一步都可借助成熟的算法来构造每一步都可借助成熟的算法来构造, , 无须人工干预。无须人工干预。v词法分析器生成器词法分析器生成器，就是将这些算法组合起来所形成，就是将这些算法组合起来所形成的软件。的软件。v利用这样的软件，只需将所需的词法分析器识别的单利用这样的软件，只需将所需的词法分析器识别的单词符号用正规式的方式描述出来，生成器就会生成相词符号用正规式的方式描述出来，生成器就会生成相应的词法分析器。应的词法分析器。v当前最成熟、最广泛应用的当前最成熟、最广泛应用的词法分析器生成器是词法分析器生成器是LEXLEX和和与与LEXLEX相似的工具，不妨统称为相似的工具，不妨统称为LEXLEX。1003.4 词法分析器的自动生成词法分析器的自动生成 由由于于不不同同高高级级语语言言中中单单词词的的结结构构大大致致相相同同, , 基基本本上上都都可可用用一一组组正正规规式式描描述述, ,因因而而希希望望构构造造一一自自动动生生成成系系统统: : 只只要要给给出出某某高高级级语语言言单单词词的的一一组组正正规规式式及及识识别别各各类类单单词词时时应应采采取取的的语义动作语义动作, , 该系统便可自动产生该语言的词法分析程序。该系统便可自动产生该语言的词法分析程序。正规式正规式有限自动机有限自动机词法分析器词法分析器控制程序控制程序自动生成器自动生成器转化转化合成合成101LEX源程序LEX编译系统词法分析程序L输入串词法分析程序L单词符号串3.4.1 语言语言LEX 的一般描述的一般描述vLEX 语言语言 LEX LEX 是美国是美国BellBell实验室研制的一个词法分析程序的实验室研制的一个词法分析程序的自动生成工具。对任一高级程序语言，用户必须用自动生成工具。对任一高级程序语言，用户必须用正规正规式式描述该语言的各个词法类描述该语言的各个词法类(LEX(LEX的源程序的源程序) )，LEXLEX就可自就可自动生成该语言的词法分析程序。动生成该语言的词法分析程序。LEXLEX及其编译系统作用及其编译系统作用如下如下: :102LEX语言语言源程序源程序LEX编译编译词法分析器词法分析器 LEXLEX语言源程序由两部分组成语言源程序由两部分组成: :正规式辅助定义式正规式辅助定义式识别规则识别规则3.4.1 语言语言LEX 的一般描述的一般描述vLEX 语言语言 LEX LEX 语言用正规式描述单词的词法规则语言用正规式描述单词的词法规则, ,并通并通过过LEXLEX编译编译, ,自动生成词法扫描器。自动生成词法扫描器。参见参见P58.P58. Pascal Pascal标识符集合的正规式定义例标识符集合的正规式定义例参见参见P59.P59. Pascal Pascal无符号集合的正规式定义例无符号集合的正规式定义例参见参见P59.P59. LEX LEX源程序的识别规则形式例源程序的识别规则形式例参见参见P5960. P5960. 识别识别P42.P42.表表3.13.1的单词符号的的单词符号的LEXLEX程序例程序例103 M1 M2 Mm x P1 P2Pm 3.4.2 LEX 的实现的实现vLEX编译的工作原理编译的工作原理 LEX LEX编译对源程序进行处理编译对源程序进行处理, , 产生一个词法分产生一个词法分析器析器. .主要有三个步骤主要有三个步骤: : 1 1 对每条识别规则对每条识别规则P Pi i, ,构造一个非确定有限构造一个非确定有限自动机自动机 M Mi i, , 设一初态设一初态X ,X ,用边连接每个用边连接每个M Mi i的初态的初态, ,构构成一个总的成一个总的NFAMNFAM104 控制程序控制程序用于扫描输入字符串用于扫描输入字符串, ,控制状态的控制状态的转移转移;(;(对任何转换矩阵对任何转换矩阵, ,其控制程序是一样的其控制程序是一样的) )当当识别出某词形识别出某词形P Pi i后后, ,执行执行A Ai i.(.(返回种别码及值返回种别码及值) )状态转状态转换矩阵换矩阵控制控制程序程序词法分析器词法分析器 22根据定理根据定理3 ,3 ,把把 NFAM NFAM 确定化确定化, ,得到一确定有限自动得到一确定有限自动机机 DFAMDFAM的的状态转换矩阵状态转换矩阵;33产生一个产生一个控制程序控制程序；输出如下所示的词法分析器输出如下所示的词法分析器: :3.4.2 LEX 的实现的实现105 词法分析涉及的概念及关系词法分析涉及的概念及关系扫描识别扫描识别, 依据构词规依据构词规则则源程序源程序(字符串字符串)单词符号串单词符号串词法分析程序词法分析程序(扫描器扫描器)输入输入输出输出输入输入, 扫描扫描 预处理预处理, 超前搜超前搜索索单词分类单词分类 内部表示内部表示手工生成手工生成 自动生成自动生成 等价等价状态转换图状态转换图用程序实现用程序实现, 即扫描器即扫描器正规式正规式, 正规集正规集有限自动机有限自动机 DFA NFA自动生成工具自动生成工具LEX,用正规式描述用正规式描述, 扫扫描器象描器象FA一样工作一样工作 生成生成描述描述工具工具等价等价106词法分析小词法分析小结结单词符号结单词符号结构的描述构的描述状态转换图状态转换图词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现正规正规(表达表达)式式E 用用正规集正规集L(E) 表示表示,值集值集正规文法正规文法G正规语言正规语言L(G)用用产生产生有限自动有限自动机机 FA单词符号单词符号集集L(M)形式形式化化识别识别,接接受受DFA DFA简化简化NFA NFA确定化确定化 三者相同三者相同等价等价等价等价等价等价107第三章第三章 结束结束 作业作业 P64 7（1） 12 （b）