正则表达式的定义

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表示方法。

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 $r$ 定义（表示）一个语言，记为 $L(r)$ 。这个语言也是根据 $r$ 的子表达式所表示的语言递归定义的。

例如：

语言 $L=\{a\}\{a,b\}^(\{\varepsilon\}\cup (\{.,\_\}\{a,b\}\{a,b\}^))$

正则表达式 $r=a(a|b)^(\varepsilon|(.,\_)(a|b)(a|b)^)$

$\varepsilon$ 是一个 RE，$L(\varepsilon)=\{\varepsilon\}$

如果 $a \in \sum$ ，则 $a$ 是一个 RE， $L(a)=\{a\}$

假设 $r$ 和 $s$ 都是 RE，表示的语言分别是 $L(r)$ 和 $L(s)$，则

• $r|s$ 是一个 RE，$L(r|s)=L(r)\cup L(s)$
• $rs$ 是一个 RE，$L(rs)=L(r)L(s)$
• $r^$ 是一个 RE，$L(r^)=(L(r))^*$
• $(r)$ 是一个 RE，$L((r))=L(r)$

运算的优先级：$()、*、\small{连接}、|$

举例

C语言的无符号整数的RE

十进制整数的RE：$(1|...|9)^*|0$

八进制整数的RE：$0(1|...|7)(0|...|7)^*$

十六进制整数的RE：$0x(1|...|9||a|...|f||A|...|F)(0|...|9||a|...|f||A|...|F)^*$

正则语言

可以用RE定义的语言叫做正则语言（regular language）或正则集合（regular set）。

正则表达式的代数定律