编译原理第三章词法分析优秀PPT.ppt

《编译原理第三章词法分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《编译原理第三章词法分析优秀PPT.ppt（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理第三章 词法分析现在学习的是第1页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o几个概念几个概念:n考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集n其中每一个元素称为一个其中每一个元素称为一个字符字符n上的上的字字(也叫也叫字符串字符串)是指由是指由中的字符所构成的中的字符所构成的一个有穷序列一个有穷序列n不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为n用用*表示表示上的所有字的全体上的所有字的全体,包含空字包含空字现在学习的是第2页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o*的子集的子集U和和V的的连接连接（积积）定

2、义为）定义为UV|U&V oV自身的自身的 n次积记为次积记为Vn=VVVo规定规定V0=，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;记记 VVV*，称，称V+是是V的正规闭包。的正规闭包。现在学习的是第3页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o上下文无关文法的定义：上下文无关文法的定义：一个上下文无关文法一个上下文无关文法G G是一个四元式是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中，其中nV VT T：终结符集合：终结符集合(非空非空)nV VN N：非终结符集合：非终结符集合(非空非空)，且，且V VT T V V

3、N N=nS S：文法的开始符号，：文法的开始符号，S S V VN NnP P：产生式集合：产生式集合(有限有限)，每个产生式形式为，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*n开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。现在学习的是第4页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o定义：称定义：称 A 直接推出直接推出，即，即 A 仅当仅当A 是一个产生式，是一个产生式，且且，(VT VN)*。o如果如果 1 2 n，则我们称这个序列，则我们称这个序列是从是从 1到到 n的一个的一个推导推

4、导。若存在一个从。若存在一个从 1到到 n的推导，则称的推导，则称 1可以可以推导推导出出 n。现在学习的是第5页，共111页o通常，用通常，用 表示：从表示：从 1 1出发，经过出发，经过一步或若干步，可以推出一步或若干步，可以推出 n n。用用 表示：从表示：从 1 1出发，经过出发，经过0 0步或步或若干步，可以推出若干步，可以推出 n n。所以所以 ：即即 或或o定义：假定定义：假定G G是一个文法，是一个文法，S S 是它的开始符号。是它的开始符号。如果如果 ，则，则 称是一个称是一个句型句型。仅含终结符。仅含终结符号的句型是一个号的句型是一个句子句子。文法。文法G G所产生的句子的

5、全所产生的句子的全体是一个体是一个语言语言，将它记为，将它记为 L(G)L(G)。现在学习的是第6页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o最左推导最左推导：任何一步：任何一步 都是对都是对 中的最左中的最左非终结符进行替换。非终结符进行替换。最右推导最右推导：任何一步：任何一步 都是对都是对 中的最右非中的最右非终结符进行替换。终结符进行替换。现在学习的是第7页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o用一张图表示一个句型的推导用一张图表示一个句型的推导,称为称为语法树语法树。E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+

6、i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)现在学习的是第8页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o定义：如果一个文法存在某个句子对应两颗定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个不同的语法树，则说这个文法是二义的文法是二义的。o语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如果，如果对它不存在无二义性的文法。对它不存在无二义性的文法。现在学习的是第9页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o形式语言鸟瞰形式语言鸟瞰0型型(短语文法，图灵机短语文法，图灵机)：产生式形如：产生式

