《编译原理第三章词法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《编译原理第三章词法分析精选PPT.ppt（111页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 VN N=nS
3、 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+i)E(E)(E+E)(E+
6、i)(E*E+i)(E*i+i)(i*i+i)第8页，此课件共111页哦复习：复习：程序语言的语法描述程序语言的语法描述 o定义：如果一个文法存在某个句子对应两颗定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个不同的语法树，则说这个文法是二义的文法是二义的。o语言的二义性：一个语言的二义性：一个语言是二义性的语言是二义性的，如果，如果对它不存在无二义性的文法。对它不存在无二义性的文法。第9页，此课件共111页哦复习：复习：程序语言的语法描述程序语言的语法描述 o形式语言鸟瞰形式语言鸟瞰0型型(短语文法，图灵机短语文法，图灵机)：产生式形如：产生式形如：其中：其中：(VT VN)*且
7、至少含有一个非终结符；且至少含有一个非终结符；(VT VN)*1型型(上下文有关文法，线性界限自动机上下文有关文法，线性界限自动机)：产生式形如：产生式形如：其中：其中：|，仅，仅 S 例外。例外。第10页，此课件共111页哦复习：复习：程序语言的语法描述程序语言的语法描述 o形式语言鸟瞰形式语言鸟瞰2型型(上下文无关文法，非确定下推自动机上下文无关文法，非确定下推自动机)：产生式形如：产生式形如：A 其中：其中：A VN；(VT VN)*。3型型(正规文法，有限自动机正规文法，有限自动机)：产生式形如：产生式形如：A B 或或 A 其中：其中：VT*；A，B VN 产生式形如：产生式形如：A
8、 B 或或 A 其中：其中：VT*；A，B VN第11页，此课件共111页哦第三章第三章 词法分析词法分析o词法分析是编译的第一个阶段，在单词的词法分析是编译的第一个阶段，在单词的级别上分析和翻译源程序。级别上分析和翻译源程序。o理论基础：理论基础：n有限自动机理论；有限自动机理论；n有限自动机理论与正规文法、正规式之间在有限自动机理论与正规文法、正规式之间在描述语言方面有一一对应的关系。描述语言方面有一一对应的关系。o学习目标：学习目标：n掌握有限自动机与正规文法、正规式之间的掌握有限自动机与正规文法、正规式之间的转换转换n能够构造词法分析程序。能够构造词法分析程序。第12页，此课件共111
9、页哦第三章第三章 词法分析词法分析o词法分析的任务：从左至右逐个字符地对词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。源程序进行扫描，产生一个个单词符号。o词法分析器词法分析器(Lexical Analyzer)又称扫描器又称扫描器(Scanner)：执行词法分析的程序：执行词法分析的程序第13页，此课件共111页哦3.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式一、词法分析器的功能和输出形式o功能功能:输入源程序、输出单词符号输入源程序、输出单词符号o单词符号的种类：单词符号的种类：n基本字基本字：如：如 beginbegin，r
10、epeatrepeat，n标识符标识符表示各种名字：如变量名、数表示各种名字：如变量名、数组名和过程名组名和过程名n常数常数：各种类型的常数：各种类型的常数n运算符运算符：+，-，*，/，n界符界符：逗号、分号、括号和空白：逗号、分号、括号和空白第14页，此课件共111页哦o输出的单词符号的表示形式输出的单词符号的表示形式:(单词种别单词种别，单词自身的值单词自身的值)o单词种别通常用整数编码表示。单词种别通常用整数编码表示。n若一个种别只有一个单词符号，则种别编码若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和就代表该单词符号。假定基本字、运算符和界符都是一符一种
11、。界符都是一符一种。n若一个种别有多个单词符号，则对于每个单词若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。符号，给出种别编码和自身的值。o标识符单列一种；标识符自身的值表示成按机器标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。字节划分的内部码。o常数按类型分种；常数的值则表示成标准的常数按类型分种；常数的值则表示成标准的二进制形式。二进制形式。第15页，此课件共111页哦例例 C程序程序o while(i=j)i-;o输出单词符号：输出单词符号：=,-第16页，此课件共111页哦例例 FORTRAN程序程序oIF(5.EQ.M)GOTO 100IF(5.
12、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词法分析是作为一个独立的阶段，是否应词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？当将其处理为一遍呢？n作为独立阶段的优点：结构简洁、清晰
13、和作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝条理化，有利于集中考虑词法分析一些枝节问题。节问题。n不作为一遍：将其处理为一个子程序。不作为一遍：将其处理为一个子程序。第18页，此课件共111页哦词法分析器词法分析器词法分词法分析器析器语法分语法分析器析器符号表符号表源程序源程序单词符号单词符号取下一单词取下一单词.第19页，此课件共111页哦词法分析器的结构词法分析器的结构预处理预处理子程序子程序扫描器扫描器输入缓冲区输入缓冲区扫描缓冲区扫描缓冲区单词符号单词符号输入输入列表列表3.2 词法分析器的设计词法分析器的设计第20页，此课件共111页哦o输入串放在输入缓
14、冲区中。输入串放在输入缓冲区中。o预预处处理理子子程程序序：剔剔除除无无用用的的空空白白、跳跳格格、回回车车和和换换行行等等编编辑辑性性字字符符;区区分分标标号号区区、捻接续行和给出句末符等捻接续行和给出句末符等o扫描缓冲区扫描缓冲区 起点起点 搜索搜索指示器指示器 指示器指示器一、输入、预处理一、输入、预处理第21页，此课件共111页哦 WhatALongWord WhatALongWo rdrd WhatALongWord WhatALongWo第22页，此课件共111页哦二、单词符号的识别二、单词符号的识别:超前搜索超前搜索1 基本字识别基本字识别:例如例如:DO99K=1，10 DO
15、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 算符和界符的识别算符和界符的识别o把多个字符符合而成的算符和界符拼合成一把多个字符符合而成的算符和界符拼合成一
16、个单一单词符号。个单一单词符号。:=，*，.EQ.，+，-，=第24页，此课件共111页哦三、状态转换图三、状态转换图1 1 概念概念o状态转换图是一张有限方向图。状态转换图是一张有限方向图。213XYn结点代表状态，用圆圈表示。结点代表状态，用圆圈表示。o状态之间用箭弧连结，箭弧上状态之间用箭弧连结，箭弧上的标记的标记(字符字符)代表射出结状态代表射出结状态下可能出现的输入字符或字符下可能出现的输入字符或字符类。类。o一张转换图只包含有限个状态，其中有一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。一个为初态，至少要有一个终态。第25页，此课件共111页哦识别标识符的状态转换
17、图识别标识符的状态转换图123字母字母其他其他字母或数字字母或数字*识别识别整常数整常数的状态转换图的状态转换图123数字数字其他其他数字数字*o一个状态转换图可用于识别一个状态转换图可用于识别(或接受或接受)一定的一定的字符串。字符串。第26页，此课件共111页哦2 2 例子例子o助忆符助忆符：直接用编码表示不便于记忆，因此用：直接用编码表示不便于记忆，因此用助忆符来表示编码。助忆符来表示编码。第27页，此课件共111页哦第28页，此课件共111页哦1 12 23 34 45 56 67 78 89 910101111121213130 0空白空白字母字母字母或数字字母或数字非字母与数字非字
18、母与数字数字数字非数字非数字数字数字=+*非非*,()其它其它*第29页，此课件共111页哦o几点重要限制几点重要限制不必使用超前搜索不必使用超前搜索n所所有有基基本本字字都都是是保保留留字字;用用户户不不能能用用它它们们作作自自己的标识符己的标识符n基基本本字字作作为为特特殊殊的的标标识识符符来来处处理理;不不用用特特殊殊的的状态图来识别，只要查保留字表。状态图来识别，只要查保留字表。n如如果果基基本本字字、标标识识符符和和常常数数(或或标标号号)之之间间没没有有确确定定的的运运算算符符或或界界符符作作间间隔隔，则则必必须须使使用用一个空白符作间隔。一个空白符作间隔。DO99K=1，10 要
19、写成要写成 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的对应程序段的对应程序段;else if(ch=/)状态状态l的对应程序段的对应程序段;else 错误处理错误处理;ijkl字母字母
20、数字数字第31页，此课件共111页哦3 状态转换图的实现状态转换图的实现2)2)对含回路的状态结，可对应一段由对含回路的状态结，可对应一段由WHILEWHILE结构结构和和IFIF语句构成的程序语句构成的程序.i字母或数字字母或数字其它其它jGetChar();while(IsLetter()or IsDigit()GetChar();状态状态j的对应程序段的对应程序段第32页，此课件共111页哦3 状态转换图的实现状态转换图的实现3)终态结表示识别出某种单词符号，因此，对应终态结表示识别出某种单词符号，因此，对应语句为语句为 RETURN(C，VAL)其中，其中，C为单词种别，为单词种别，V
21、AL为单词自身值为单词自身值.第33页，此课件共111页哦o全局变量与过程全局变量与过程1)ch 字符变量、存放最新读入的源程序字符字符变量、存放最新读入的源程序字符2)strToken 字符数组，存放构成单词符号字符数组，存放构成单词符号的字符串的字符串3)GetChar 子程序过程，把下一个字符读入子程序过程，把下一个字符读入到到 ch 中中4)GetBC 子程序过程，跳过空白符，直至子程序过程，跳过空白符，直至 ch 中读入一非空白符中读入一非空白符5)Concat 子程序，把子程序，把ch中的字符连接到中的字符连接到 strToken 第34页，此课件共111页哦6)IsLetter和
22、和 IsDisgital 布尔函数，判布尔函数，判断断ch中字符是否为字母中字符是否为字母和数字和数字7)Reserve 整型函数，对于整型函数，对于 strToken 中中的字符串查找保留字表，若它的字符串查找保留字表，若它是保留字则给是保留字则给出它的编码，否则回送出它的编码，否则回送08)Retract 子程序，把搜索指针回调一个子程序，把搜索指针回调一个字符位置字符位置9)InsertId 整型函数，将整型函数，将strToken中的中的标识符插入符号表，返回符号表指针标识符插入符号表，返回符号表指针10)InsertConst 整型函数过程，将整型函数过程，将strToken中的常数
23、插入常数表，返回常数中的常数插入常数表，返回常数表指针。表指针。第35页，此课件共111页哦int code,value;strToken:=“”;/*置置strToken为空串为空串*/GetChar();GetBC();if(IsLetter()beginwhile(IsLetter()or IsDigit()beginConcat();GetChar();endRetract();code:=Reserve();if(code=0)beginvalue:=InsertId(strToken);return($ID,value);endelsereturn(code,-);end第36页，
24、此课件共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=*)beginGetChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);endelse if(ch=
25、;)return($SEMICOLON,-);else if(ch=()return($LPAR,-);else if(ch=)return($RPAR,-);else ProcError();/*错误处理错误处理*/第38页，此课件共111页哦3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机o几个概念几个概念:n考虑一个考虑一个有穷有穷 字母表字母表 字符集字符集n其中每一个元素称为一个其中每一个元素称为一个字符字符n上的上的字字(也叫也叫字符串字符串)是指由是指由中的字符中的字符所构成的一个有穷序列所构成的一个有穷序列n不包含任何字符的序列称为不包含任何字符的序列称为空字空字，
26、记为，记为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的正规闭包。的正规闭包。第40页，此课件共111页哦3.3.1 正规式和正规集正规式和正规集o正正规规集集可可以以用用正正规规表表达达式式（简简称称正正规规式式）表示。表示。o正正规规表表达
27、达式式是是表表示示正正规规集集一一种种方方法法。一一个个字字集集合合是是正正规规集集当当且且仅仅当当它它能能用用正正规规式式表表示。示。第41页，此课件共111页哦o正规式和正规集的递归定义：正规式和正规集的递归定义：对给定的字母表对给定的字母表 1)和和都是都是 上的正规式，它们所表示的正上的正规式，它们所表示的正规集为规集为 和和;2)任何任何a ，a是是 上的正规式，它所表示的上的正规式，它所表示的正规集为正规集为a;第42页，此课件共111页哦3)假定假定e e1 1和和e2都是都是 上的正规式，它们所表示的上的正规式，它们所表示的正规集为正规集为L(e1)和和L(e2)，则，则i)(
28、e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才使用上述三步骤而定义的表达式才是是 上的正规式，仅由这些正规式表示的字上的正规式，仅由这些正规式表示的字集才是集才是 上的正规集。上的正规集。第43页，此课件共111页哦o所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。o若若两两个个正正规规式式所
29、所表表示示的的正正规规集集相相同同，则则称称这这两个正规式等价。如两个正规式等价。如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*=b ,ab,abab,ababab,=b,bab,babab,bababab,L(b(ab)*)=L(ba)*b)b(ab)*=(ba)*b第44页，此课件共111页哦o
30、对正规式，下列等价成立：对正规式，下列等价成立：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)第45页，此课件共111页哦正规集正规集正规式正规式3.3.1第46页，此课件共111页哦3.3.2 确定有限自动机确定有限自动机(DFA)o对状态图进行形式化，则可以下定义：对状态
31、图进行形式化，则可以下定义：自动机自动机M是一个五元式是一个五元式M=(S,f,S0,F),其中：其中：1.S:有穷状态集，有穷状态集，2.：输入字母表：输入字母表(有穷有穷)，3.f:状状态态转转换换函函数数，为为SS的的单单值值部部分分映映射射，f(s，a)=s表表示示：当当现现行行状状态态为为s，输输入入字字符符为为a时时，将将状状态态转转换换到到下下一一状状态态s。我我们们把把s称称为为s的一个后继状态。的一个后继状态。4.S0 S是唯一的一个初态；是唯一的一个初态；5 F S：终态集：终态集(可空可空)。第47页，此课件共111页哦o例如：例如：DFA M=(0，1，2，3，a，b，
32、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个个输输入入字字符符，那那么么，这这个个图图含含有有m个个状状态态结结点点，每每个个结结点点顶顶多多含含有有n条条箭箭弧弧射射出出，且且每每条条箭箭弧弧用用上上的的不不同同的的输输入入字符来作标记。字符来作标记。第49页，此课件
33、共111页哦o对对于于*中中的的任任何何字字，若若存存在在一一条条从从初初态态到到某某一一终终态态的的道道路路，且且这这条条路路上上所所有有弧弧上上的的标标记记符符连连接接成成的的字字等等于于，则则称称 为为DFA M所所识别识别(接收接收)oDFA M所识别的字的全体记为所识别的字的全体记为L(M)。o可可以以证证明明：上上的的字字集集V V*是是正正规规集集，当当且且仅当存在上的仅当存在上的DFA M，使得，使得VL(M)。第50页，此课件共111页哦3.3.3 3.3.3 非确定有限自动机非确定有限自动机(NFA)o定定义义：一一个个非非确确定定有有限限自自动动机机(NFA)M是是一一个
34、五元式个五元式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 和和DFA的区别：的区别：1 弧弧上上的的标标记记可可以以是是*中中的的一一个个字字，而而不不一一定是单个字符；定是单个字符；2 同同一一个个字字可可能能出出现现在在同同状状态态射射出出的的多多条条弧弧
35、上。上。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自动机理论中一个重要的结论：判定两个自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。自动机等价性的算法是存在的。o对于每个对于每个NFA M存在一个存在一个DFA M，使得，使得 L(M)=L(M)。亦即。亦即DFA与与N
36、FA描述能力相描述能力相同。同。第54页，此课件共111页哦1.假定假定NFA M=，我们对，我们对M的状的状态转换图进行以下改造：态转换图进行以下改造：1)引进新的初态结点引进新的初态结点X和终态结点和终态结点Y，X,Y S，从从X到到S0中任意状态结点连一条中任意状态结点连一条 箭弧，箭弧，从从F中任意状态结点连一条中任意状态结点连一条 箭弧到箭弧到Y。2)对对M的状态转换图进一步施行替换，其中的状态转换图进一步施行替换，其中k是是新引入的状态。新引入的状态。证明证明:第55页，此课件共111页哦代之为代之为ikABjijAB代之为代之为ijA|BijBA代之为代之为ijA*ik jA按下
37、面的三条规则对按下面的三条规则对V进行分裂进行分裂:第56页，此课件共111页哦o逐步把这个图转变为每条弧只标记为逐步把这个图转变为每条弧只标记为 上的一上的一个字符或个字符或，最后得到一个，最后得到一个NFA M，显然，显然L(M)=L(M)第57页，此课件共111页哦o识别所有含相继两个识别所有含相继两个a或相继两个或相继两个b的字的字XY 514236ab ababab5126ab abaabb第58页，此课件共111页哦2.把上述把上述NFA确定化确定化采用子集法采用子集法.设设I是的状态集的一个子集，定义是的状态集的一个子集，定义I的的-闭包闭包-closure(I)为为:i)若若s
38、 I，则，则s-closure(I)；ii)若若s I，则从则从s出发经过任意条出发经过任意条 弧而能到达弧而能到达的任何状态的任何状态s都属于都属于-closure(I)即即 -closure(I)=I s|从某个从某个s I出发经过任意条出发经过任意条 弧能到达弧能到达s第59页，此课件共111页哦o设设a是是 中的一个字符，定义中的一个字符，定义Ia=-closure(J)其中，其中，J为为I中的某个状态出发经过一条中的某个状态出发经过一条a弧而弧而到达的状态集合。到达的状态集合。第60页，此课件共111页哦o-closure(1)=1，2=I J=5，4，3 Ia=-closure(J
39、)=-closure(5，4，3)=5，4，3，6，2，7，861a 234578aa o设设a是是 中的一个字中的一个字符，定义符，定义Ia=-closure(J)其中，其中，J为为I中的某个中的某个状态出发经过一条状态出发经过一条a弧而到达的状态弧而到达的状态集合。集合。第61页，此课件共111页哦o把确定化的过程把确定化的过程:不失一般性，设字母表只包含两个不失一般性，设字母表只包含两个a a和和b b，我们构造一张表我们构造一张表:第62页，此课件共111页哦首先，置第首先，置第1行第行第1列为列为-closure(X)求出这一列求出这一列的的Ia，Ib；然后，检查这两个然后，检查这两
40、个Ia，Ib，看它们是否已在表中，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空的第一列中出现，把未曾出现的填入后面的空行的第行的第1列上，求出每行第列上，求出每行第2，3列上的集合列上的集合.重复上述过程，直到所有第重复上述过程，直到所有第2，3列子集全部列子集全部出现在第一列为止。出现在第一列为止。第63页，此课件共111页哦IIaIbX,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,
41、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这张表唯一刻划了一个确定的有限自动机这张表唯一刻划了一个确定的有限自动机M，它的初态是，它的初态是-closure(X)，它的终态是，它的终态是含有原终态含有原终态Y的子集。的子集。o不难看出，这个不难看出，这个DFA M与与M等价。等价。第65页，此课件共111页哦Iab01213221533
42、44655656340123546aabbbabaababab第66页，此课件共111页哦FA正规集正规集正规式正规式DFANFA正规文法正规文法3.3.13.3.23.3.33.3.4第67页，此课件共111页哦3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o对于正规文法对于正规文法G和有限自动机和有限自动机M，如果，如果L(G)L(M)，则称，则称G和和M是是等价等价的。关于的。关于正规文法和有限自动机的等价性，有以下正规文法和有限自动机的等价性，有以下结论：结论：第68页，此课件共111页哦3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o定理：
43、定理：1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正规文法或左线性正规文法G，都存在一个有限自动机都存在一个有限自动机(FA)M，使得，使得L(M)L(G)。2.对每一个对每一个FA M，都存在一个右线性正规文法，都存在一个右线性正规文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。第69页，此课件共111页哦o证明：证明：1.1.对每一个右线性正规文法对每一个右线性正规文法G或左线性正规或左线性正规文法文法G，都构造一个有限自动机（，都构造一个有限自动机（FA）M，使得使得L(M)L(G)。(1)设右线性正规文法设右线性正规文法G=。将。将V
44、N中中的每一非终结符号视为状态符号，并增加一个的每一非终结符号视为状态符号，并增加一个新的终结状态符号新的终结状态符号f，f VN。令令M=，其中状态转换，其中状态转换函数函数 由以下规则定义：由以下规则定义：第70页，此课件共111页哦(a)若对某个若对某个A VN及及a VT，P中有产生中有产生式式Aa，则令，则令(A,a)=f(b)对任意的对任意的A VN及及a VT，设，设P中左中左端为端为A，右端第一符号为，右端第一符号为a的所有产生式为：的所有产生式为：AaA1|aAk （不包括（不包括Aa），），则令则令(A,a)=A1,Ak。显然，上述显然，上述M是一个是一个NFA。第71页，
45、此课件共111页哦对于右线性正规文法对于右线性正规文法G，在，在S w的最左推导过程中的最左推导过程中:o利用利用AaB一次就相当于在一次就相当于在M中从状态中从状态A经过标记为经过标记为a的箭弧到达状态的箭弧到达状态B（包括（包括a=的情形）的情形）;o在推导的最后，利用在推导的最后，利用Aa一次则相当于在一次则相当于在M中从状态中从状态A经过标记为经过标记为a的箭弧到达终结状态的箭弧到达终结状态f（包括（包括a=的情形）。的情形）。综上，在正规文法综上，在正规文法G中，中，S w的充要条件是：在的充要条件是：在M中，从状态中，从状态S到状态到状态f有一条通路，其上所有箭弧的标有一条通路，其
46、上所有箭弧的标记符号依次连接起来恰好等于记符号依次连接起来恰好等于w，这就是说，这就是说，w L(G)当且仅当当且仅当w L(M)，故，故L(G)L(M)。第72页，此课件共111页哦(2)设左线性正规文法设左线性正规文法G=。将。将VN中的每中的每一符号视为状态符号，并增加一个初始状态符号一符号视为状态符号，并增加一个初始状态符号q0，q0 VN。令令M=，其中状态转换函，其中状态转换函数数 由以下规则定义：由以下规则定义：(a)若对某个若对某个A VN及及a VT，若，若P中有产生式中有产生式Aa，则令，则令(q0,a)=A(b)对任意的对任意的A VN及及a VT，若，若P中所有右端第中
47、所有右端第一符号为一符号为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出发构造出发构造NFA M=，M的状态转换图如右图的状态转换图如右图所示。所示。o显然显然 L(M)=L(GR)。例例:ABCD100,1110f000第74页，此课件共111页哦3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性o定理：定理：1.对每一个右线性正规文法对每一个右线性
48、正规文法G或左线性正规文或左线性正规文法法G，都存在一个有限自动机，都存在一个有限自动机(FA)M，使，使得得L(M)L(G)。2.对每一个对每一个FA M，都存在一个右线性正规文，都存在一个右线性正规文法法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。第75页，此课件共111页哦证明证明2：对每一个：对每一个DFA M，都存在一个右线性正，都存在一个右线性正规文法规文法GR和左线性正规文法和左线性正规文法GL，使得，使得L(M)L(GR)L(GL)。设设DFA M=(1)若若s0 F，我们令，我们令GR=，其中，其中P是是由以下规则定义的产生式集合：由以下
49、规则定义的产生式集合：对任何对任何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，则存在一个最左推导：，则存在一个最左推导：s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因而，在因而，在M中有一条从中有一条从s0出发依次经过出发依次经过A1，Ak-1到达终态的通路，该通路上所有箭弧的标记依到达终态的通路，该通路上所有箭弧的标记依次为次为a1,ak。反之亦然。所以，。反之亦然。所
50、以，w L(GR)当且仅当且仅当当w L(M)。第77页，此课件共111页哦q 现在考虑现在考虑s0 F的情形：的情形：因为因为(s0,)=s0，所以，所以L(M)。但。但 不属于上面构造的不属于上面构造的GR所产生的语言所产生的语言L(GR)。不难发现，。不难发现，L(GR)=L(M)-。所以，我们在上述所以，我们在上述GR中添加新的非终结符号中添加新的非终结符号s0，(s0S)和产生式和产生式s0s0|，并用，并用s0 代替代替s0作开始符号。这样修正作开始符号。这样修正GR后得到的文法后得到的文法GR 仍是右线性正规文法，并且仍是右线性正规文法，并且L(GR)=L(M)。(2)类似于类似