欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    5.第三章词法分析详解优秀PPT.ppt

    • 资源ID:55123414       资源大小:590.50KB        全文页数:45页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    5.第三章词法分析详解优秀PPT.ppt

    第第3章章 词法分析词法分析词法分析词法分析(Lexical Analysis)(Lexical Analysis)词法的表示词法的表示词法分析器的设计与实现词法分析器的设计与实现2本章在编译程序中的地位本章在编译程序中的地位表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理主要教学内容主要教学内容n3.1 3.1 词法分析器的功能、输出形式和结构词法分析器的功能、输出形式和结构n3.2 3.2 词法分析程序的设计方法词法分析程序的设计方法-重点重点 n3.3 3.3 正正规规表表达达式式与与有有穷穷状状态态自自动动机机 -重重点难点点难点n3.4 3.4 词法分析器的自动产生词法分析器的自动产生 2022/10/30Ch3.词法分析34教学要求教学要求n驾驭:驾驭:n正规式、状态转换图、有限自动机的概念正规式、状态转换图、有限自动机的概念,n将将NFANFA转换为转换为DFADFA、DFADFA的化简、的化简、n正规式与有限自动机间的转换、正规式与有限自动机间的转换、n正规文法与有穷自动机间的转换,正规文法与有穷自动机间的转换,n词法分析程序的功能和设计方法。词法分析程序的功能和设计方法。n了解理解:了解理解:n词法分析器的自动产生工具词法分析器的自动产生工具LEXLEX。词法分析涉及的概念及关系词法分析涉及的概念及关系扫描识别扫描识别,依据构词规则依据构词规则源程序源程序(字符串字符串)单词符号串单词符号串词法分析程序词法分析程序(扫描器扫描器)输入输入 输出输出 输入输入,扫描扫描 (3.2)(3.2)预处理预处理,超前搜索超前搜索单词分类单词分类 (3.1)(3.1)内部表示内部表示手工生成手工生成(3.2)(3.2)自动生成自动生成(3.3)(3.3)等价等价状态转换图状态转换图用程序实现用程序实现,即扫描器即扫描器正规式正规式,正规集正规集有限自动机有限自动机 DFADFA NFA自动生成工具自动生成工具LEX,LEX,用正规式描述用正规式描述,扫描器扫描器象象FAFA一样工作一样工作(3.4)(3.4)生成生成描述描述工具工具等价等价63.1 3.1 对词法分析器的要求对词法分析器的要求3.1.1 3.1.1 词法分析器的词法分析器的功能和输出形式功能和输出形式n输入源程序,扫描识别输入源程序,扫描识别,输出单词符号输出单词符号n程序语言的单词符号一般分为五种:程序语言的单词符号一般分为五种:n关关 键键 字字(保保 留留 字字 或或 基基 本本 字字):如如 begin,end,if,then,else,while,dobegin,end,if,then,else,while,do等等 n标识符标识符:用来表示各种名字,如:用来表示各种名字,如 X1X1n字面字面常数常数:如:如 256 256,3.143.14,true,abctrue,abcn运算符运算符:如:如 、*、/等等等等n分分界符界符:如:如 逗号,分号,冒号等逗号,分号,冒号等7while ij do if ij then i:ij else j:=ji;例例词法分析器词法分析器输入输入输出输出while i j do if i j then i :=i jelse j :=j i ;3.1.1 3.1.1 词法分析(扫描)器的功能词法分析(扫描)器的功能n功能:功能:n读源程序,产生记号序列读源程序,产生记号序列n剥剥去去源源程程序序中中的的注注释释(块块、行行)和和“空空白白”符符n预处理宏处理与文件包含预处理宏处理与文件包含n单词符号的形式单词符号的形式n依据最小的语义单位设计依据最小的语义单位设计n通常表示为二元组:通常表示为二元组:n(单词符号种别,属性值(单词符号种别,属性值 )n关键关键找出符号的分割符找出符号的分割符1)单词符号的表示单词符号的表示n常用单词符号种别常用单词符号种别分类(分类(P42)n各各关关键键字字(保保留留字字、基基本本字字),各各种种运运算算符,各种分界符符,各种分界符各用一个种别码标识各用一个种别码标识n其它标识符其它标识符用一个种别码标识用一个种别码标识n常数常数用一个种别码标识用一个种别码标识n属性(值)属性(值)单词符号的值单词符号的值n常数的值,标识符的名字等常数的值,标识符的名字等n保保留留字字、运运算算符符、分分界界符符的的属属性性值值可可以以省省略略单词的机内表示单词的机内表示编译器运用二元式标识特定的标识符:编译器运用二元式标识特定的标识符:又称种别码又称种别码 单词值单词值 单词值单词值 关键字和分界符若接受一字和一符一种编码关键字和分界符若接受一字和一符一种编码时,单词值无意义;倘如一类一种编码,单词值时,单词值无意义;倘如一类一种编码,单词值可取整数的内部编码或自身的符号串表示。标识可取整数的内部编码或自身的符号串表示。标识符的单词值可取单词符号本身;常数的单词值通符的单词值可取单词符号本身;常数的单词值通常取二进制表示。常取二进制表示。2022/10/30Ch3.词法分析11n单词符号的内部表示是二元式:单词符号的内部表示是二元式:n (词词类类种种别别编编码码,单单词词符符号号自自身身的的属属性性值值)n1.1.词词类类种种别别编编码码供供应应应应语语法法分分析析程程序序运用;运用;n2.2.单单词词自自身身的的属属性性值值供供应应应应语语义义分分析析程程序运用。序运用。n3.3.具具体体的的分分类类设设计计方方法法以以便便利利语语法法分分析程序运用为原则。析程序运用为原则。单词符号的内部表示单词符号的内部表示12例子例子n考考虑虑下下述述C C语语言言代代码码段段:while while(i=j)(i=j)i-i-;经经词词法法分分析析器器处处理理后后,它它将将转转换换为为如如下下的的单单词符号序列:词符号序列:id,id,指向指向i i的符号表项的指针的符号表项的指针 =,-=,-100 i地址地址名字名字符号表符号表10如标识符单词如标识符单词 i 对对应的二元组应的二元组(6,10)133.1.2 3.1.2 词法分析器作为独立子程序词法分析器作为独立子程序n把把词词法法分分析析设设计计成成一一个个独独立立程程序序,每每当当语语法法分分析器须要一个单词符号时就调用这个子程序。析器须要一个单词符号时就调用这个子程序。n每每一一次次调调用用,词词法法分分析析器器从从源源程程序序字字符符串串中中识识别别出出一一个个单单词词符符号号,并并把把它它的的内内部部表表示示二二元元组组交给语法分析器处理。如图所示:交给语法分析器处理。如图所示:词法分词法分析器析器语法分析器语法分析器语义分析和语义分析和中间代码生成器中间代码生成器源源程程序序中中间间代代码码143.2 3.2 词法分析器的设计词法分析器的设计n3.2.1 输入、预处理输入、预处理n 处理源程序输入的技术处理源程序输入的技术n3.2.2 单词符号的识别:超前搜寻单词符号的识别:超前搜寻n 识别单词符号的技术识别单词符号的技术n3.2.3 状态转换图状态转换图n 单词符号结构的一种图形表示方法单词符号结构的一种图形表示方法n 识别单词符号的一种方法识别单词符号的一种方法n3.2.4 状态转换图的实现状态转换图的实现n 词法分析程序的一种手工构造方法词法分析程序的一种手工构造方法n 状态转换图状态转换图 词法分析程序词法分析程序153.2.1 3.2.1 输入、预处理输入、预处理n词法分析器工作的第一步是输入源程序文本。词法分析器工作的第一步是输入源程序文本。n输输入入串串一一般般放放在在一一个个输输入入缓缓冲冲区区中中。但但在在很很多多状状况况下下,可以先预处理输入串,识别工作将更便利。可以先预处理输入串,识别工作将更便利。n预预处处理理工工作作包包括括对对空空白白符符、跳跳格格符符、回回车车符符和和换换行行符符等编辑性字符的处理,及删除注解等。等编辑性字符的处理,及删除注解等。n可可以以构构造造一一个个预预处处理理子子程程序序完完成成上上面面的的工工作作。每每当当词词法法分分析析器器调调用用它它时时就就处处理理出出一一串串确确定定长长度度的的输输入入字字符符,并将其装入指定的缓冲区并将其装入指定的缓冲区-扫描缓冲区中。扫描缓冲区中。n这这样样分分析析器器就就可可以以在在扫扫描描缓缓冲冲区区中中干干脆脆进进行行单单词词符符号号的识别工作。的识别工作。P40.P40.图图3.13.1词法分析器的结构词法分析器的结构16输入、预处理:词法分析第一步输入、预处理:词法分析第一步扫描缓冲区扫描缓冲区预处理程序预处理程序预处理预处理扫描识别扫描识别输入缓冲区输入缓冲区内存内存源程序源程序文本文本外存外存读入读入词法分析程序词法分析程序扫描识别扫描识别2)相关问题)相关问题n词词法法分分析析器器可可以以作作为为一一个个独独立立的的子子程程序序,也可以作为一遍独立的扫描来支配。也可以作为一遍独立的扫描来支配。n输入缓冲区输入缓冲区 工作区工作区工作区工作区(token)(token)(token)(token)单词开始指针单词开始指针扫描指针扫描指针正拼单词正拼单词正拼单词正拼单词双缓冲区双缓冲区 并行、捻接并行、捻接并行、捻接并行、捻接每次移动向前指针都须要每次移动向前指针都须要做两次测试做两次测试2)相关问题)相关问题n n?如何设计和实现扫描器?如何设计和实现扫描器?如何设计和实现扫描器?如何设计和实现扫描器n n大小问题大小问题大小问题大小问题128Byte*2|1024Byte*2|4096Byte*2128Byte*2|1024Byte*2|4096Byte*2forward:=forward+1;if forward在缓冲区第一部分末尾 then 重装缓冲区其次部分else if forward在缓冲区其次部分末尾 then begin 重装缓冲区第一部分;将forward移到缓冲区第一部分起先 endforward:=forward+1;if forward!=eof then if forward在第一部分末尾 then 重装其次部分 else if forward在其次部分末尾 then begin 重装第一部分;将forward 移到第一部分起先 end else终止词法分析 /*eof 在表示输入结束*/2022/10/30Ch3.词法分析19n下面通过单词符号:下面通过单词符号:n关键字的识别关键字的识别n标识符的识别标识符的识别n常数的识别常数的识别n算符的识别算符的识别n界符的识别界符的识别n介介绍绍单单词词符符号号识识别别的的一一个个简简洁洁方方法法-超超前前搜搜寻寻3.2.2 3.2.2 单词符号的识别:超前搜寻单词符号的识别:超前搜寻2022/10/30Ch3.词法分析20关键字的识别关键字的识别(1)n像像FORTRAN这这样样的的语语言言,关关键键字字的的识识别甚为麻烦。因为别甚为麻烦。因为n1.关关键键字字不不加加疼疼惜惜(只只要要不不引引起起冲冲突突,用户可以用它们作为一般标识符)。用户可以用它们作为一般标识符)。n2.关关键键字字和和用用户户自自定定义义的的标标识识符符或或标标号号之间没有特殊的界符作间隔。之间没有特殊的界符作间隔。21关键字的识别关键字的识别(2)n下下面面是是几几个个FORTRAN的的正正确确语语句句,空空白白可可有有可无,不作分隔符可无,不作分隔符:1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.1 4 IF(5)=55n语语句句1和和2分分别别是是DO和和IF语语句句,它它们们都都是是以以某某关键字开头的。关键字开头的。n语语句句3和和4是是赋赋值值语语句句,它它们们都都是是以以用用户户自自定定义的标识符开头的。义的标识符开头的。22标识符、常数的识别标识符、常数的识别n标识符的识别标识符的识别 (参考参考P40,P41)n是是字字母母开开头头的的字字母母数数字字串串,后后跟跟算算符符或或界界符符,识别不困难,例如识别不困难,例如 DO99K=1.10n常数的识别常数的识别n算算术术常常数数的的识识别别:多多数数语语言言很很干干脆脆,有有的的须须接接受超前搜寻,如受超前搜寻,如FORTRAN语言中:语言中:n IF(5.EQ.M)GOTO55-5.E08n逻辑逻辑(布尔布尔)常数的识别常数的识别:比较简洁比较简洁nFORTRAN文文字字常常数数的的识识别别:麻麻烦烦,须须作作特特殊殊处理处理2022/10/30Ch3.词法分析23算符、界符的识别算符、界符的识别 (参考参考P40,P41)算符的识别算符的识别单个字符构成的算符的识别较简洁单个字符构成的算符的识别较简洁 如如 i+j多个字符构成的算符的识别须运用超前搜寻多个字符构成的算符的识别须运用超前搜寻 如如 i+界符的识别界符的识别 界符的识别比较简洁界符的识别比较简洁243.2.3 状态转换图状态转换图n状态转换图状态转换图用来:用来:n描述单词符号的结构描述单词符号的结构n识别单词符号串识别单词符号串n是设计词法分析器的工具是设计词法分析器的工具n手工生成词法分析器的方法手工生成词法分析器的方法:转换转换 实现实现词法分析程序词法分析程序构造识别单词符号的状态转换图构造识别单词符号的状态转换图2022/10/30Ch3.词法分析25状态转换图状态转换图n状状态态转转换换图图是是一一张张有有限限方方向向图图,只只包包含含有有限限个状态,即有限个结点。个状态,即有限个结点。n1.结点代表结点代表状态状态,用,用圆圈圆圈表示表示n2.终止状态终止状态用用双圈双圈表示表示n3.初始状态初始状态前标记符号前标记符号“”来表示来表示n4.状态之间用状态之间用箭弧箭弧连结连结n5.箭箭弧弧上上的的标标记记代代表表在在射射出出结结点点即即箭箭弧弧始始结结点点状状态态下下可可能能出出现现的的输输入入字字符符或或字字符符类类,箭弧标记表示箭弧标记表示状态转换的条件状态转换的条件。26状态转换图:例状态转换图:例n例例 P41.图图3.2(a)表示:表示:n在在状状态态1下下,若若输输入入字字符符为为X,则则读读进进X,并并转转换换到到状状态态2。n若若输输入入字字符符为为y,则则读读进进y,并转换到状态并转换到状态3。n若若输输入入字字符符非非x和和非非y,则则此此转换图不工作。转换图不工作。231Y YX X一个状态转换图可用于识别确定的字符串一个状态转换图可用于识别确定的字符串27状态转换图识别字符串:例状态转换图识别字符串:例1n例例1 1 P41.P41.图图3.2(b)3.2(b),识识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态,为初态,2 2为终态。为终态。n这这个个转转换换图图识识别别标标识识符符的的过过程程是是:从从初初态态0 0起起先先,若若在在状状态态0 0下下输输入入字字符符是是字字母母,则则读读进进它它,并并转转入入状状态态1 1。在在状状态态1 1之之下下,若若输输入入字字符符为为字字母母或或数数字字,则则读读进进它它,并并重重新新进进入入状状态态1 1。始始终终重重复复这这个个过过程程直直到到发发觉觉输输入入字字符符不不再再是是字字母母或数字时或数字时(这个字符已经被读进这个字符已经被读进)就进入状态就进入状态2 2。12字母或数字字母或数字0*其他其他字母字母28状态转换图识别字符串状态转换图识别字符串:例例n例例1 1 P41.P41.图图3.2(b)3.2(b),识识别别标标识识符符的的状状态态转转换换图图。其中其中0 0为初态,为初态,2 2为终态。为终态。n状状态态2 2是是终终态态,它它意意味味着着到到此此已已经经识识别别出出一一个个标标识识符符。终终态态上上打打个个*号号,表表示示多多读读进进了了一一个个不不属属于于标标识识符符部部分分的的字字符符,应应把把它它退退还还给给输输入入串串。假假如如在在状状态态0 0时时输输入入字字符符不不为为“字字母母”,则意味着这个转换图不工作。则意味着这个转换图不工作。12字母或数字字母或数字0*其他其他字母字母2022/10/30Ch3.词法分析29状态转换图识别字符串状态转换图识别字符串:例例2 2n例例2 P41.图图3.2(c)是是识识别别整整数数的的转转换换图图。其其中中0为初态,为初态,2为终态为终态,打了打了*号。号。n识别的过程类似前例。识别的过程类似前例。1 12 2数字数字0 0*其他其他数字数字30例例3 P41.图图3.2(d)是是一个一个识别识别FORTRAN实实型常数型常数的转换图。其中的转换图。其中0为初态,为初态,7为终态。为终态。状态转换图识别字符串状态转换图识别字符串:例例3 3该转换图可以识别下面该转换图可以识别下面形式的一些实形式的一些实数数:123.,.123,123E3,123.456.123E+10,123.456E-3 等等5其他其他数字数字617数字数字0*234其他其他E或或D.E或或D+或或-数字数字数字数字.数字数字数字数字数字数字单词符号编码举例单词符号编码举例单词符号单词符号种别编码种别编码内部值内部值助记符助记符DIM1$DIMIF2$IFDO3$DOSTOP4$STOPEND5$END标识符标识符6内部符号串内部符号串$IDN整数整数7标准二进制标准二进制$INT=8$ASG+9$PLUS*10$STAR*11$POWER,12$COMMA(13$SLP)14$SRP状态图letter,digitletter(IDN,入口),入口)digitdigit(其它其它)(其它其它)(NUM,值),值)(ASG,_)=*(STAR,_)s s s s*(POWER,_)其它其它IDNIDNIDNIDNletter(letter|digit)letter(letter|digit)*NUMNUMNUMNUMdigit(digit)digit(digit)*ASGASGASGASG=POWERPOWERPOWERPOWER*STARSTARSTARSTAR*空白空白2022/10/30Ch3.词法分析33 3.3 3.3 正规表达式与有限自动机正规表达式与有限自动机n为为了了更更好好地地运运用用状状态态转转换换图图构构造造词词法法分分析析器器,为为了了探探讨讨词词法法分分析析器器的的自自动动生生成成,还须要将转换图的概念形式化。还须要将转换图的概念形式化。n本本节节主主要要探探讨讨词词法法分分析析器器自自动动产产生生所所须须要要的的工工具具,引引入入:正正规规式式,正正规规集集,有有限自动机等概念。限自动机等概念。n本节是本章的重点和难点。本节是本章的重点和难点。本节内容及关系本节内容及关系单词符号结单词符号结构的描述构的描述状态转换图状态转换图词法分析器词法分析器(扫描器扫描器)用用手工实现手工实现正规表达正规表达式式E(3.3.1)用用正规集正规集L(E)(3.3.1)表示表示,值集值集正规文法正规文法G正规语言正规语言L(G)用用产生产生有限自动机有限自动机 FA M单词符号集单词符号集L(M)形式化形式化识别识别,接受接受DFA(3.3.2)最少化最少化(3.3.6)NFA(3.3.3)确定化确定化(3.3.3)三者相同三者相同等价等价等价等价(3.3.4)等价等价(3.3.5)353.3.1 正规式与正规集正规式与正规集n对对于于字字母母表表,有有符符号号串串集集合合*和和+,我我们们感感爱好的是它的一些特殊的子集,即所谓正规集。爱好的是它的一些特殊的子集,即所谓正规集。n运用正规式这个概念来描述正规集。运用正规式这个概念来描述正规集。n例如例如,=a,b,c,z,0,1,2,9n *=全部字母数字串全部字母数字串n 我们对如下子集感爱好我们对如下子集感爱好:n 字母开头的字母数字串字母开头的字母数字串=标识符集合标识符集合正规式表示正规式表示:l(l|d)l(l|d)*一个正规集一个正规集即一个正规语言即一个正规语言36正规式与正规集的递归定义正规式与正规集的递归定义(P4647)n(1)和和都都是是 上上的的正正规规式式,它它们们所所表表示示的的正正规规集集分别为分别为 和和;n(2)任任何何a,a是是上上的的一一个个正正规规式式,它它所所表表示示的的正正规集为规集为a;n(3)假假定定U和和V都都是是上上的的正正规规式式,它它们们所所表表示示的的正正规规集集分分别别记记为为L(U)和和L(V),那那么么,U|V、U.V和和U*也也都都是是正正规规式式,它它们们所所表表示示的的正正规规集集分分别别为为L(U)L(V)、L(U)L(V)(连接积连接积)和和(L(U)*(闭包闭包)n仅仅由由有有限限次次运运用用上上述述三三步步骤骤而而得得到到的的表表达达式式才才是是上上的的正正规规式式。仅仅由由这这些些正正规规式式所所表表示示的的字字集集才才是是上的正规集,正规集也称为正规语言。上的正规集,正规集也称为正规语言。37正规式定义正规式定义 正规表达式正规表达式 正规表达式对应的正规集正规表达式对应的正规集 1.,2.a a 3.若若 r,s L(r),L(s)则则 选择选择 r s L(r)L(s)连接连接 r.s L(r).L(s)闭包闭包 r*(L(r)*(r)L(r)运算优先级由高到低依次是运算优先级由高到低依次是:闭包闭包*、连接、连接.、选择、选择|,括号最优先。注:有的书还引入了正则闭包,括号最优先。注:有的书还引入了正则闭包,r+表表示示r作至少一次的随意有限次连接。作至少一次的随意有限次连接。2022/10/30Ch3.词法分析38正规式与正规集正规式与正规集:例例1例例1:=A,B,Z,a,b,z,0,1,9 正规式:正规式:A B .Z 正规集:正规集:L(A)L(B)L(Z)=A,B,Z 正规式:正规式:0123456789 正规集:正规集:L(0)L(1).L(9)=0123456789 若若 l A,B,Z,a,b,z,d 0,1,9 正规式:正规式:l(l|d)*正规集:正规集:标识符标识符39正规式与正规集正规式与正规集:例例2n例例2:设设 =a,b,则则正规式和正规集正规式和正规集:a b a,b (a b)(a b)aa,ab,ba,bb a*,a,aa,aaa,aaaa,=an|n0 (a b)*,a,b,aa,ab,ba,bb,aaa,.=a,b*a ab*a,ab,abb,abbb,abbbb,.=abn|n0问:正规式问:正规式 b(a|b)*a 表示的正规集是表示的正规集是?40正规式与正规集正规式与正规集:例例3.1n通通过过这这一一节节的的学学习习,要要求求能能依依据据给给出出的的简简洁洁正规式,会写出其表示的正规集。正规式,会写出其表示的正规集。n例例3.1 令令=a,b,其正规式和正规集如下:其正规式和正规集如下:n 正规式正规式 正规集正规集n 1.ba*上上全全部部以以b为为首首后后跟跟着着n 随意多个随意多个a的字。的字。n 2.a(a|b)*上全部以上全部以a为首的字。为首的字。n 3.(a|b)*(aa|bb)(a|b)*上上全全部部含含有有两两n 个相继的个相继的a或两个相继的或两个相继的b 的字。的字。41正规式与正规集正规式与正规集:例例3.2n例例3.2:令令=A,B,0,1,则:则:正规式正规式 正规集正规集1.(A|B)(A|B|0|1)*上上的的“标标识识符符”的的全全体体 =A,B.A,B,0,1*2.(0|1)(0|1)*上上“数数”的全体的全体 =0,1.0,1*问问:正正规规式式,0,110,0|1,1*表表示示的的正正规规集是集是?答答:正规集分别是正规集分别是,0,110,0,1,1,11,111,=1*=1n|n0。42正规式的等价正规式的等价n若若两两个个正正规规式式U和和V所所表表示示的的正正规规集集相相同同,即即L(U)=L(V),则认为二者,则认为二者等价等价,记为记为U=V。n例例1:b(ab)*=(ba)*b 因为因为:b(ab)*和和(ba)*b表示的正规集分别是表示的正规集分别是:bab*ba*b =b,ab,abab,=,ba,baba,b =b,bab,babab,=b,bab,babab,n例例2:00*=0*00*0*正规集为正规集为 0n|n1n例例3:(a|b)*=(a*b*)*正规集为正规集为,a,b,aa,bb,ab,ba,bb,aaa,43正规表达式的代数性质正规表达式的代数性质n注注:上述恒等式都表示两个正规式上述恒等式都表示两个正规式等价等价。n证明两个正规式等价证明两个正规式等价:U=V L(U)=L(V)恒等式恒等式说明说明r|s=s|r“|”是可交换的是可交换的(r|s)|t=r|(s|t)“|”是可结合的是可结合的(rs)t=r(st)连接是可结合的连接是可结合的r(s|t)=rs|rt,(s|t)r=sr|tr分配律分配律r=r,r=r 是连接的单位元素是连接的单位元素r*=(r|)*“*”和和之间的关系之间的关系r*=r*“*”是幂等的是幂等的44正规式等价的证明正规式等价的证明n例例1.证明证明(V|W)U=VU|WU L(V|W)U)=L(V|W)L(U)=(L(V)L(W)L(U)=L(V)L(U)L(W)L(U)=L(VU)L(WU)=L(VU|WU)n例例2.证明证明 A*=|AA*L(|AA*)=L()L(A)L(A*)=L()L(A)(L(A)*=L()L(A)(L(A)0(L(A)1(L(A)2)=L()(L(A)1(L(A)2(L(A)3 =(L(A)*=L(A*)45写正规表达式写正规表达式:例例 给出下列在字母表给出下列在字母表0,10,1上的正规集的正规式上的正规集的正规式1.1.全部以全部以0000结束的串的集合。结束的串的集合。解解:(0|1)*00:(0|1)*00n方法:方法:分析符号串的结构分析符号串的结构,试着写出正规式试着写出正规式,验证是否能表示正规集验证是否能表示正规集,不断调整直到正确。不断调整直到正确。n2.2.全部具有三个全部具有三个0 0的串的集合。的串的集合。n 解解:1*01*01*01*:1*01*01*01*

    注意事项

    本文(5.第三章词法分析详解优秀PPT.ppt)为本站会员(1398****507)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开