《编译原理3.3.1- 正规式课件》由会员分享，可在线阅读，更多相关《编译原理3.3.1- 正规式课件（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
2、Expression,正规语言是VT*上的正规集,L(G) VT*,单词描述工具,2 、正规式和正规集的定义,设字母表为, 辅助字母表= | * ( ) ,(1),(2),: 语言的字母表 VT,(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
3、和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* (d
4、d* = 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,