7、形如：其中：其中：(VT VN)*且至少含有一个非终结符；且至少含有一个非终结符；(VT VN)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)：产生式形如：产生式形如：其中：其中：|，仅，仅 S 例外。例外。现在学习的是第10页，共111页复习：复习：程序语言的语法描述程序语言的语法描述 o形式语言鸟瞰形式语言鸟瞰2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如：A 其中：其中：A VN；(VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；

8、A，B VN 产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN现在学习的是第11页，共111页第三章第三章 词法分析词法分析o词法分析是编译的第一个阶段，在单词的词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。级别上分析和翻译源程序。o理论基础：理论基础：n有限自动机理论；有限自动机理论；n有限自动机理论与正规文法、正规式之间在有限自动机理论与正规文法、正规式之间在描述语言方面有一一对应的关系。描述语言方面有一一对应的关系。o学习目标：学习目标：n掌握有限自动机与正规文法、正规式之间的掌握有限自动机与正规文法、正规式之间的转换转换n能够构造词法分析程序。能

9、够构造词法分析程序。现在学习的是第12页，共111页第三章第三章 词法分析词法分析o词法分析的任务：从左至右逐个字符地对词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。源程序进行扫描，产生一个个单词符号。o词法分析器词法分析器(Lexical Analyzer)又称扫描器又称扫描器(Scanner)：执行词法分析的程序：执行词法分析的程序现在学习的是第13页，共111页3.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式o功能功能:输入源程序、输出单词符号输入源程序、输出单词符号o单词符号的种类：单词符号的种

10、类：n基本字基本字：如：如 beginbegin，repeatrepeat，n标识符标识符表示各种名字：如变量名、数表示各种名字：如变量名、数组名和过程名组名和过程名n常数常数：各种类型的常数：各种类型的常数n运算符运算符：+，-，*，/，n界符界符：逗号、分号、括号和空白：逗号、分号、括号和空白现在学习的是第14页，共111页o输出的单词符号的表示形式输出的单词符号的表示形式:(单词种别单词种别，单词自身的值单词自身的值)o单词种别通常用整数编码表示。单词种别通常用整数编码表示。n若一个种别只有一个单词符号，则种别编码就若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算

11、符和界符代表该单词符号。假定基本字、运算符和界符都是一符一种。都是一符一种。n若一个种别有多个单词符号，则对于每个若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。单词符号，给出种别编码和自身的值。o标识符单列一种；标识符自身的值表示成按标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。机器字节划分的内部码。o常数按类型分种；常数的值则表示成标准的二进常数按类型分种；常数的值则表示成标准的二进制形式。制形式。现在学习的是第15页，共111页例例 C程序程序o while(i=j)i-;o输出单词符号：输出单词符号：=,-现在学习的是第16页，共111页例例 FOR

12、TRAN程序程序oIF(5.EQ.M)GOTO 100IF(5.EQ.M)GOTO 100o输出单词符号：输出单词符号：逻辑逻辑IFIF(34(34，-)-)左括号左括号(2(2，-)-)整常数整常数(20(20，5 5的二进制的二进制)等号等号(6(6，-)-)标识符标识符(26(26，M M)右括号右括号(16(16，-)-)GOTOGOTO(30(30，-)-)标号标号(19(19，100100的二进制的二进制)现在学习的是第17页，共111页二、词法分析器作为一个独立子程序二、词法分析器作为一个独立子程序o词法分析是作为一个独立的阶段，是否应词法分析是作为一个独立的阶段，是否应当将其处

13、理为一遍呢？当将其处理为一遍呢？n作为独立阶段的优点：结构简洁、清晰和作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝条理化，有利于集中考虑词法分析一些枝节问题。节问题。n不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。现在学习的是第18页，共111页词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.现在学习的是第19页，共111页词法分析器的结构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词

14、法分析器的设计词法分析器的设计现在学习的是第20页，共111页o输入串放在输入缓冲区中。输入串放在输入缓冲区中。o预预处处理理子子程程序序：剔剔除除无无用用的的空空白白、跳跳格格、回回车车和和换换行行等等编编辑辑性性字字符符;区区分分标标号号区区、捻接续行和给出句末符等捻接续行和给出句末符等o扫描缓冲区扫描缓冲区 起点起点 搜索搜索指示器指示器 指示器指示器一、输入、预处理一、输入、预处理现在学习的是第21页，共111页 WhatALongWord WhatALongWo rdrd WhatALongWord WhatALongWo现在学习的是第22页，共111页二、单词符号的识别二、单词符号

15、的识别:超前搜索超前搜索1 基本字识别基本字识别:例如例如:DO99K=1，10 DO 99 K=1，10 IF(5.EQ.M)GOTO55 IF(5.EQ.M)GOTO 55DO99K=1.10IF(5)=55o需要超前搜索才能确定哪些是基本字需要超前搜索才能确定哪些是基本字现在学习的是第23页，共111页2 标识符识别标识符识别:o字母开头的字母数字串，后跟界符或算符字母开头的字母数字串，后跟界符或算符3 常数识别常数识别:o识别出算术常数并将其转变为二进制内码表识别出算术常数并将其转变为二进制内码表示。有些也要超前搜索。示。有些也要超前搜索。5.EQ.M 5.E084 算符和界符的识别算

16、符和界符的识别o把多个字符符合而成的算符和界符拼合成一把多个字符符合而成的算符和界符拼合成一个单一单词符号。个单一单词符号。:=，*，.EQ.，+，-，=现在学习的是第24页，共111页三、状态转换图三、状态转换图1 1 概念概念o状态转换图是一张有限方向图。状态转换图是一张有限方向图。213XYn结点代表状态，用圆圈表示。结点代表状态，用圆圈表示。o状态之间用箭弧连结，箭弧上的状态之间用箭弧连结，箭弧上的标记标记(字符字符)代表射出结状态下可代表射出结状态下可能出现的输入字符或字符类。能出现的输入字符或字符类。o一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有一个为初态，至

17、少要有一个终态。有一个为初态，至少要有一个终态。现在学习的是第25页，共111页识别标识符的状态转换图识别标识符的状态转换图123字母字母其他其他字母或数字字母或数字*识别识别整常数整常数的状态转换图的状态转换图123数字数字其他其他数字数字*o一个状态转换图可用于识别一个状态转换图可用于识别(或接受或接受)一定的一定的字符串。字符串。现在学习的是第26页，共111页2 2 例子例子o助忆符助忆符：直接用编码表示不便于记忆，因此用：直接用编码表示不便于记忆，因此用助忆符来表示编码。助忆符来表示编码。现在学习的是第27页，共111页现在学习的是第28页，共111页1 12 23 34 45 56

18、 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字母与数字数字数字非数字非数字数字数字=+*非非*,()其它其它*现在学习的是第29页，共111页o几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索n所所有有基基本本字字都都是是保保留留字字;用用户户不不能能用用它它们们作作自自己的标识符己的标识符n基基本本字字作作为为特特殊殊的的标标识识符符来来处处理理;不不用用特特殊殊的的状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。n如如果果基基本本字字、标标识识符符和和常常数数(或或标标号号)之之间间没没有有确确定定的的运

19、运算算符符或或界界符符作作间间隔隔，则则必必须须使使用用一个空白符作间隔。一个空白符作间隔。DO99K=1，10 要写成要写成 DO 99 K=1，10现在学习的是第30页，共111页3 状态转换图的实现状态转换图的实现o思想：每个状态结对应一小段程序。思想：每个状态结对应一小段程序。o做法做法:1)1)对不含回路的分叉结，可用一个对不含回路的分叉结，可用一个CASECASE语句或语句或一组一组IF-THEN-ELSEIF-THEN-ELSE语句实现语句实现GetChar();if(IsLetter()状态状态j的对应程序段的对应程序段;else if(IsDigit()状态状态k的对应程序段

20、的对应程序段;else if(ch=/)状态状态l的对应程序段的对应程序段;else 错误处理错误处理;ijkl字母字母数字数字现在学习的是第31页，共111页3 状态转换图的实现状态转换图的实现2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构结构和和IFIF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段现在学习的是第32页，共111页3 状态转换图的实现状态转换图的实现3)终态结表示识别出某种单词符号，因

21、此，对应终态结表示识别出某种单词符号，因此，对应语句为语句为 RETURN(C，VAL)其中，其中，C为单词种别，为单词种别，VAL为单词自身值为单词自身值.现在学习的是第33页，共111页o全局变量与过程全局变量与过程1)ch 字符变量、存放最新读入的源程序字符字符变量、存放最新读入的源程序字符2)strToken 字符数组，存放构成单词符号字符数组，存放构成单词符号的字符串的字符串3)GetChar 子程序过程，把下一个字符读入子程序过程，把下一个字符读入到到 ch 中中4)GetBC 子程序过程，跳过空白符，直至子程序过程，跳过空白符，直至 ch 中读入一非空白符中读入一非空白符5)Co

