3--正规表达式.pptVIP免费

WenshengLiBUPT正规表达式--1/6正规表达式用正规表达式可以精确地定义集合，定义Pascal语言标识符的正规表达式：letter(letter|digit)*定义：字母表上的正规表达式(1)是正规表达式，它表示的语言是{}(2)如果a，则a是正规表达式，它表示的语言是{a}(3)如果r和s都是正规表达式,分别表示语言L(r)和L(s),则：1)(r)|(s)是正规表达式，表示的语言是L(r)∪L(s)2)(r)(s)是正规表达式，表示的语言是L(r)L(s)3)(r)*是正规表达式，表示的语言是(L(r))*4)(r)是正规表达式，表示的语言是L(r)正规表达式表示的语言叫做正规集。WenshengLiBUPT正规表达式--2/6正规表达式的书写约定一元闭包‘*’具有最高优先级，并且遵从左结合连接运算的优先级次之，遵从左结合并运算‘|’的优先级最低，遵从左结合例：如果={a，b}，则有：正规表达式a|b表示集合{a，b}(a|b)(a|b)表示：{aa，ab，ba，bb}a*表示：由0个或多个a组成的所有符号串的集合a|a*b表示：a和0个或多个a后跟一个b的所有符号串的集合(a|b)*表示：由a和b构成的所有符号串的集合(a*|b*)*如果两个正规表达式r和s表示同样的语言，即L(r)=L(s),则称r和s等价，写作r=s。如：(a|b)=(b|a)WenshengLiBUPT正规表达式--3/6正规表达式遵从的代数定律定律说明r|s=s|r“并”运算是可交换的r|(s|t)=(r|s)|t“并”运算是可结合的(rs)t=r(st)连接运算是可结合的r(s|t)=rs|rt(s|t)r=sr|tr连接运算对并运算的分配r=r，r=r对连接运算而言，是单位元素r*=(r|)**和之间的关系r**=r**是等幂的r*=r+|，r+=rr*+和*之间的关系WenshengLiBUPT正规表达式--4/6正规定义式定义：令是字母表，正规定义式是如下形式的定义序列：d1r1d2r2…dnrn其中di是不同的名字，ri是∪{d1,d2,…,di-1}上的正规表达式。例：Pascal语言的无符号数可用如下的正规表达式来描述：digit+(.digit+|)(E(+|-|)digit+|)正规定义式：digit0|1|…|9digitsdigitdigit*optional_fraction.digits|optional_exponent(E(+|-|)digits)|numdigitsoptional_fractionoptional_exponentWenshengLiBUPT正规表达式--5/6表示的缩写引入正闭包运算符‘+’–r*=r+|、r+=rr*–digitsdigit+引入可选运算符‘？’–r?=r|–optional_fraction(.digits)?–optional_exponent(E(+|-)?digits)?引入表示‘[…]’–字符组[abc]，表示正规表达式a|b|c–digit[0-9]–标识符的正规表达式：[A-Za-z][A-Za-z0-9...