编译原理3.3.1- 正规式.ppt

单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,第三章 词法分析,3.1,对于词法分析器的要求,3.2,词法分析器的设计,3.3,正规表达式和自动机,3.4,词法分析器的自动产生,3.3,正规表达式和自动机,3.3.1,正规式和正规集,3.3.2,确定有限自动机,3.3.3,非确定有限自动机,3.3.4,正规文法与有限自动机的等价性,3.3.5,正规式与有限自动机的等价性,3.3.6,确定有限自动机的化简,正规语言,确定化,最小化,正规式,正规文法,自动机,3.3.1,正规式和正规集,1,、正规式的引入,2,、正规式和正规集的定义,3,、两个正规式等价的定义,4,、正规式服从的代数规律,1,、正规式的引入正则表达式，正规表达式,RE,R,egular,E,xpression,正规式,正规集,正规文法,正规语言,正规语言是,V,T,*,上的正规集,L(G),V,T,*,单词描述工具,2,、正规式和正规集的定义,设字母表为,辅助字母表,=,|,*,(,),正规式,正规集,a,a,(1),(2),:,语言的字母表,V,T,正规式,正规集,或,U|V,L(U)L(V),连接积,UV,L(U)L(V),闭包,(U)*,(L(U)*,补充,:(),(U),L(U),(3),假定,U,和,V,都是,上的正规式，,他们所表示的正规集分别为,L(U),和,L(V),(4),仅由有限次使用上述三步骤而定义的表达式才是,上的正规式，仅由这些正规式表示的字集才是,上的正规集,规定算符的优先顺序,()*|,正规式,a,a|b,ab,(,a|b)(a|b,),a*,(,a|b,)*,正规集,a,a,b,ab,aa,ab,ba,bb,a,aa,aaa,a,b,aa,ab,所有由,a,和,b,组成的串,补充例,:,令,=a,，,b,，,上的正规式和相应的正规集,例,3.1,=a,，,b,P47,ba,*,ba,*,上所有以,b,为首,后面跟任意多个,a,的符号串,a(a|b,)*,aa,b,*,上所有以,a,为首的符号串,(,a|b,)*(,aa|bb)(a|b,)*,a,b,*,aa,bba,b,*,上所有含有两个相继,a,或两个相继,b,的符号串,例,3.2,=A,B,0,1,P47,(A|B)(A|B|0|1)*,A,BA,B,0,1*,上,标识符,的全体,(0|1)(0|1)*,0,10,1*,上,数,的全体,补充例,:,=0,9,a,z,A,Z,正规式,d,=0|1|9,正规式,l,=a|,z|A,|Z,整数的集合,:,dd,*,(,dd,*,=,d,+,),标识符的集合,:,l,(,l,|,d,),*,3,、两个正规式等价的定义,若两个正规式,U,和,V,表示的正规集相同,则说,U,和,V,等价，,写作,U=V,例,a|b,b|a,b(ab,)*,(,ba,)*b,(,a|b,)*,(a*|b*)*,4,、正规式服从的代数规律,U,V,W,为正规式,U|V=V|U,U|(V|W)=(U|V)|W,(UV)W=U(VW),U(V|W)=UV|UW,，,(V|W)U=VU|WU,U,=,U,=U,P47,补充：,正规式服从的代数规律,r|r,=r,r*=,|r|rr,|,(r*)*=r*,*,=,0,1,2,n,补充例：,定义无符号数的正规式,=,d,.,e,+,d,为,09,的数字,.,表示小数点,d,*,(,.,dd,*,|,)(,e(+|,|,),dd,*,|,),2,，,12.59,，,3.6e2,，,471.88e,1,