编译原理3.3.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、正规式的引入－正则表达式，正规表达式,RERegularExpression正规式正规集正规文法正规语言正规语言是VT*上的正规集L(G)VT*单词描述工具2、正规式和正规集的定义设字母表为Σ,辅助字母表Σ’={Φε|·*()}正规式正规集ε{ε}Φ{}a∈Σ{a}(1)(2)Σ:语言的字母表VT正规式正规集或U|VL(U)∪L(V)连接积U·VL(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*{b}{a}*Σ上所有以b为首,后面跟任意多个a的符号串•a(a|b)*{a}{a,b}*Σ上所有以a为首的符号串•(a|b)*(aa|bb)(a|b)*{a,b}*{aa,bb}{a,b}*Σ上所有含有两个相继a或两个相继b的符号串例3.2∑={A,B,0,1}P47•(A|B)(A|B|0|1)*{A,B}{A,B,0,1}*∑上‘标识符’的全体•(0|1)(0|1)*{0,1}{0,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ε=UP47补充：正规式服从的代数规律⑥r|r=rr*=ε|r|rr|…(r*)*=r*∑*=∑0∑1∑2…∑n…补充例：定义无符号数的正规式•Σ={d.e+－}d为0~9的数字,‘.’表示小数点•d*(.dd*|ε)(e(+|－|ε)dd*|ε)2，12.59，3.6e2，471.88e－1