22、ncat 子程序，把子程序，把ch中的字符连接到中的字符连接到 strToken 现在学习的是第34页，共111页6)IsLetter和和 IsDisgital 布尔函数，判布尔函数，判断断ch中字符是否为字母中字符是否为字母和数字和数字7)Reserve 整型函数，对于整型函数，对于 strToken 中中的字符串查找保留字表，若它的字符串查找保留字表，若它是保留字则给是保留字则给出它的编码，否则回送出它的编码，否则回送08)Retract 子程序，把搜索指针回调一个子程序，把搜索指针回调一个字符位置字符位置9)InsertId 整型函数，将整型函数，将strToken中的中的标识符插入符号

23、表，返回符号表指针标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将整型函数过程，将strToken中的常数插入常数表，返回常数中的常数插入常数表，返回常数表指针。表指针。现在学习的是第35页，共111页int code,value;strToken:=“”;/*置置strToken为空串为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalu

24、e:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end现在学习的是第36页，共111页else if(IsDigit()beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);endelse if(ch=)return($ASSIGN,-);else if(ch=+)return($PLUS,-);现在学习的是第37页，共111页else if(ch=*)beginG

25、etChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);endelse if(ch=;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else ProcError();/*错误处理错误处理*/现在学习的是第38页，共111页3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机o几个概念几个概念:n考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集n其中每一个元素称为一个其中每一个元素称为一个字符字符n上的上的字字

