1. 正则表达式¶

正则表达式 （regular expression，亦称为 RegEx 或 RE）是定义语言的另一种方式。 它们在职业程序员中被大量使用，例如用于定义简单的搜索模式。 这在我们已知的用于定义语言的方法（文法（grammar）、DFA 和 NFA）之外，又增加了一种方式。 当然，我们也可以直接用英语描述来定义语言。 为什么还需要另一种方式呢？

英语描述（或任何其他人类使用的语言）的问题是它太不精确， 而且不便于我们实现。 使用 DFA 或 NFA 通常需要某种图形编辑器， 输入所有的状态（state）和转移（transition）也要花一些时间。 我们将看到，正则表达式易于输入， 而且对于常见的、我们希望表示的语言，它们往往使用相对较短的描述。 当然，即使是相对较小且精确的语言规范，也可能难以构思（或难以理解）。 但至少对于正则表达式来说，一旦你写出了它，输入通常就快速而简单。

1.1. 正则表达式的定义与示例¶

Settings

Saving...
Server Error
Resubmit

正则表达式（RE）的 定义：给定 \(\Sigma\)，

1. \(\lambda\) 以及所有 \(a \in \Sigma\) 都是 RE

2. 如果 \(r\) 和 \(s\) 是正则表达式，那么

   • \(r + s\) 是一个 RE

   • \(r s\) 是一个 RE

   • \((r)\) 是一个 RE

   • \(r^*\) 是一个 RE

3. \(r\) 是 RE，当且仅当它能由 (1) 出发，通过有限次应用 (2) 推导得出。

我们很快就会证明，正则表达式并不比我们已有的 DFA 具有更多的能力。 但在接下来的练习中你会看到，它们往往更容易写出来。 .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/Regular/RegExFS.js