正则表达式
正则表达式概念基本概念及操作基本概念基本操作
归纳定义
正则表达式的代数定律相等定义代数定律
正则表达式的拓展
正则表达式概念
基本概念及操作
基本概念
一个正则表达式描述了一个定义在某个字母表
Σ
\Sigma
Σ上的字符串的集合+一个描述空串的
ϵ
\epsilon
ϵ。字符串的这种集合称为一种语言。
基本操作
选择：两个字符串集合
R
R
R和
S
S
S的并集，记
R
∣
S
R|S
R∣S，
{
x
∣
x
∈
R
或
x
∈
S
}
\{x|x \in R 或 x \in S\}
{x∣x∈R或x∈S}连接：记
R
S
RS
RS，包含前面集合的任一元素后接上后面集合的任一元素形成的所有字符串，
{
x
y
∣
x
∈
R
且
y
∈
S
}
\{xy|x \in R 且 y \in S \}
{xy∣x∈R且y∈S}闭包：集合
R
R
R的柯林闭包，集合与自身连接零或多次形成的集合取并集，记作
R
∗
R^*
R∗，定义为
⋃
i
=
0
∞
R
i
\bigcup_{i = 0}^\infty R^i
⋃i=0∞Ri
归纳定义
对给定的字符集
Σ
=
{
c
1
,
c
2
,
…
,
c
n
}
\Sigma = \{c1,c2,\dots,cn\}
Σ={c1,c2,…,cn} 归纳定义：
空串
ϵ
\epsilon
ϵ是正则表达式，表示仅含空串的集合，该语言只含空串。对于任意
c
∈
Σ
c \in \Sigma
c∈Σ，
c
c
c是正则表达式，表示尽包含
c
c
c的集合，仅串
c
c
c如果
M
M
M和
N
N
N是正则表达式，则以下也是正则表达式
选择：
M
∣
N
=
{
M
,
N
}
M|N = \{M,N\}
M∣N={M,N}连接：
M
N
=
{
m
n
∣
m
∈
M
,
n
∈
N
}
MN = \{mn|m \in M, n \in N\}
MN={mn∣m∈M,n∈N}闭包：
M
∗
=
{
ϵ
,
M
,
M
M
,
M
M
M
,
…
}
M^* = \{\epsilon,M,MM,MMM,\dots\}
M∗={ϵ,M,MM,MMM,…} 优先级：括号、闭包、连接、选择、左结合
正则表达式的代数定律
相等定义
如果两个正则表达式
r
r
r和
s
s
s表示相同的语言
称为
r
r
r和
s
s
s等价如：
a
∣
b
=
b
∣
a
a|b = b|a
a∣b=b∣a
代数定律
r
∣
s
=
s
∣
r
r|s = s|r
r∣s=s∣r
r
∣
(
s
∣
t
)
=
(
r
∣
s
)
∣
t
r|(s|t) = (r|s)|t
r∣(s∣t)=(r∣s)∣t
r
(
s
t
)
=
(
r
s
)
t
r(st) = (rs)t
r(st)=(rs)t
r
(
s
∣
t
)
=
r
s
∣
r
t
,
(
s
∣
t
)
r
=
s
r
∣
t
r
r(s|t) = rs|rt,(s|t)r = sr|tr
r(s∣t)=rs∣rt,(s∣t)r=sr∣tr
ϵ
r
=
r
ϵ
=
r
\epsilon r = r\epsilon = r
ϵr=rϵ=r
r
∗
=
(
r
∣
ϵ
)
∗
r^* = (r|\epsilon)^*
r∗=(r∣ϵ)∗
r
∗
∗
=
r
∗
r^{**} = r^*
r∗∗=r∗
正则表达式的拓展
多种针对RE的拓展，以增强RE描述字符串的能力
+：一个或多个实例，e+ == 一个或多个e？：零个或一个实例，e？ == 零个或一个e字符类
[abc] == a|b|c连接：第一个和最后一个符号，中间连词符：[a-c] == a|b|c 转义
如：使用\*表示*