26、(也叫也叫字符串字符串)是指由是指由中的字符中的字符所构成的一个有穷序列所构成的一个有穷序列n不包含任何字符的序列称为不包含任何字符的序列称为空字空字，记为，记为n用用*表示表示上的所有字的全体上的所有字的全体,包含空字包含空字例如例如:设设=a，b，则，则*=,a,b,aa,ab,ba,bb,aaa,.现在学习的是第39页，共111页o*的子集的子集U和和V的的连接连接（积积）定义为）定义为UV|U&V V自身的自身的 n次积记为次积记为Vn=VVVo规定规定V0=，令，令 V*=V0V1V2V3 称称V*是是V的的闭包闭包;记记 VVV*，称，称V+是是V的正规闭包。的正规闭包。现在学习的

27、是第40页，共111页3.3.1 正规式和正规集正规式和正规集o正正规规集集可可以以用用正正规规表表达达式式（简简称称正正规规式式）表示。表示。o正正规规表表达达式式是是表表示示正正规规集集一一种种方方法法。一一个个字字集集合合是是正正规规集集当当且且仅仅当当它它能能用用正正规规式式表表示。示。现在学习的是第41页，共111页o正规式和正规集的递归定义：正规式和正规集的递归定义：对给定的字母表对给定的字母表 1)和和都是都是 上的正规式，它们所表示的正上的正规式，它们所表示的正规集为规集为 和和;2)任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a;现在学习

