##### 正则表达式 - 正则表达式 - **正则表达式是**一种描述[[正则语言]]的代数方法. 一个正则表达式 $R$ 是由[[字符集]]基本元素和[[正则运算]]通过以下规则[[递归]]定义的. 现代正则表达式通过正则表达式引擎实现, 主要用于文本编辑器中的模式匹配和编译器中的词法分析, 在理论基础之上进行了大量扩展, 增加了实用功能, 但也偏离了严格的正则语言定义 - 字母 $a \in \Sigma$, 字母表中一个字符可以作为一个正则表达式 - 空字符串 $\epsilon$, 一个包含零个字符的字符串可以作为一个正则表达式 - 空集 $\emptyset$, 没有任何字符串的语言可以作为一个正则表达式 - 如果 $R_1$​ 和 $R_2$​ 是正则表达式, 那么 $R_1 \cup R_2$​ 也是正则表达式 - 如果 $R_1$​ 和 $R_2$​ 是正则表达式, 那么 $R_1 \circ R_2$​ 也是正则表达式 - 如果 $R_1$​ 是正则表达式, 那么 $R_1^*$​ 也是正则表达式 >[!example]- 正则表达式 > - $0^* 1 0^*$ > - $\{ w \mid w \text{包含单个 1} \}$ > - 字符串由任意数量的 $0$, 即前缀 $0^*$, 接一个 $1$, 再接任意数量的 $0$, 即后缀 $0^*$, 例如 $1$, $01$, $10$, $00100$ > - $\Sigma^* 1 \Sigma^*$ > - $\{ w \mid w \text{至少包含一个 1} \}$ > - 字符串在任意位置包含至少一个 $1$, 例如 $1$, $01$, $100$, $01010$ > - $\Sigma^* 001 \Sigma^*$ > - $\{ w \mid w \text{包含子串 001} \}$ > - 字符串在某处包含子串 $001$, 例如 $001$, $1001$, $00010$ > - $1^* (0 1^+)^*$ > - $\{ w \mid w \text{中每个 0 后至少跟一个 1} \}$ > - 字符串由 $1$ 的序列或 $0 1^+$ 的重复组成, 例如 $\varepsilon$, $1$, $11$, $011$, $0111$ > - $(\Sigma \Sigma)^*$ > - $\{ w \mid w \text{的长度为偶数} \}$ > - 字符串由长度为 $2$ 的块 $\Sigma \Sigma$ 重复任意次, 例如 $\varepsilon$, $00$, $01$, $10$, $11$, $0011$ > - $(\Sigma \Sigma \Sigma)^*$ > - $\{ w \mid w \text{的长度是 3 的倍数} \}$ > - 字符串由长度为 $3$ 的块重复任意次, 例如, $\varepsilon$, $000$, $111$, $010101$. > - $01 \cup 10$ > - $\{ 01, 10 \}$ > - 仅包含字符串 $01$ 和 $10$ > - $0 \Sigma^* 0 \cup 1 \Sigma^* 1 \cup 0 \cup 1$ > - $\{ w \mid w \text{以相同符号开始和结束} \}$ > - 字符串以 $0$ 开始和结束, 或以 $1$ 开始和结束, 或为单个 $0$ 或 $1$, 例如 $0$, $1$, $00$, $11$, $010$, $101$ > - $(0 \cup \varepsilon) 1^*$ > - $01^* \cup 1^*$ > - 字符串以 $0$ 或 $\varepsilon$ 开头, 接任意数量的 $1$, 例如, $\varepsilon$, $0$, $1$, $01$, $11$ > - $(0 \cup \varepsilon)(1 \cup \varepsilon)$ > - $\{ \varepsilon, 0, 1, 01 \}$ > - 第一个部分为 $0$ 或 $\varepsilon$, 第二个部分为 $1$ 或 $\varepsilon$ , 连接后生成所有组合. > - $1^* \emptyset$ > - $\emptyset$ > - 任何语言与空集连接得到空集 > - $\emptyset^*$ > - $\{ \varepsilon \}$ > - 空集的星号运算只生成空字符串, 即 $0$ 次连接