《09--第三章有限自动机与词法分析器.ppt》由会员分享，可在线阅读，更多相关《09--第三章有限自动机与词法分析器.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章 有穷自动有穷自动机与词法分析器机与词法分析器任课教师任课教师王养廷王养廷1 正则表达式正则表达式n基本概念基本概念字母表：它是非空有限集合，其中的字母表：它是非空有限集合，其中的元素称为字母（或符号），一般使用元素称为字母（或符号），一般使用表示。表示。例如：例如：=a,b,c,.,z符号串：符号的有限序列符号串：符号的有限序列例如：例如：a,ab,cda、表示空串表示空串区分区分和和1 正则表达式（续）正则表达式（续）符号串长度：符号串中包含符号符号串长度：符号串中包含符号的个数，使用的个数，使用|表示符号串表示符号串的长的长度度例如：例如：|a|=1,|abc|=3,|=0符
2、号串的连接：符号串的连接：、是符号串，是符号串，为符号串为符号串和和的连接的连接例如：例如：=aa,=bb,=aabb =1 正则表达式（续）正则表达式（续）符号串的乘积：符号串的乘积：A、B是符号串的集合，则是符号串的集合，则AB定义为符号串定义为符号串A和和B的乘积。的乘积。AB=|A,B，若，若为空集，则为空集，则A=A=A。例如：例如：A=ab,cd,B=12,34，则，则AB=ab12,ab34,cd12,cd34符号串集合的方幂：设符号串集合的方幂：设A是是符号串的集合，符号串的集合，则称则称Ai为符号串的方幂为符号串的方幂A0=A1=AAk=AA.A(k个个)1 正则表达式（续）
3、正则表达式（续）符号串的正闭包：设符号串的正闭包：设A是符号串的集合，则是符号串的集合，则称称A+是是符号串的正闭包符号串的正闭包A+=A1 A2 A3.例如：例如：A=a,A+=a,aa,aaa,.符号串的星闭包：设符号串的星闭包：设A是符号串的集合，则是符号串的集合，则称称A*是符号串的星闭包是符号串的星闭包A+=A0 A+例如：例如：A=a,A*=,a,aa,aaa,.问题问题A=a,b，A的正闭包和星闭包是什么的正闭包和星闭包是什么1 正则表达式（续）正则表达式（续）n正则符号串集：用正则符号串集：用RSS表示，定义为：表示，定义为：字母表字母表的任何子集的任何子集空集空集 若若A A
4、、B B是是RSS,RSS,则则ABAB是是RSSRSS若若A A、B B是是RSS,RSS,则则ABAB是是RSSRSS若若A A、B B是是RSS,RSS,则则A A*是是RSSRSS1 正则表达式（续）正则表达式（续）n正则表达式正则表达式设设是给定字符集，则每个是给定字符集，则每个上的正则表达式将定义上的正则表达式将定义上的一个字符串集。若用上的一个字符串集。若用RE表示表示的正则表达式，的正则表达式，则用则用L(RE)表示表示RE所表示的正则集，则所表示的正则集，则RE的定义的定义及含义如下：及含义如下：是正则表达式，即是正则表达式，即 R E，其中，其中L()=是正则表达式，即是正
5、则表达式，即 R E，其中，其中L()=aa是正则表达式，即是正则表达式，即 a RE，其中其中L(a)=a设设A和和B是正则表达式，即是正则表达式，即A RE，B RE,则有则有(A)R E，L(A)=L(A)A|B R E，L(A|B)=L(A)|L(B)AB R E，L(AB)=L(A)L(B)A*R E，L(A*)=L(A)*1 正则表达式（续）正则表达式（续）算符优先级算符优先级幂运算幂运算 连接连接 选择选择a*b|c=(a*)b)|c扩充扩充REA+R E，L(A+)=L(A)+A?R E，L(A?)=L(A)chchi i-chchk k R E 表示（表示（chchi i|c
6、hchi+1i+1|chchk k）abc R E 表示（表示（a|b|c）chchi i-chchk k chchj j-ch-chl l表示表示chchi i-chchk k|chchj j-ch-chl l正则表达式（续）正则表达式（续）正则表达式的性质：正则表达式的性质：P48A|B=B|A|的可交换性的可交换性A|(B|C)=(A|B)|C|的可结合性的可结合性A(BC)=(AB)C 连接的可结合性连接的可结合性A(B|C)=AB|AC 连接的可分配性连接的可分配性(A|B)C=AC|BC 连接的可分配性连接的可分配性A*=A*幂的等价性幂的等价性正则表达式（续）正则表达式（续）正则表达式示例正则表达式示例假设：假设：D=0,1,9,L=az,AZD+D+.D+L(D|L)举例举例(a|bc)*d)+(0|1)*(2|3)+)|0011正则表达式（续）正则表达式（续）n实例实例aa|baba*a*b*(a|b)*(ab)*a+a(b|c)a+(b|c)a*(a|b)(a|c)(a|b)c*总结总结n主要内容主要内容正则表达式正则表达式正则表达式到有穷自动机的转换正则表达式到有穷自动机的转换n作业作业P61 2(3,4,5),3(3,4,5),4(2)