编译原理3.3.1-正规式.ppt

《编译原理3.3.1-正规式.ppt》由会员分享，可在线阅读，更多相关《编译原理3.3.1-正规式.ppt（17页珍藏版）》请在三一办公上搜索。

1、第三章 词法分析,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、正规式的引入正则表达式，正规表达式,RERegular Expression

2、,正规语言是VT*上的正规集,L(G)VT*,单词描述工具,2、正规式和正规集的定义,设字母表为,辅助字母表=|*(),(1),(2),:语言的字母表 VT,(3)假定U和V都是上的正规式，他们所表示的正规集分别为L(U)和L(V),(4)仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集,规定算符的优先顺序,()*|,正规式a a|bab(a|b)(a|b)a*(a|b)*,正规集aa,bab aa,ab,ba,bb,a,aa,aaa,a,b,aa,ab 所有由a和b组成的串,补充例:令=a，b，上的正规式和相应的正规集,例 3.1=a，b P47,

3、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.88e1,