《04-词法分析-备课.ppt》由会员分享，可在线阅读，更多相关《04-词法分析-备课.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理第四章第四章 词法分析词法分析主要内容主要内容n本章学习目标本章学习目标n4.1 4.1 词法分析程序的设计词法分析程序的设计n4.2 4.2 单词的描述工具单词的描述工具n4.3 4.3 有穷自动机有穷自动机n4.44.4正规式和有穷自动机的等价性正规式和有穷自动机的等价性n4.54.5正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性n4.6 4.6 词法分析程序的自动生成器词法分析程序的自动生成器LEXLEXn小结本章小结本章n重点习题解析重点习题解析n作业作业n相关术语的回顾（英文版）相关术语的回顾（英文版）2一起交流 共同进步本章学习目标本章学习目标一学习目标一学习目标
2、理解词法分析程序的功能和有限自动机及其理解词法分析程序的功能和有限自动机及其化简方法；化简方法；掌握正规表达式与正规文法和理解状态转换掌握正规表达式与正规文法和理解状态转换图的实现；图的实现；了解词法分析器的自动产生。了解词法分析器的自动产生。二课程安排二课程安排n6学时学时3一起交流 共同进步本章重点本章重点n有穷自动机是构造词法分析程序的理论基础。n本章主要介绍词法分析程序的设计原理和构造方法，重点介绍有穷自动机的基本概念以及正规文法、正规表达式与有穷自动机之间的相互关系。4一起交流 共同进步4.1词法分析程序的设计词法分析程序的设计n实现词法分析（实现词法分析（lexicalanalys
3、is）的程序的程序n逐个读入源程序字符并按照构词规则切分成一系列逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。括保留字、标识符、运算符、标点符号和常量等。n词法分析是编译过程中的一个阶段，在语法分析前词法分析是编译过程中的一个阶段，在语法分析前进行进行。也可以和语法分析结合在一起作为一遍，由。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析程序调用词法分析程序来获得当前单词供语法分析使用。语法分析使用。5一起交流 共同进步词
4、法分析程序和语法分析程序的关系词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokenget token.6一起交流 共同进步词法分析程序的任务词法分析程序的任务主要任务：主要任务：n读源程序，产生单词符号读源程序，产生单词符号其他任务：其他任务：n滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符n追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序，n宏展开，宏展开，7一起交流 共同进步词法分析分离的考虑词法分析分离的考虑词法分析从语法分析独立出来的原因：词法分析从语法分析独立出来的原因：n简化设计简化设计n改进编译效率改进编译效率n增加编译系统的可移植性增加编译系
5、统的可移植性8一起交流 共同进步常常遇到的术语Token单词单词,词标，符号词标，符号lexeme词素，词位词素，词位pattern模式，式样模式，式样9一起交流 共同进步 帮助理解术语 In general，there is a set of strings in the input for which the same token is produced as output.This set of strings is described by a rule called a pattern associated with the token.The pattern is said to
6、match each string in the set.A lexeme is a sequence of characters in the source program that is matched by the pattern for a token.e.g.nConst pi=3.14159；中的pi是token“identifier”的lexeme，其pattern为letter followed by letters and/or digit.10一起交流 共同进步单词符号及输出单词的形式单词符号及输出单词的形式 关键字关键字 例如，例如，C语言中的语言中的if，else，wh
7、ile,do等等,这些字在语言中有固定的意义，这些字在语言中有固定的意义，一般不作为标识符使用。一般不作为标识符使用。标识符标识符 表示各种名字，如变量名、常表示各种名字，如变量名、常 量名、数组名和函数名等量名、数组名和函数名等。语言的语言的单词符号单词符号是指语言中具有独立是指语言中具有独立 意义的最小语法单位意义的最小语法单位。单词符号及输出单词的形式单词符号及输出单词的形式 常数常数 各种类型的常数，如整型常数各种类型的常数，如整型常数 125、实型常数、实型常数0.718、布尔型常数、布尔型常数TRUE 等等。运算符运算符 如、如、*、/、等。、等。分界符分界符 如如，、；、（、）等
8、。，、；、（、）等。单词符号及输出单词的形式单词符号及输出单词的形式 词词法法分分析析程程序序所所输输出出的的单单词词符符号号通常表示成如下的二元式：通常表示成如下的二元式：（单词种别，单词自身的值）（单词种别，单词自身的值）单词符号及输出单词的形式单词符号及输出单词的形式 单词种别单词种别 单词种别表示单词的种类，它是单词种别表示单词的种类，它是语法分析需要的信息。语法分析需要的信息。为处理方便为处理方便通常让每种单词对应通常让每种单词对应一个整数码一个整数码。单词符号及输出单词的形式单词符号及输出单词的形式 常数常数:可统归为一种，也可按类型可统归为一种，也可按类型 （整型、实型、布尔型等
9、）分种（整型、实型、布尔型等）分种。基本字基本字:可将其全体视为一种，也可可将其全体视为一种，也可 以一字一种。以一字一种。标识符标识符:一般统归为一种。一般统归为一种。运算符和界符运算符和界符:可采用一符一种的分法，可采用一符一种的分法，也可以统归为一种。也可以统归为一种。单词符号及输出单词的形式单词符号及输出单词的形式 单词自身的值单词自身的值 一个种别只含一个单词符号一个种别只含一个单词符号 一个种别含有多个单词符号一个种别含有多个单词符号 (1)对于标识符其自身值是标识符对于标识符其自身值是标识符自自 身的字符串；身的字符串；(2)常数自身值是常数本身的二进制常数自身值是常数本身的二进
10、制 数值。数值。单词符号及输出单词的形式单词符号及输出单词的形式 (3)用指向某类表格一个特定项目指用指向某类表格一个特定项目指 针值来区分同类中不同的单词。针值来区分同类中不同的单词。例如例如,对于标识符用它在符号表的入对于标识符用它在符号表的入口指针作为它自身值口指针作为它自身值;常数用它在常常数用它在常数表的入口指针作为它自身的值。数表的入口指针作为它自身的值。单词符号及输出单词的形式单词符号及输出单词的形式 常数自身的值用常数本身的值常数自身的值用常数本身的值(转变成转变成 标准二进制形式标准二进制形式)表示；表示；例子例子:if (a1)b=100；假定假定:基本字、运算符和界符都是
11、一符一种；基本字、运算符和界符都是一符一种；标识符自身的值用自身的字符串表示；标识符自身的值用自身的字符串表示；18一起交流 共同进步单词符号及输出单词的形式单词符号及输出单词的形式 假设:关键字关键字if种别编码为种别编码为1；标识符的种别编码为整数标识符的种别编码为整数10；常数的种别编码为整数常数的种别编码为整数11；赋值号的种别编码为赋值号的种别编码为4；大于号的种别编码为大于号的种别编码为23；分号的种别编码为分号的种别编码为26；左括号的种别编码为左括号的种别编码为29；右括号的种别编码为右括号的种别编码为30；则程序段；则程序段：19一起交流 共同进步单词符号及输出单词的形式单词
12、符号及输出单词的形式 if (a1)b=100；在经在经词法分析程序扫词法分析程序扫 描后描后，它所输出的单词符号串是：，它所输出的单词符号串是：（1，）基本字if（29，）左括号(（10，a）标识符a（23，）大于号（11，1）常数 1（30，）右括号)（10，b）标识符b（4，）赋值号=（11，100）常数 100（26,）分号 ；4.2单词的描述工具单词的描述工具n程序设计语言中的单词是基本语法成分。程序设计语言中的单词是基本语法成分。n单词符号的语法可以用有效的工具加以描单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分述，并且基于这类描述工具，实现词法分析程序的
13、自动构造。析程序的自动构造。n程序设计语言的单词的语法都能用程序设计语言的单词的语法都能用正规文正规文法和正规式法和正规式描述。描述。21一起交流 共同进步正规文法正规文法3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中，其中AVAVN N ，BVBVN N ，a Va VT T*单词符号的两种定义方式：单词符号的两种定义方式：n正规文法，以标识符为例正规文法，以标识符为例:n Il|Il|Id 或 n Il|lTn Tl|d|lT|dT 其中，l代表az中任一字母；d代表09中任一数字n正规式，以标识符为例正规式，以标识符为例:n l(l|d)*2
14、2一起交流 共同进步正规式正规式正规式也称正则表达式正规式也称正则表达式,正规表达式正规表达式（regularexpression）是说明单词的是说明单词的模式模式(pattern)的一种重要的表示法（记的一种重要的表示法（记号），是定义正规集的号），是定义正规集的数学工具。我们数学工具。我们用以描述单词符号。下面是正规式和它用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。所表示的正规集的递归定义。23一起交流 共同进步n定义（正规式和它所表示的正规集）：定义（正规式和它所表示的正规集）：设字母表为设字母表为，辅助字母表，辅助字母表=，。n1.和和 都是都是 上的正规式，它们所表示
15、的正上的正规式，它们所表示的正规集分别为规集分别为 和和；正规式正规式24一起交流 共同进步2.任何任何a ，a是是 上的一个正规式，它所表上的一个正规式，它所表示的正规集为示的正规集为a；3.假定假定e1和和e2都是都是 上的正规式，它们所表示上的正规式，它们所表示的正规集分别为的正规集分别为L(e1)和和L(e2)，那么，那么，(e1),e1 e2,e1 e2,e1 也都是正规式也都是正规式,它它们所表示的正规集分别为们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和和(L(e1)。4.仅由有限次使用上述三步骤而定义的表达仅由有限次使用上述三步骤而定义的表达式才
16、是式才是 上的正规式，仅由这些正规式所表上的正规式，仅由这些正规式所表示的集合才是示的集合才是 上的正规集。上的正规集。正规式正规式25一起交流 共同进步reviewRegularexpressionsonthealphabet aredefinedbythefollowingrecursiverules:1)Everysymbolof isaregularexpression2)and and f f isaregularexpression3)ifr1andr2areregularexpressions,soare(r1)r1r2r1|r2r1*4)Nothingelseisaregula
17、rexpression.=0,1,2,3,4,5,6,7,8,9(1|2|3|4|5|6|7|8|9|0)*isaregularexpression(1|2|3|4|.8|9|0)(1|2|3.|8|9|0)*isaregularexpression(1|2|3.|8|9|0)+26一起交流 共同进步正规式中的三种运算符正规式中的三种运算符n“”读为读为“或或”（也有使用也有使用“+”代替代替“”的）；的）；n“”读为读为“连接连接”；n“”读为读为“闭包闭包”（即，任意有限次的自重（即，任意有限次的自重复连接）。复连接）。在不致混淆时，括号可省去，但规定算符的优先在不致混淆时，括号可省去，但
18、规定算符的优先顺序为顺序为“”、“”、“”。连接符。连接符“”一般可省略不写。一般可省略不写。“”、“”和和“”都是左结合的。都是左结合的。27一起交流 共同进步正规式和正规集正规式和正规集 例例1 设有字母表设有字母表=a,b，根据正规式与，根据正规式与 正规集的定义，则有：正规集的定义，则有：1.a 和和 b是正规式，相应正规集为是正规式，相应正规集为2.a|b 是正规式，相应正规集为是正规式，相应正规集为3.ab 是正规式，相应正规集为是正规式，相应正规集为L(a)=a,L(b)=b L(a|b)=L(a)L(b)=a,bL(ab)=L(a)L(b)=ab=ab正规式和正规集正规式和正规
19、集4.(a|b)*是正规式，相应正规集为是正规式，相应正规集为 例如，例如，a,b*的子集的子集 an bn|n1 就不是就不是一个正规集，一个正规集，不能用正规式来描述，也不不能用正规式来描述，也不能用正规文法来描述，只能用上下文无关能用正规文法来描述，只能用上下文无关法来描述。法来描述。需要指出的是，对需要指出的是，对 a,b*的任一子集不的任一子集不能认为是一个正规集。能认为是一个正规集。L(a|b)*)=(L(a|b)*=a,b*=,a,b,aa,ab,ba,bb,5.ba a*是正规式，相应的正规集为是正规式，相应的正规集为正规式和正规集正规式和正规集L(ba a*)=L(b)L(a
20、 a*)=b,ba,baa,baaa,6.(a|b)*(aa|bb)(a|b)*是正规式，相是正规式，相应正规集为应正规集为即上所有含两个相继a或两个相继b组成的串。L(a|b)*(aa|bb)(a|b)*)=L(a|b)*)L(aa|bb)L(a|b)*)a,b*aa,bba,b*30一起交流 共同进步正规式和正规集正规式和正规集 例例2 设设=a,b,c,则则 aa*bb*cc*是是上的一上的一个正规式个正规式,它所表示的正规集：它所表示的正规集：L=abc,aabc,abbc,abcc,aaabc,=ambnck|m,n,k1a+b+c+正规式和正规集正规式和正规集 例例3 设程序语言字
21、母表是键盘字符集合，设程序语言字母表是键盘字符集合，则程序语言部分单词符号可用如下正规式则程序语言部分单词符号可用如下正规式定义：定义：关键字 if|else|while|do标识符 l(l|d)*l代表az中任一字母整常数 dd*d代表09中任一数字关系运算符 =例子例子4.2令令=a，b，上的正规式和相应的正规集的上的正规式和相应的正规集的例子有：例子有：正规式正规式正规集正规集aaa ba,babab(a b)(a b)aa,ab,ba,bba ,a,a,任意个任意个a的串的串33一起交流 共同进步正规式正规式正规集正规集(a b),a,b,aa,ab所有由所有由a和和b组成的串组成的串
22、(a b)(aa bb)(a b)上所有含有两个相继的上所有含有两个相继的a或两个相继的或两个相继的b组成组成的串的串34一起交流 共同进步例例4.1令令=l，d，则则 上的正规式上的正规式r=l(l d)定义的正规集定义的正规集为为:l,ll,ld,ldd,其中其中l代表字母代表字母,d代表数字代表数字,正规式正规式即是即是字母字母(字母字母|数字数字),它表示的正规集中的它表示的正规集中的每个元素的模式是每个元素的模式是“字母打头的字母数字串字母打头的字母数字串”,就是就是Pascal和和多数程序设计语言允许的标识符的词法规则多数程序设计语言允许的标识符的词法规则.例例4.3=d，e，+，
23、-,则则 上的正规式上的正规式d(dd )(e(+-)dd)表表示的是无符号数的集合。其中示的是无符号数的集合。其中d为为09的数字。的数字。程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义.例子讨论下面两个例子例子讨论下面两个例子35一起交流 共同进步n若两个正规式若两个正规式e1和和e2所表示的正规集相同所表示的正规集相同,则则说说e1和和e2等价等价,写作写作e1=e2。n例如：例如：e1=(a b)，e2=b an又如：又如：e1=b(ab),e2=(ba)be1=(a b),e2=(a b)正规式等价正规式等价36一起交流 共同进步n设设r,s,t为正规式，
24、正规式服从的代数规律为正规式，正规式服从的代数规律:n1.r s=s r“或或”服从交换律服从交换律n2.r(s t)=(r s)t“或或”的可结合律的可结合律n3.(rs)t=r(st)“连接连接”的可结合律的可结合律n4.r(s t)=rs rt(s t)r=sr tr分配律分配律n5.r=r,r=r 是是“连接连接”的恒等元的恒等元素素n6.r r=rr=r rr“或或”的抽取律的抽取律37一起交流 共同进步正规式正规式正规文法正规文法对对 上的正规式上的正规式r,存在一个存在一个RG=(VN,VT,P,S)：L(G)=L(r)初始，初始，VT=,S VN，生成正规产生式生成正规产生式S
25、r(R1)对形如对形如Ar1r2的的正规产生式：正规产生式：Ar1BBr2B VN(R2)对形如对形如Ar r1的的正规产生式：正规产生式：ArBAr1BrBBr1B VN(R3)对形如对形如Ar1 r2的的正规产生式正规产生式:Ar1Ar2不断应用不断应用R做变换，直到每个产生式右端做变换，直到每个产生式右端都符合正规文法都符合正规文法的形式。的形式。38一起交流 共同进步例例4.4 r=a(a d)Sa(a d)SaAA(a d)A(a d)BAB(a d)BBGs:SaAAVT=a,dAaBVN=S,A,BAdBBaBBdBB39一起交流 共同进步正规文法正规文法正规式正规式对对G=(V
26、N,VT,P,S),存在一个存在一个=VT上的正规式上的正规式r:L(r)=L(G)AxB,ByA=xyAxA yA=x yAx yA=x y40一起交流 共同进步正规文法正规文法正规式正规式例例4.5Gs:SaA|aAaA a dA dA(a d)A(a d)A(a d)(a d)S=a(a d)(a d)a=a(a d)(a d)=a(a d)R=a(a d)41一起交流 共同进步有穷自动机有穷自动机作为一种识别装置，它能准确地识别正规集，有穷自动机作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，即识别正规文法所定义的语言和正规式所表示的集合，引入有
27、穷自动机这个理论，正是为词法分析程序的自动引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。构造寻找特殊的方法和工具。有穷自动机是具有离散输入与输出系统的一种抽象数学有穷自动机是具有离散输入与输出系统的一种抽象数学模型。模型。分类：分类：确定的有穷自动机确定的有穷自动机(DeterministicFiniteAutomata)不确定的有穷自动机不确定的有穷自动机(NondeterministicFiniteAutomata)n确定的有穷自动机和非确定的有穷自动机都能准确地识确定的有穷自动机和非确定的有穷自动机都能准确地识别正规集别正规集42一起交流 共同进步有穷自动机有
28、穷自动机n有穷自动机，或有穷状态的机器，是描述（或有穷自动机，或有穷状态的机器，是描述（或“机器机器”）特定类型算法）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序。程，因此也能用作构造扫描程序。n通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义（假设已定义了（假设已定义了letter和和digit）：）：nidentifier=letter(letter|digit)*n它代表以一个字母开头且其后为任
29、意字母和它代表以一个字母开头且其后为任意字母和/或数字序列的串。或数字序列的串。nnn通过标明数字通过标明数字1和和2的圆圈表示的是状态（的圆圈表示的是状态（state），它们表示其中记），它们表示其中记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录已被发现的模式的数量在识别过程中的位置。带有箭头的线代表由记录一个状态向另一个状态的转换（录一个状态向另一个状态的转换（transition），该转换依赖于所标字），该转换依赖于所标字符的匹配。符的匹配。43一起交流 共同进步关于关于有穷自动机有穷自动机我们将讨论如下题目我们将讨论如下题目确定的有穷自动机确定的有穷自动机DFA不确
30、定的有穷自动机不确定的有穷自动机NFANFA的确定化的确定化DFA的最小化的最小化44一起交流 共同进步确定的有穷自动机确定的有穷自动机DFAnDFA定义：定义：一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一个五元组：是一个五元组：M=（K，f，S，Z）其中其中1.K1.K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；2.2.是一个有穷字母表，它的每个元素称为一个输是一个有穷字母表，它的每个元素称为一个输入符号，所以也称入符号，所以也称为输入符号表；为输入符号表；45一起交流 共同进步DFA定义定义3.3.f是转换函数，是在是转换函数，是在KK上的
31、映射，即，上的映射，即，如如 f（ki，a）=kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为a时，时，将转换为下一个状态将转换为下一个状态kj，我们把我们把kj称作称作k ki的的一个后继状态；一个后继状态；4.SKK是唯一的一个初态；是唯一的一个初态；5.5.Z K是一个终态集，终态也称可接受状态是一个终态集，终态也称可接受状态或结束状态。或结束状态。46一起交流 共同进步一个一个DFA的例子：的例子：DFAM=（S，U，V，Q，a，b，f，S，Q）其中其中f定义为：定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，
32、a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q47一起交流 共同进步n一个一个DFA可以表示成一个状态图可以表示成一个状态图(或称状态转或称状态转换图换图)。假定。假定DFAM含有含有m个状态，个状态，n个输入字个输入字符，那么这个状态图含有符，那么这个状态图含有m个结点，每个结点个结点，每个结点最多有最多有n个弧射出，整个图含有唯一一个初态个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头结点和若干个终态结点，初态结点冠以双箭头“=”或标以或标以“-”，终态结点用双圈表示或标以，终态结点用双圈表示或标以“+”，若，若f(ki,a)=kj，则从状态结点则从状态结
33、点ki到状态结到状态结点点kj画标记为画标记为a的弧；的弧；DFA的状态图表示的状态图表示48一起交流 共同进步DFA的状态图表示的状态图表示bSUVQaaaba，b49一起交流 共同进步DFA的矩阵表示的矩阵表示一个一个DFA还可以用一个矩阵表示，该矩阵还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的元素表示相应状态行和输入字符列下的新状态，即新状态，即k行行a列为列为f(k,a)的值。用双的值。用双箭头箭头“=”标明初态；否则第一行即是初标明初态；否则第一行即是初态，相应终态行在表的右端标以态，相应终态行在表
34、的右端标以1，非终，非终态标以态标以0。50一起交流 共同进步DFA的矩阵表示的矩阵表示字符字符状态状态000151一起交流 共同进步为了说明为了说明DFA如何作为一种识别机制如何作为一种识别机制,我我们还要理解下面的定义们还要理解下面的定义n*上的符号串上的符号串t t在在DFA MDFA M上运行上运行一个输入符一个输入符号号串串t，（，（将它表示成将它表示成Tt1的形式，的形式，其中其中T，t1*）在）在DFAM=（K，f，S，Z）上运行的定义为：上运行的定义为：f（Q，Tt1）=f（f（Q，T），），t1）其中其中QK扩充转换函数扩充转换函数f f为为 K*K上的映射，且：上的映射，且
35、：f（ki，）=ki52一起交流 共同进步*上的符号串上的符号串t t被被DFADFA M M接受接受M=（K，f，S，Z）若若t*，f(S，t)=P，其中其中S为为M的开始状的开始状态，态，P Z，Z为终态集。为终态集。则称则称t为为DFAM所接受（识别）所接受（识别）.53一起交流 共同进步举例举例例例：证明证明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属于终态。属于终态。得证。得证。,bbSUVQababaa54一起交流
36、共同进步DFAM所能接受的符所能接受的符号号串的全体记为串的全体记为L(M).对于任何两个有穷自动机对于任何两个有穷自动机M和和M，如果如果L(M)=L(M)，则称则称M与与M是等价的是等价的.结论：结论：上一个符上一个符号号串集串集V 是正规的，当且仅当存是正规的，当且仅当存在一个在一个 上的确定有穷自动机上的确定有穷自动机M，使得使得V=L(M)。55一起交流 共同进步nDFA的确定性表现在转换函数的确定性表现在转换函数f:KK是一个是一个单值函数单值函数，也就是说，对任何状，也就是说，对任何状态态kK，和输入符号和输入符号a，f(k,a)唯一唯一地确定了下一个状态。从状态转换图来地确定了
37、下一个状态。从状态转换图来看，若字母表看，若字母表含有含有n个输入字符，那么个输入字符，那么任何一个状态结点最多有任何一个状态结点最多有n条弧射出，而条弧射出，而且每条弧以一个不同的输入字符标记。且每条弧以一个不同的输入字符标记。56一起交流 共同进步DFA的行为的程序来模拟DFAM=（K，f，S，Z）的行为的模拟程序的行为的模拟程序nK:=S；nc:=getchar;nwhileceofdonK:=f(K,c);nc:=getchar;n;nifKisinZthenreturn(yes)nelsereturn(no)57一起交流 共同进步reviewDFA M=（K，f，S，Z）1)A fi
38、nite set of states,one of which is designated the initial state or start state,and some of which are designated as final states.2)An alphabet of possible input symbols.3)A finite set of transitions that specifies for each state and for each symbol of the input alphabet,which state to go to next.58一起
39、交流 共同进步3型文法产生的语言是有穷自动机（型文法产生的语言是有穷自动机（FA）所接受的集合所接受的集合定理定理 设设G=G=（V VN N，V VT T，P P，S S）是是3 3型型文法文法，则存在，则存在一个有穷自一个有穷自 动机动机 M=(K,f,A,Z)M=(K,f,A,Z)，使得使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 这样构造：这样构造：=V VT T K=K=V VN N N,NN,N为一个新状态为一个新状态,它它不不在在V VN N中中 A=S A=S Z=N Z=N 对对G G中的形如中的形如 DtBDtB的产生式的产生式,t,t
40、为终结符或为终结符或,有有f(D,t)=Bf(D,t)=B；对对G G中形如中形如DtDt的产生式，的产生式，t t为终结符或为终结符或,有有f(D,t)=N;f(D,t)=N;对对V VT T中的每一个中的每一个a,a,有有f(N,a)=f(N,a)=59一起交流 共同进步G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bBASaaabbba,bDZabab60一起交流 共同进步定理定理 已知一有穷自动机已知一有穷自动机M=M=(K,f,A,Z)(K,f,A,Z),存在有一个存在有一个3 3型文法型文法G=G=（V VN N，V VT T，P P，S S）,使使得得L
41、(G)=L(M)L(G)=L(M)G G 的定义：的定义：V VT T=V VN N=K K S=A S=A 若若 f(D,t)=B f(D,t)=B，则，则DtBDtB在在P P中中 若若 f(D,t)=B f(D,t)=B，且，且B B在在Z Z中，则中，则DtDt在在P P中中61一起交流 共同进步G：SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|bDBASaaabba,bb62一起交流 共同进步DFA63一起交流 共同进步DFA=digit,not digit64一起交流 共同进步不确定的有穷自动机不确定的有穷自动机NFA定义定义nNFAM=K，f，S，Z，其中其
42、中K为状态为状态的有穷非空集，的有穷非空集，为有穷输入字母表，为有穷输入字母表，f为为K *到到K的子集（的子集（2K）的一种映射，的一种映射，S K是初始状态集，是初始状态集，Z K为终止状态集为终止状态集.65一起交流 共同进步NFA举例举例NFAM=（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,111166一起交流 共同进步SPZ00,1111状态图表示状态图表示67一起交流 共同进步矩阵表示矩阵表示矩阵表示简化为68一起交流 共同进步具有转移的不确定的有穷自动机123abc69一起交流 共同
43、进步定理定理n对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFAN，一定存在一个一定存在一个不具有不具有 转移的不确定转移的不确定的有穷自动机的有穷自动机NFA，使得，使得L(M)=L(N)。与上例等价的一个与上例等价的一个NFA.2acbb31acacbb70一起交流 共同进步类似类似DFA,对对NFAM=K，f，S，Z 也有如下定义也有如下定义*上的符上的符号号串串t在在NFAM上运行上运行.一个输入符一个输入符号号串串t，（，（我们将它表示成我们将它表示成Tt1的形式，其的形式，其中中T，t1*）在）在NFAM上运行的定义为：上运行的定义为：f（Q，Tt
44、1）=f（f（Q，T），），t1）其中其中QK.*上的符上的符号号串串t被被NFAM接受接受若若t*，f(S0，t)=P，其中其中S0S，P Z，则称则称t为为NFAM所接受（识别）所接受（识别）71一起交流 共同进步*上的符号串上的符号串t t被被NFA MNFA M接受也可以这样接受也可以这样理解理解n对于对于*中的任何一个串中的任何一个串t t，若存在一条从某一若存在一条从某一初态结到某一终态结的道路，且这条道路上所初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串有弧的标记字依序连接成的串(不管标记为不管标记为的弧的弧)等于等于t t，则称则称t t可为可为NFA MN
45、FA M所识别所识别(读出或读出或接受接受)。n若若M M的某些结既是初态结又是终态结，或者存的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路在一条从某个初态结到某个终态结的道路,其其上所有弧的标记均为上所有弧的标记均为，那么空字可为那么空字可为M M所接所接受。受。72一起交流 共同进步0001111010001110000001000110073一起交流 共同进步NFAM所能接受的符所能接受的符号号串的全体记为串的全体记为L(M)结论：结论：上一个符上一个符号号串集串集V 是正规的，当且仅当是正规的，当且仅当存在一个存在一个 上的不确定的有穷自动机上的不确定的有穷自
46、动机M，使得使得V=L(M)。74一起交流 共同进步(0|1)*(000|111)(0|1)75一起交流 共同进步NFA等价转换等价转换DFAnDFA是是NFA的特例的特例.对每个对每个NFAN一定存一定存在一个在一个DFA，使得使得L(M)=L(N)。对对每个每个NFAN存在着与之等价的存在着与之等价的DFAM。n有有一种算法，将一种算法，将NFA转换成接受同样语言的转换成接受同样语言的DFA,这种算法称为这种算法称为子集法子集法.n注：与某一注：与某一NFA等价的等价的DFA不唯一不唯一.76一起交流 共同进步NFADFAn从从NFA的矩阵表示中可以看出，表项通常的矩阵表示中可以看出，表项
47、通常是一状态的集合，而在是一状态的集合，而在DFA的矩阵表示中的矩阵表示中，表项是一个状态，表项是一个状态，NFA到相应的到相应的DFA的构造的基本思路是：的构造的基本思路是：DFADFA的每一个状的每一个状态对应态对应NFANFA的一组状态的一组状态.DFA使用它的使用它的状态去记录在状态去记录在NFA读入一个输入符号后读入一个输入符号后可能达到的所有状态可能达到的所有状态.77一起交流 共同进步NFADFA算法算法假设假设NFAN=(K,f,K0,Kt)按如下办法按如下办法构造一个构造一个DFAM=(S,d,S0,St)，使使得得L(M)=L(N)：1.M的状态集的状态集S由由K K的一些
48、子集的一些子集组成。用组成。用S1S2.Sj表示表示S的元素，其中的元素，其中S1,S2,.Sj是是K的状态。并且约定，状态的状态。并且约定，状态S1,S2,.Sj是按某种规则排列的，即对于子集是按某种规则排列的，即对于子集S1,S2=S2,S1,来说，来说，S的状态就是的状态就是S1S2；78一起交流 共同进步NFADFA算法算法2M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是；3转换函数是这样定义的：转换函数是这样定义的：d(S1S2,.Sj,a)=R1R2.Rt其中其中R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)4S0=-closure(K0)
49、为为M的开始状态；的开始状态；5St=SiSk.Se，其中其中SiSk.Se S且且Si,Sk,.Se Kt79一起交流 共同进步定义对状态集合定义对状态集合I的几个有关运算的几个有关运算1.状态集合状态集合I I的的-闭包闭包，表示为表示为-closure(I)，定义为一定义为一状态集，是状态集状态集，是状态集I中的任何状态中的任何状态S经任意条经任意条弧而能到弧而能到达的状态的集合。达的状态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于-closure(I)。2.状态集合状态集合I I的的a a弧转换弧转换，表示为表示为move(I,a)定义为状态集定义为状态集合合J，其中其
50、中J是所有那些可从是所有那些可从I中的某一状态经过一条中的某一状态经过一条a弧弧而到达的状态的全体。而到达的状态的全体。80一起交流 共同进步状态集合状态集合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；12534687aaa81一起交流 共同进步构造构造NFAN的的状态K的子集的算法的算法n假定所构造的子集族为假定所构造的子集族为C，即，即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态为状态K的子集。的子集。1开始