28、的是第42页，共111页3)假定假定e e1 1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集为正规集为L(e1)和和L(e2)，则，则i)(e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才使用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字上的正规式，仅由这些正规式表示的字

29、集才是集才是 上的正规集。上的正规集。现在学习的是第43页，共111页o所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。o若若两两个个正正规规式式所所表表示示的的正正规规集集相相同同，则则称称这这两个正规式等价。如两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*L(ba)*b)=L(ba)*)L(b)=(L(ba)*L(b)=(L(b)L(a)*L(b)=ba*b=,ba,baba,bababa,b=b,bab,babab,bababab,L(b(ab)*)=L(b)L(ab)*)=L(b)(L(ab)*=L(b)(L(a)L(b)*=b ab*

30、=b ,ab,abab,ababab,=b,bab,babab,bababab,L(b(ab)*)=L(ba)*b)b(ab)*=(ba)*b现在学习的是第44页，共111页o对正规式，下列等价成立：对正规式，下列等价成立：ne1|e2=e2|e1 交换律交换律ne1|(e2|e3)=(e1|e2)|e3 结合律结合律ne1(e2e3)=(e1e2)e3 结合律结合律ne1(e2|e3)=e1e2|e1e3 分配律分配律n(e2|e3)e1=e2e1|e3 e1分配律分配律ne =e=e e1e2 e2 e1 L(e1|e2)=L(e1)L(e2)=L(e2)L(e1)=L(e2|e1)现在学

31、习的是第45页，共111页正规集正规集正规式正规式3.3.1现在学习的是第46页，共111页3.3.2 确定有限自动机确定有限自动机(DFA)o对状态图进行形式化，则可以下定义：对状态图进行形式化，则可以下定义：自动机自动机M是一个五元式是一个五元式M=(S,f,S0,F),其中：其中：1.S:有穷状态集，有穷状态集，2.：输入字母表：输入字母表(有穷有穷)，3.f:状状态态转转换换函函数数，为为SS的的单单值值部部分分映映射射，f(s，a)=s表表示示：当当现现行行状状态态为为s，输输入入字字符符为为a时时，将将状状态态转转换换到到下下一一状状态态s。我我们们把把s称称为为s的一个后继状态。

32、的一个后继状态。4.S0 S是唯一的一个初态；是唯一的一个初态；5 F S：终态集：终态集(可空可空)。现在学习的是第47页，共111页o例如：例如：DFA M=(0，1，2，3，a，b，f，0，3)，其中：其中：f定义如下：定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbb现在学习的是第48页，共111页oDFA可可以以表表示示为为状状态态转转换换图图。假假定定DFA M含含有有m个个状状态态和和n个个输输入入字字符符，那那么么，这这

33、个个图图含含有有m个个状状态态结结点点，每每个个结结点点顶顶多多含含有有n条条箭箭弧弧射射出出，且且每每条条箭箭弧弧用用上上的的不不同同的的输输入入字符来作标记。字符来作标记。现在学习的是第49页，共111页o对对于于*中中的的任任何何字字，若若存存在在一一条条从从初初态态到到某某一一终终态态的的道道路路，且且这这条条路路上上所所有有弧弧上上的的标标记记符符连连接接成成的的字字等等于于，则则称称 为为DFA M所所识别识别(接收接收)oDFA M所识别的字的全体记为所识别的字的全体记为L(M)。o可可以以证证明明：上上的的字字集集V V*是是正正规规集集，当当且且仅当存在上的仅当存在上的DFA

34、 M，使得，使得VL(M)。现在学习的是第50页，共111页3.3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA)o定定义义：一一个个非非确确定定有有限限自自动动机机(NFA)M是是一一个五元式个五元式M=(S,M=(S,f,S,S0 0,F),F)，其中：，其中：1 S:有穷状态集；有穷状态集；2 ：输入字母表：输入字母表(有穷有穷)；3 f:状状态态转转换换函函数数，为为S*2S的的部部分分映映射射(非单值非单值)；4 S S0 0 S S是非空的初态集；是非空的初态集；5 F S S：终态集：终态集(可空可空)。现在学习的是第51页，共111页o从状态图中看从状态图中看NFA

35、 和和DFA的区别：的区别：1 弧弧上上的的标标记记可可以以是是*中中的的一一个个字字，而而不不一一定是单个字符；定是单个字符；2 同同一一个个字字可可能能出出现现在在同同状状态态射射出出的的多多条条弧弧上。上。oDFA是是NFA的特例。的特例。现在学习的是第52页，共111页021 a，baaa，bbba，b012abab识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字ambn|m，n 1现在学习的是第53页，共111页o定义：对于任何两个有限自动机定义：对于任何两个有限自动机M和和M，如果如果L(M)=L(M)，则称，则称M与与M等价。等价。o自动机理论中一个重要的结论

36、：判定两个自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。自动机等价性的算法是存在的。o对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与NFA描述能力相描述能力相同。同。现在学习的是第54页，共111页1.假定假定NFA M=，我们对，我们对M的状的状态转换图进行以下改造：态转换图进行以下改造：1)引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,Y S，从从X到到S0中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧，从从F中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y。2)对对M的状态转换图进

