正则表达式( Regular Expression,RE) 正则表达式可以高效、简洁地描述处理词法单元时用 到的模式类型 ●可以描述所有通过对某个字母表上的符号应用运算符 而得到的语言。其定义的集合叫做正则集合 regular set ●每个正则表达式r可以描述一个语言L(r),也即其定义 的正则集合。 ●C语言标识符的语言,可以用如下正则表达式来表示: letter_(letter_digit)
正则表达式（Regular Expression, RE） 正则表达式可以高效、简洁地描述处理词法单元时用 到的模式类型。 可以描述所有通过对某个字母表上的符号应用运算符 而得到的语言。其定义的集合叫做正则集合(regular set)。 每个正则表达式r可以描述一个语言L(r)，也即其定义 的正则集合。 C语言标识符的语言，可以用如下正则表达式来表示： letter_(letter_|digit)*
正则表达式 字母表∑上的正则表达式的定义 ●基本部分 E是一个正则表达式,L(E){e} 如果a是∑上的一个符号,那么a是正则表达式,L(a)={a} 归纳步骤: 选择:(r)|(s),L(r)|(s)=L(r)UL(s); 连接:(r)s),L(r)(s)=L(r)L(s); 闭包:(r)*,L(n)*)=(L(r)*; 括号:(r),L(r)=L(r) 运算的优先级:*>连接符> (a)(b)+(c)可以改写为ab+c
正则表达式 字母表Σ上的正则表达式的定义 基本部分 ε 是一个正则表达式，L(ε)={ε} 如果a是Σ上的一个符号，那么a是正则表达式，L(a)={a} 归纳步骤： 选择：(r) | (s)，L((r) | (s))=L(r) U L(s)； 连接：(r)(s)，L((r)(s))=L(r)L(s) ； 闭包：(r)*，L((r)*)=(L(r))*； 括号：(r)，L((r))=L(r) 运算的优先级：* > 连接符 > | (a)|((b)*(c))可以改写为 a|b*c
正则表达式的例子 °2={a,b} °L(ab)={ab} L(ab(ab)=faa, ab, ba, bb) ●L(a*)={8,a,a,aa,aa,…… L(ab))=a, a, b, aa, ab, ba, bb, aaa, aab, ...3S ala *b)=a,b, ab, aab, aaab, .i
正则表达式的例子 Σ={a,b} L(a|b) = {a,b} L((a|b)(a|b)) = {aa,ab,ba,bb} L(a*) = {ε,a,aa,aaa,aaaa,……} L((a|b)*) = {ε,a,b,aa,ab,ba,bb, aaa,aab,……} L(a|a*b) = {a,b,ab,aab,aaab,…}
正则表达式的性质 等价性 如果两个正则表达式r和s表示同样的语言,则r=s 代数定律 定律 描述 r8=87 是可以交换的 I(8t)=(rls)lt 是可结合的 r(st)=(rst 连接是可结合的 r()=(=m连接对是可分配的 ET=re=r ∈是连接的单位元 r*=(rle 闭包中一定包含e 具有幂等性
正则表达式的性质 等价性 如果两个正则表达式r和s表示同样的语言，则r=s 代数定律
正则定义 对正则表达式命名,使表示简洁。 d2→r2 dn→rn 各个d不在字母表Σ中,且名字都不同 每个r都是ΣU{d,d,…,d1}上的正则表达式
正则定义 对正则表达式命名，使表示简洁。 d1 ➔ r1 d2 ➔ r2 . . . dn ➔ rn 各个di不在字母表Σ中，且名字都不同 每个ri都是Σ U {d1 , d2 , …, di-1 }上的正则表达式