资源描述
第三章词法分析,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、正规式和正规集的定义,设字母表为,辅助字母表=|*(),(1),(2),:语言的字母表VT,(3)假定U和V都是上的正规式，他们所表示的正规集分别为L(U)和L(V),(4)仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式表示的字集才是上的正规集,规定算符的优先顺序,()*|,正规式aa|bab(a|b)(a|b)a*(a|b)*,正规集aa,babaa,ab,ba,bb,a,aa,aaa,a,b,aa,ab所有由a和b组成的串,补充例:令=a，b，上的正规式和相应的正规集,例3.1=a，bP47,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,1P47,(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|bb|ab(ab)*(ba)*b(a|b)*(a*|b*)*,4、正规式服从的代数规律,U,V,W为正规式U|V=V|UU|(V|W)=(U|V)|W(UV)W=U(VW)U(V|W)=UV|UW，(V|W)U=VU|WUU=U=U,P47,补充：正规式服从的代数规律,r|r=rr*=|r|rr|(r*)*=r*=012n,补充例：定义无符号数的正规式,=d.e+d为09的数字,.表示小数点d*(.dd*|)(e(+|)dd*|),2，12.59，3.6e2，471.88e1,
展开阅读全文