37、一步施行替换，其中的状态转换图进一步施行替换，其中k是是新引入的状态。新引入的状态。证明证明:现在学习的是第55页，共111页代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下面的三条规则对按下面的三条规则对V进行分裂进行分裂:现在学习的是第56页，共111页o逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的一上的一个字符或个字符或，最后得到一个，最后得到一个NFA M，显然，显然L(M)=L(M)现在学习的是第57页，共111页o识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字XY 514236ab aba

38、bab5126ab abaabb现在学习的是第58页，共111页2.把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的-闭包闭包-closure(I)为为:i)若若s I，则，则s-closure(I)；ii)若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到达弧而能到达的任何状态的任何状态s都属于都属于-closure(I)即即 -closure(I)=I s|从某个从某个s I出发经过任意条出发经过任意条 弧弧能到达能到达s现在学习的是第59页，共111页o设设a是是 中的一个字符，定义中的一个字符，定义Ia=-c

39、losure(J)其中，其中，J为为I中的某个状态出发经过一条中的某个状态出发经过一条a弧而弧而到达的状态集合。到达的状态集合。现在学习的是第60页，共111页o-closure(1)=1，2=I J=5，4，3 Ia=-closure(J)=-closure(5，4，3)=5，4，3，6，2，7，861a 234578aa o设设a是是 中的一个字中的一个字符，定义符，定义Ia=-closure(J)其中，其中，J为为I中的某中的某个状态出发经过一个状态出发经过一条条a弧而到达的状弧而到达的状态集合。态集合。现在学习的是第61页，共111页o把确定化的过程把确定化的过程:不失一般性，设字母表

40、只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表:现在学习的是第62页，共111页首先，置第首先，置第1行第行第1列为列为-closure(X)求出这求出这一列的一列的Ia，Ib；然后，检查这两个然后，检查这两个Ia，Ib，看它们是否已在表中，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第一列中出现，把未曾出现的填入后面的空行的第的第1列上，求出每行第列上，求出每行第2，3列上的集合列上的集合.重复上述过程，直到所有第重复上述过程，直到所有第2，3列子集全部列子集全部出现在第一列为止。出现在第一列为止。现在学习的是第63页，共111页II

41、aIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 514236ab ababab现在学习的是第64页，共111页o现在把这张表看成一个状态转换矩阵，把其现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。中的每个子集看成一个状态。o这张表唯一刻划了一个确定的有限自动机这张

42、表唯一刻划了一个确定的有限自动机M，它的初态是，它的初态是-closure(X)，它的终态是，它的终态是含有原终态含有原终态Y的子集。的子集。o不难看出，这个不难看出，这个DFA M与与M等价。等价。现在学习的是第65页，共111页Iab0121322153344655656340123546aabbbabaababab现在学习的是第66页，共111页FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.4现在学习的是第67页，共111页3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o对于正规文法对于正规文法G和有限自动机和有限自动

43、机M，如果，如果L(G)L(M)，则称，则称G和和M是是等价等价的。关于的。关于正规文法和有限自动机的等价性，有以下正规文法和有限自动机的等价性，有以下结论：结论：现在学习的是第68页，共111页3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o定理：定理：1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正规文法或左线性正规文法G，都存在一个有限自动机都存在一个有限自动机(FA)M，使得，使得L(M)L(G)。2.对每一个对每一个FA M，都存在一个右线性正规文法，都存在一个右线性正规文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(G

44、L)。现在学习的是第69页，共111页o证明：证明：1.1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正规或左线性正规文法文法G，都构造一个有限自动机（，都构造一个有限自动机（FA）M，使得使得L(M)L(G)。(1)设右线性正规文法设右线性正规文法G=。将。将VN中中的每一非终结符号视为状态符号，并增加一的每一非终结符号视为状态符号，并增加一个新的终结状态符号个新的终结状态符号f，f VN。令令M=，其中状态转换，其中状态转换函数函数 由以下规则定义：由以下规则定义：现在学习的是第70页，共111页(a)若对某个若对某个A VN及及a VT，P中有产生中有产生式式Aa，则令，则令

