正则表达式 描述程序设计语言中单词的一种简单而 且数学化的工具。 ●表示符号串的构成模式 ●正则表达式定义了一个符号串集合rs, rs内的每个符号串都与r所定义的模式 相匹配,rs称为由r生成的语言L(r) ●正则表达式中出现的所有符号构成的集 合为该正则表达式的字母表,用Σ表示
正则表达式 ⚫描述程序设计语言中单词的一种简单而 且数学化的工具。 ⚫表示符号串的构成模式 ⚫正则表达式r定义了一个符号串集合rs, rs内的每个符号串都与r所定义的模式 相匹配，rs称为由r生成的语言L(r) ⚫正则表达式中出现的所有符号构成的集 合为该正则表达式的字母表，用S表示
正则表达式 主要内容 ●基本概念 ●正则表达式定义及一些性质 ●扩充的正则表达式及程序设计语言中 单词的定义 正则表达式的局限性。 正则定义
正则表达式 主要内容： ⚫基本概念 ⚫正则表达式定义及一些性质 ⚫扩充的正则表达式及程序设计语言中 单词的定义 ⚫正则表达式的局限性。 ⚫正则定义
正则表达式 基本概念: 字母表:非空有限集,∑,其元素称为符号或字母 符号串:符号的有限序列,也称为字。或表示 空串 空串集{不同于空集⑦。 符号串长度:符号串中字符的个数|β 符号串连接:和β都是符号串,则aβ为符号串的连接 特别有:Aβ=β=β ●符号串集的乘积:A和B是符号串的集合,则称 AB={aP|a∈A,β∈B 特别有:A=A=A,其中必表示空集
正则表达式 ⚫ 基本概念： ⚫ 字母表：非空有限集，，其元素称为符号或字母. ⚫ 符号串：符号的有限序列，也称为‘字’ 。或表示 空串 空串集{}不同于空集 。 ⚫ 符号串长度：符号串中字符的个数.|| ⚫ 符号串连接：和都是符号串，则为符号串的连接 特别有： = = ⚫ 符号串集的乘积：A和B是符号串的集合，则称 AB={| A， B} 特别有：A=A=A，其中表示空集
●符号串的方幂: 设A是符号串的集合,则称A为符号 串集A的方幂,其中i是非负整数。 A0={ A1 AK AA A2=A A A A(k个) 符号串集合的正闭包: A+=A1∪A2∪A3 ●符号串集合的星闭包: A*〓A∪A1∪A2∪A3
⚫ 符号串的方幂： 设A是符号串的集合，则称A i为符号 串集A的方幂，其中i是非负整数。 A 0 ={} A 1 = A , A2 = A A A K = AA......A(k个) ⚫ 符号串集合的正闭包： A + =A1 A 2 A 3 ...... ⚫ 符号串集合的星闭包： A * =A0 A 1 A 2 A 3
正则表达式及其一些性质 ∑为给定的字母表,则每个Σ上的正则表达 式将定义∑上的一个字符串集。用R2表示∑ 上的正则表达式用LR)表示R所表示的字 符串集合。即:函数L表示 正则表达式→字符申集的映射 ●则R的定义及其含义如下:
正则表达式及其一些性质 ⚫ 为给定的字母表，则每个S上的正则表达 式将定义S上的一个字符串集。 用RS表示 上的正则表达式 ， 用L(RS )表示RS所表示的字 符串集合 。即：函数L表示 正则表达式→字符串集的映射。 ⚫ 则RS 的定义及其含义如下：
是正则表达式,即∈R2。其中(②)=l 入是正则表达式,即入∈R。其中L(A)=。 ■c∈∑是正则表达式,即c∈R。其中L(c)={c}。 ■A和B是正则表达式,即A∈R2,B∈Rz,则有 (A)∈R ∑ L((A)) AB∈R L(A|B)=L(A)∪儿(B) AB∈R L(AB)=L(AL( B) L(A*) L(A)*
■ 是 正则表达式，即RS 。其中L()={ }。 ■ 是正则表达式，即RS 。其中L()={ }。 ■ cS是正则表达式，即cRS。其中L(c)={c}。 ■ A和B是正则表达式，即A RS，B RS ，则有 ( A )RS， L( (A) ) = L(A) A | BRS， L( A | B )= L(A)L(B) A B RS， L( A B ) = L(A)L(B) A * RS， L( A*) = L(A)*
正则表达式例 ∑=[a,b}. 正则表达式eL(e) ab米 1.∑上所有以a为首后跟任意多 个(包括0个)b的字符串集 2.a(a|b)*2.2上所有以a为首的字符串集
正则表达式例 ⚫ ={ a,b }. 正则表达式e 1. ab* 2. a(a|b)* L(e) 1. 上所有以a为首后跟任意多 个（包括0个）b的字符串集 2. 上所有以a为首的字符串集
正则表达式的性质 口A|B=BA 的可交换性 口A|(B|0)=(A|B)G|的可结合性 口A(B)=(AB)c 连接的可结合性 口A(B|C)=AB|AG连接的可分配性 口(A|B)G=AG|Bc连接的可分配性 口A*三A 幂的等价性 口A=A=A 入是连接的恒等元素
正则表达式的性质 ❑ A | B = B | A | 的可交换性 ❑ A | (B | C) =(A | B ) C | 的可结合性 ❑ A (B C) =(A B )C 连接的可结合性 ❑ A (B | C) =A B | A C 连接的可分配性 ❑ (A | B ) C =A C | B C 连接的可分配性 ❑ A ** =A* 幂的等价性 ❑ A=A=A 是连接的恒等元素
扩充的正则表达式 一次或多次重复:A 任何符号:“…”在字母表中任何符号.|. 符号范围:[0-9][a-z][A-2] 不在给定范围内的符号:(a|b|c)或[^a] 可选:(+|-)?
扩充的正则表达式 ⚫ 一次或多次重复: A + ⚫ 任何符号: “ … ”在字母表中任何符号.|... ⚫ 符号范围: [0--9] [a--z] [A--Z] ⚫ 不在给定范围内的符号: ~(a|b|c)或[^ a] ⚫ 可选: （＋|-）?
程序设计语言中单词的 正则表达式定义 保留字如 Begin= beg in ●标识符 letter=la-z, A-ZI digit=[0-9] identifier=letter(letter digit* 数字 整数Int=[1-9]Dgit*|0 实数rea=nt.nt 特殊符号+-
程序设计语言中单词的 正则表达式定义 ⚫ 保留字 如 Begin＝begin ⚫ 标识符 letter=[a-z，A-Z] digit=[0-9] identifier=letter(letter|digit)* ⚫ 数字 整数Int＝[1-9]Digit*|0 实数real＝Int.Int ⚫ 特殊符号 +|-|…