正则表达式
- 对给定的字符集$\Sigma = C_1,C_2,...,C_n$
- 空串$\epsilon$是正则表达式
- 对于任意$c\in\Sigma$，$c$是正则表达式
如果M和N是正则表达式，则以下也是正则表达式：
- 选择： M | N = {M, N}
- 连接： MN = {mn | m ∈ M, n ∈ N}
- 闭包： M* = {ε, M, MM, MMM, ...} (Kleene 闭包)
C语言中有很多关键字，例如 if, while 等：
对于if，$i\in\Sigma$，$f\in\Sigma$，所以if属于正则表达式。其他同理。
C语言中的标识符，是以字母和下划线开头，后跟零个或者多个字母、数字或下划线。其用正则表达式表达的方式如下：(a|b|...|z|A|B|...|Z|_)(a|b|...|z|A|B|...|Z|_|0|1|...|9)*。因为这里的后面部分是可以为零的，也就是任意个，所以直接使用闭包即可。