45、(A,a)=f(b)对任意的对任意的A VN及及a VT，设，设P中左端中左端为为A，右端第一符号为，右端第一符号为a的所有产生式为：的所有产生式为：AaA1|aAk （不包括（不包括Aa），），则令则令(A,a)=A1,Ak。显然，上述显然，上述M是一个是一个NFA。现在学习的是第71页，共111页对于右线性正规文法对于右线性正规文法G，在，在S w的最左推导过程中的最左推导过程中:o利用利用AaB一次就相当于在一次就相当于在M中从状态中从状态A经过标记为经过标记为a的的箭弧到达状态箭弧到达状态B（包括（包括a=的情形）的情形）;o在推导的最后，利用在推导的最后，利用Aa一次则相当于在一次则

46、相当于在M中从状中从状态态A经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态f（包括（包括a=的情的情形）。形）。综上，在正规文法综上，在正规文法G中，中，S w的充要条件是：在的充要条件是：在M中，中，从状态从状态S到状态到状态f有一条通路，其上所有箭弧的标记符有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于号依次连接起来恰好等于w，这就是说，这就是说，w L(G)当当且仅当且仅当w L(M)，故，故L(G)L(M)。现在学习的是第72页，共111页(2)设左线性正规文法设左线性正规文法G=。将。将VN中的每中的每一符号视为状态符号，并增加一个初始状态符号一符号视为状态符号，

47、并增加一个初始状态符号q0，q0 VN。令令M=，其中状态转换函，其中状态转换函数数 由以下规则定义：由以下规则定义：(a)若对某个若对某个A VN及及a VT，若，若P中有产生式中有产生式Aa，则令，则令(q0,a)=A(b)对任意的对任意的A VN及及a VT，若，若P中所有右端中所有右端第一符号为第一符号为A，第二个符号为，第二个符号为a的产生式为：的产生式为：A1Aa,AkAa，则令则令(A,a)=A1,Ak。与与(1)类似，可以证明类似，可以证明L(G)L(M)。现在学习的是第73页，共111页oGR(A)：A0|0B|1DB0D|1CC0|0B|1DD0D|1Do从从GR出发构造出

48、发构造NFA M=，M的状态转换图如右图所示。的状态转换图如右图所示。o显然显然 L(M)=L(GR)。例例:ABCD100,1110f000现在学习的是第74页，共111页3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o定理：定理：1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正规文或左线性正规文法法G，都存在一个有限自动机，都存在一个有限自动机(FA)M，使，使得得L(M)L(G)。2.对每一个对每一个FA M，都存在一个右线性正规文，都存在一个右线性正规文法法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。现在学习的是第

49、75页，共111页证明证明2：对每一个：对每一个DFA M，都存在一个右线性正，都存在一个右线性正规文法规文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。设设DFA M=(1)若若s0 F，我们令，我们令GR=，其中，其中P是是由以下规则定义的产生式集合：由以下规则定义的产生式集合：对任何对任何a及及A,B S，若有，若有(A,a)=B，则：，则：(a)当当B F时，令时，令AaB，(b)当当B F时，令时，令Aa|aB。现在学习的是第76页，共111页对任何对任何w*，不妨设，不妨设w=a1ak，其中，其中ai(i=1,k)。若。若s0 w，则存在一个最

50、左推导：，则存在一个最左推导：s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因而，在因而，在M中有一条从中有一条从s0出发依次经过出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依次到达终态的通路，该通路上所有箭弧的标记依次为为a1,ak。反之亦然。所以，。反之亦然。所以，w L(GR)当且仅当且仅当当w L(M)。现在学习的是第77页，共111页q 现在考虑现在考虑s0 F的情形：的情形：因为因为(s0,)=s0，所以，所以L(M)。但。但 不属于上面构造的不属于上面构造的GR所产生的语言所产生的语言L(GR)。不难发现，。不难发现，L(GR)=L(M)-。