正则表达式
?描述程序设计语言中单词的一种简单而
且数学化的工具。
?表示符号串的构成模式
?正则表达式 r定义了一个符号串集合 rs,
rs内的每个符号串都与 r所定义的模式
相匹配,rs称为由 r生成的语言 L(r)
?正则表达式中出现的所有符号构成的集
合为该正则表达式的字母表, 用 S表示
正则表达式
主要内容：
?基本概念
?正则表达式定义及一些性质
?扩充的正则表达式及程序设计语言中
单词的定义
?正则表达式的局限性。
?正则定义
正则表达式
? 基本概念：
? 字母表,非空有限集,?，其元素称为符号或字母,
? 符号串,符号的有限序列，也称为 ‘ 字 ’ 。 ?或 ?表示
空串
空串集 {?}不同于空集 ? 。
? 符号串长度,符号串中字符的个数,|?|
? 符号串连接,?和 ?都是符号串，则 ??为符号串的连接
特别有,?? = ?? = ?
? 符号串集的乘积,A和 B是符号串的集合，则称
AB={??| ??A,? ?B}
特别有,?A=A?=A,其中 ?表示空集。
? 符号串的方幂：
设 A是符号串的集合，则称 Ai为符号
串集 A的方幂，其中 i是非负整数。
A0 ={?}
A1 = A,A2 = A A
AK = AA......A(k个 )
? 符号串集合的正闭包：
A+ =A1 ? A2 ?A3,....,
? 符号串集合的星闭包：
A* =A0 ? A1 ? A2 ?A3,.....
正则表达式及其一些性质
??为给定的字母表，则每个 S上的正则表达
式将定义 S上的一个字符串集。 用 RS表示 ?
上的正则表达式, 用 L(RS)表示 RS所表示的字
符串集合 。即：函数 L表示
正则表达式 ?字符串集的映射。
? 则 RS 的定义及其含义如下：
■ ?是 正则表达式, 即 ??RS 。 其中 L(?)={ }。
■ ?是正则表达式, 即 ??RS 。 其中 L(?)={ ? }。
■ c?S是正则表达式, 即 c?RS。 其中 L(c)={c}。
■ A和 B是正则表达式, 即 A ?RS,B ?RS, 则有
( A )?RS,L( (A) ) = L(A)
A | B?RS,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 }.
正则表达式 e
1,ab*
2,a(a|b)*
L(e)
1,?上所有以 a为首后跟任意多
个（包括 0个） b的字符串集
2,?上所有以 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--Z]
? 不在给定范围内的符号, ~(a|b|c)或 [^a]
? 可选, （＋ |-）?
程序设计语言中单词的
正则表达式定义
? 保留字 如 Begin＝ begin
? 标识符
letter=[a-z,A-Z]
digit=[0-9]
identifier=letter(letter|digit)*
? 数字
整数 Int＝ [1-9]Digit*|0
实数 real＝ Int.Int
? 特殊符号 +|-|…
正则表达式的局限性
? 正则表达式不能用于描述配对或嵌套的结
构
? 正则表达式不能用于描述重复串
例,{w c w | w是 a和 b的串 }无法用正则表
达式表示（保证两边 w是相同的）。
正则定义
? 为较长的正则表达式提供一个简化了的
名字。如要为一个或多个数字序列写一
个正则表达式，则可写作：
? （ 0|1|2|… |9)(0|1|2|… 9)*
? 或写作 digit digit*
? 其中 digit= 0|1|2|… |9就是名字
digit的正则定义，表示为：
digit ? 0|1|2|… |9
习题作业
? S={a,b,c}
试给出 S-上一个 不包含连续两个 b的所有符号
串集合的正则定义,
? S={a,b,c}
叙述正则式 ((b|c)*a(b|c)*a)*(b|c)* 描述的符号串
?S＝ {0,1}叙述正则式
(00 | 11)? ( (01 | 10) (00 | 11)? (01 | 10 ))? (00 | 11)?
描述的符号串
? 给出能被 5整除的二进制数表示形式的正则定
义 。
?描述程序设计语言中单词的一种简单而
且数学化的工具。
?表示符号串的构成模式
?正则表达式 r定义了一个符号串集合 rs,
rs内的每个符号串都与 r所定义的模式
相匹配,rs称为由 r生成的语言 L(r)
?正则表达式中出现的所有符号构成的集
合为该正则表达式的字母表, 用 S表示
正则表达式
主要内容：
?基本概念
?正则表达式定义及一些性质
?扩充的正则表达式及程序设计语言中
单词的定义
?正则表达式的局限性。
?正则定义
正则表达式
? 基本概念：
? 字母表,非空有限集,?，其元素称为符号或字母,
? 符号串,符号的有限序列，也称为 ‘ 字 ’ 。 ?或 ?表示
空串
空串集 {?}不同于空集 ? 。
? 符号串长度,符号串中字符的个数,|?|
? 符号串连接,?和 ?都是符号串，则 ??为符号串的连接
特别有,?? = ?? = ?
? 符号串集的乘积,A和 B是符号串的集合，则称
AB={??| ??A,? ?B}
特别有,?A=A?=A,其中 ?表示空集。
? 符号串的方幂：
设 A是符号串的集合，则称 Ai为符号
串集 A的方幂，其中 i是非负整数。
A0 ={?}
A1 = A,A2 = A A
AK = AA......A(k个 )
? 符号串集合的正闭包：
A+ =A1 ? A2 ?A3,....,
? 符号串集合的星闭包：
A* =A0 ? A1 ? A2 ?A3,.....
正则表达式及其一些性质
??为给定的字母表，则每个 S上的正则表达
式将定义 S上的一个字符串集。 用 RS表示 ?
上的正则表达式, 用 L(RS)表示 RS所表示的字
符串集合 。即：函数 L表示
正则表达式 ?字符串集的映射。
? 则 RS 的定义及其含义如下：
■ ?是 正则表达式, 即 ??RS 。 其中 L(?)={ }。
■ ?是正则表达式, 即 ??RS 。 其中 L(?)={ ? }。
■ c?S是正则表达式, 即 c?RS。 其中 L(c)={c}。
■ A和 B是正则表达式, 即 A ?RS,B ?RS, 则有
( A )?RS,L( (A) ) = L(A)
A | B?RS,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 }.
正则表达式 e
1,ab*
2,a(a|b)*
L(e)
1,?上所有以 a为首后跟任意多
个（包括 0个） b的字符串集
2,?上所有以 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--Z]
? 不在给定范围内的符号, ~(a|b|c)或 [^a]
? 可选, （＋ |-）?
程序设计语言中单词的
正则表达式定义
? 保留字 如 Begin＝ begin
? 标识符
letter=[a-z,A-Z]
digit=[0-9]
identifier=letter(letter|digit)*
? 数字
整数 Int＝ [1-9]Digit*|0
实数 real＝ Int.Int
? 特殊符号 +|-|…
正则表达式的局限性
? 正则表达式不能用于描述配对或嵌套的结
构
? 正则表达式不能用于描述重复串
例,{w c w | w是 a和 b的串 }无法用正则表
达式表示（保证两边 w是相同的）。
正则定义
? 为较长的正则表达式提供一个简化了的
名字。如要为一个或多个数字序列写一
个正则表达式，则可写作：
? （ 0|1|2|… |9)(0|1|2|… 9)*
? 或写作 digit digit*
? 其中 digit= 0|1|2|… |9就是名字
digit的正则定义，表示为：
digit ? 0|1|2|… |9
习题作业
? S={a,b,c}
试给出 S-上一个 不包含连续两个 b的所有符号
串集合的正则定义,
? S={a,b,c}
叙述正则式 ((b|c)*a(b|c)*a)*(b|c)* 描述的符号串
?S＝ {0,1}叙述正则式
(00 | 11)? ( (01 | 10) (00 | 11)? (01 | 10 ))? (00 | 11)?
描述的符号串
? 给出能被 5整除的二进制数表示形式的正则定
义 。
